更新3
終わり。以下は、最終的にすべてのテストに合格したコードです。繰り返しになりますが、これはMuriloVasconceloによるSteveHanovのアルゴリズムの修正バージョンをモデルにしています。助けてくれたすべてに感謝します！
/**
* Computes the minimum Levenshtein Distance between the given word (represented as an array of Characters) and the
* words stored in theTrie. This algorithm is modeled after Steve Hanov's blog article "Fast and Easy Levenshtein
* distance using a Trie" and Murilo Vasconcelo's revised version in C++.
*
* http://stevehanov.ca/blog/index.php?id=114
* http://murilo.wordpress.com/2011/02/01/fast-and-easy-levenshtein-distance-using-a-trie-in-c/
*
* @param ArrayList<Character> word - the characters of an input word as an array representation
* @return int - the minimum Levenshtein Distance
*/
private int computeMinimumLevenshteinDistance(ArrayList<Character> word) {
theTrie.minLevDist = Integer.MAX_VALUE;
int iWordLength = word.size();
int[] currentRow = new int[iWordLength + 1];
for (int i = 0; i <= iWordLength; i++) {
currentRow[i] = i;
}
for (int i = 0; i < iWordLength; i++) {
traverseTrie(theTrie.root, word.get(i), word, currentRow);
}
return theTrie.minLevDist;
}
/**
* Recursive helper function. Traverses theTrie in search of the minimum Levenshtein Distance.
*
* @param TrieNode node - the current TrieNode
* @param char letter - the current character of the current word we're working with
* @param ArrayList<Character> word - an array representation of the current word
* @param int[] previousRow - a row in the Levenshtein Distance matrix
*/
private void traverseTrie(TrieNode node, char letter, ArrayList<Character> word, int[] previousRow) {
int size = previousRow.length;
int[] currentRow = new int[size];
currentRow[0] = previousRow[0] + 1;
int minimumElement = currentRow[0];
int insertCost, deleteCost, replaceCost;
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] = minimum(insertCost, deleteCost, replaceCost);
if (currentRow[i] < minimumElement) {
minimumElement = currentRow[i];
}
}
if (currentRow[size - 1] < theTrie.minLevDist && node.isWord) {
theTrie.minLevDist = currentRow[size - 1];
}
if (minimumElement < theTrie.minLevDist) {
for (Character c : node.children.keySet()) {
traverseTrie(node.children.get(c), c, word, currentRow);
}
}
}
更新2
最後に、ほとんどのテストケースでこれを機能させることができました。私の実装は、実際には、MuriloのC++バージョンのSteveHanovのアルゴリズムからの直接翻訳です。では、このアルゴリズムをどのようにリファクタリングしたり、最適化したりする必要がありますか？以下はコードです...
public int search(String word) {
theTrie.minLevDist = Integer.MAX_VALUE;
int size = word.length();
int[] currentRow = new int[size + 1];
for (int i = 0; i <= size; i++) {
currentRow[i] = i;
}
for (int i = 0; i < size; i++) {
char c = word.charAt(i);
if (theTrie.root.children.containsKey(c)) {
searchRec(theTrie.root.children.get(c), c, word, currentRow);
}
}
return theTrie.minLevDist;
}
private void searchRec(TrieNode node, char letter, String word, int[] previousRow) {
int size = previousRow.length;
int[] currentRow = new int[size];
currentRow[0] = previousRow[0] + 1;
int insertCost, deleteCost, replaceCost;
for (int i = 1; i < size; i++) {
insertCost = currentRow[i - 1] + 1;
deleteCost = previousRow[i] + 1;
if (word.charAt(i - 1) == letter) {
replaceCost = previousRow[i - 1];
} else {
replaceCost = previousRow[i - 1] + 1;
}
currentRow[i] = minimum(insertCost, deleteCost, replaceCost);
}
if (currentRow[size - 1] < theTrie.minLevDist && node.isWord) {
theTrie.minLevDist = currentRow[size - 1];
}
if (minElement(currentRow) < theTrie.minLevDist) {
for (Character c : node.children.keySet()) {
searchRec(node.children.get(c), c, word, currentRow);
}
}
}
この質問に貢献してくれた皆さん、ありがとうございました。Levenshtein Automataを動作させようとしましたが、実現できませんでした。
したがって、上記のコードに関するリファクタリングや最適化に関する提案を探しています。混乱があれば教えてください。いつものように、必要に応じて残りのソースコードを提供できます。
更新1
そこで、単純なTrieデータ構造を実装し、Steve HanovのPythonチュートリアルに従って、レーベンシュタイン距離を計算しようとしました。実際、私は特定の単語とTrie内の単語の間の最小レーベンシュタイン距離を計算することに興味があるので、 MuriloVasconcelosのバージョンのSteveHanovのアルゴリズムに従っています。うまく機能していませんが、これが私のTrieクラスです。
public class Trie {
public TrieNode root;
public int minLevDist;
public Trie() {
this.root = new TrieNode(' ');
}
public void insert(String word) {
int length = word.length();
TrieNode current = this.root;
if (length == 0) {
current.isWord = true;
}
for (int index = 0; index < length; index++) {
char letter = word.charAt(index);
TrieNode child = current.getChild(letter);
if (child != null) {
current = child;
} else {
current.children.put(letter, new TrieNode(letter));
current = current.getChild(letter);
}
if (index == length - 1) {
current.isWord = true;
}
}
}
}
...およびTrieNodeクラス：
public class TrieNode {
public final int ALPHABET = 26;
public char letter;
public boolean isWord;
public Map<Character, TrieNode> children;
public TrieNode(char letter) {
this.isWord = false;
this.letter = letter;
children = new HashMap<Character, TrieNode>(ALPHABET);
}
public TrieNode getChild(char letter) {
if (children != null) {
if (children.containsKey(letter)) {
return children.get(letter);
}
}
return null;
}
}
Murilo Vasconcelosが持っているように検索を実装しようとしましたが、何かがおかしいので、これをデバッグするのに助けが必要です。これをリファクタリングする方法や、バグがどこにあるかを指摘する方法について提案してください。最初にリファクタリングしたいのは「minCost」グローバル変数ですが、これは最小のものです。とにかく、ここにコードがあります...
public void search(String word) {
int size = word.length();
int[] currentRow = new int[size + 1];
for (int i = 0; i <= size; i++) {
currentRow[i] = i;
}
for (int i = 0; i < size; i++) {
char c = word.charAt(i);
if (theTrie.root.children.containsKey(c)) {
searchRec(theTrie.root.children.get(c), c, word, currentRow);
}
}
}
private void searchRec(TrieNode node, char letter, String word, int[] previousRow) {
int size = previousRow.length;
int[] currentRow = new int[size];
currentRow[0] = previousRow[0] + 1;
int replace, insertCost, deleteCost;
for (int i = 1; i < size; i++) {
char c = word.charAt(i - 1);
insertCost = currentRow[i - 1] + 1;
deleteCost = previousRow[i] + 1;
replace = (c == letter) ? previousRow[i - 1] : (previousRow[i - 1] + 1);
currentRow[i] = minimum(insertCost, deleteCost, replace);
}
if (currentRow[size - 1] < minCost && !node.isWord) {
minCost = currentRow[size - 1];
}
Integer minElement = minElement(currentRow);
if (minElement < minCost) {
for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
searchRec(node, entry.getKey(), word, currentRow);
}
}
}
コメントが不足していることをお詫び申し上げます。だから私は何が間違っているのですか？
初期投稿
2つの弦の間のレーベンシュタイン距離を計算する効率的な方法を理解することを期待して、「トライを使用した高速で簡単なレーベンシュタイン距離」という記事を読んでいます。これに関する私の主な目標は、大量の単語セットが与えられた場合に、入力単語とこの単語セットの間の最小レーベンシュタイン距離を見つけることができるようにすることです。
私の簡単な実装では、入力単語ごとに、入力単語と単語のセットの間のレーベンシュタイン距離を計算し、最小値を返します。動作しますが、効率的ではありません...
私はJavaでのTrieの実装を探していましたが、2つの一見良い情報源に出くわしました。
- Koders.comバージョン
- code.google.comバージョン （編集：これはgithub.com/rkapsiに移動したようです）
ただし、これらの実装は、私がやろうとしていることには複雑すぎるようです。それらがどのように機能し、Trieデータ構造が一般的にどのように機能するかを理解するためにそれらを読んでいると、私はさらに混乱するようになりました。
では、Javaで単純なTrieデータ構造を実装するにはどうすればよいでしょうか。私の直感によると、各TrieNodeは、それが表す文字列と、必ずしもすべての文字ではなく、アルファベットの文字への参照を格納する必要があります。私の直感は正しいですか？
それが実装されたら、次のタスクはレーベンシュタイン距離を計算することです。上記の記事のPythonコード例を読みましたが、Pythonについては話せません。再帰検索を実行すると、Java実装のヒープメモリが不足します。では、Trieデータ構造を使用してレーベンシュタイン距離をどのように計算しますか？このソースコードをモデルにした簡単な実装がありますが、Trieを使用していません...非効率的です。
あなたのコメントや提案に加えて、いくつかのコードを見るのは本当に素晴らしいことです。結局のところ、これは私にとっての学習プロセスです...私はTrieを実装したことがありません...したがって、この経験から学ぶことがたくさんあります。
ありがとう。
ps必要に応じて、任意のソースコードを提供できます。また、 Nick Johnsonのブログで提案されているようにBK-Treeを読んで使用してみましたが、思ったほど効率的ではありません...または私の実装が間違っている可能性があります。