如何爲正則表達式詞幹製作通用前綴？

Question

我有一個單詞數組，我需要通過正則表達式來進行查找和替換，有時這個數組可能長達數千個單詞。我已經測試並發現，使用通用前綴填充單詞比單獨搜索單詞要快得多。也就是說，^where|why$比^wh(ere|y)$慢。很顯然，在這樣一個簡短的例子中，這並不是一個明顯的差異，但是在有成千上萬個替代方案並且主題字符串很長的情況下，它會快得多。

所以我在尋找一種方式來做到這一點自動詞幹，例如轉換一個string[] { "what", "why", "where", "when", "which" }爲wh(at|y|e(re|n)|i(ch))

是否已有一個公認的算法，在那裏，這是否？如果沒有，你會怎麼做呢？它似乎需要遞歸地完成，但我不能完全理解如何去做。我有一個我寫的方法在有限的範圍內工作，但它不雅，60行，並使用多個嵌套的foreach循環，因此這是未來的維護噩夢。我敢肯定有一個更好的方法，如果任何人都可以在這會是大加讚賞指向正確的方向我...

Answer 1

此代碼應工作：

public static class StemmingUtilities 
{ 
    private class Node 
    { 
     public char? Value { get; private set; } 
     public Node Parent { get; private set; } 
     public List<Node> Children { get; private set; } 
     public Node(char? c, Node parent) 
     { 
      this.Value = c; 
      this.Parent = parent; 
      this.Children = new List<Node>(); 
     } 
    } 

    public static string GetRegex(IEnumerable<string> tokens) 
    { 
     var root = new Node(null,null); 
     foreach (var token in tokens) 
     { 
      var current = root; 
      for (int i = 0; i < token.Length; i++) 
      { 
       char c = token[i]; 
       var node = current.Children.FirstOrDefault(x => x.Value.Value == c); 
       if (node == null) 
       { 
        node = new Node(c,current); 
        current.Children.Add(node); 
       } 
       current = node; 
      } 
     } 
     return BuildRexp(root); 
    } 

    private static string BuildRexp(Node root) 
    { 
     string s = ""; 
     bool addBracket = root.Children.Count > 1; 
     // uncomment the following line to avoid first brakets wrapping (occurring in case of multiple root's children) 
     // addBracket = addBracket && (root.Parent != null); 
     if (addBracket) 
      s += "("; 
     for(int i = 0; i < root.Children.Count; i++) 
     { 
      var child = root.Children[i]; 
      s += child.Value; 
      s += BuildRexp(child); 
      if (i < root.Children.Count - 1) 
       s += "|"; 
     } 
     if (addBracket) 
      s += ")"; 
     return s; 
    } 
} 

用法：

var toStem1 = new[] { "what", "why", "where", "when", "which" }; 
string reg1 = StemmingUtilities.GetRegex(toStem1); 
// reg1 = "wh(at|y|e(re|n)|ich)" 

string[] toStem2 = new[] { "why", "abc", "what", "where", "apple", "when" }; 
string reg2 = StemmingUtilities.GetRegex(toStem2); 
// reg2 = "(wh(y|at|e(re|n))|a(bc|pple))" 

編輯：
得到reg2 = "wh(y|at|e(re|n))|a(bc|pple)"即沒有第一包裹支架，只需取消對標線BuildRexp方法。