|
Программные системы: теория и приложения, 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, метрика Левенштейна.
Полный текст:
PDF файл (1547 kB)
Список литературы:
PDF файл
HTML файл
Тип публикации:
Статья
УДК:
004.416
MSC: 68T37; 68P10, 68W32 Поступила в редакцию: 24.11.2016 Подписана в печать : 28.12.2016
Образец цитирования:
С. В. Знаменский, “Приближение длины наибольшей общей подпоследовательности пары случайных строк”, Программные системы: теория и приложения, 7:4 (2016), 347–358
Цитирование в формате AMSBIB
\RBibitem{Zna16}
\by С.~В.~Знаменский
\paper Приближение длины наибольшей общей подпоследовательности пары случайных строк
\jour Программные системы: теория и приложения
\yr 2016
\vol 7
\issue 4
\pages 347--358
\mathnet{http://mi.mathnet.ru/ps229}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/ps229 http://mi.mathnet.ru/rus/ps/v7/i4/p347
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
|
Просмотров: |
Эта страница: | 123 | Полный текст: | 36 | Литература: | 14 |
|