Содержание
- 2. Определение СД Суффиксное дерево Т для произвольной строки из m смволов – это ориентированное дерево с
- 3. Суффиксные деревья. Примечание Для каждого листа I конкатенация дуговых меток пройденных от корня до листа I
- 4. Пример СД Строка xabxac
- 5. Определения
- 6. Определения Строка ха на 4 слайде помечает внутреннюю вершину , , строка а помечает вершину u,
- 7. Использование СД для задачи о точных совпадениях Заданы образец Р длины n, и текст Т длины
- 8. Пример определения вхождения строки
- 9. Наивный алгоритм построения суффиксного дерева В дерево включаем простую дугу S$( суффикс S[1..m] $). Последовательно включаются
- 10. Неявные суффиксные деревья
- 11. СД строки xabxa$
- 12. Неявное суффиксное дерево строки xabxa.
- 13. Алгоритм Укконена.
- 14. Правила продолжения суффиксов Правило 1. В текущем дереве путь β заканчивается в листе. При изменении дерева
- 15. Неявное суффиксное дерево строки аxabx до добавления 6 символа b
- 16. Расширенное неявное суффиксное дерево строки аxabx после добавления b
- 17. Реализация и ускорение Важно в реализации алгоритма Укконена определить концы всех суффиксов S[1..i]. При наивном подходе
- 18. Суффиксные связи Первое ускорение реализации Определение. Пусть ха –произвольная строка. Х-первый символ, а - оставшаяся подстрока(м.б.
- 19. Пример суффиксной связи из v в s(v) v S(v)
- 20. Следствия Следствие 1. В алгоритме Укконена любая вновь созданная внутренняя вершина будет иметь суффиксную связь с
- 21. Переходы по суффиксным связям при построении Т[i+1] На фазе i+1 алгоритм находит место суффикса S[j..i] строки
- 22. Переходы по суффиксным связям при построении Т[i+1](прод1) Первое продолжение(j=1) фазы i+1 Конец полной строки S[1..i] в
- 23. Переходы по суффиксным связям при построении Т[i+1](прод2) Второе продолжение. Пусть ϒ- дуговая метка дуги (v,1). Для
- 24. Пример второго продолжения(в конце пути а дерево изм. по правилам продолжения суффикса)
- 25. Переходы по суффиксным связям при построении Т[i+1] Различия между первыми двумя продолжениями и продолжением при j>2.
- 26. Алгоритм отдельного продолжения(SEA). Продолжение j>=2 фазы i+1
- 27. Алгоритм отдельного продолжения(SEA). Продолжение j>=2 фазы i+1(1)
- 28. Замечание Результат: Улучшение за счет сокращения перемещений от корня в каждом продолжении. Для улучшения оценки до
- 29. Прием №1 – скачок по счетчику На шаге 2 продолжения j+1 алгоритм идет вниз из вершины
- 30. Прием №1 Пусть g –длина ϒ. Пусть g1 – число символов в дуге перехода. Если g1
- 31. Пример Прием - скачок по счетчику. В фазе i+1 подстрока γ имеет длину 10. Из вершины
- 32. Пример
- 33. Лемма о суффиксной связи Определение. Вершинная глубина вершины – число вершин на пути от нее до
- 34. Соотношение верш глубин:вершина с меткой xab имеет глубину 2, глубина аb равна 1. Глубина вершины с
- 35. Алгоритм Укконена. Теорема. При использовании скачков по счетчику любая фаза алгоритма Укконена занимает время O(m). Всего
- 36. Простая деталь реализации. Сжатие дуговых меток Вместо явной записи подстроки записываем индексную пару: начальная позиция, конечная
- 37. Деревья с явно заданными дуговыми метками(слева) и сжатыми дуговыми метками(справа)
- 38. Дополнительные приемы реализации Замечание 1. В любой фазе- если правило продолжения 3 применяется в продолжении j,
- 39. Дополнительные приемы реализации Замечание 2. Стал листом, листом и останешься. Прием 3. В фазе i+1, когда
- 40. Дополнение При использовании приемов 2 и 3 явные продолжения в фазе i+1( применяющие алгоритм SEA) требуются
- 41. Фаза i+1
- 42. Теорема 2 Используя суффиксные связи и реализацию приемов 1, 2, 3, алгоритм Укконена строит неявные суффиксные
- 44. Скачать презентацию