RUS  ENG
Полная версия
ЖУРНАЛЫ // Программные системы: теория и приложения // Архив

Программные системы: теория и приложения, 2016, том 7, выпуск 4, страницы 347–358 (Mi ps229)

Математические основы программирования

Приближение длины наибольшей общей подпоследовательности пары случайных строк

С. В. Знаменский

Институт программных систем им. А. К. Айламазяна РАН

Аннотация: Математическое ожидание $E$ длины длиннейшей общей подпоследовательности букв двух случайных слов рассматривается как функция от длин $m$ и $n$ этих слов и мощности алфавита $\alpha=|A|$. При этом предполагается, что любая буква независимо и с равной вероятностью оказывается в любой позиции слова.
Указан вид приближённой формулы для $E (m,n,\alpha)$, позволяющий вычислять $E (m,n,\alpha)$ с погрешностью в $0.3$ процента для $64\leqslant m+n\leqslant 65536$ и $1<\alpha<129$. Коэффициенты подобраны вручную и могут быть уточнены. Ожидается, что формула справедлива для всех больших значений аргументов с той же относительной погрешностью.

Ключевые слова и фразы: сходство строк, выравнивание последовательностей, случайные общие подпоследовательности, LCS, метрика Левенштейна.

УДК: 004.416

MSC: 68T37; 68P10, 68W32

Поступила в редакцию: 24.11.2016
Подписана в печать : 28.12.2016



© МИАН, 2024