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

Question

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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

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

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

Answer 4

Я нашел другую оптимизацию, которая утверждает, что O (max (m, n)):

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

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