Суффиксные деревья

Термины   20 января 2013  Автор статьи:  
geekbrains.ru/

Суффиксное дерево — это бор, который хранит все суффиксы заданной строки. Основное свойство суффиксного дерева — оно хранит все подстроки строки. Тривиальный алгоритм построения суффиксного дерева пишется за квадрат, но есть алгоритмы за линию(размер сжатого бора), так как в сжатом дереве кол — во сыновей у любой вершины либо 0 (лист), либо больше 1 (внутренняя вершина). Корень — исключение, то количество внутренних вершин не превосходит количества листьев, следовательно общее количество вершин не превосходит удвоенного количества листьев, тогда сжатый бор занимает память от количества строк в наборе.
Сжатое суффиксное дерево — это бор из n суффиксов. Линейный размер сжатого суффиксного дерева и существование линейного алгоритма позволяет для большого текста T длины N постоить индекс размера O(N) за время O(N), что позволяет отвечать на вопрос о вхождение строки длины M за время O(M).
Суффиксные деревья мощный инструмент, позволяющий решать большое количество строковых задач.

Количество различных подстрок заданной строки

Рассмотрим произвольное суффиксное дерево. Часто при построении суффиксного дерева строки в ее конец добавляется специальный символ, который нигде не встречается, чтобы каждый суффикс строки был одним из листов дерева. Очевидно, что вершина суффиксного дерева соответствует состоянию поиска подстроки в строке, следовательно любая внутренняя вершина кроме корня находится во взаимно однозначном соответствии с множеством различных непустых подстрок, следовательно количество внутренних вершин без корня равно количеству подстрок. Таким образом наивный алгоритм построения суффиксного дерева работает за квадрат от длины строки, а линейный позволяет решить эту задачу за O(N).

Научиться программировать

  • на Delphi

  • на Java

  • на C++

geekbrains.ru/
geekbrains.ru/