🗊Презентация Суффиксные массивы

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Суффиксные массивы, слайд №1Суффиксные массивы, слайд №2Суффиксные массивы, слайд №3Суффиксные массивы, слайд №4Суффиксные массивы, слайд №5Суффиксные массивы, слайд №6Суффиксные массивы, слайд №7Суффиксные массивы, слайд №8Суффиксные массивы, слайд №9Суффиксные массивы, слайд №10Суффиксные массивы, слайд №11Суффиксные массивы, слайд №12Суффиксные массивы, слайд №13
Скачать
Вы можете ознакомиться и скачать презентацию на тему Суффиксные массивы. Доклад-сообщение содержит 13 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


Суффиксные массивы
Описание слайда:
Суффиксные массивы

Слайд 2


Суффиксные массивы Пусть задан текст T длины m. Нужно так подготовить текст T, чтобы за минимальное время находить вхождения образца Pдлины n в текст T
Описание слайда:
Суффиксные массивы Пусть задан текст T длины m. Нужно так подготовить текст T, чтобы за минимальное время находить вхождения образца Pдлины n в текст T

Слайд 3


Суффиксные массивы . В 1993 году Манбер (Manber U.) и Майерс (Myers G.) предложили для решения задачи о подстроке структуру, названную суффиксным массивом, которая достаточно рационально использует память и работает почти так же быстро, как суффиксные деревья(O(n) )
Описание слайда:
Суффиксные массивы . В 1993 году Манбер (Manber U.) и Майерс (Myers G.) предложили для решения задачи о подстроке структуру, названную суффиксным массивом, которая достаточно рационально использует память и работает почти так же быстро, как суффиксные деревья(O(n) )

Слайд 4


Суффиксные массивы. Пусть задана m-символьная строка T.  Суффиксным массивом для T, обозначенным Pos, называется массив целых чисел от 1 до m, определяющих лексикографический порядок всех m суффиксов строки T.
Описание слайда:
Суффиксные массивы. Пусть задана m-символьная строка T.  Суффиксным массивом для T, обозначенным Pos, называется массив целых чисел от 1 до m, определяющих лексикографический порядок всех m суффиксов строки T.

Слайд 5


Пример суффиксов и суффиксного массива для строки «абракадабра».
Описание слайда:
Пример суффиксов и суффиксного массива для строки «абракадабра».

Слайд 6


Суффиксный массив Суффиксный массиве Pos не занимает много памяти. Огромный плюс суффиксных массивов — их размер в памяти определяется только размерами текста T и никак не зависит от его алфавита. Суффиксный массив можно использовать для поиска всех вхождений в T образца P заO(n+log2m).
Описание слайда:
Суффиксный массив Суффиксный массиве Pos не занимает много памяти. Огромный плюс суффиксных массивов — их размер в памяти определяется только размерами текста T и никак не зависит от его алфавита. Суффиксный массив можно использовать для поиска всех вхождений в T образца P заO(n+log2m).

Слайд 7


Построение суффиксного массива Упорядочим суффиксы по первой букве и занесём результат в Pos.  Корзиной будем называть несколько соседних суффиксов с одинаковыми первыми буквами. Сделаем разбиение на корзины мельче, пока количество корзин не совпадёт с длиной m строки T.
Описание слайда:
Построение суффиксного массива Упорядочим суффиксы по первой букве и занесём результат в Pos.  Корзиной будем называть несколько соседних суффиксов с одинаковыми первыми буквами. Сделаем разбиение на корзины мельче, пока количество корзин не совпадёт с длиной m строки T.

Слайд 8


Построение суффиксного массива Последний суффикс (он же — последний символ строки T) перенесём на первое место в своей корзине. Далее сортируем в каждой корзине суффиксы по второму символу. Обновляем разбиение на корзины: в каждой суффиксы, совпадающие по двум символам Продолжаем процесс до получения полностью массива
Описание слайда:
Построение суффиксного массива Последний суффикс (он же — последний символ строки T) перенесём на первое место в своей корзине. Далее сортируем в каждой корзине суффиксы по второму символу. Обновляем разбиение на корзины: в каждой суффиксы, совпадающие по двум символам Продолжаем процесс до получения полностью массива

Слайд 9


Поиск образца в строке с помощью суффиксного массива Если образец P входит в строку T, то он является префиксом какого-нибудь суффикса T. . При этом все вхождения P в T, если они есть, в суффиксном массиве Pos будут находиться рядом. Пример: образец «бра» находится в строке «абракадабра» начиная со второго и с девятого символа. «бра» — префикс 2-го и 9-го суффиксов слова «абракадабра», которые в суффиксном массиве Pos находятся рядом.
Описание слайда:
Поиск образца в строке с помощью суффиксного массива Если образец P входит в строку T, то он является префиксом какого-нибудь суффикса T. . При этом все вхождения P в T, если они есть, в суффиксном массиве Pos будут находиться рядом. Пример: образец «бра» находится в строке «абракадабра» начиная со второго и с девятого символа. «бра» — префикс 2-го и 9-го суффиксов слова «абракадабра», которые в суффиксном массиве Pos находятся рядом.

Слайд 10


Поиск образца в строке с помощью суффиксного массива Вхождения P в T находим двоичным поиском в упорядоченном массиве. Проверяем Pos[m ⁄ 2]. Если суффикс Pos[m ⁄ 2] лексикографически меньше, то первая позиция, где P входит в T, должна быть в первой половине Pos. Если суффикс Pos[m ⁄ 2] лексикографически больше, чем P, то первая позиция, где P входит в T, должна быть во второй половине Pos. Далее аналогично ищем P в половине массива Pos. И так далее, пока не найдём (если такие существуют) наименьший и наибольшей индексы imin и imax такие, что образец P входит в текст T в позициях Pos[imin], Pos[imin+1], …, Pos[imax].
Описание слайда:
Поиск образца в строке с помощью суффиксного массива Вхождения P в T находим двоичным поиском в упорядоченном массиве. Проверяем Pos[m ⁄ 2]. Если суффикс Pos[m ⁄ 2] лексикографически меньше, то первая позиция, где P входит в T, должна быть в первой половине Pos. Если суффикс Pos[m ⁄ 2] лексикографически больше, чем P, то первая позиция, где P входит в T, должна быть во второй половине Pos. Далее аналогично ищем P в половине массива Pos. И так далее, пока не найдём (если такие существуют) наименьший и наибольшей индексы imin и imax такие, что образец P входит в текст T в позициях Pos[imin], Pos[imin+1], …, Pos[imax].

Слайд 11


Поиск образца в строке с помощью суффиксного массива При использовании двоичного поиска в массиве Pos все вхождения образца P в текст T могут быть найдены за время O(nlogm). Для случайных строк метод работает за ожидаемое время, но на случай, если в T есть много длинных префиксов P, метод можно улучшить
Описание слайда:
Поиск образца в строке с помощью суффиксного массива При использовании двоичного поиска в массиве Pos все вхождения образца P в текст T могут быть найдены за время O(nlogm). Для случайных строк метод работает за ожидаемое время, но на случай, если в T есть много длинных префиксов P, метод можно улучшить

Слайд 12


Поиск образца в строке с помощью суффиксного массива Простой ускоритель mlr При двоичном поиске обозначим левую и правую границы текущего интервала поиска как L и R. В начале работы поиска L = 1, R = m. На каждой итерации лексикографически сравнивается образец P с суффиксом Pos[(L+R) ⁄ 2].  
Описание слайда:
Поиск образца в строке с помощью суффиксного массива Простой ускоритель mlr При двоичном поиске обозначим левую и правую границы текущего интервала поиска как L и R. В начале работы поиска L = 1, R = m. На каждой итерации лексикографически сравнивается образец P с суффиксом Pos[(L+R) ⁄ 2].  

Слайд 13


Обозначим через l длину общего префикса Pos[L] и P, через r — длину общего префикса Pos[R] и P, а через mlr — минимум из l и r. Значение mlr приходится поддерживать при двоичном поиске. Зная значение mlr, мы можем ускорить лексикографическое сравнение P с Pos[(L+R) ⁄ 2], так как для любого числа i от L до R первые mlr символов в Pos[i] одинаковы и сравнение можно начинать не с начала, а с позиции mlr+1. Наихудшее время остаётся прежним — O(nlogm), однако Майерс и Манбер сообщают, что использование mlr дает O(n+logm).
Описание слайда:
Обозначим через l длину общего префикса Pos[L] и P, через r — длину общего префикса Pos[R] и P, а через mlr — минимум из l и r. Значение mlr приходится поддерживать при двоичном поиске. Зная значение mlr, мы можем ускорить лексикографическое сравнение P с Pos[(L+R) ⁄ 2], так как для любого числа i от L до R первые mlr символов в Pos[i] одинаковы и сравнение можно начинать не с начала, а с позиции mlr+1. Наихудшее время остаётся прежним — O(nlogm), однако Майерс и Манбер сообщают, что использование mlr дает O(n+logm).

Скачать

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