Wie werden gemeinsame Präfixe für die Regex-Wortstammbildung erstellt?

Question

Ich habe ein Array von Wörtern, die ich durch Regex-Operation suchen und ersetzen muss, und manchmal kann dieses Array Tausende von Wörtern lang sein. Ich habe getestet und gefunden, dass das Stempeln der Wörter mit gemeinsamen Präfixen viel schneller ist, als nach ihnen einzeln zu suchen. Das heißt, ^where|why$ ist langsamer als ^wh(ere|y)$. Offensichtlich ist es in einem so kurzen Beispiel kein bemerkenswerter Unterschied, aber es ist wesentlich schneller, wenn es Tausende von Alternativen gibt und die Betreffzeile lang ist.

Ich bin auf der Suche nach einem Weg, also diese automatisch ergeben zu tun, zum Beispiel ein string[] { "what", "why", "where", "when", "which" } in wh(at|y|e(re|n)|i(ch))

zu konvertieren Gibt es bereits ein anerkannter Algorithmus gibt, die dies tut? Wenn nicht, wie würdest du das machen? Es scheint rekursiv zu sein, aber ich kann nicht ganz klar werden, wie es geht. Ich habe eine Methode, die ich schrieb, die in einem begrenzten Ausmaß funktioniert, aber es ist unelegant, 60 Zeilen lang und verwendet mehrere verschachtelte foreach-Schleifen, so dass es ein zukünftiger Wartungsalbtraum ist. Ich bin sicher, es ist ein viel besserer Weg, wenn jemand mich in die richtige Richtung zeigen könnte, die sehr geschätzt werden würde ...

Answer 1

Dieser Code sollte funktionieren:

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

Verbrauch:

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:
zu bekommen reg2 = "wh(y|at|e(re|n))|a(bc|pple)" also ohne die ersten Verpackungs Klammern, Kommentar- nur die markierte Zeile in BuildRexp Methode.