Алгоритм расстояния Левенштейна лучше, чем O (n * m)?

Я искал продвинутый алгоритм расстояния levenshtein и лучшее, что я нашел до сих пор, это O (n * m), где n и m - длины двух строк. Причина, по которой алгоритм находится в этом масштабе, - это пространство, а не время, с созданием матрицы двух строк, таких как:

alt text

Есть ли общедоступный алгоритм levenshtein, который лучше O (n * m)? Я не прочь взглянуть на передовые статьи в области компьютерных наук и исследований, но не смог найти что-нибудь. Я нашел одну компанию Exorbyte, которая предположительно построила супер-продвинутый и сверхбыстрый алгоритм Левенштейна, но, конечно, это коммерческая тайна. Я создаю приложение для iPhone, которое я бы хотел использовать для расчета расстояния Левенштейна. Доступна реализация objective-c, но с ограниченным объемом памяти на iPod и iPhone я хотел бы найти лучший алгоритм, если возможно.

Ответы

Ответ 1

Вы заинтересованы в сокращении временной сложности или сложности пространства? Средняя временная сложность может быть уменьшена O (n + d ^ 2), где n - длина более длинной строки, d - расстояние редактирования. Если вас интересует только расстояние редактирования и не интересует восстановление последовательности редактирования, вам нужно сохранить только две последние строки матрицы в памяти, так что это будет порядок (n).

Если вы можете позволить приблизиться, существуют полилогарифмические аппроксимации.

Для алгоритма O (n + d ^ 2) найдите оптимизацию Укконена или ее улучшение Enhanced Ukkonen. Лучшее приближение, о котором я знаю, это Andoni, Krauthgamer, Onak

Ответ 2

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

Ответ 3

Посмотрите в Wiki - у них есть некоторые идеи по улучшению этого алгоритма для лучшей сложности пространства:

Wiki-Link: расстояние Левенштейна

Цитирование:

Мы можем адаптировать алгоритм для использования меньшего пространства, O (m) вместо O (mn), так как он требует только, чтобы предыдущая строка и текущая строка сохранялись в любой момент времени.