Biểu thức chính quy đối sánh từ một từ điển trong C#

Question

Tôi đang cố gắng có một số loại đối tượng dữ liệu (tôi đang nghĩ từ điển) để giữ TÔN của cụm từ thông dụng làm khóa, sau đó tôi cần lấy một chuỗi văn bản và phù hợp với họ để có được giá trị thực tế từ từ điển. Tôi cần một cách hiệu quả để làm điều này cho một tập hợp lớn dữ liệu.

Tôi đang ở trong C# và tôi không chắc chắn nên bắt đầu từ đâu.

Answer 1

Tại sao không sử dụng LINQ?

Dictionary<string, string> myCollection = new Dictionary<string, string>(); 

myCollection.Add("(.*)orange(.*)", "Oranges are a fruit."); 
myCollection.Add("(.*)apple(.*)", "Apples have pips."); 
myCollection.Add("(.*)dog(.*)", "Dogs are mammals."); 
// ... 

string input = "tell me about apples and oranges"; 

var results = from result in myCollection 
       where Regex.Match(input, result.Key, RegexOptions.Singleline).Success 
       select result; 

foreach (var result in results) 
{ 
    Console.WriteLine(result.Value); 
} 

// OUTPUT: 
// 
// Oranges are a fruit. 
// Apples have pips. 

Answer 2

Tôi không chắc liệu bạn có thực sự cần cụm từ thông dụng cho điều này hay không - bạn có thể sử dụng trie. Đại diện cho từ điển là một ứng dụng phổ biến cho một trie. (Tôi giả sử bạn có nghĩa là một từ điển như trong một danh sách các từ, và không phải là "mảng kết hợp" có nghĩa).

Answer 3

Bạn có nghĩa là khớp một chuỗi so với các regex để nhận được kết quả regex không? Hay chỉ là một trận đấu văn bản? Nói cách khác, là chuỗi bạn sẽ là một trong những regexes, hoặc một số dữ liệu để áp dụng một regex đến?

Nếu nó là một regex và bạn muốn tìm nó trong danh sách, bạn không cần một từ điển, đó là 2 phần container. Bạn chỉ có thể sử dụng một List hoặc StringCollection, và yêu cầu IndexOf (mytString), -1 có nghĩa là nó không có trong đó.

Answer 4

Nếu regexps của bạn không phải là tầm thường đơn chuỗi, và bạn chăm sóc cho hiệu quả, bạn muốn để đại diện cho họ trong một đơn NFA (nondeterministic finite-state automaton, với giá trị trong trạng thái cuối. Nếu có thể cho một đầu vào khớp với nhiều hơn một regexp, thì các trạng thái cuối cùng sẽ cần một tập các giá trị.

Tại thời điểm này, bạn đã sẵn sàng xem xét tối ưu hóa automaton. Nếu nó có thể được xác định thực tế (điều này cho bạn một DFA có thể lớn hơn theo cấp số nhân so với NFA), thì bằng mọi cách làm điều đó. Một khi bạn có DFA, bạn có thể hiệu quả (và duy nhất đến đẳng cấu) giảm thiểu nó (nhưng vì bạn có giá trị trong trạng thái cuối cùng của bạn, cần phải sửa đổi rõ ràng usual algorithm).

Ngoài ra còn có các kỹ thuật để giảm thiểu NFA trực tiếp. Ví dụ, nếu hai trạng thái có cùng một bộ hậu tố ({(phần còn lại của chuỗi, giá trị)}) chúng tương đương nhau và có thể được kết hợp. Tương đương trong một NFA tuần hoàn có thể được thực hiện thông qua hash-consing bắt đầu từ các trạng thái cuối cùng.

Answer 5

Hãy nhớ rằng nếu bạn dự định sử dụng regex nhiều hơn một lần bạn có thể tạo đối tượng regex như được biên dịch và sử dụng lại nó để giảm chi phí.

Regex RegexObject = new Regex(Pattern, RegexOptions.Compiled); 

Sử dụng mô hình này, bạn sẽ lưu trữ tốt nhất đối tượng regex thay vì chuỗi mẫu.