Efektywny algorytm do przekształcania zestawu znaków w nfa/dfa

Question

Obecnie pracuję nad generatorem skanera. Generator działa już poprawnie. Ale gdy używasz klas postaci, algorytm staje się bardzo wolny.

Generator skanera tworzy skaner dla plików zakodowanych w UTF8. Pełen zakres znaków (od 0x000000 do 0x10ffff) powinien być obsługiwany.

Jeśli używam dużych zestawów znaków, takich jak dowolny operator ". lub właściwość unicode {L}, nfa (a także dfa) zawiera wiele stanów (> 10000). Tak więc konwersja dla nfa do dfa i stworzenie minimalnej dfa zajmuje dużo czasu (nawet jeśli wyjściowy minimalny dfa zawiera tylko kilka stanów).

Oto moja obecna implementacja tworzenia zestawu znaków w 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; 
} 

Czy ktoś wie, jak wdrożyć funkcję o wiele bardziej wydajnie, aby stworzyć tylko niezbędne stany?

Edycja:

Konkretniej muszę funkcji takich jak:

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

funkcja pomocniczych do konwersji postaci (int) do bajtu kodowania UTF-8 [] jest zdefiniowany jako:

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

Answer 1

Zobacz, co robią biblioteki wyrażeń regularnych, takie jak Google RE2 i TRE.

Answer 2

Istnieje wiele sposobów, aby sobie z tym poradzić. Wszystkie one sprowadzają się do traktowania zestawów znaków w czasie w strukturach danych, zamiast wymieniać cały alfabet w ogóle. W ten sposób tworzysz skanery do Unicode w rozsądnej ilości pamięci.

Masz wiele możliwości wyboru sposobu przedstawiania i przetwarzania zestawów znaków. Obecnie pracuję nad rozwiązaniem, które zachowuje uporządkowaną listę warunków brzegowych i odpowiadające im stany docelowe. Możesz przetwarzać operacje na tych listach znacznie szybciej niż byś, gdybyś musiał skanować cały alfabet w każdym momencie. W rzeczywistości jest wystarczająco szybki, aby działał w Pythonie z akceptowalną szybkością.

Answer 3

Miałem ten sam problem z moim generatorem skanerów, więc wpadłem na pomysł zastąpienia interwałów ich identyfikatorami, które są określane przy użyciu drzewa interwałowego. Na przykład zakres a.z w dfa może być reprezentowany jako: 97, 98, 99, ..., 122, zamiast tego reprezentuję zakresy jako [97, 122], a następnie buduję z nich strukturę drzewa interwałowego, więc na końcu są one reprezentowane jako identyfikatory, które odnoszą się do drzewa interwałowego. Biorąc pod uwagę następujące RE: a ..Z +, możemy skończyć z takim DFA:

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 

Teraz kompresji przedziały:

0 -> a..z -> 1 

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

wyodrębnić wszystkie przedziały z twojego DFA i zbudować drzewo przedziałowe z nich:

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

Wymień rzeczywisty interwały do ​​ich identyfikatorów:

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

Answer 4

W tej bibliotece (http://mtimmerm.github.io/dfalex/) robię to poprzez umieszczenie zakresu kolejnych znaków na każdym przejściu, zamiast pojedynczych znaków. Jest to realizowane przez wszystkie etapy budowy NFA, NFA-> DFA, minimalizacji DFA i optymalizacji.

Jest dość kompaktowy, ale dodaje złożoności kodu do każdego kroku.