Повышение производительности нечеткого сопоставления строк со словарем

Question

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

Когда я хочу выполнить нечеткое сопоставление строк, я сначала проверяю, находится ли строка в hashMap, а затем перебираю все остальные потенциальные ключи, вычисляя сходство строк и сохраняя пару k, v/ с с наибольшим сходством.В зависимости от того, какой словарь я использую, это может занять много времени (12330 - 1800035 записей).Есть ли способ ускорить это или сделать это быстрее?В настоящее время я пишу функцию / таблицу памятки как способ ускорить это, но может ли кто-нибудь еще придумать лучший способ улучшить скорость этого?Может быть, другая структура или что-то еще, что я скучаю.

Большое спасибо заранее,

Натан

Answer 1

Что вам нужно, так это BKTree (BK-Tree) в сочетании с алгоритмом расстояния Левенштейна. Производительность поиска в BKtree зависит от того, насколько «нечетким» является ваш поиск. Где нечеткий определяется как количество расстояний (правок) между поисковым словом и совпадениями.

Вот хороший блог на эту тему: http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees

Некоторые заметки о спектакле: http://www.kafsemo.org/2010/08/03_bk-tree-performance-notes.html

Замечания по алгоритму http://en.wikipedia.org/wiki/Levenshtein_distance.

Также здесь есть BK-дерево, написанное на Java. Должен дать вам представление об интерфейсе: http://code.google.com/p/java-bk-tree/

Answer 2

Или вы также можете использовать Java Fuzzy HashMap (расширение java hashMap, которое позволяет нечеткий поиск): http://sourceforge.net/projects/fuzzyhashmap/ Я думаю, это именно то, что вам нужно.Здесь у вас есть полное описание структуры данных: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5565628

Answer 3

см. Эту превосходную статью для объяснения и сравнения различных нечетких совпадений строк: http://ntz -develop.blogspot.com / 2011/03 / нечеткой строка-search.html

исходный код Java доступен на https://code.google.com/p/fuzzy-search-tools/