Was muss sonst in der Methode "push_links" des folgenden Codes blockiert werden? - Aho-Corasick

Dieser Code ist für den Aho-Corasick-Algorithmus, von dem ich referiert habe Hier

Ich habe diesen Code bis zu Block of verstandenPush_links-Methode, aber ich habe nicht die Verwendung oder Anforderung für den else-Teil derselben Methode erhalten. Insbesondere wird die erste Methode für den Bau von Trie verwendet. Die verbleibende Arbeit wird durch ein zweites Verfahren erledigt, d. Dies wird vom If-Block ausgeführt, was sonst noch benötigt wird.

Bitte hilf mir dabei.

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];
}
}
}

Antworten:

IMO brauchst du nicht die else-Bedingung. Wenn es keine Kinder gibt, ist es entweder schon ein Link oder nichts.

Es gibt einige Variationen des Aho-Corasick-Algorithmus. Der Basisalgorithmus geht davon aus, dass die Kante vom aktuellen Knoten (cur) über Symbol (c) fehlt, dann gehst du über Suffixverknüpfungen zum ersten Knoten, der die Kante überschritten hat c (Sie bewegen sich über diese Kante). Ihr Weg über Suffix-Links ist jedoch derselbe (aus dem gleichen) cur und c), weil Sie den Automaten während der Suche nicht ändern

// 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

in [Knoten] [c]. Das nächste Mal tun Sie dies also nicht mehr. Und es überträgt den Automaten von einer nicht deterministischen in eine deterministische Zustandsmaschine (Sie müssen dies nicht tun.) Verknüpfung Array nach dem Drücken können Sie nur verwenden zu Array).

Bei dieser Implementierung gibt es einige Probleme. Erstens können Sie einen Index der gefundenen Zeichenfolge erhalten (Sie speichern ihn nicht). Außerdem wird das len-Array nicht überall verwendet.

Zum

Das heißt, dieser Algorithmus überprüft lediglich das Vorhandensein des Zeichens in der aktuellen Knotenverbindung mit "link [nach [V] [c]] = V [bis] [c]: 0". sollte es nicht auch im elternlink verifizieren?

Ja, es ist in Ordnung, denn wenn zu [U] [c] 0 ist, dann gibt es keine Kanten über c aus allen Ketten U-> Suffix_Parent-> Suffix Parent von Suffix_Parent ... -> Root = 0. Also sollte auf [V] [c] auf Null gesetzt werden.