Thuật toán động cho văn bản tự động sửa

Question

Tôi đang viết chương trình tự động sửa sử dụng levenshtein distance để sửa cụm từ không quá 64 ký tự dựa trên từ điển cụ thể chứa 8000 từ.

Từ điển chứa trên mỗi dòng, cặp "Word word_frequency". Tôi sử dụng các đối tượng DictionarEntry để lưu trữ các cặp đó. Entry Dictionar Class có hai trường: giá trị: lưu trữ chuỗi từ freq: lưu trữ tần số Từ điển được lưu trữ dưới dạng LinkedList. Tôi đọc từ stdin chuỗi ký tự 64. trước khi xử lý, tôi xóa tất cả các khoảng trắng. "Coo lweather" -> "Coolweather" Tôi nhận thấy rằng việc tính toán khoảng cách levenshtein cho mỗi tiền tố, trong hàng cuối cùng của ma trận được tính toán bởi động lượng levenshtein (xem ví dụ wikipedia) nó trả về khoảng cách cho tất cả các tiền tố .

Hàm lev trả về một vectơ chứa l.distance từ chuỗi tham số thứ hai tới tất cả tiền tố đầu tiên, kể cả tiền tố.

Vấn đề của tôi là tôi phải tôn trọng một vài quy tắc bổ sung: phút tối thiểu. khoảng cách -> số lượng từ tối thiểu -> tổng tần số tối đa -> từ điển tối thiểu Điều đó sẽ được giải thích như tổng số giải pháp lớn hơn 1 chúng tôi lấy số từ có số từ tối thiểu. Nếu vẫn còn nhiều hơn một chúng tôi theo danh sách các quy tắc.

Hoạt động tôi đang áp dụng là điều gì đó tương tự như năng động của ba lô. Tôi không biết làm thế nào để thực hiện số lượng tối thiểu các từ quy tắc (một trong những tần số tối đa là rất tương tự)

Dưới đây là những gì tôi đã cố gắng cho đến nay đầu vào/đầu ra ví dụ nơi này không thành công: "đau dành riêng" câu trả lời nên được dành riêng, những gì tôi có được thực sự là để phục vụ Tôi đã chọn phương pháp này bởi vì nó là hiệu quả hơn. Giới hạn thời gian là 2 giây đối với Java.

cập nhật: ngày 7 tháng 4. Tôi đã tìm ra giải pháp cho vấn đề của mình, tuy nhiên thời gian cpu quá lớn nên tôi cần tối ưu hóa nó. Không được cao hơn 2000 mili giây và hiện tại khoảng 6000 mili giây. Vì vậy, bây giờ tập trung chính của tôi trở nên tối ưu hóa nó.

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

Tôi nên triển khai quy tắc và cách nào (lý tưởng theo cách hiệu quả hơn sử dụng ma trận)?

Trong trường hợp có bất kỳ thắc mắc hoặc tôi đã để lại một cái gì đó không rõ ràng vui lòng hỏi

Answer 1

Bất kỳ lý do tại sao bạn không thể sử dụng một thư viện hiện như Apache Lucene? Nó hỗ trợ fuzzy queries sử dụng khoảng cách Levenshtein.

Ngoài ra bạn có thể muốn xem xét Suffix Trees để tăng tốc độ tìm kiếm chuỗi phần