🗊Презентация Суффиксные деревья (СД)

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Суффиксные деревья (СД), слайд №1Суффиксные деревья (СД), слайд №2Суффиксные деревья (СД), слайд №3Суффиксные деревья (СД), слайд №4Суффиксные деревья (СД), слайд №5Суффиксные деревья (СД), слайд №6Суффиксные деревья (СД), слайд №7Суффиксные деревья (СД), слайд №8Суффиксные деревья (СД), слайд №9Суффиксные деревья (СД), слайд №10Суффиксные деревья (СД), слайд №11Суффиксные деревья (СД), слайд №12Суффиксные деревья (СД), слайд №13Суффиксные деревья (СД), слайд №14Суффиксные деревья (СД), слайд №15Суффиксные деревья (СД), слайд №16Суффиксные деревья (СД), слайд №17Суффиксные деревья (СД), слайд №18Суффиксные деревья (СД), слайд №19Суффиксные деревья (СД), слайд №20Суффиксные деревья (СД), слайд №21Суффиксные деревья (СД), слайд №22Суффиксные деревья (СД), слайд №23Суффиксные деревья (СД), слайд №24Суффиксные деревья (СД), слайд №25Суффиксные деревья (СД), слайд №26Суффиксные деревья (СД), слайд №27Суффиксные деревья (СД), слайд №28Суффиксные деревья (СД), слайд №29Суффиксные деревья (СД), слайд №30Суффиксные деревья (СД), слайд №31Суффиксные деревья (СД), слайд №32Суффиксные деревья (СД), слайд №33Суффиксные деревья (СД), слайд №34Суффиксные деревья (СД), слайд №35Суффиксные деревья (СД), слайд №36Суффиксные деревья (СД), слайд №37Суффиксные деревья (СД), слайд №38Суффиксные деревья (СД), слайд №39Суффиксные деревья (СД), слайд №40Суффиксные деревья (СД), слайд №41Суффиксные деревья (СД), слайд №42Суффиксные деревья (СД), слайд №43
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Суффиксные деревья (СД). Доклад-сообщение содержит 43 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Суффиксные деревья(СД)
Описание слайда:
Суффиксные деревья(СД)

Слайд 2


Определение СД Суффиксное дерево Т для произвольной строки из m смволов – это ориентированное дерево с корнем, имеющим ровно m листьев, пронумерованных от 1 до m. Каждая внутренняя вершина, отличная от корня, имеет не менее 2 детей, и каждая дуга помечена непустой подстрокой строки S(дуговой меткой). Никакие 2 дуги, выходящие из одной вершины, не могут иметь пометки, начинающиеся с одного и того же символа.
Описание слайда:
Определение СД Суффиксное дерево Т для произвольной строки из m смволов – это ориентированное дерево с корнем, имеющим ровно m листьев, пронумерованных от 1 до m. Каждая внутренняя вершина, отличная от корня, имеет не менее 2 детей, и каждая дуга помечена непустой подстрокой строки S(дуговой меткой). Никакие 2 дуги, выходящие из одной вершины, не могут иметь пометки, начинающиеся с одного и того же символа.

Слайд 3


Суффиксные деревья. Примечание Для каждого листа I конкатенация дуговых меток пройденных от корня до листа I дуг, т.е. суффикс строки S[i..m].
Описание слайда:
Суффиксные деревья. Примечание Для каждого листа I конкатенация дуговых меток пройденных от корня до листа I дуг, т.е. суффикс строки S[i..m].

Слайд 4


Пример СД Строка xabxac
Описание слайда:
Пример СД Строка xabxac

Слайд 5


Определения
Описание слайда:
Определения

Слайд 6


Определения Строка ха на 4 слайде помечает внутреннюю вершину , , строка а помечает вершину u, а строка xabx помечает путь, который заканчивается внутри дуги ( ,1), ведущей к листу 1
Описание слайда:
Определения Строка ха на 4 слайде помечает внутреннюю вершину , , строка а помечает вершину u, а строка xabx помечает путь, который заканчивается внутри дуги ( ,1), ведущей к листу 1

Слайд 7


Использование СД для задачи о точных совпадениях Заданы образец Р длины n, и текст Т длины m.Найти все вхождения Р в Т за время O(n+m). Строим СД для текста Т за время O(m). Ищем путь совпадения для Р. Если такого пути нет, нет вхождения. Если есть, каждый лист в поддереве, корнем которого является вершина окончания поиска, задает номер начальной позиции положения Р в Т.
Описание слайда:
Использование СД для задачи о точных совпадениях Заданы образец Р длины 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 ).
Описание слайда:
Наивный алгоритм построения суффиксного дерева В дерево включаем простую дугу 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$
Описание слайда:
СД строки xabxa$

Слайд 12


Неявное суффиксное дерево строки xabxa.
Описание слайда:
Неявное суффиксное дерево строки xabxa.

Слайд 13


Алгоритм Укконена.
Описание слайда:
Алгоритм Укконена.

Слайд 14


Правила продолжения суффиксов Правило 1. В текущем дереве путь β заканчивается в листе. При изменении дерева надо добавить к концу метки этой листовой дуги S[i+1]. Правило 2. Ни один путь из конца строки β не начинается символом S[i+1], но по крайней мере 1 путь оттуда существует. Правило 3. Некоторый путь из конца строки β начинается символом S[i+1], тогда строка βS[i+1]уже существует в текущем дереве. Ничего не делать.
Описание слайда:
Правила продолжения суффиксов Правило 1. В текущем дереве путь β заканчивается в листе. При изменении дерева надо добавить к концу метки этой листовой дуги S[i+1]. Правило 2. Ни один путь из конца строки β не начинается символом S[i+1], но по крайней мере 1 путь оттуда существует. Правило 3. Некоторый путь из конца строки β начинается символом S[i+1], тогда строка βS[i+1]уже существует в текущем дереве. Ничего не делать.

Слайд 15


Неявное суффиксное дерево строки аxabx до добавления 6 символа b
Описание слайда:
Неявное суффиксное дерево строки аxabx до добавления 6 символа b

Слайд 16


Расширенное неявное суффиксное дерево строки аxabx после добавления b
Описание слайда:
Расширенное неявное суффиксное дерево строки аxabx после добавления b

Слайд 17


Реализация и ускорение Важно в реализации алгоритма Укконена определить концы всех суффиксов S[1..i]. При наивном подходе конец любого суффикса находится за время, порядка его длины. Т[i+1] создается из T[i] за О(i*i), а T[m] – за O(m*m*m). Уменьшим время до O(m).
Описание слайда:
Реализация и ускорение Важно в реализации алгоритма Укконена определить концы всех суффиксов 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)).
Описание слайда:
Суффиксные связи Первое ускорение реализации Определение. Пусть ха –произвольная строка. Х-первый символ, а - оставшаяся подстрока(м.б. пустой). Если для внутренней вершины v с путевой меткой ха существует другая вершина s(v) c путевой меткой а, то указатель из v в s(v) называется суффиксной связью. Иногда суффиксная связь из v в s(v) обозначается парой (v,s(v)).

Слайд 19


Пример суффиксной связи из v в s(v)
Описание слайда:
Пример суффиксной связи из v в s(v)

Слайд 20


Следствия Следствие 1. В алгоритме Укконена любая вновь созданная внутренняя вершина будет иметь суффиксную связь с концом следующего предложения. Следствие 2. В любом неявном суффиксно дереве T[i] , если внутренняя вершина v имеет путевую метку xa, то найдется вершина s(v) дерева T[i] с путевой меткой а
Описание слайда:
Следствия Следствие 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. Суффиксные связи сокращают движение по пути и каждое продолжение.
Описание слайда:
Переходы по суффиксным связям при построении Т[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] =ав текущем дереве.
Описание слайда:
Переходы по суффиксным связям при построении Т[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) вниз по пути с меткой ϒ. Конец пути – конец а.
Описание слайда:
Переходы по суффиксным связям при построении Т[i+1](прод2) Второе продолжение. Пусть ϒ- дуговая метка дуги (v,1). Для нахождения конца а, надо пройти вверх от листа 1 до v, затем по суффиксной связи из v в s(v), затем от s(v) вниз по пути с меткой ϒ. Конец пути – конец а.

Слайд 24


Пример второго продолжения(в конце пути а дерево изм. по правилам продолжения суффикса)
Описание слайда:
Пример второго продолжения(в конце пути а дерево изм. по правилам продолжения суффикса)

Слайд 25


Переходы по суффиксным связям при построении Т[i+1] Различия между первыми двумя продолжениями и продолжением при j>2. В общем случае конец S[j-1..i] мб в вершине, из которой выходит уже суффиксная связь. Алгоритм проходит эту суффиксную связь. Теоретически доказано, что в продолжении j алгоритм никогда не поднимается выше, чем на одну дугу.
Описание слайда:
Переходы по суффиксным связям при построении Т[i+1] Различия между первыми двумя продолжениями и продолжением при j>2. В общем случае конец S[j-1..i] мб в вершине, из которой выходит уже суффиксная связь. Алгоритм проходит эту суффиксную связь. Теоретически доказано, что в продолжении j алгоритм никогда не поднимается выше, чем на одну дугу.

Слайд 26


Алгоритм отдельного продолжения(SEA). Продолжение j>=2 фазы i+1
Описание слайда:
Алгоритм отдельного продолжения(SEA). Продолжение j>=2 фазы i+1

Слайд 27


Алгоритм отдельного продолжения(SEA). Продолжение j>=2 фазы i+1(1)
Описание слайда:
Алгоритм отдельного продолжения(SEA). Продолжение j>=2 фазы i+1(1)

Слайд 28


Замечание Результат: Улучшение за счет сокращения перемещений от корня в каждом продолжении. Для улучшения оценки до O(m*m) введем прием, который будет использоваться при построении и использовании суффиксных деревьев.
Описание слайда:
Замечание Результат: Улучшение за счет сокращения перемещений от корня в каждом продолжении. Для улучшения оценки до O(m*m) введем прием, который будет использоваться при построении и использовании суффиксных деревьев.

Слайд 29


Прием №1 – скачок по счетчику На шаге 2 продолжения j+1 алгоритм идет вниз из вершины s(v) по пути с меткой ϒ. При буквальной реализации прохождение по ϒ имеет сложность, пропорциональную ее длине. При использовании скачка по счетчику временная сложность уменьшается до числа вершин пути. Временная сложность не превзойдет О(m).
Описание слайда:
Прием №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)завершился на этой дуге.
Описание слайда:
Прием №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 вершины.
Описание слайда:
Пример Прием - скачок по счетчику. В фазе i+1 подстрока γ имеет длину 10. Из вершины s(v) выходит копия подстроки γ. Ее конец найден в 3 символах по последней дуге, после того, как алгоритм проскочил 4 вершины.

Слайд 32


Пример
Описание слайда:
Пример

Слайд 33


Лемма о суффиксной связи Определение. Вершинная глубина вершины – число вершин на пути от нее до корня. Лемма 2.Пусть (v,s(v)) – суффиксная связь, проходимая в алгоритме Укконена. В этот момент вершинная глубина v не более чем на единицу превосходит вершинную глубину s(v)).
Описание слайда:
Лемма о суффиксной связи Определение. Вершинная глубина вершины – число вершин на пути от нее до корня. Лемма 2.Пусть (v,s(v)) – суффиксная связь, проходимая в алгоритме Укконена. В этот момент вершинная глубина v не более чем на единицу превосходит вершинную глубину s(v)).

Слайд 34


Соотношение верш глубин:вершина с меткой xab имеет глубину 2, глубина аb равна 1. Глубина вершины с меткой xabcdefg равна 4, а вершины abcdefg -5.
Описание слайда:
Соотношение верш глубин:вершина с меткой xab имеет глубину 2, глубина аb равна 1. Глубина вершины с меткой xabcdefg равна 4, а вершины abcdefg -5.

Слайд 35


Алгоритм Укконена. Теорема. При использовании скачков по счетчику любая фаза алгоритма Укконена занимает время O(m). Всего m фаз. Поэтому справедливо следствие: Суффиксные связи в алгоритме Укконена обеспечивают время работы O(m*m).
Описание слайда:
Алгоритм Укконена. Теорема. При использовании скачков по счетчику любая фаза алгоритма Укконена занимает время O(m). Всего m фаз. Поэтому справедливо следствие: Суффиксные связи в алгоритме Укконена обеспечивают время работы O(m*m).

Слайд 36


Простая деталь реализации. Сжатие дуговых меток Вместо явной записи подстроки записываем индексную пару: начальная позиция, конечная позиция подстроки в S. Пусть S=abcdefabcuvw Деревья представлены на следующем слайде
Описание слайда:
Простая деталь реализации. Сжатие дуговых меток Вместо явной записи подстроки записываем индексную пару: начальная позиция, конечная позиция подстроки в S. Пусть S=abcdefabcuvw Деревья представлены на следующем слайде

Слайд 37


Деревья с явно заданными дуговыми метками(слева) и сжатыми дуговыми метками(справа)
Описание слайда:
Деревья с явно заданными дуговыми метками(слева) и сжатыми дуговыми метками(справа)

Слайд 38


Дополнительные приемы реализации Замечание 1. В любой фазе- если правило продолжения 3 применяется в продолжении j, оно будет применяться во всех следующих продолжениях (от j+1 до i+1) до конца фазы. Прием 2. Заканчивать каждую i+1 после первого использования продолжения 3. Если это произошло в продолжении j, нет необходимости нахождения концов строк S[k..i] с k>j.
Описание слайда:
Дополнительные приемы реализации Замечание 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.
Описание слайда:
Дополнительные приемы реализации Замечание 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 реализуется:
Описание слайда:
Дополнение При использовании приемов 2 и 3 явные продолжения в фазе i+1( применяющие алгоритм SEA) требуются только от продолжения ji +1 до первого продолжения, использующего правило 3( или до продолжения i+1). Все другие продолжения выполняются неявно. Т.е. фаза i+1 реализуется:

Слайд 41


Фаза i+1
Описание слайда:
Фаза i+1

Слайд 42


Теорема 2 Используя суффиксные связи и реализацию приемов 1, 2, 3, алгоритм Укконена строит неявные суффиксные деревья от Т1 до Тm за полное время О(m).
Описание слайда:
Теорема 2 Используя суффиксные связи и реализацию приемов 1, 2, 3, алгоритм Укконена строит неявные суффиксные деревья от Т1 до Тm за полное время О(m).

Слайд 43


Создание настоящего суффиксного дерева Теорема 3. Алгоритм Укконена строит настоящее суффиксное дерево для S и все его суффиксные связи за время O(m). Окончательное неявное дерево Tm можно преобразовать в истинное суффиксное дерево за время O(m). Для этого к S добавляется терминальный символ $ и выполняется шаг алгоритма Укконена с этим символом.
Описание слайда:
Создание настоящего суффиксного дерева Теорема 3. Алгоритм Укконена строит настоящее суффиксное дерево для S и все его суффиксные связи за время O(m). Окончательное неявное дерево Tm можно преобразовать в истинное суффиксное дерево за время O(m). Для этого к S добавляется терминальный символ $ и выполняется шаг алгоритма Укконена с этим символом.

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию