Cet algorithme a-t-il été implémenté correctement?

Question

Je suis exécute actuellement un BK-Tree pour faire un correcteur orthographique. Le dictionnaire avec lequel je travaille est très volumineux (des millions de mots), ce qui explique pourquoi je ne peux me permettre aucune inefficacité. Cependant, je sais que la fonction de recherche que j'ai écrite (sans doute la partie la plus importante de tout le programme) peut être améliorée. J'espérais trouver de l'aide concernant la même chose. Voici la recherche que j'ai écrit:

public int get(String query, int maxDistance) 
{ 
    calculateLevenshteinDistance cld = new calculateLevenshteinDistance(); 
    int d = cld.calculate(root, query); 
    int tempDistance=0; 

    if(d==0) 
     return 0; 

    if(maxDistance==Integer.MAX_VALUE) 
     maxDistance=d; 

    int i = Math.max(d-maxDistance, 1); 
    BKTree temp=null; 

    for(;i<=maxDistance+d;i++) 
    { 
     temp=children.get(i); 
     if(temp!=null) 
     { 
      tempDistance=temp.get(query, maxDistance); 
     } 
     if(maxDistance<tempDistance) 
      maxDistance=tempDistance; 
    } 

    return maxDistance; 
} 

Je sais que je courais la boucle un nombre inutilement grand nombre de fois et que nous pouvons réduire l'espace de recherche pour accélérer la recherche. Je ne suis pas sûr de savoir comment faire mieux.

Answer 1

Votre boucle semble généralement correcte, si un peu Byzantin. Votre tentative d'affiner la condition d'arrêt (avec tempdistance/maxDistance) est incorrect, cependant: la structure du BK-arbre exige que vous explorez tous les noeuds dk distance levenshtein à d + k du noeud courant si vous voulez trouver tous les résultats, de sorte que vous ne pouvez pas l'élaguer comme ça.

Ce que vous fait penser que vous explorez trop de l'arbre?

Vous pourriez trouver mon post sur L evenshtein Automata suivi instructifs, car ils sont plus efficaces que les BK arbres. Si vous construisez un vérificateur d'orthographe, cependant, je recommande de suivre la suggestion de Favonius et de vérifier this article sur la façon d'en écrire un. Il est beaucoup mieux adapté à la correction d'orthographe qu'une vérification naïve de la distance entre cordes.