Algorithme dynamique de correction automatique du texte

Question

Je suis en train d'écrire un programme de correction automatique qui utilise le levenshtein distance pour corriger une phrase de pas plus de 64 caractères basés sur un dictionnaire spécifique contenant 8000 mots.

Le dictionnaire contient sur chaque ligne la paire "Word word_frequency". J'utilise des objets DictionarEntry pour stocker ces paires. Classe Dictionar Entry a deux champs: value: stocke la chaîne de caractères freq: stocke la fréquence Le dictionnaire est stocké en tant que LinkedList. Je lis depuis stdin la chaîne de 64 caractères. avant de le traiter Je supprime tous les espaces. "Coo lweather" -> "Coolweather" J'ai remarqué que insead de calculer la distance levenshtein pour chaque préfixe, dans la dernière rangée de la matrice calculée par la dynamique levenshtein (voir l'exemple wikipedia) il renvoie les distances pour tous les préfixes .

La fonction lev renvoie un vecteur contenant la distance l.distance de la deuxième chaîne de paramètres à tous les préfixes du premier, y compris lui-même. Mon problème est que je dois respecter quelques règles supplémentaires: min lev. distance -> min nombre de mots -> somme maximum de fréquence -> minimum lexicographique Cela serait expliqué comme si le nombre total de solutions est supérieur à 1 nous prenons ceux avec un nombre minimum de mots. S'il y en a encore plus d'un, nous suivons la liste des règles.

La dynamique que j'applique est quelque chose de similaire à une dynamique de sac à dos. Je ne sais pas comment mettre en œuvre le nombre minimum de règle de mots (une fréquence maximale est très similaire)

Voici ce que je l'ai essayé jusqu'à présent exemples d'entrée/sortie où cela ne fonctionne pas: « mal réservé » la réponse devrait être si réservée, ce que j'obtiens est effectivement tellement servi J'ai choisi cette méthode parce qu'elle est plus efficace. La limite de temps est de 2 secondes pour Java.

mise à jour: 7 avril. J'ai trouvé la solution à mon problème, mais le temps de CPU est trop important et je dois donc l'optimiser. Il ne devrait pas dépasser 2000 ms et il est actuellement d'environ 6000 ms. Alors maintenant, mon objectif principal devient l'optimisation. Où dois-je implémenter les règles et comment (idéalement d'une manière plus efficace que d'utiliser une matrice)

public static String guess (String input, LinkedList<DictionarEntry> Dictionar){ 
     String curent = new String(); 
     String output = new String(); 

     int costMatrix[][][] = new int [input.length()][8000][input.length()];   
    int index[] = new int[128]; 
    int prev[]= new int[128]; 
     int d[]=new int [128]; 
     int freq[]= new int[128]; 
     int wcount[]=new int[128]; 
     String values[] = new String[128]; 
     for (int i=0 ; i < 128 ; i++){ 
       d[i]=127; 
       freq[i]=0; 
       wcount[i]=1; 
       values[i]=""; 
     }   
    d[0]=0; 
    freq[0]=0; 

     for (int i = 0 ; i <input.length(); ++i){ 

      curent=input.subSequence(i, input.length()).toString(); 
      long start =System.currentTimeMillis(); 
       for (int j = 0 ; j < Dictionar.size();++j){ 

        costMatrix[i][j]=lev(Dictionar.get(j).value,curent); 
        for(int k=1;k<costMatrix[i][j].length;++k){ 

         if(d[i]+costMatrix[i][j][k]<d[i+k]){ 
          d[i+k]= d[i]+costMatrix[i][j][k]; 
           values[i+k]=values[i]+Dictionar.get(j).value; 
           freq[i+k]=freq[i]+Dictionar.get(j).freq; 
           index[i+k]=j; 
           prev[i+k]=i; 
           wcount[i+k]=wcount[i]+1; 
         } 
         else if ((d[i]+costMatrix[i][j][k])==d[i+k]) 
             if((wcount[i]+1) <wcount[i+k]){ 
           values[i+k]=values[i]+Dictionar.get(j).value; 
           freq[i+k]=freq[i]+Dictionar.get(j).freq; 
           index[i+k]=j; 
           prev[i+k]=i; 
           wcount[i+k]=wcount[i]+1;  
             } 
             else if ((wcount[i]+1)==wcount[i+k]) 
             if((freq[i]+Dictionar.get(j).freq)>freq[i+k]){ 
              values[i+k]=values[i]+Dictionar.get(j).value; 
              freq[i+k]=freq[i]+Dictionar.get(j).freq; 
              index[i+k]=j; 
              prev[i+k]=i; 
              wcount[i+k]=wcount[i]+1;  
             } 
             else if ((freq[i]+Dictionar.get(j).freq)==freq[i+k]){ 
              if((values[i]+Dictionar.get(j).value).compareTo(values[i+k])>0){ 
               values[i+k]=values[i]+Dictionar.get(j).value; 
               freq[i+k]=freq[i]+Dictionar.get(j).freq; 
               index[i+k]=j; 
               prev[i+k]=i; 
               wcount[i+k]=wcount[i]+1; 
              } 
             } 
        }  
       } 
       long finished =System.currentTimeMillis(); 
        System.out.println((finished-start)); 

     output=""; 

     } 

      int itr=input.length(); 
        while(itr!=0){ 
     output = Dictionar.get(index[itr]).value + " " + output; 
     itr=prev[itr]; 
    } 
    return output; 
    } 

En cas de questions ou j'ai laissé quelque chose pas clair s'il vous plaît ne hésitez pas à demander

Answer 1

Toute raison pour laquelle vous ne pouvez pas utiliser une bibliothèque existante comme Apache Lucene? Il prend en charge fuzzy queries qui utilisent la distance Levenshtein.

Autre que vous voudrez peut-être envisager Suffix Trees pour accélérer la recherche de chaîne partielle