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