Главная » Java, Структуры данных и алгоритмы » Trie

0

В предыдущих разделах представлены алгоритмы, скорость поиска в которых увеличивалась за счет предварительной обработки шаблона (вычисление функции отказа в КМП-алгоритме или функции last в БМ-алго- ритме). В этом разделе рассматривается другой подход, где поисковый алгоритм сразу обрабатывает исходный текст. Этот подход применяется в приложениях, в которых к одному и тому же тексту направляется серия запросов и, следовательно, предварительная обработка текста увеличивает скорость последующих запросов (например, поиск шаблона «Гамлет» на Web-сайте или поисковая машина для нахождения страниц, имеющих заголовок «Гамлет»).

Речь идет о древовидной структуре данных для хранения строк, поддерживающей поиск по шаблону. Основная цель данной структуры — поиск необходимой информации, отсюда и ее название trie — от английского «retrieval» — поиск. Во многих поисковых приложениях (например, нахождение определенной последовательности ДНК в базе данных геномов) поиск осуществляется в наборе строк, использующих единый алфавит. Основными операциями, поддерживаемыми trie-алгоритмом, являются проверка на соответствие шаблону и соответствие префиксу. Последняя предполагает наличие строки Хи поиск в S всех строк, содержащих Хв качестве префикса.

Стандартный trie

Допустим, S — множество строк алфавита Е, при этом ни одна из строк не является префиксом другой. Стандартный trie идя S представляет собой упорядоченное дерево Тсо следующими свойствами (см. рис. 11.6):

•           каждый узел в Т\ за исключением корня, помечен символом из S;

•          порядок дочерних элементов составного узла Г определяется каноническим порядком алфавита S;

•          Т содержит $ простых узлов, причем соединение меток узлов на пути от корня до простого узла v в Т составляет строку из ассоциируемую с V.

Таким образом, строки из S соответствуют в Г маршрутам от корня до простых узлов. Повторно отметим, что ни одна строка в S не должна быть префиксом другой строки. Это гарантирует соответствие каждой строки только одному простому узлу в Т. Для большей уверенности в конце каждой строки можно добавить специальный символ, отсутствующий в S.

Составной узел стандартного trie Т может иметь от 1 до d дочерних элементов, где d — размерность алфавита. От корня к каждому дочернему Элементу, являющемуся первым символом строки в S, проведена линия. Кроме того, маршрут от корня Г до составного узла v на глубине i соответствует /-символьному префиксу X[0 … / – 1] строки ^множества S. То есть для каждого символа с, который может следовать за префиксом Л^О … /- 1] в строке множества S, существует дочерний элемент узла v, отмеченный символом с. В таком виде trie последовательно хранит префиксы, имеющиеся в наборе строк.

Если в алфавите всего два символа, то trie по существу будет бинарным деревом, хотя некоторые из составных узлов могут иметь только по одному дочернему элементу (то есть это будет неправильное бинарное дерево). В принципе если в алфавите d символов, то trie будет многопроходным деревом, в котором каждый составной узел имеет от 1 до d дочерних элементов. Кроме того, скорее всего, узлы стандартного trie будут иметь менее d дочерних элементов. Например, trie, показанный на рис. 11.6, содержит несколько составных узлов, имеющих только один дочерний элемент. Реализовано trie может быть деревом, хранящим в своих узлах символы.

Утверждение 11.2. Стандартный trie, хранящий коллекцию S из s строк общей длиной п, составленных из алфавита размером d, имеет следующие свойства:

•    каждый составной узел в Гимеет максимум d дочерних элементов;

•     Т имеет s составных узлов;

•    высота Т равна длине наибольшей строки в $\

•    количество узлов в Г есть О(п).

Максимальное количество узлов будет в случае, когда ни одна из строк не имеет общего непустого префикса; то есть, за исключением корня, все остальные Составные узлы имеют по одному дочернему элементу.

Г для множества строк Сможет использюваться для реализации словаря, ключами которого являются строки из S. То есть поиск в Тстроки ^выполняется прослеживанием Маршрута, определяемого символами X, от корня. Если такой маршрут существует и заканчивается простым узлом, то ^находится в словаре. Например, в trie на рис. 11.6 маршрут для «bull» заканчивается простым узлом. Если же маршрут нельзя-отследить или же он закончится в составном узле — Хв словаре нет. В примере на рис. 11.6 нельзя отследить маршрут «bet», а маршрут «Ье» заканчивается в составном узле. Таким образом,, ни одного из этих слов в словаре нет. Заметим, что в такой реализации словаря сопоставляются отдельные символы, а не целиком строки (ключи). Несложно оценить, что время выполнения поиска строки размером m составит 0(dm), где d — размер алфавита. То есть обращение происходит максимум к/w+l узлу в Т и тратится 0(d) временила каждый узел. Для некоторых алфавитов время

затрат на один узел можно уменьшить до 0(1) или 0(log d), пользуясь словарем символов, реализованным хеш-таблицей или поисковой таблицей. Однако, поскольку d в большинстве приложений постоянно, можно придерживаться простого подхода, при котором на обращение к узлу тратится 0(d) времени.

Из приведенного выше следует, что trie можно использовать для выполнения специального сопоставления — поиска слова по шаблону, когда требуется определить точное соответствие шаблона одному из слов в тексте (см. рис. 11.7). Поиск слова отличается от обычного шаблонного поиска, так как шаблон может соответствовать не произвольной подстроке текста, а только одному из его слов. С помощью trie поиск слова по шаблону длиной т занимает 0(dm) времени, где d — размер алфавита, независимо от размера самого текста. Если у алфавита постоянный размер (как в случае с текстом на любом из существующих языков или при работе с ДНК), запрос занимает 0(т) времени пропорционально размеру шаблона. С помощью простого расширения такой схемы можно добиться и префиксного сопоставления. Тем не менее произвольное вхождение такого (префиксного) шаблона (например, стандартного суффикса слова или союза) не всегда удается обнаружить.

При создании стандартного trie для множества строк S можно воспользоваться алгоритмом, который добавляет одну строку за раз, учитывая условие, что ни одна строка не должна быть префиксом другой строки. Для добавления строки Хв текущий trie Т вначале в Г отслеживается соответствующий Xмаршрут. Поскольку Хеще отсутствует в Ги ни одна из строк не является префиксом добавляемой строки, прослеживаемый маршрут закончится в составном узле v дерева Т. Затем создается новая цепочка потомков узла v для хранения остальных символов X. Время добавления ^составляет 0(dm), где m — длина X, a d — размер алфавита. Таким образом, создание целого trie для множества S занимает 0(dn) времени, где п — общая длина всех строк в S.

Требования к занимаемому месту стандартного trie стали причиной появления компактного trie (compressed trie), известного также как патрицианский trie (Patricia trie). То есть стандартный trie потенциально может иметь большое количество узлов с одним дочерним элементом, занимающих много излишнего места. Поэтому рассмотрим ниже компактный trie.

Компактный trie

Компактный (или сжатый) trie подобен обьдчному trie, но каждый составной узел в нем имеет минимум два дочерних элемента. Для соблюдения этого условия цепочки из однодетных узлов сжимаются в индивидуальные связки (см. рис. 11.8). Допустим, Т— стандартный trie. Ранее упоминалось, что составной узел v в Г не может иметь только один дочерний элемент и не являться при этом корнем. Например, trie на рис. 11.6 содержит 6 таких избыточных узлов. Тогда можно сказать, что цепочка из к

> 2 связок, (v0,vi)(vi,v2) … (vk-\,vk), не удовлетворяет требованиям компактного trie, если:

•                Vj избыточно для / = 1, …, к- 1;

Рис. 11.7. Поиск слова и префикса с помощью стандартного trie: (э) текст, в котором выполняется поиск; (Ь) стандартный trie для слов в тексте (артиклей и предлогов включительно) с простыми узлами, приведены отметки позиций слова

(b)

•                v0 и vk не избыточны.

(а)

Дерево Г можно трансформировать в компактный trie, представив каждую избыточную цепочку (v0,vi)(vi,v2) … ьу^) из к > 2 связок,одной связкой (vo,^), заменив v^ цепочкой узлов vj, v^.

Рис. 11.8. Компактный trie для строк {bear, bell, bid, bull, buy, sell, stock, stop}.

Сравните со стандартным trie (рис. 11.6)

Таким образом, узлы компактного trie помечаются строками, являющимися подстроками строк данного множества, а не отдельными символами. Преимущество такого компактного trie в том, что количество узлов в нем пропорционально количеству строк, а не их общей длине, как гласит следующее утверждение (сравните с утверждением 11.2).

Утверждение 11.3. Компактный trie, хранящий множество S из s строк, составленных из алфавита размером d, имеет следующие свойства:

•          каждый составной узел в Г имеет минимум два и максимум d дочерних элемента;

•     Т имеет $ составных узлов;

•    количество узлов в Г составляет 0(s).

Любознательный читатель может поинтересоваться, действительно ли сжатие маршрутов обеспечивает значительное преимущество, поскольку представляет собой всего лишь дерево, метки узловкоторого удлинились. Однако такое сжатие удобнее только при использовании в качестве вспомогательной индексной структуры для множества строк, имеющихся в первичной структуре, но не для непосредственного хранения строк.

Предположим, что множество 5 из s строк представляет собой массив строк S [0], 5,[1],…,5[5′-1]. Вместо того чтобы явно хранить метку Годного из узлов, неявно представим ее тремя целыми числами (/, j, к) так, что Х= S [/][у … к] \ то есть Сбудет подстрокой S[i], состоящей из символов оту-го по к-й включительно (рис. 11.9, сравните со стандартным trie на рис. 11.7).

Такая схема позволяет уменьшить требуемую память, занимаемую trie, со значения О(п) для стандартной версии до 0(у\?дя компактной

версии, где п — общая длина всех строк в S, a s — количество строк в S. Конечно же, в S по-прежнему должны храниться разные строки, но при этом занимаемое пространство уменьшается. В следующем разделе представим приложение, в котором множество строк тоже может сохраняться в компактном виде.

 

Рис. 11.9. (а) Множество S строк, хранящихся в массиве; (Ь) представление компактного trie для S

Суффиксный trie

Одним из основных применений trie являются случаи, когда все строки множества S являются суффиксами строки X. Такой trie называют «суффиксный trie» строки X, известный также как суффиксное дерево, или позиционное дерево. Например, на рис. 11.10, а показано суффиксное дерево для восьми суффиксов строки «minimize». Для такой строки показанное в предыдущем разделе компактное представление может быть еще более упроще^р. А именно, меткой каждой вершины будет пара (/,у), обозначающая строку X[i… j] (рис. 11.10, b). Требование — ни один из суффиксов не является префиксом другого — осуществляется добавлением специального символа, обозначаемого знаком $, отсутствующим в алфавите Z, в конец Х(и к каждому суффиксу). То есть, если строка X имеет длину п, создаем trie для множества из п строк X[i… п – 1]$ для i = 0, …, п -

Рис. 11.10. (а) Суффиксный trie Т для строки X = «minimize»; (b) компактное представление Т, где пара (i,j) обозначает X[i …j]

(b)

Преимущество такого представления суффиксного дерева теперь является очевидным. Поскольку общая длина суффиксов строки ЛГ длиной п составляет

(а)

Создание суффиксного дерева

Можно создать суффиксное дерево для строки длиной п с помощью алгоритма добавления, подобного приведенному в п. 11.3.1. Процесс создания занимает 0(dn2) времени, поскольку общая длина суффиксов равна квадрату п. Однако (компактное) суффиксное дерево для строки длиной п можно создать и за 0(п) времени с помощью специального алгоритма, отличного от применяемого в стандартном trie. Этот линейно-временной алгоритм сравнительно сложен и здесь не приводится. Но все же можно воспользоваться таким методом, когда потребуется создать суффиксное дерево для решения других задач.

Применение суффиксного дерева

Суффиксное дерево Г для строки Сможет использоваться для эффективного выполнения поисковых запросов в тексте X. А именно, можно определить, является ли шаблон Р подстрокой X, прослеживая в Т маршрут, ассоциируемый с Р. Шаблон Р будет подстрокой X, если такой мар- щрут можно проследить. Подробности поискового шаблонного алгоритма приводятся во фрагменте кода 11.7, который предполагает наличие следующего дополнительного свойства для меток узлов в компактном представлении суффиксного дерева:

• если узел v имеет метку (i,j) и Y— строка длиной у, ассоциируемая с маршрутом от корня до v (включительно), то X\j —у + 1 …у] = Y.

Это свойство обеспечивает возможность простого вычисления индекса начала шаблона в тексте при обнаружении совпадения.

Алгоритм suffixMatch( Т,Р)\

Input: компактное суффиксное дерево Т для текста Хи шаблона Р.

Output: индекс начала подстроки X, совпадающей с Р, или признак того, что Р не является подстрокой X.

р <- P. Iength() { длина суффикса, задаваемого шаблоном } у <- 0 { начало суффикса, задаваемого шаблоном } v <- T.root() repeat

J true { флаг указывает, что ни один из дочерних элементов

не обработан } for each child w of v do / <- start (v) if P[j] = T[i] then

{ обработан дочерний узел w } х <- end(w) – / +1

if p < x then                                                       <

{ суффикс короче или равен длине имени узла } If P[j..j + р - 1] =X[U + р - 1] then

return / – / { совпадение } else

return "P is not a substring of X"

else

{ суффикс длиннее имени узла.} If P\j..j + x – 1] = X[/../ + x – 1] then

p <- p – x { уточнить длину суффикса } у <- j + х { уточнить индекс начала суффикса } v <- w f <- false

break out of th? for loop until f or TisExternal(v) return "P is not a substring of X"

Фрагмент кода 11.7. Поиск по шаблону с помощью суффиксного дерева. Метка узла v обозначена ((start(v),end(v)), то[23]есть парой индексов, определяющих подстроку текста, ассоциируемую с v

Правильность работы алгоритма suffixMatch проистекает из того, что поиск в дереве Г выполняется сопоставлением одного за другим символов с шаблоном Рдо тех пор, пока не произойдет одно из трех событий:

•       обнаружено точное соответствие Шаблону Р\

•       обнаружено неточное соответствие;

•       обработан простой узел и соответствие не обнаружено.

. Пусть т — размер шаблона Р, a d — размер алфавита. Чтобы определить время выполнения алгоритма suffixMatch:

Производительность

Из вышесказанного можно сделать вывод, что алгоритм suffixMatch выполняет запрос на поиск по шаблону за O(dm) времени (и даже быстрее при использовании словаря для индексации дочерних элементов узлов в суффиксном дереве). Заметим, что время выполнения не зависит от размера самого текста X. К тому же оно линейно по отношению к размеру шаблона, то есть составит 0(т) для алфавита с постоянным размером. Следовательно, суффиксное дерево весьма подходит для приложений, в которых применяются повторяющиеся поисковые запросы и выполняется серия сопоставлений шаблона с одним и тем же текстом.

Утверждение 11.5. Пусть Сбудет текстовой строкой из п символов, содержащихся в алфавите размером d. Поисковые запросы к ^выполняются за O(dm) времени, где т — длина шаблона, с помощью суффиксного дерева X, занимающего О(п) места и создающегося за O(dn) времени.

Поисковые системы

Глобальная Сеть (World Wide Web) хранит в себе огромное множество текстовых документов (Web-страниц). Информацию об этих страницах можно получить с помощью поисковых систем (Web-crawler), которые отыскивают информацию и наполняют специальную словарную базу данных. Поисковая система позволяет пользователям получать необходимую информацию, содержащую конкретные ключевые слова. В этом разделе покажем упрощенную модель такой поисковой системы.

Инвертированные файлы

Основная информация, обеспечивающая работу поисковой системы, представлена словарем, называемым инвертированным индексом (inverted index), или инвертированным файлом (inverted file) для хранения пар «ключ-значение» (w,L), где w — слово, a L — подборка страниц, содержащих это слово. Ключи (слова) в словаре называются индексными термами (index term) и являются достаточно обширными группами словарных статей и правильных существительных. Элементы такого словаря называются списками появлений (occurrence list), которые должны покрывать по возможности наибольшее количество Web-страниц.

Реализовать инвертированный индекс можно с помощью структуры данных, состоящей:

Необходимость хранения списков появлений вне trie исходит из требования обеспечения небольшого размера дерева, чтобы размещать trie в основной памяти. В свокУ очередь, Ьписки Появлений из-за своих размеров должны храниться на диске[24].    1 ‘         ‘

При работе с такой структурой данных запрос для одного ключевого слова будет выглядеть так же, как запрос на поиск слова в тексте (см. п. 11.3.1), то есть находим это ключевое слово в дереве и возвращаем ассоциируемый с ним список появлений.

Если требуется сразу несколько ключевых слов, получим все страницы с ними, с помощью trie извлекаем списки появлений каждого из слов и возвращаем пересечение этих списков. Для упрощения его получения каждый список появлений реализуется упорядоченной по адресам последовательностью или словарем (см. раздел 10.2).

Кроме списка страниц, содержащих данное ключевое слово, поисковые машины предоставляют дополнительную возможность ранжирования возвращаемых страниц по значимости. Создание быстрого и верно работающего механизма ранжирования является серьезной задачей для компьютерных исследователей и компаний, занимающихся электронной коммерцией.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии