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

Question

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

Answer 1

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

Answer 2

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

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

Answer 3

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