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