Содержание
- 2. Вычисление длины МПД: L(0, j) = 0; L(i, 0) = 0; 0 ≤ i ≤ m;
- 3. Алгоритм Хишберга (Hirschberg D.S.) – линейная память Пусть L*(i, j) – длина МДП текстов А[i +
- 4. Адаптивные алгоритмы вычисления длины МПД: Hunt - Shimanski Qi k – наим. j, такое что (L(A[1
- 5. Адаптивные алгоритмы вычисления длины МПД: Nakatsu-Kambayashi-Yajima Ri k – max j, такое что (L(A[i : m],
- 6. Близкие задачи: задача о наикратчайшей надпоследовательности задача о медиане (string merging): построение текста Т3, сумма переходов
- 7. Расстояния и меры сходства, отличные от ред. расстояния Пусть T1 и T2 два текста. Назовем совместной
- 8. Мера сходства, учитывающая частоты встречаемости l-грамм: где α – произвольная цепочка текстов T1 и (или) T2,
- 9. Ранговые меры близости. Коэффициент корреляции τ Пусть l-граммы в Φ l(T1) и Φ l(T2) упорядочены по
- 10. Ранговые меры близости. Коэффициент корреляции τ
- 11. Ранговые меры близости. Коэффициент Спирмэна Пусть l-граммы в Φ l(T1) и Φ l(T2) упорядочены по убыванию
- 12. Ранговые меры близости. Коэффициент Спирмэна
- 13. Ранговые меры близости. Коэффициент конкордации W W используется для сравнения m последовательностей. Вычисляем суммы рангов каждого
- 14. Обобщение подхода Лемпеля-Зива Представление S1 в виде конкатенации фрагментов из S2 назовем сложностным разложением S1 по
- 15. Относительная сложность и редакционное расстояние S2 = aaaa a cccc c ttttttttttttt – acacacac a atatatat
- 16. Трансформационное расстояние Трансформационое расстояние и относительная сложность идейно близки. Операция «вставка сегмента» используется, если посимвольная генерация
- 17. Инверсионное расстояние Инверсионное расстояние dI(π,σ) между последовательностями π и σ определяется минимальным числом инверсий, переводящих одну
- 18. Точки разрыва π0 = 0 and πN+1 = N + 1 π and σ − произвольные
- 20. Скачать презентацию