Быстро сравните строку с коллекцией в Java

Question

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

Answer 1

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

Answer 2

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

См .: Шульц К., Михов С. (2002) Быстрая коррекция строки с помощью Левенштейна-автомата .

Answer 3

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