Dynamiczny algorytm automatycznej korekty tekstu

Question

Piszę program do automatycznej korekty, który używa levenshtein distance do poprawienia frazy nie większej niż 64 znaków w oparciu o konkretny słownik zawierający 8000 słów.

Słownik zawiera w każdym wierszu parę "Word word_frequency". Używam obiektów DictionarEntry do przechowywania tych par. Wpis klasy Dictionar ma dwa pola: wartość: przechowuje ciąg znaków freq: przechowuje częstotliwość Słownik jest przechowywany jako lista_połączeń. Przeczytałem ze stdin ciąg 64 znaków. przed przetworzeniem Usuwam wszystkie spacje. "Coo lweather" -> "Coolweather" Zauważyłem, że to nieodwracalne obliczanie odległości dla każdego prefiksu, w ostatnim wierszu macierzy obliczonym przez dynamiczny levenshtein (patrz przykład wikipedia) zwraca odległości dla wszystkich prefiksów .

Funkcja lew zwraca wektor zawierający l.distance od drugiego ciągu parametrów do wszystkich pierwszych prefiksów, w tym samego siebie.

Moim problemem jest to, że muszę przestrzegać kilku dodatkowych zasad: min. Lew. odległość -> min. liczba słów -> maksymalna suma częstotliwości -> minimalna leksykograficzna Wyjaśnilibyśmy to tak, jakby całkowita liczba rozwiązań była większa niż 1 przyjmujemy te z minimalną liczbą słów. Jeśli nadal jest więcej niż jeden, postępujemy zgodnie z listą reguł.

Dynamika, którą stosuję, jest podobna do dynamiki plecaka. nie wiem jak zaimplementować minimalnej liczby słów reguły (jedna maksymalna częstotliwość jest bardzo podobny)

Oto, co starałem dotąd przykłady wejścia/wyjścia, w którym to się nie powiedzie: „ból Reserved” odpowiedź powinna być tak zarezerwowana, co ja otrzymuję, tak naprawdę jest obsługiwana Wybrałem tę metodę, ponieważ jest bardziej wydajna. Limit czasu wynosi 2 sekundy dla Java.

aktualizacja: 7 kwietnia. Znalazłem rozwiązanie mojego problemu, jednak czas procesora jest zbyt duży, więc muszę go zoptymalizować. Powinien być nie wyższy niż 2000 ms i wynosi obecnie około 6000 ms. Teraz moim głównym celem staje się optymalizacja.

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

Gdzie należy wdrożyć zasady i jak (najlepiej w bardziej efektywny sposób niż przy użyciu matrycy)?

W przypadku jakichkolwiek pytań lub Zostawiłem coś niejasne proszę czuć swobodnie pytać

Answer 1

jakiegokolwiek powodu, dlaczego nie można użyć istniejącej biblioteki jak Apache Lucene? Obsługuje fuzzy queries, które wykorzystują odległość Levenshtein.

Poza tym warto rozważyć Suffix Trees przyspieszyć częściowe wyszukiwanie ciągów