¿Cómo hacer prefijos comunes para la derivación de palabras regex?

Question

Tengo un conjunto de palabras que necesito hacer una operación de búsqueda y reemplazo por expresión regex, y en ocasiones esta matriz puede tener miles de palabras. He probado y encontré que derivar las palabras usando prefijos comunes es mucho más rápido que buscarlas individualmente. Es decir, ^where|why$ es más lento que ^wh(ere|y)$. Obviamente, no es una diferencia notable en un ejemplo tan breve, pero es considerablemente más rápido donde hay miles de alternativas y la secuencia del tema es larga.

Así que estoy buscando una manera de hacer esto de forma automática derivada, por ejemplo, para convertir un string[] { "what", "why", "where", "when", "which" } en wh(at|y|e(re|n)|i(ch))

ya existe un algoritmo reconocido por ahí que hace esto? Si no, ¿cómo lo harías? Parece que es necesario hacerlo recursivamente, pero no puedo entender cómo hacerlo. Tengo un método que escribí que funciona de forma limitada, pero no es elegante, tiene 60 líneas de largo y usa múltiples bucles foreach anidados, por lo que es una pesadilla de mantenimiento en el futuro. Estoy seguro de que hay una manera mucho mejor, si alguien me podría apuntar en la dirección correcta Eso sería muy apreciada ...

Answer 1

Este código debería funcionar:

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

Uso:

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:
para obtener reg2 = "wh(y|at|e(re|n))|a(bc|pple)" es decir, sin los primeros soportes de envoltura, simplemente elimine la línea marcada en BuildRexp método.