편집 거리 알고리즘

Question

나는 'n'개의 단어 사전을 가지고 있으며 응답 할 'm'개의 검색어가 있습니다.

: I 출력하도록 I는 n 및 m 편집 아래 답변에서 추가 3000

대략 것을 주어진 결과 집합을 최적화 할 편집 거리가 1 또는 2이다 사전의 단어의 수를 원하는 다르게 말하려고 노력할 것입니다.

처음에는 'n'단어가 사전 단어 세트로 제공됩니다. 다음 'm'단어가 검색어로 주어지며 각 검색어에 대해 단어가 사전 (Edit Distance '0') 또는 편집 거리 1에있는 사전의 총 단어 수에 이미 있는지 확인해야합니다. 2 사전 단어에서.

질문이 이제 취소되기를 바랍니다.

시간 복잡도가 (m * n)이면 시간이 초과됩니다. DP 편집 거리 알고리즘을 사용하면 시간이 오래 걸립니다. 위의 경우 k가 임계 값 인 곳에서 2k + 1 배의 대각선 요소를 계산합니다. 여기에서는 k = 3입니다.

Answer 1

두 단어 사이에 Levenshtein distance을 사용하고 싶지만 그 질문의 태그가 말하는 그 이후로 알고 있다고 가정합니다.

목록 (가정)을 반복하고 목록의 모든 단어를 실행중인 현재 쿼리와 비교해야합니다. 검색 공간을 제한하기 위해 BK-tree을 만들 수도 있지만 ~ 3000 단어 만 있으면 과장된 소리가납니다.

var upperLimit = 2; 
var allWords = GetAllWords(); 
var matchingWords = allWords 
     .Where(word => Levenshtein(query, word) <= upperLimit) 
     .ToList(); 

추가 당신은 대소 문자를 구분 사전이있는 경우 거리 = 0이 용이 포함 - 쿼리 될 경우를 찾기 원래의 질문에

의 편집 후. 거리가 < = 2 인 경우 검색 공간을 완전히 검색해야하며 검색어 당 3000 개의 비교가 필요합니다. 동일한 양의 질의어를 가정하면 9 백만 건의 비교가됩니다.

시간이 초과되었다는 것을 언급 했으므로 시간 초과가 구성되었다고 가정합니다. 귀하의 속도가 Levenshtein 계산의 빈약하거나 느린 구현으로 인한 것일 수 있습니까? 그래프 위

Graph showing visited search space using a bk-tree with different amount of input http://www.students.itu.edu.tr/~yazicivo/bk-tree-report.png 은 < = 2 만 검색 공간의 약 1 %를 방문 할 편집 거리 BK-트리를 사용하여 볼 수 있듯이 CLiki: bk-tree

에서 도난하지만 당신이 매우 큰이 있다고 가정 것 입력 데이터, 그들의 경우 최대 50 만 단어. 나는 당신의 경우에 비슷한 수를 가정 할 것이지만, 그런 적은 양의 입력은 List/Dictionary에 저장되어 있어도 많은 문제를 일으키지 않을 것입니다.

Answer 2

나는 그것을 다르게하려고 노력할 것이다.

처음에는 'n'단어가 사전 단어 세트로 제공됩니다. 다음 'm'단어가 검색어로 주어지며 각 검색어에 대해 단어가 사전 (Edit Distance '0') 또는 편집 거리 1에있는 사전의 총 단어 수에 이미 있는지 확인해야합니다 또는 사전 단어에서 2.

질문이 이제 취소되기를 바랍니다.

시간 복잡도가 (m * n) * n이면 시간이 초과됩니다. DP 편집 거리 알고리즘을 처음 사용하면 시간이 초과됩니다. 2 * k + 1 배의 대각선 요소 계산 k가 임계 값 인 경우 위의 경우 k = 3입니다.

추 신 : BK 트리는 목적을 충족시켜야합니다. C++의 구현에 관한 모든 링크.

Answer 3

public class Solution { 
    public int minDistance(String word1, String word2) { 
     int[][] table = new int[word1.length()+1][word2.length()+1]; 
     for(int i = 0; i < table.length; ++i) { 
      for(int j = 0; j < table[i].length; ++j) { 
       if(i == 0) 
        table[i][j] = j; 
       else if(j == 0) 
        table[i][j] = i; 
       else { 
        if(word1.charAt(i-1) == word2.charAt(j-1)) 
         table[i][j] = table[i-1][j-1]; 
        else 
         table[i][j] = 1 + Math.min(Math.min(table[i-1][j-1], 
          table[i-1][j]), table[i][j-1]); 
       } 
      } 
     } 
     return table[word1.length()][word2.length()]; 
    } 
}