Оптимальный метод для наилучшего совпадения Левенштейна с Map на Java

Question

У меня есть карта на Java. Я хотел бы сравнить исходную строку со всеми элементами на карте и вернуть лучшее соответствие на основе алгоритма отношения Левенштейна. Мне интересно, каким будет оптимальный способ выполнить эту проверку для каждого элемента в списке.

Спасибо, Мэтт

Answer 1

Вы не сможете добиться более высокой производительности, чем O (n), со стандартной картой - просто используйте наивный подход для их последовательного тестирования.

Однако есть гораздо более эффективные способы сделать это. Один из них называется bk-tree . По сути, вы строите дерево с n путями, ребра которого определяются расстоянием Левенштейна между узлами. Затем вы можете использовать неравенство треугольника для массового сокращения узлов, которые вы должны искать. На короткие расстояния это очень эффективно. Вот статья в блоге , которую я написал некоторое время назад, с подробным описанием. Приложив немного больше работы, вы можете запросить его для ближайшего соседа, а не повторять запросы с расстояния 1, 2 и т. Д.

Answer 2

И, конечно, если вы этого еще не сделали, используйте готовую оптимизированную реализацию Левенштейна, например, в commons-lang StringUtils.

Answer 3

Если итерации по всем элементам карты слишком дороги, вы можете рассмотреть возможность использования индексов в килограммах .

Answer 4

Поскольку коэффициент Левенштейна зависит как от источника, так и от цели, значения будут меняться для каждой строки источника. Если нет высокой вероятности повторения исходной строки при последующих поисках, просто выполните итерации по элементам карты. Если скорость действительно является проблемой, убедитесь, что вы используете новейшие компиляторы Java и используете опции оптимизации.