ОБНОВЛЕНИЕ 3
Сделанный. Ниже приведен код, который, наконец, прошел все мои тесты. Опять же, это смоделировано на основе модифицированной версии алгоритма Стива Ханова Мурило Васконсело. Спасибо всем, что помогло!
/**
* 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
Наконец, мне удалось заставить это работать для большинства моих тестовых случаев. Моя реализация - это практически прямой перевод с Версия Мурило для C ++ алгоритма Стива Ханова . Итак, как мне провести рефакторинг этого алгоритма и / или провести оптимизацию? Ниже приведен код ...
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);
}
}
}
Спасибо всем, кто внес свой вклад в этот вопрос. Я пытался заставить работать Автоматы Левенштейна, но у меня ничего не получалось.
Поэтому я ищу предложения по рефакторингу и / или оптимизации приведенного выше кода. Пожалуйста, дайте мне знать, если возникнет какая-то путаница. Как всегда, я могу предоставить остальной исходный код по мере необходимости.
ОБНОВЛЕНИЕ 1
Итак, я реализовал простую структуру данных Trie и пытался следовать руководству Стива Ханова по питону, чтобы вычислить расстояние Левенштейна. На самом деле, меня интересует вычисление минимального расстояния Левенштейна между заданным словом и словами в Trie, поэтому я следил за Версия алгоритма Стива Ханова Мурило Васконселос < / а>. Это не очень хорошо работает, но вот мой класс 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;
}
}
Теперь я попытался реализовать поиск как Мурило Васконселос есть, но что-то не так, и мне нужна помощь в его отладке. Пожалуйста, дайте предложения по рефакторингу этого и / или укажите, где находятся ошибки. Самое первое, что я хотел бы отрефакторить, - это глобальная переменная 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);
}
}
}
Прошу прощения за отсутствие комментариев. Так что я делаю не так?
НАЧАЛЬНАЯ ПОЧТА
Я читал статью Быстрое и легкое расстояние Левенштейна с использованием Trie в надежде найти эффективный способ вычисления расстояния Левенштейна между двумя строками. Моя главная цель - с учетом большого набора слов найти минимальное расстояние Левенштейна между входным словом (ями) и этим набором слов.
В моей тривиальной реализации я вычисляю расстояние Левенштейна между входным словом и набором слов для каждого входного слова и возвращаю минимум. Работает, но неэффективно ...
Я искал реализации Trie на Java и наткнулся на два, казалось бы, хороших источника:
- версия Koders.com
- версия code.google.com (РЕДАКТИРОВАТЬ: похоже, это перемещено в github.com/rkapsi)
Однако эти реализации кажутся слишком сложными для того, что я пытаюсь сделать. Когда я читал их, чтобы понять, как они работают и как в целом работают структуры данных Trie, я только больше запутался.
Итак, как мне реализовать простую структуру данных Trie в Java? Моя интуиция подсказывает мне, что каждый TrieNode должен хранить строку, которую он представляет, а также ссылки на буквы алфавита, не обязательно на все буквы. Моя интуиция верна?
Как только это будет реализовано, следующая задача - вычислить расстояние Левенштейна. Я прочитал пример кода Python в статье выше, но я не говорю на Python, и моя реализация Java исчерпывает память кучи, как только я нажимаю на рекурсивный поиск. Итак, как мне вычислить расстояние Левенштейна, используя структуру данных Trie? У меня есть тривиальная реализация, смоделированная на основе этого исходного кода, но он не использует Trie ... это неэффективно.
Было бы здорово увидеть код в дополнение к вашим комментариям и предложениям. В конце концов, для меня это процесс обучения ... Я никогда не реализовывал Trie ... так что мне есть чему поучиться на этом опыте.
Спасибо.
p.s. При необходимости могу предоставить любой исходный код. Кроме того, я уже прочитал и попытался использовать BK-Tree, как предлагается в Блог Ника Джонсона, но он не так эффективен, как я думаю ... или, может быть, моя реализация неверна.
if (currentRow[size - 1] < minCost && !node.isWord) {эта строка неверна. Вы можете обновитьminCost, только если есть слово, заканчивающееся на этом узле, поэтому правильным являетсяif (currentRow[size - 1] < minCost && node.isWord) {- person Murilo Vasconcelos schedule 02.02.2011StackOverflowError, я полагаю, из-за слишком большой рекурсии. В вашей версии C ++ у вас есть _2 _... что именно означает вторая часть этого? Что из себя представляет? - person Hristo schedule 02.02.2011tree->word == ""означает, что в этом узле нет конца слова. Поэтому, если текущая стоимость меньшеmin_costи одно или несколько слов заканчиваются на этом узле, мы должны обновитьmin_cost, указав текущую стоимость. - person Murilo Vasconcelos schedule 03.02.2011StackOverflowErrorможет быть потому, что у вас очень большие слова. Вы знаете, какова максимальная длина ваших слов? Кроме того, вы можете попробовать запустить мой код с вашими данными и посмотреть, произойдет ли такая же ошибка. - person Murilo Vasconcelos schedule 03.02.2011StackOverflowErrorне из-за рекурсии ... Максимальная глубина рекурсии - 15, что мало. - person Murilo Vasconcelos schedule 04.02.2011