Jak utworzyć wspólne przedrostki dla słowa wyrażenia regularnego?

Question

Mam tablicę słów, które muszę zrobić, aby znaleźć i zastąpić przez operację regex na, a czasami ta tablica może mieć tysiące słów. Przetestowałem i odkryłem, że wymawianie słów przy użyciu wspólnych prefiksów jest znacznie szybsze niż poszukiwanie ich pojedynczo. Oznacza to, że ^where|why$ jest wolniejszy niż ^wh(ere|y)$. Oczywiście nie jest to zauważalna różnica w tak krótkim przykładzie, ale jest znacznie szybsza, gdy istnieją tysiące alternatyw, a temat jest długi.

Więc szukam sposobu, aby to zrobić wynikającego automatycznie, na przykład konwertować string[] { "what", "why", "where", "when", "which" } do wh(at|y|e(re|n)|i(ch))

Czy jest już uznanym algorytm tam, że to robi? Jeśli nie, to jak byś to zrobił? Wydaje się, że trzeba to zrobić rekursywnie, ale nie mogę sobie poradzić z tym, jak to zrobić. Mam metodę, którą napisałem, która działa w ograniczonym zakresie, ale jest nieelegancka, ma długość 60 linii i wykorzystuje wiele zagnieżdżonych pętli foreach, więc jest to koszmar dla przyszłych działań konserwacyjnych. Jestem pewien, że jest to znacznie lepszy sposób, jeśli ktoś może wskazać mi w dobrym kierunku, to byłoby bardzo doceniane ...

Answer 1

Kod ten powinien działać:

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; 
    } 
} 

Zastosowanie:

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))" 

EDIT:
dostać reg2 = "wh(y|at|e(re|n))|a(bc|pple)" czyli bez owijania pierwszych nawiasach, po prostu odkomentować zaznaczonej linii w BuildRexp metoda.