Budowa DFA w algorytmie Knutha-Morrisa-Pratta

Question

Budowa DFA w algorytmie Knutha-Morrisa-Pratta

Odnoszę się do zarysu algorytmu Knutha-Morrisa-Pratta (KMP) do wyszukiwania podciągów w książce Sedgewicka "algorytmy" (4th ed.).

Algorytm KMP używa kopii zapasowej w wyszukiwaniu substringów w oparciu o deterministyczny automat skończony (Dfa). Rozumiem, jak DFA wchodzi do algorytmu, jednak nie rozumiem, jak skonstruować DFA, co odbywa się za pomocą następującego fragmentu kodu:

dfa[pat.charAt(0)][0] = 1;
for (int X = 0; j = 1; j< M; j++) {
    for (int c = 0; c < R; c++) {
       dfa[c][j] = dfa[c][X];
    }
    dfa[pat.charAt(j)][j] = j+1;
    X = dfa[pat.charAt(j)][X];
}

Gdzie M jest długością wzoru pat i R rozmiar alfabetu. Funkcja charAt() Zwraca wartość całkowitą znaku na odpowiedniej pozycji.

Czy ktoś może wyjaśnić w jaki sposób ten fragment kodu konstruuje dfa? Gubię się w intuicyjnym znaczeniu wewnętrznej pętli for.

10

algorithm string substring dfa knuth-morris-pratt

Author: madison54, 2015-05-30

Source

1 answers

score 8 · Accepted Answer

Przyjrzyjmy się poniższemu FA dla wzoru ACACAGA.

Tutaj wpisz opis obrazka

Powyższe diagramy przedstawiają graficzne i tabelaryczne reprezentacje wzoru ACACAGA.

Tutaj liczba stanów w DFA to M + 1, Gdzie M jest długością wzoru. Najważniejszą rzeczą do skonstruowania DFA jest uzyskanie następnego stanu ze stanu bieżącego dla każdego możliwego znaku. Biorąc pod uwagę znak x i stan k, możemy uzyskać następny stan, biorąc pod uwagę ciąg " pat[0..k-1] x" czyli w zasadzie konkatenacja znaków wzorca pat [0], pat1 ... pat [k-1] i znak x. chodzi o to, aby uzyskać długość najdłuższego przedrostka danego wzoru, tak aby przedrostek był również sufiksem (LPS) "pat[0..k-1] x". Wartość długości daje nam Następny stan.

Na przykład zobaczmy, jak uzyskać następny stan z bieżącego stanu 5 i znak " C " na powyższym diagramie. Musimy wziąć pod uwagę ciąg " pat[0..5] C "czyli " ACACAC". Długość najdłuższy przedrostek wzoru taki, że przedrostek jest przyrostkiem "ACACAC" wynosi 4 ("ACAC"). Więc następny stan (ze stanu 5) to 4 dla znaku 'C'.

// dfa[i][j] = k denotes the transition function will go k'th state 
// with character i from state j

// DFA will go always (i + 1)'th state from i'th state 
//if the character c is equal to current character of pattern 
dfa[pat.charAt(0)][0] = 1;

//  here X is initialized with LPS (longest prefix suffix) 
// of pattern[0....j - 1]. LPS[0] is always 0
for (int X = 0; j = 1; j< M; j++) {
    for (int c = 0; c < R; c++) { // for all possible characters
        // transition function from j'th state taking character c 
        // will go to the same state where it went from X(LPS)'th state
        // taking character c (justify it with an example) 
        dfa[c][j] = dfa[c][X];
    }
    // DFA will go always (i + 1)th state from i'th state if 
    // the character c is equal to current character of pattern
    dfa[pat.charAt(j)][j] = j + 1;
    X = dfa[pat.charAt(j)][X]; // update LPS
}