jaka jest potrzeba innego bloku w metodzie "push_links" następującego kodu? - aho-corasick

Ten kod jest dla algorytmu Aho-Corasick, z którego sędziowałem tutaj

Zrozumiałem ten kod aż do blokumetoda push_links, ale nie dostałem zastosowania ani wymagania dla innej części tej samej metody. Dokładniej pierwsza metoda jest używana do konstruowania trie. Pozostała praca jest wykonywana za pomocą drugiego sposobu, tj. Łączenia węzła z ich najdłuższym właściwym sufiksem, który jest także przedrostkiem pewnego wzorca. Jest to wykonywane przez blok If, a co za tym idzie potrzeba innej części.

Proszę, pomóż mi w tym.

const int MAXN = 404, MOD = 1e9 + 7, sigma = 26;

int term[MAXN], len[MAXN], to[MAXN][sigma], link[MAXN], sz = 1;

// this method is for constructing trie

void add_str(string s)
{

// here cur denotes current node

int cur = 0;

// this for loop adds string to trie character by character

for(auto c: s)
{
if(!to[cur][c - "a"])
{

//here two nodes or characters are linked using transition
//array "to"

to[cur][c - "a"] = sz++;
len[to[cur][c - "a"]] = len[cur] + 1;

}

// for updating the current node

cur = to[cur][c - "a"];
}

//for marking the leaf nodes or terminals

term[cur] = cur;
}


void push_links()
{
//here queue is used for breadth first search of the trie
int que[sz];
int st = 0, fi = 1;

//very first node is enqueued
que[0] = 0;

while(st < fi)
{

// here nodes in the queue are dequeued
int V = que[st++];

// link[] array contains the suffix links.
int U = link[V];


if(!term[V]) term[V] = term[U];

// here links for the other nodes are find out using assumption that the
// link for the parent node is defined

for(int c = 0; c < sigma; c++)

// this if condition ensures that transition is possible to the next node
// for input "c"

if(to[V][c])
{

// for the possible transitions link to the reached node is assigned over
// here which is nothing but transition on input "c" from the link of the
// current node

link[to[V][c]] = V ? to[U][c] : 0;
que[fi++] = to[V][c];
}
else
{
to[V][c] = to[U][c];
}
}
}

Odpowiedzi:

IMO nie potrzebujesz warunku innego. Jeśli nie ma dzieci, to jest to już link lub nic.

Istnieją pewne odmiany algorytmu Aho-Corasick. Algorytm bazowy zakłada, że ​​jeśli krawędź z bieżącego węzła (kundel) nad symbolem (do) brakuje, a następnie przechodzisz przez sufiksy do pierwszego węzła, który ma przewagę do (wykonujesz ruch przez tę krawędź). Ale twój sposób na linki przyrostkowe jest taki sam (z tego samego kundel i do), ponieważ nie zmieniasz automatu podczas wyszukiwania, więc możesz go buforować (zapisać wynik

// start from node
while (parent of node doesn"t have an edge over c) {
node = parent
}
// set trie position
node = to[node][c]
// go to next character

w do [węzeł] [c]. Więc następnym razem, gdy nie zrobisz tego ponownie. I przeniesie się z automatu z niedeterministycznego na deterministyczną maszynę stanu (nie musisz używać połączyć tablica po naciśnięciu, możesz użyć tylko do szyk).

Istnieją pewne problemy z tą implementacją. Po pierwsze, możesz uzyskać indeks znalezionego ciągu (nie zapisujesz go). Ponadto tablica len nie jest nigdzie używana.

Dla

oznacza, że ​​ten algorytm sprawdza tylko istnienie znaku w bieżącym łączu węzłowym, używając „łącza [do [V] [c]] = V? do [U] [c]: 0;”. czy nie powinien również weryfikować linku rodziców?

Tak, jest ok, ponieważ jeśli do [U] [c] jest 0, to nie ma żadnych krawędzi przez c ze wszystkich łańcuchów U-> sufiks_parent-> sufiks rodzic sufiksu_parent ... -> root = 0. należy ustawić na [V] [c] na zero.