поиска Быстрой строки на основе метрики расстояния в Java

Question

Учитывая произвольную строка s, я хотел бы способ быстро восстановить все строки S ⊆ M из большого набора строк M (где | М |> 1 млн), где все строки S имеют минимальное расстояние редактирования < t (некоторый минимальный порог) от s.

В худшем случае S может быть пустым, если нет строки в M матче этих критерии, и в лучшем случае, S = {сек} (точное совпадение). В любом случае между ними я полностью ожидаю, что S может быть довольно большим.

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

Хотя я использовал расстояние редактирования в качестве примерной метрики, мне бы хотелось использовать другие показатели, такие как индекс Jaccard.

Может ли кто-нибудь сделать предложение о существующей реализации Java, которая может это сделать, или указать мне на правильные алгоритмы и структуры данных для решения этой проблемы?

UPDATE # 1

С тех пор я узнал, что Metric trees являются именно такой структурой я после, который использует расстояние метрическую организовать подмножество строк в М на основе их удаленности друг от друга с метрика. Как Vantage-Point, BK, так и другие аналогичные структуры и алгоритмы древовидной структуры данных кажутся идеальными для такого рода проблем. Теперь, чтобы найти простую в использовании реализации в Java ...

UPDATE # 2

Используя комбинацию этого bk-tree и это Levenshtein distance реализации, я успешно смог получить подмножество от произвольных строк из множества (M) одного миллиона строк со временем поиска около 10 мс.

Answer 1

BK trees предназначены для такого случая. Он работает с метрическим расстоянием, таким как индекс Левенштейна или Жаккарда.

Answer 2

Хотя я и не пробовал это сам, возможно, стоит посмотреть на Levenshtein Automaton. Однажды я закладка этой статьи, которая выглядит довольно разработка и предоставляет несколько фрагментов кода:

Damn Cool Algorithms: Levenshtein Automata

Как уже упоминался Н W вы не сможете избежать проверок каждое слова в словаре. Однако автомат ускорит расчет расстояния. Объедините это с эффективной структурой данных для вашего словаря (например, Trie, как указано в статье в Википедии), и вы сможете ускорить ваш текущий подход.