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

Question

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

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

Answer 1

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

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

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

Answer 2

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

Wiki-Link: Levenshtein distance

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

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

Answer 3

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

Answer 4

я нашел другую оптимизацию, которая утверждает, что О (макс (т, п)):

http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C

(вторая реализация С)