Approximation of the longest common subsequence length for two long random strings
Sergej Vital'evich Znamenskij · Program systems theory and applications · 2016
ЗнаменскийПриближение длины наибольшей общей подпоследовательности пары случайных строк Аннотация.Математическое ожидание 𝐸 длины длиннейшей общей подпоследовательности букв двух случайных слов рассматривается как функция от длин 𝑚 и 𝑛 этих слов и мощности алфавита 𝛼 = A. При этом предполагается, что любая буква независимо и с равной вероятностью оказывается в любой позиции слова.Указан вид приближённой формулы для 𝐸(𝑚, 𝑛, 𝛼), позволяющий вычислять 𝐸(𝑚, 𝑛, 𝛼) с погрешностью в 0.3 процента для 64 𝑚 + 𝑛 65536 и 1 < 𝛼 < 129.Коэффициенты подобраны вручную и могут быть уточнены.Ожидается, что формула справедлива для всех больших значений аргументов с той же относительной погрешностью.Ключевые слова и фразы: сходство строк, выравнивание последовательностей, случайные общие подпоследовательности, LCS, метрика Левенштейна. ВведениеДва случайных слова длин 𝑚 и 𝑛 из алфавита 𝛼 часто иначе называют случайными последовательностями символов.Будем считать появления букв в различных позициях равновероятными и независимыми событиями.Тогда математическое ожидание длины наибольшей общей подпоследовательности этих случайных последовательностей является функцией 𝐸(𝑚, 𝑛, 𝛼), характеризующей близость исходных слов.Эта функция тесно связана с эффективностью разнообразных алгоритмов нечёткого поиска и выделения различий, поэтому её поведение c 70-х годов прошлого века привлекало внимание исследователей [1], выявивших линейную асимптотику при фиксированном 𝛼 при больших равных длинах 𝑚 и 𝑛 и приближённо вычисливших коэффициенты пропорциональности