Levenshtein Trie 잘못된 거리

Question

나는 levenshtein trie의 구현을 위해 웹을 검색했으며 이걸 발견했습니다 : Levenshtein Distance Challenge: Causes. 단어를 정규화하는 코드를 추가하려고했습니다. 예를 들어 단어 에 5 글자 ('Apple')가 있고이 단어 ('Aple')가있는 경우 거리가 1이고 동일한 것으로 간주합니다. 예를 들어 에 단어가 더 길면 ('상황') 더 많은 실수를 할 수 있습니다. 이 단어에 실수가 두 번있는 경우 원래 코드 은 최소 거리를 2로 계산하고 받아들이지 않을 것입니다. 그래서 에 대수를 쓰길 원합니다. 로그로 '상황' 과 'kirkumstances'사이의 거리가 2보다 작고 캐스팅이 인데 int가 1이 될 것이기 때문에 그 사이의 거리는 내가 원하는 것입니다.

public class LevenshteinTrie { 
    private int distance = -1; 
    private Trie trie = null; 

    public LevenshteinTrie(int distance, Set<String> words) { 
     this.distance = distance; 
     this.trie = new Trie(); 

     for(String word : words) { 
      this.trie.insert(word); 
     } 
    } 

    public Set<String> discoverFriends(String word, boolean normalized) { 
     Set<String> results = new HashSet<String>(); 

     int[] currentRow = new int[word.length() + 1]; 

     List<Character> chars = new ArrayList<Character>(word.length()); 

     for(int i = 0; i < word.length(); i++) { 
      chars.add(word.charAt(i)); 
      currentRow[i] = i; 
     } 

     currentRow[word.length()] = word.length(); 

     for(Character c : this.trie.getRoot().getChildren().keySet()) { 
      this.traverseTrie(this.trie.getRoot().getChildren().get(c), c, chars, currentRow, results, normalized); 
     } 

     return results; 
    } 

    private void traverseTrie(TrieNode node, char letter, List<Character> word, int[] previousRow, Set<String> results, boolean normalized) { 
     int size = previousRow.length; 
     int[] currentRow = new int[size]; 

     currentRow[0] = previousRow[0] + 1; 

     int minimumElement = currentRow[0]; 

     int insertCost = 0; 
     int deleteCost = 0; 
     int replaceCost = 0; 

     for(int i = 1; i < size; i++) { 
      insertCost = currentRow[i - 1] + 1; 
      deleteCost = previousRow[i] + 1; 

      if(word.get(i - 1) == letter) { 
       replaceCost = previousRow[i - 1]; 
      } else { 
       replaceCost = previousRow[i - 1] + 1; 
      } 

      currentRow[i] = Math.min(Math.min(insertCost, deleteCost), replaceCost); 

      if(currentRow[i] < minimumElement) { 
       if(normalized) { 
        minimumElement = (int)(currentRow[i]/(Math.log10(word.size()))); 
       } else { 
        minimumElement = currentRow[i]; 
       } 
      } 
     } 

     int tempCurrentRow = currentRow[size - 1]; 

     if(normalized) { 
      tempCurrentRow = (int)(currentRow[size - 1]/(Math.log10(word.size()))); 
     } 

     System.out.println(tempCurrentRow); 

     if(tempCurrentRow <= this.distance && node.getWord() != null) { 
      results.add(node.getWord()); 
     } 

     if(minimumElement <= this.distance) { 
      for(Character c : node.getChildren().keySet()) { 
       this.traverseTrie(node.getChildren().get(c), c, word, currentRow, results, normalized); 
      } 
     } 
    } 
} 

public class Trie { 
    private TrieNode root = null;; 

    public Trie() { 
     this.root = new TrieNode(); 
    } 

    public void insert(String word) { 
     TrieNode current = this.root; 

     if (word.length() == 0) { 
      current.setWord(word); 
     } 

     for (int i = 0; i < word.length(); i++) { 
      char letter = word.charAt(i); 

      TrieNode child = current.getChild(letter); 

      if (child != null) { 
       current = child; 
      } else { 
       current.getChildren().put(letter, new TrieNode()); 
       current = current.getChild(letter); 
      } 

      if (i == word.length() - 1) { 
       current.setWord(word); 
      } 
     } 
    } 
} 

public class TrieNode { 
    public static final int ALPHABET = 26; 
    private String word = null; 
    private Map<Character, TrieNode> children = null; 

    public TrieNode() { 
     this.word = null; 
     this.children = new HashMap<Character, TrieNode>(ALPHABET); 
    } 

    public TrieNode getChild(char letter) { 
     if(this.children != null) { 
      if(children.containsKey(letter)) { 
       return children.get(letter); 
      } 
     } 

     return null; 
    } 

    public String getWord() { 
     return word; 
    } 
} 

불행히도이 코드는 올바르게 작동하지 않습니다. 최대 거리를 1로 설정했습니다. 이제 프로그램을 실행하고 'vdimir putin'을 검색하면 프로그램이 친구로 받아 들여지지 않습니다 (블라디미르 putin ' ). 난 임시 계산 된 거리를 출력 할 때 해당 같다 :

tempCurrentRows 때 최대 거리 = 1 :

11 
11 
10 
10 
10 
10 
11 
11 
11 
11 
10 
11 
11 
11 
11 
11 
11 
11 
10 
10 
10 
10 
10 
10 
10 
10 
10 
10 
9 
11 
11 
10 
10 
10 
10 

하지만 2에 최대 거리를 설정하는 경우 임시 거리는 변화된다

11 
11 
11 
10 
10 
10 
10 
9 
9 
8 
7 
6 
5 
4 
3 
2 
1 
11 
11 
10 
10 
9 
9 

그래서 코드에서 큰 실수가 있어야합니다 : 최대 거리 = 2

tempCurrentRows. 하지만 난 어디서 왜 이유가 그리고 어떻게 작동하도록 코드를 변경해야합니다.

Answer 1

'vdimir putin'에 대한 검색을 어떻게 구현 했습니까? 코드가 올바른 것처럼 보입니다. 나는 그것을 테스트 : 의미, '푸틴 vdimir'

public static void main(String[] args) { 
    HashSet<String> words = new HashSet<String>(); 
    words.add("vdimir putin"); 
    LevenshteinTrie lt = new LevenshteinTrie(2, words); 
    Set<String> friends = lt.discoverFriends("vladimir putin", false); 
    System.out.println(friends.iterator().next()); 
} 

이 인쇄 "블라디미르 푸틴은"너무 최소의 요소를 정상화해야하는 경우 것 같아요, Levenshtein 거리 2

Answer 2

오와 친구가 있습니다

if(normalized) { 
    tempCurrentRow = (int)(currentRow[size - 1]/(Math.log10(word.size()))); 
    minimumElement = (int)(minimumElement/(Math.log10(word.size()))); 
} 

그리고이 대체 :이와

if(normalized) { 
    minimumElement = (int)(currentRow[i]/(Math.log10(word.size()))); 
} else { 
    minimumElement = currentRow[i]; 
} 

을 :

minimumElement = currentRow[i]; 

이 작은 변경 사항을 적용하면 원하는대로 작동합니다. 지금 내가 일 때 'vdmir putin'을 검색하고 최대 거리가 1 인 경우 그는 정확히 에서 'vladimir putin'을 (를) 찾습니다.