BK - Arbre Recherche tout

Question

Un BK Trees (Burkhard-Keller Trees) est associé aux recherches de chaînes floues (par exemple, vérification orthographique, recommandations de mots). Et tout l'algorithme de recherche BK Trees est le même que explained here. L'objectif est de revenir, par exemple, "seek" and "peek" if I search for "aeek".

Maintenant, ma question est, je suis en train d'utiliser cet algorithme flou de recherche de chaîne à rechercher tous articles similaires du dictionnaire donnés . Par exemple, étant donné un mot "chercher", je veux trouver tous mots similaires, comme "peek", "geek", "siège", etc dans le dictionnaire. Cependant, j'ai trouvé le BK Trees searching algorithm that everyone uses n'est pas conçu pour cela.

Regardez sample test result here. J'ai trouvé que the dictionary will be different if the feeding words order is different, thus the search result can be different as well.

Ce que je veux, en utilisant mon ci-dessus sample test, compte tenu de l'un des quatre livres Python, une fonction SearchAll retourne toujours les quatre livres Python, malgré l'ordre du dictionnaire est construit, ou l'ordre de la recherche est effectuée.

Cependant, j'ai essayé de nombreuses façons, mais toutes ont échoué (par exemple, this is one of them). Maintenant, je lève les mains et demande de l'aide. Un pseudo code ou un algorithme générique décrivant ferait l'affaire. THX.

Answer 1

Vous avez un débordement d'entier sur les lignes 77 et 106 de bktree.go:

k: = d - r

Depuis les types de d et r sont uint8, le type de k est également uint8, donc quand d < r, k finit plus grand que d + r, et le cycle suivant ne s'exécute pas.

Vous pouvez le fixer comme ceci:

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