Я пытаюсь количественно определить разницу между двумя строками как часть системы мониторинга изменений.Быстрая приблизительная разность строк для больших строк
Проблема, которая возникает у меня, это то, что строки big - Я часто могу иметь дело со строками с символами 100K +.
В настоящее время я использую расстояние Левенштейна, но вычисление расстояния levenshtein для больших струн очень неэффективно. Даже самые лучшие реализации управляют только O(min(mn)).
Поскольку обе строки имеют примерно одинаковую длину, процесс вычисления расстояния может занять много секунд.
Мне не нужна высокая точность. Для моего приложения было бы достаточно разрешения на изменение 1 в 1000 (например, 0,1%).
Какие существуют варианты для более эффективного вычисления расстояния по струнам?
Aaaand stackoverflow не имеет mathjax. WTF? –
http://meta.stackexchange.com/questions/30559/latex-on-stack-overflow –
Интересный вопрос! Осуществляете ли вы левенштинское расстояние, создавая матрицу? Это может быть медленным. Теперь вы не указали, какой язык вы используете, но если вы создаете массив байтов каждой строки, возможно, вы можете просто перебирать их через них? Я имею в виду, что итерации по 100 КБ должны быть довольно быстрыми, если бы вы могли иметь дело с получением числа 'd' - разницы в символах. Однако я думаю, что вы не можете получить более низкую временную сложность, но вы можете получить постоянную память, если используете, например, Java, что обеспечит более быструю практическую реализацию. –