Быстро сравнить строку с сборкой в Java

Я пытаюсь вычислить расстояния редактирования строки против коллекции, чтобы найти ближайшее совпадение. Моя текущая проблема заключается в том, что коллекция очень большая (около 25000 элементов), поэтому мне пришлось сузить набор до простых строк одинаковой длины, но это все равно ограничило бы его до нескольких тысяч строк, и это все еще очень медленно. Есть ли структура данных, которая позволяет быстро найти похожие строки или есть ли другой способ решить эту проблему?Быстро сравнить строку с сборкой в Java

источник

2012-02-04 Lezan

Как вы это делаете прямо сейчас? Можете ли вы показать код? –

Определите «похожие». –

Подобным я имею в виду сравнение слов, которые являются распространенными орфографическими ошибками, такими как «exanple» и «example» или «weird» и «wierd». – Lezan

Похоже, что BK-tree может быть тем, что вы хотите. Вот статья, обсуждающая их: http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees. A quick Google дает некоторые реализации Java.

источник

2012-02-04 08:50:22 SimonC

Спасибо, я посмотрю это и дам вам знать, как оно идет, спасибо! – Lezan

Yup, который сделал это, нужна была другая реализация поиска, но это было прекрасно! Спасибо!! – Lezan

Если ваши критерии для «похожих» определяют общий порядок, вы должны иметь возможность определить Компаратор и использовать TreeSet для поиска ближайших совпадений (например, с использованием методов потолка и пола).

источник

2012-02-04 08:42:32

Levenshtein Automata позволяют быстро выбирать набор слов из большого словаря таким образом, чтобы они находились в пределах данного расстояния Левенштейна от данного слова.

См .: Schulz K, Mihov S. (2002) Fast String Correction with Levenshtein-Automata.

источник

2012-02-04 10:32:52 kkm

Быстро сравнить строку с сборкой в ​​Java

ответ

Смежные вопросы

Быстро сравнить строку с сборкой в Java