Làm cách nào để tạo các tiền tố chung cho từ regex?

Question

Tôi có một loạt các từ tôi cần phải thực hiện tìm và thay thế bằng thao tác regex, và đôi khi mảng này có thể dài hàng ngàn từ. Tôi đã thử nghiệm và thấy rằng bắt nguồn từ bằng cách sử dụng tiền tố phổ biến là nhanh hơn nhiều so với việc tìm kiếm chúng riêng lẻ. Tức là, ^where|why$ chậm hơn ^wh(ere|y)$. Rõ ràng nó không phải là một sự khác biệt đáng chú ý trong một ví dụ ngắn như vậy, nhưng nó nhanh hơn đáng kể, nơi có hàng ngàn lựa chọn thay thế và chuỗi chủ đề là dài.

Vì vậy, tôi đang tìm kiếm một cách để làm điều này bắt nguồn tự động, ví dụ để chuyển đổi một string[] { "what", "why", "where", "when", "which" } vào wh(at|y|e(re|n)|i(ch))

Có đã là một thuật toán nhận ra có mà thực hiện điều này? Nếu không, làm thế nào bạn sẽ đi về nó? Có vẻ như cần được thực hiện một cách đệ quy nhưng tôi hoàn toàn không thể làm cho đầu của tôi tròn như thế nào. Tôi có một phương pháp tôi đã viết mà làm việc đến một mức độ hạn chế, nhưng nó không phù hợp, 60 dòng dài và sử dụng nhiều vòng foreach lồng nhau vì vậy nó là một cơn ác mộng bảo trì trong tương lai. Tôi chắc rằng có một cách tốt hơn, nếu có ai có thể chỉ cho tôi đi đúng hướng mà muốn được nhiều đánh giá cao ...

Answer 1

Mã này nên làm việc:

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

Cách sử dụng:

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:
để có được reg2 = "wh(y|at|e(re|n))|a(bc|pple)" tức mà không có gói ngoặc đầu tiên, chỉ cần bỏ ghi chú dòng đánh dấu trongPhương pháp.