Информатика · объяснение и практика
Как префиксное дерево различает общее начало и целое слово
Строим префиксное дерево для небольшого словаря, отделяем существующий путь от конца слова и проверяем поиск по общему началу.

В теме Структуры данных · Учебная карта
Главная мысль
В префиксном дереве рёбра помечены символами, а путь от корня задаёт прочитанное начало строки. Чтобы различать целое слово и его префикс, узлу нужна отдельная отметка окончания слова. Наличие дальнейших ветвей не заменяет эту отметку.
Один путь может быть и словом, и началом другого
Сохраним слова ДОМ, ДОМИК и ДОЗА. От корня идёт ребро Д, затем О. После общего начала ДО пути расходятся: ветвь М ведёт к слову ДОМ и продолжению И→К, ветвь З→А — к слову ДОЗА. Общие первые буквы не приходится хранить заново для каждого слова.
В узле после М ставим отметку окончания: ДОМ есть в словаре, хотя у узла имеется ребёнок И. Узел после О этой отметки не получает: ДО встречается только как начало. Если принимать за слово любой достигнутый узел, программа выдумает слова Д и ДО. Если считать словом только лист, она потеряет ДОМ.
Пример
Поиск точного слова ДО возвращает «нет», поиск префикса ДО — «есть».
Оба запроса проходят один и тот же путь. Разница состоит в последней проверке: для целого слова обязательна отметка окончания.
Что происходит при вставке и удалении
При добавлении ДОК сначала используем уже существующие рёбра Д и О, затем создаём ветвь К и отмечаем её конец. Другие слова не меняются. При повторном добавлении того же слова структура может остаться прежней, если словарь хранит множество, а не частоты. Счётчики встречаемости требуют отдельного поля.
При удалении ДОМ нельзя стереть весь путь к М: он ещё нужен слову ДОМИК. Сначала снимают отметку конца ДОМ. Удалять пустые ветви разрешено только когда они не ведут ни к одному сохранённому слову. Этот пример полезен для проверки удаления короткого слова, которое одновременно является началом длинного.
Цена поиска и правила записи символов
Поиск проходит по числу символов запроса, если нужный переход из узла получается за постоянное время. Но перечисление всех слов по префиксу требует также обхода найденных продолжений и вывода результата. Префикс из одной буквы может подходить тысячам слов, поэтому мгновенный вывод всего списка не следует из быстрого нахождения узла.
Перед построением определяют, различаются ли регистр, е и ё, а также варианты Unicode-записи одного видимого символа. Если вставка нормализует строку, а поиск нет, одинаковое на вид слово может не найтись. Эти правила относятся к словарю, а не автоматически задаются формой дерева. Память зависит от числа различных префиксов и способа хранения переходов в каждом узле.
От чтения к действию
А теперь — вы
Частые вопросы
Пустая строка может быть ключом?
Да, если условие допускает её: тогда отметка окончания находится в корне. Это нужно оговорить, а не выводить из наличия остальных слов.
Префиксное дерево проверяет смысл или орфографию?
Само по себе оно проверяет наличие строки или начала в заданном наборе. Достоверность словаря и языковые правила должны обеспечиваться отдельно.
Углублённый разбор
Классы endpos в суффиксном автомате
Суффиксный автомат объединяет подстроки по одинаковым позициям окончания. Добавление новой буквы иногда разделяет прежний класс: короткая подстрока получает новое вхождение, длинная — нет. Клон состояния сохраняет переходы, одновременно исправляя границу класса длин и суффиксные ссылки.
Перед началом: ДКА и состояние; Подстрока и суффикс.
Одинаковый endpos означает одинаковые правые продолжения
Для непустой подстроки u текста T множество endpos(u) содержит все индексы, где заканчивается её вхождение. Если две подстроки имеют одинаковые endpos, они допускают одинаковые продолжения до суффикса всего текста. Обратно, такие продолжения определяют позиции окончания. Поэтому классы endpos дают состояния минимального частичного автомата суффиксов. Переход по букве означает дописывание этой буквы справа, если новая подстрока существует.
Внутри одного класса более короткая строка является суффиксом более длинной: достаточно рассмотреть одно общее окончание в тексте. Все промежуточные суффиксные длины тоже имеют то же множество окончаний. Поэтому состояние q представляет непрерывный интервал длин от len(link(q))+1 до len(q), где link ведёт к ближайшему более короткому суффиксному классу. Корень с пустой строкой рассматривается отдельно и в подсчёт непустых подстрок не входит.
Клон нужен, когда старый переход перескакивает новую границу
При онлайн-добавлении символа создаётся состояние нового полного префикса. Суффиксные переходы, которых раньше не было, направляются в него. Если обнаруженный старый переход p→q по этой букве удовлетворяет len(p)+1<len(q), короткое продолжение не может оставаться в прежнем классе q. Создаётся clone с len=len(p)+1, копиями переходов и прежней суффиксной ссылкой q; подходящие входящие переходы перенаправляются в clone.
Ссылки старого q и нового состояния переводятся в clone. Клон не означает ещё одно отдельное вхождение: он разделяет множество представляемых длин. Счётчики вхождений нельзя бездумно скопировать как готовый финальный ответ; их обычно получают распространением по суффиксным ссылкам после построения. Правильность маленького расщепления удобно проверять прямыми endpos всех подстрок, а не только числом состояний.
Интервалы дают подсчёт, но не меняют принимающий язык
Каждая непустая подстрока принадлежит одному классу, поэтому их число равно Σ_{q≠root}(len(q)−len(link(q))). Для распознавания именно суффиксов терминальными отмечаются классы, достигаемые по ссылкам из состояния полного текста. Если считать принимающими все состояния, можно распознавать все подстроки, но такой автомат уже не обязан быть минимальным для этого другого языка. Минимальность всегда относится к выбранному множеству принимаемых слов.
Добавленная b разделяет прежний класс
Условие. Постройте endpos-классы для T=abb, нумеруя позиции 0,1,2. Объясните, какой клон появляется при переходе от ab к abb, и посчитайте различные непустые подстроки.
- У текста ab подстроки b и ab имеют одно окончание{1} и находятся в одном классе длиной до2. После добавления b множество endpos(b) становится{1,2}, но endpos(ab) остаётся{1}. Класс необходимо разделить.
- Создаётся клон для b с len=1 и ссылкой в корень. Старое состояние ab длины 2 и новое состояние abb длины 3 получают ссылку в этот клон.
- Финальные непустые классы: a с окончаниями{0}; ab с{1}; b с{1,2}; bb,abb с{2}. Их интервалы длин соответственно[1,1],[2,2],[1,1],[2,3].
- Число подстрок равно 1+1+1+2=5. Прямой список a,b,ab,bb,abb подтверждает ответ и показывает, что клон не добавил вымышленное шестое слово.
Ответ. Нужен клон класса b; у abb ровно 5 различных непустых подстрок.
Проверка. Независимый перебор всех отрезков группирует слова по точным множествам окончаний и находит четыре непустых класса. Автоматное построение даёт те же len/link-интервалы и один клон.
Где легко ошибиться. Не воспринимайте клон как новое вхождение и не объявляйте автомат минимальным для всех подстрок только потому, что его можно использовать для их распознавания.
Проверьте понимание
Вопросы к этой главе
Почему bb и abb можно объединить?
Обе строки заканчиваются только в позиции 2, и все их продолжения до конца текста совпадают. Разница длин учитывается интервалом[2,3], поэтому два разных слова остаются посчитанными, хотя состояние одно.
Почему нельзя навсегда оставить b вместе с ab?
После добавления третьей буквы b имеет два окончания, а ab одно. Например, разные правые контексты различают возможность завершения до суффикса; объединение нарушило бы смысл состояния минимального автомата суффиксов.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Crochemore, Lecroq, Rytter: Suffix Structures
Прочитан авторский раздел: минимизация суффиксного trie, линейный размер suffix automaton и отличие от factor automaton. Изображения автоматов не инспектировались. endpos-интервалы и конкретное расщепление abb доказаны и проверены отдельно. Bar-IlanPDF дал timeout, 06-tsi.pdf502, большой ShanghaiTechPDF не извлечён; они не считаются прочитанными главами.
Ахо — Корасик ищет много образцов за один проход
При поиске многих образцов общий префиксный бор экономит повторную работу, а ссылки отказа сохраняют самый длинный возможный суффикс. Но одного найденного терминала недостаточно: в той же позиции могут завершаться более короткие образцы. Выходные ссылки позволяют сообщить их все за один проход текста.
Перед началом: Префиксный бор; Префикс и суффикс.
Состояние представляет суффикс уже прочитанного текста
Построим бор конечного набора непустых образцов. Узел соответствует префиксу хотя бы одного из них. Ссылка отказа узла u ведёт в узел самого длинного собственного суффикса строки u, который тоже есть в боре. Корень соответствует пустому слову. При чтении буквы без подходящего ребра идём по отказам, пока переход не появится либо не будет достигнут корень.
После перехода состояние представляет самый длинный суффикс прочитанного текста, являющийся префиксом образца. Поэтому символы текста не нужно перечитывать. Ссылки удобно строить BFS по глубине: отказ родителя уже известен, а отказ ребёнка находится продолжением по его букве через более короткие контексты. В полном автоматном варианте отсутствующие переходы можно заполнить заранее, явно учитывая размер алфавита.
Терминальный выход и суффиксные выходы различаются
Если текущий узел соответствует целому образцу, сообщаем его вхождение. Затем необходимо сообщить терминальные узлы по цепочке отказов: все они являются суффиксами текущего совпадения и заканчиваются в той же позиции. Выходная ссылка может перескакивать сразу к ближайшему терминальному отказу, чтобы не обходить бесполезные нетерминальные узлы при каждом сообщении.
Общая стоимость поиска при подходящем представлении переходов равна O(|T|+z), где z — число выданных вхождений. Член z нельзя убрать: если образцы a,aa,… и текст состоит из a, сообщений может быть очень много. Следует заранее определить, нужны все старты, только факт наличия каждого образца или суммарный счётчик; это разные форматы вывода, хотя основная трасса автомата одна.
Перекрытия являются нормальными совпадениями
После выдачи образца автомат не сбрасывается в корень и не пропускает его длину в тексте. Следующая буква может продолжить перекрывающееся совпадение. Пустой образец в этой главе исключён: иначе он совпадал бы между символами и требовал отдельного соглашения о числе позиций. Повтор одного и того же образца во входном словаре также нужно трактовать явно: как один шаблон или как несколько разных идентификаторов с общим текстом.
Три выхода на одной позиции
Условие. Образцы a,aba,ba, текст T=ababa. Найдите все вхождения, считая старты с0, и объясните выходы после чтения третьего символа.
- Бор содержит пути a–b–a и b–a. Ссылка отказа узла aba ведёт в ba, а отказ ba — в a. Все три узла терминальны.
- После символа с индексом 0 выдаётся a со стартом 0. После индекса 1 полного образца нет; состояние соответствует ab.
- После индекса 2 состояние aba выдаёт aba со стартом 0, затем по выходной цепочке ba со стартом 1 и a со стартом 2. Одна позиция окончания дала три разных совпадения.
- На индексе 4 повторяется такая же тройка со стартами 2,3,4. Итого a начинается в0,2,4; aba в0,2; ba в1,3 — семь сообщений.
Ответ. Всего 7 вхождений: a:{0,2,4}, aba:{0,2}, ba:{1,3}.
Проверка. Независимое посимвольное сравнение каждого образца в каждой допустимой позиции даёт те же семь пар(образец,старт). Проверка отказов перебором собственных суффиксов подтверждает цепочку aba→ba→a.
Где легко ошибиться. Не выдавайте только самый длинный терминал и не сбрасывайте состояние после совпадения. Это теряет вложенные суффиксные и перекрывающиеся вхождения.
Проверьте понимание
Вопросы к этой главе
Почему ba не пропущена, хотя поиск пришёл по ветви a?
Состояние aba хранит длинный контекст, но его терминальный суффикс ba также завершён. Выходная цепочка как раз сообщает образцы, которые не являются текущим полным путём от корня.
Можно ли просто перебрать все отказы после каждой буквы?
Это корректно для значений, но может потерять выходочувствительную оценку времени, обходя много нетерминальных узлов. Выходные ссылки оставляют только узлы, которые действительно нужно сообщать.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Stanford CS166: Aho–Corasick Automata
Прочитаны определения suffix/failure links, output-link chains и Final Matching Algorithm; просмотр ограничен этими разделами большого slide-deck. Собственные образцы a,aba,ba и текст ababa дают 7 вхождений с вложенными выходами.
Минимальный ациклический словарь через правые языки узлов
Префиксное дерево повторно хранит одинаковые будущие подсловари в разных ветвях. Для конечного словаря их можно объединить снизу вверх по сигнатурам узлов. Полученный ациклический автомат сохраняет все слова, но совместно использует эквивалентные продолжения, включая общие терминальные листья.
Перед началом: Trie и терминальные узлы; Правый язык состояния автомата.
Будущее состояние описывается множеством суффиксов
Правый язык узла — множество строк, которые можно дописать от этого узла до принятия. Для терминального узла в него входит пустая строка. Два узла детерминированного словаря можно слить ровно тогда, когда их правые языки совпадают. Различие уже прочитанных префиксов само по себе не препятствует слиянию.
Здесь используем частичный автомат: отсутствующее ребро означает отказ, отдельный поглощающий узел не хранится. Все сохранённые узлы достижимы и ведут хотя бы к одному слову. Если требовать полный автомат по алфавиту, нужно добавить состояние отказа с циклами; тогда число состояний и буквальная ацикличность графа изменятся.
Сигнатура сравнивается только после обработки детей
В ациклическом trie дети расположены глубже родителей. Обрабатываем узлы снизу вверх и назначаем канонические номера уже обработанным детям. Сигнатура узла состоит из терминального флага и упорядоченного списка пар «буква, канонический номер ребёнка». Равные сигнатуры помещаются в один класс.
По индукции от листьев равенство сигнатур эквивалентно равенству правых языков: флаг задаёт пустое продолжение, а первая буква разбивает все непустые продолжения на непересекающиеся группы. Поэтому объединение сохраняет язык и оставляет ровно один узел для каждого различного будущего подсловаря. Одного совпадения набора исходящих букв недостаточно, если их дети имеют разные языки.
Сортированный ввод позволяет закрывать завершённые ветви
При лексикографически отсортированных словах после добавления следующего слова неизменяемой становится часть предыдущей ветви ниже их общего префикса. Её можно сразу минимизировать снизу вверх и зарегистрировать канонические узлы. Непрочитанные будущие слова уже не потребуют дописывать эту закрытую часть.
При несортированном вводе такое простое правило небезопасно: общее состояние может обслуживать несколько префиксов, и изменение одной ветви затронет остальные. Нужны копирование разделяемых состояний либо другой алгоритм. В небольшом примере сначала строим весь trie, затем минимизируем; это позволяет отдельно проверить правильность объединений и итоговый язык.
Одинаковые окончания двух разных начал
Условие. Минимизируйте частичный ациклический словарь {at,bar,bat,car,cat}. Найдите число узлов trie, число состояний после слияний и все различные правые языки.
- В trie есть корень и десять непустых префиксов: a,at,b,ba,bar,bat,c,ca,car,cat. Всего одиннадцать узлов.
- Все пять терминальных листьев имеют правый язык {ε} и объединяются в один конечный узел F.
- Узлы ba и ca имеют правый язык {r,t} и одинаковые переходы r,t в F. Они объединяются в X. Узлы b и c имеют правый язык {ar,at} и переход a в X, поэтому объединяются в Y.
- Узел a имеет правый язык {t} и остаётся отдельным Z. Корень имеет исходный пятисловный язык и переходы a→Z, b→Y, c→Y.
- Итак, остаются R,Y,X,Z,F — пять состояний. Их правые языки попарно различны: исходный словарь, {ar,at}, {r,t}, {t}, {ε}. Это доказывает минимальность в выбранном частичном представлении.
Ответ. Trie содержит 11 узлов, минимальный частичный ациклический словарь — 5 состояний и 7 переходов. Его язык состоит из тех же пяти слов.
Проверка. Перечисление всех принимаемых путей независимо восстанавливает исходное множество. Попарно разные правые языки подтверждают невозможность дальнейшего слияния.
Где легко ошибиться. Не забывайте терминальный флаг в сигнатуре. Одинаковые переходы не делают узлы эквивалентными, если из одного уже принимается пустое продолжение, а из другого нет.
Проверьте понимание
Вопросы к этой главе
Нужно ли добавлять состояние отказа в эти пять?
Нет, здесь явно выбран частичный автомат. Если требуется полная функция переходов по всему алфавиту, добавится отдельное поглощающее состояние; это другая договорённость о представлении.
Почему отметка конца влияет даже при одинаковых рёбрах?
В словаре {a,ab,cb} узлы после a и c имеют одинаковое ребро b, но первый терминальный, второй нет. Их слияние ошибочно приняло бы слово c.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Daciuk, Mihov, Watson, Watson: minimal acyclic automata
Прочитаны определение правого языка и §3 о построении из сортированных данных и слиянии одинаковых поддеревьев. Пятисловный словарь, все сигнатуры и счёт состояний вычислены отдельно; выбранное частичное представление явно отличается от полного ДКА с состоянием отказа.
Компактное суффиксное дерево из массива SA и LCP
Суффиксный массив уже задаёт порядок листьев, а соседний LCP — глубину их общей развилки. Этих данных вместе с текстом достаточно для восстановления компактного суффиксного дерева. Последовательная обработка листьев поддерживает только правую ветвь и при необходимости разрезает одно ребро, не вставляя каждый символ каждого суффикса заново.
Перед началом: Суффиксный массив и LCP соседних суффиксов; Префиксное дерево и сжатие цепочек без ветвления.
Глубина измеряет символы, а не число рёбер
Одна строка с уникальным минимальным терминатором, готовые согласованные SA и соседний LCP; строится компактное дерево всех суффиксов.
В компактном дереве одно ребро может хранить целую непустую подстроку. Строковая глубина узла — суммарная длина меток от корня, а не количество пройденных рёбер. Лист начала s имеет глубину n−s. Уникальный терминатор гарантирует, что никакой полный суффикс не является префиксом другого, поэтому каждому суффиксу соответствует отдельный лист.
Договоримся: LCP[0]=0, а LCP[i] при i>0 сравнивает SA[i−1] и SA[i]. Их наименьший общий предок должен иметь глубину LCP[i]. Все листья с данным префиксом идут подряд в SA, поэтому новые вставки меняют только последнюю, правую ветвь уже построенного дерева.
Стек находит место развилки и разрезает старое ребро
Храним стек внутренних узлов правой ветви с возрастающими глубинами, начиная с корня глубины ноль. Для следующего листа возьмём l=LCP[i]. Снимаем вершины, пока верхняя глубина больше l. Если она равна l, новый лист прикрепляется непосредственно к этому узлу.
Если верхняя глубина меньше l, создаём внутренний узел глубины l. Под него переносим последнего ребёнка прежней вершины — это поддерево предыдущего суффикса. Затем добавляем новый лист вторым ребёнком. Так разрезается ровно одно прежнее ребро. При равной глубине новый узел создавать нельзя: возникла бы лишняя вершина или ребро нулевой длины.
Структура получается линейной, если не копировать метки
Для ребра от глубины d к глубине e достаточно хранить пару границ [s+d,s+e) в исходной строке, где s — начало любого суффикса из дочернего поддерева. Копирование всех строковых меток может скрытно увеличить объём данных. Каждая созданная внутренняя вершина имеет хотя бы двух детей, поэтому их не больше числа листьев минус один.
Каждый узел входит в стек и покидает его не более одного раза. При постоянной цене переноса последнего ребёнка построение после готовых SA,LCP занимает O(n) времени и памяти. Это сжатие цепочек, а не слияние узлов с одинаковыми правыми языками: итог остаётся деревом, а листья разных стартовых позиций не объединяются даже при похожих окончаниях.
Ветви a, aba и ba возникают из трёх положительных LCP
Условие. Для текста cababa$ заданы SA=[6,5,3,1,4,2,0] и LCP=[0,0,1,3,0,2,0]. Восстановите внутренние узлы компактного дерева и число всех вершин.
- Сначала листья 6 и 5 с суффиксами $ и a$ прикрепляются к корню. При следующем LCP=1 ребро к a$ разрезается на глубине 1: возникает узел a с листьями продолжений $,ba$.
- Следующий LCP=3 глубже a. Вставляем узел aba, перенося под него прежний лист начала 3 и добавляя лист начала 1. У него два продолжения: $ и ba$; узел a сохраняет отдельный лист начала 5.
- При LCP=0 снимаем aba и a со стека и добавляем корню лист начала 4. Следующий LCP=2 разрезает эту ветвь на узле ba; под ним оказываются листья начала 4 и 2. Последний LCP=0 возвращает к корню для листа начала 0.
- Ненулевые внутренние глубины равны 1,3,2, а их листовые интервалы в SA — [1,3],[2,3],[4,5] включительно. Имеем 7 листьев, 3 внутренних узла кроме корня и корень: всего 11 вершин.
Ответ. Внутренние префиксы кроме корня: a,aba,ba. Дерево содержит 11 вершин; все семь суффиксов остаются разными листьями.
Проверка. Независимое построение обычного trie всех семи суффиксов с последующим сжатием однодетных цепочек оставляет те же три развилки. Прямые LCP соседей равны заданному массиву.
Где легко ошибиться. Глубина LCP может попасть внутрь длинного ребра. Простое прикрепление к ближайшей меньшей вершине без разрезания потеряет точную общую часть суффиксов.
Проверьте понимание
Вопросы к этой главе
Почему повторяющаяся глубина не означает два разных узла автоматически?
Нужно смотреть текущий листовой интервал и стек. Равная глубина на текущей ветви использует существующую вершину; та же глубина в другой непересекающейся группе суффиксов может относиться к другому префиксу.
Можно восстановить текстовые метки только из чисел SA,LCP без самого текста?
Нет. Числа определяют глубины и порядок групп, но не сами буквы меток. Для рёбер хранят интервалы в исходном тексте, который является частью входа.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- KIT AlgorithmenII — §9.3.5, Construction from Suffix- and LCP-Arrays
Вставка листьев по SA, подъём по правой ветви и разрезание ребра на глубине LCP. Стековая запись и пример cababa$ подготовлены отдельно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как отличить отсутствующий ключ от сохранённого пустого значения
Различаем отсутствие ключа, сохранённый None и ложные значения в словаре Python, выбираем проверку принадлежности или уникальный маркер и не теряем корректный ноль.
Открыть темуКак эквивалентные записи Unicode отличаются от замены ё на е
Сравниваем составную и разложенную запись буквы по UnicodeNFC, сохраняем различие е иё и отделяем каноническую нормализацию от регистра и поиска похожих символов.
Открыть тему