|
Программные системы: теория и приложения, 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, метрика Левенштейна.
Поступила в редакцию: 24.11.2016 Подписана в печать : 28.12.2016
Образец цитирования:
С. В. Знаменский, “Приближение длины наибольшей общей подпоследовательности пары случайных строк”, Программные системы: теория и приложения, 7:4 (2016), 347–358
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ps229 https://www.mathnet.ru/rus/ps/v7/i4/p347
|
|