BK - Baumsuche Alle

Question

Eine BK Trees (Burkhard-Keller Trees) ist mit Fuzzy-String-Suchen verbunden (z. B. Rechtschreibprüfung, Wortempfehlungen). Und alle Suchalgorithmen von BK Trees sind identisch mit explained here. Ziel ist es, beispielsweise "seek" and "peek" if I search for "aeek" zurückzugeben.

Nun, meine Frage ist, versuche ich diese Fuzzy String sucht Algorithmus zu verwenden für alle ähnliche Elemente aus dem gegeben Wörterbuch zu suchen. Zum Beispiel, mit einem Wort "suchen", möchte ich alle ähnliche Wörter finden, wie "peek", "Geek", "Sitz", etc. innerhalb des Wörterbuchs. Allerdings habe ich festgestellt, dass die BK Trees searching algorithm that everyone uses nicht dafür ausgelegt ist.

Werfen Sie einen Blick auf meine sample test result here. Ich fand das the dictionary will be different if the feeding words order is different, thus the search result can be different as well.

Was ich will ist, mit meiner oben , gegeben eines der vier Python Bücher, eine SearchAll Funktion wird immer die vier Python Bücher zurück, trotz der Reihenfolge, die das Wörterbuch gebaut wird, oder die Reihenfolge der Suche erfolgt.

Ich habe jedoch viele Möglichkeiten versucht, aber alle fehlgeschlagen (z. B. this is one of them). Jetzt werfe ich meine Hände hoch und bitte um Hilfe. Ein Pseudo-Code oder ein generischer Algorithmus würde dies tun. Danke.

Answer 1

Sie haben einen ganzzahligen Überlauf auf den Leitungen 77 und 106 von bktree.go:

k: = d - r

Da die Typen von d und ruint8 sind, die Art der k ist auch uint8, also wenn d < r, k endet größer als d + r, und der folgende Zyklus wird nicht ausgeführt.

Sie können es wie folgt beheben:

k := int16(d) - int16(r) 
max_k := int16(d) + int16(r) 
if k < 1 { 
    k = 1 
} 
for ; k <= max_k; k++ { 
    ... 
}