Thuật toán hiệu quả để chuyển đổi một bộ ký tự thành một nfa/dfa

Question

Tôi hiện đang làm việc trên một trình tạo máy quét. Máy phát điện đã hoạt động tốt. Nhưng khi sử dụng các lớp nhân vật, thuật toán sẽ rất chậm.

Trình tạo máy quét tạo ra một máy quét cho các tệp được mã hóa UTF8. Phải hỗ trợ đầy đủ các ký tự (0x000000 đến 0x10ffff).

Nếu tôi sử dụng các bộ ký tự lớn, chẳng hạn như toán tử bất kỳ '.' hoặc thuộc tính unicode {L}, nfa (và cũng là dfa) chứa rất nhiều trạng thái (> 10000). Vì vậy, việc chuyển đổi cho nfa thành dfa và tạo dfa tối thiểu mất một thời gian dài (ngay cả khi dfa tối thiểu đầu ra chỉ chứa một vài trạng thái).

Đây là triển khai hiện tại của tôi về việc tạo một bộ ký tự đặt trong nfa.

void CreateNfaPart(int startStateIndex, int endStateIndex, Set<int> characters) 
{ 
transitions[startStateIndex] = CreateEmptyTransitionsArray(); 
foreach (int character in characters) { 
    // get the utf8 encoded bytes for the character 
    byte[] encoded = EncodingHelper.EncodeCharacter(character); 
    int tStartStateIndex = startStateIndex; 
    for (int i = 0; i < encoded.Length - 1; i++) { 
     int tEndStateIndex = transitions[tStartStateIndex][encoded[i]]; 
     if (tEndStateIndex == -1) { 
      tEndStateIndex = CreateState(); 
       transitions[tEndStateIndex] = CreateEmptyTransitionsArray(); 
     }     
     transitions[tStartStateIndex][encoded[i]] = tEndStateIndex; 
     tStartStateIndex = tEndStateIndex; 
    } 
    transitions[tStartStateIndex][encoded[encoded.Length - 1]] = endStateIndex; 
} 

Có ai biết cách thực hiện chức năng hiệu quả hơn nhiều để chỉ tạo các trạng thái cần thiết không?

EDIT:

Để cụ thể hơn tôi cần một chức năng như:

List<Set<byte>[]> Convert(Set<int> characters) 
{ 
    ??????? 
} 

Một chức năng helper để chuyển đổi một ký tự (int) vào một byte mã hóa UTF8 [] được định nghĩa là:

byte[] EncodeCharacter(int character) 
{ ... } 

Answer 1

Xem thư viện biểu thức chính quy như Google RE2 và TRE đang làm gì.

Answer 2

Có một số cách để xử lý. Tất cả chúng đều đun sôi xuống để xử lý các bộ ký tự tại một thời điểm trong cấu trúc dữ liệu, thay vì liệt kê toàn bộ bảng chữ cái. Nó cũng là cách bạn làm cho máy quét cho Unicode trong một số lượng hợp lý của bộ nhớ.

Bạn có nhiều lựa chọn về cách trình bày và xử lý bộ ký tự. Tôi hiện đang làm việc với một giải pháp giữ một danh sách thứ tự các điều kiện biên và các trạng thái đích tương ứng. Bạn có thể xử lý các hoạt động trên các danh sách này nhanh hơn nhiều so với bạn nếu bạn phải quét toàn bộ bảng chữ cái ở mỗi điểm. Trong thực tế, nó đủ nhanh để nó chạy bằng Python với tốc độ chấp nhận được.

Answer 3

Tôi đã gặp vấn đề tương tự với trình tạo máy quét của mình, vì vậy tôi đã đưa ra ý tưởng thay thế khoảng thời gian bằng id của chúng được xác định bằng cây khoảng cách. Ví dụ: dãy a..z trong dfa có thể được biểu diễn dưới dạng: 97, 98, 99, ..., 122, thay vào đó tôi thể hiện phạm vi là [97, 122], sau đó xây dựng cấu trúc cây khoảng cách trong số đó, do đó, ở cuối chúng được biểu diễn dưới dạng id trỏ đến cây khoảng cách. Với RE sau đây: a ..z +, chúng tôi kết thúc với DFA như:

0 -> a -> 1 
0 -> b -> 1 
0 -> c -> 1 
0 -> ... -> 1 
0 -> z -> 1 

1 -> a -> 1 
1 -> b -> 1 
1 -> c -> 1 
1 -> ... -> 1 
1 -> z -> 1 
1 -> E -> ACCEPT 

Bây giờ nén khoảng:

0 -> a..z -> 1 

1 -> a..z -> 1 
1 -> E -> ACCEPT 

Extract tất cả khoảng thời gian từ DFA của bạn và xây dựng cây khoảng ra trong số họ:

{ 
    "left": null, 
    "middle": { 
     id: 0, 
     interval: [a, z], 
    }, 
    "right": null 
} 

Thay thế thực tế các khoảng thời gian cho id của chúng:

0 -> 0 -> 1 
1 -> 0 -> 1 
1 -> E -> ACCEPT 

Answer 4

Trong thư viện này (http://mtimmerm.github.io/dfalex/) Tôi làm điều đó bằng cách đặt một loạt các ký tự liên tiếp trên mỗi lần chuyển đổi, thay vì các ký tự đơn. Điều này được thực hiện thông qua tất cả các bước của việc xây dựng NFA, chuyển đổi NFA-> DFA, giảm thiểu DFA và tối ưu hóa.

Nó khá nhỏ gọn, nhưng nó làm tăng độ phức tạp của mã cho mỗi bước.