Построение суффиксного дерева: алгоритм Укконена

    По просьбам трудящихся выкладываю описание и доказательство алгоритма Укконена.

    Описание задачи


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

    Бор для произвольного набора строк строится за O (суммы длин этих строк). Очевидно, что сумма длин всех суффиксов строки пропорциональна квадрату длины самой строки. Таким образом, построение суффиксного дерева тривиальным алгоритмом работает за O(N2). И тут возникает резонный вопрос, можно ли построить суффиксное дерево быстрее?

    На самом деле можно.

    И так, начнём с самого начала. Пусть длина строки S=s1...sn, для которой мы строим суффиксное дерево, равна N. Представим, что дерево растёт вниз, т.е. корень — верхняя вершина, а ребра идут сверху, от предка, вниз, к потомку. В дальнейшем я иногда буду называть вершины суффиксами, и наоборот, подразумевая соответствующие им суффиксы, если они являются вершинами для суффиксов, или соответствующие им подстроки.

    Во-первых, мы откажемся от идеи добавлять суффиксы поочерёдно, а будем строит дерево для всех суффиксов одновременно, т.е. последовательным добавлением символов строки. Во-вторых, мы сожмём рёбра. Что имеется ввиду: если у нас есть несколько рёбер подряд, между которыми вершины только с одним потомком, то объединим эти рёбра в одно и напишем на нём последовательность символов, написанную на объединённых ребрах. Можно явно не хранить эту последовательность, а для каждого ребра хранить только индексы начала и конца этой подстроки в S. Удалённым вершинам сопоставим положения внутри длинного ребра и назовём эти позиции «мнимыми вершинами». Таким образом, для хранения вершины нужно: номер вершины, из которой идёт ребро, первый символ этого ребра, смещение по ребру. В качестве предков мы будем рассматривать только немнимые вершины.

    Сначала покажем, что всего количество существующих вершин в сжатом дереве O(N).

    Лемма: Количество вершин в сжатом суффиксном дереве O(N)

    Посмотрим, какого вида бывают вершины. Во-первых, это листья. Во-вторых, это «развилки» — вершины с более чем одним ребёнком. Корень тоже является вершиной.
    Корень всего один.
    Каждому листу может соответствовать только суффикс. Пусть вершине листа соответствует T = sl...sr — подстрока в S, не являющаяся суффиксом. Тогда в S существует строка Tsr+1, а значит, из нашего листа должно быть ребро. Таким образом, количество листов не больше N.
    На первый взгляд не понятно, сколько может быть развилок. Для этого рассмотрим места построения сжатого дерева, когда они создаются. При добавлении одного суффикса мы сначала идём по дереву, а потом возможно 3 случая:
    1) мы закончили добавлять суффикс, ни разу не пытаясь выйти из уже построенного дерева. Тогда развилок не создавалось
    2) мы захотели выйти из дерева в немнимой вершине. Тогда создаётся ребро до конца суффикса из этой вершины. Новой развилки также не создаётся.
    3) мы захотели выйти из дерева в мнимой вершине. Вот тогда мы должны разбить это ребро на два, создать в этом месте развилку, и одно ребро будет соответствовать остатку ребра, на котором мы остановились, а другое будет
    соответствовать окончанию суффикса. В данном случае мы создали всего одну развилку.
    Получаем, что развилок не более N.
    В итоге количество вершин в сжатом дереве O(N).

    Рассмотренный нами алгоритм будет работать в режиме online, т.е. после k-ого шага алгоритма мы хотим получить суффиксное дерево для префикса строки длины k. В этом случае, мы впоследствии сможем за малое время увеличивать длину строки по мере необходимости. Т.к. суффиксов у нас N, добавить символов требуется O(N), получаем время работы O (N2). Для ускорения работы мы добавим в дерево суффиксные ссылки и сделаем 3 оптимизации.
    Суффиксная ссылка — указатель (или номер) вершины (в том числе и мнимой), которой соответствует наибольший собственный (не равный самой строке) суффикс строки, соответствующей текущей вершины. Раз мы храним все суффиксы, а значит и все подстроки, одной строки, то суффиксная ссылка от строки T = sl...sr указывает на строку T' = sl+1...r, т.е. сокращает длину строки на единицу. Мы будем хранить суффиксные ссылки только для развилок и корня. Для того, чтобы не рассматривать случаи, мы добавим «пустую» вершину blank, из которой в корень ведут рёбра со всеми символами алфавита, а в неё ведёт суффиксная ссылка из корня. Факт, что суффиксная ссылка из развилки ведёт в немнимую вершину, я оставлю без доказательства, т.к. считаю его очевидным. Для листов аналогичное утверждение не верно. Суффиксная ссылки из листа может указывать и на мнимую вершину, поэтому для листов мы их хранить не будем. Итак, суффиксные ссылки ведут в немнимые вершины и их количество O(N).

    Теперь про оптимизации



    Оптимизация №1: был листом, листом и останешься

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

    Оптимизация №2: если просто прошли по ребру, то и в меньших суффиксах мы тоже пройдём по ребру

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

    Итак, впереди нас ждёт последняя главная и самая сложная оптимизация, которая и сокращает асимптотику до необходимого значения. Но для начала мы избавляемся от списка коненых вершин суффиксов, и для просмотра их всех будем ходить из самого длинного, первого суффикса по суффиксным ссылкам. Т.к. мы знаем, что суффиксные ссылки есть не для каждой вершины, а только для развилок (и корня, но начиная с этого момента тоже будем считать его развилкой), то прохождение по суффиксной ссылки из листа или мнимой вершины будт происходить так:
    1) идём к ближайшему предку-развилке по ребру и запоминаем подстроку, по который мы поднялись вверх;
    2) переходим по суффиксной ссылке из развилки;
    3) спускаемся вниз, пока не пройдём всю эту запомненную подстроку. Возможно, нам придётся пройти по нескольким развилкам, тогда надо просто идти нужному по ребру;
    4) вершина, возможно и мнимая, в которой мы остановимся, и будет «суффиксной ссылкой» для изначальной.
    Факт, что во время спуска вниз мы не попытаемся выйти из дерева, оставляю без доказательства в качестве очевидного.

    И так, у нас есть 3 действия с вершинами при добавлении символа:
    1) Продление листа (выполняется для листа)
    2) Создание развилки (выполняется для мнимой вершины или развилки, из которых нет ребра с этим символом)
    3) Просто проход по ребру (выполняется для мнимой вершины или развилки, из которых есть такое ребро)
    Утверждается, что если рассматривать суффиксы по уменьшеню длины, то действия с ними будут выполняться в таком порядке 11...12...23..33. (Это следует из того, что из вершины суффикса данной вершины есть хотя бы все рёбра, аналогичные рёбрам из данной вершины, но ещё могут быть другие рёбра). Причём позиции смены действия 1 на 2 и 2 на 3 двигаются только влево (не забываем, что после каждой фазы у нас длина этойй последовательности уваличивается на 1, т.к. добавляется новый суффикс).

    Назовём первую вершину, которая не является листом, как start-point (SP). Этой вершине соответствует первое вхождение 2 в эту последовательность. Правда, действий типа 2 может и не быть, тогда SP — первое вхождение 3. А вершину, соответствующую первому вхождению 3, назовём active-point (AP). Что мы получили после первых двух оптимизаций? То, что последовательность на данной фазе можно рассматривать начиная с SP, и заканчивать, когда мы придём в AP. Теперь возник резонный вопрос, как быстро найти SP для следующей фазы? Для это есть третья оптимизация

    Оптимизация №3: SP для следующей фазы есть потомок AP текущей фазы

    Для начала, SP является потомком одной из вершин суффиксов перед этой фазы. При выполнении фазы было совершено некоторое действие, а потом спуск по ребру с текущем символом. Поэтому я буду оперировать не с потомками, а с вершинами предыдущей фазы.
    Очевидный факт: следующим SP не может стать суффикс, с которым на текущем шаге было выполнено действие первого типа. Далее, SP не может быть суффикс, для которого было выполнено действие второго типа, т.к. при этом мы создали развилку и, пройдя по ребру, ведущему в лист, попали в лист. Почему же суффикс, соответствующий предыдущей AP, подходит? От AP мы хотим только того, чтобы из неё было хоть какое-то ребро. Рассмотрим суффикс T, соответствующий SP. Раз из него есть как минимум ребро с данным символом, то T встречался в качестве подстроки не суффикса в S. Значит, в S существует подстрока Tsk (напомню, что на данной фазе мы добавляли символ sk). Тогда в новой строке, с добавленным символом sk, будет подстрока Tskc, где c — некоторый символ. А значит, у вершины Tsk (потомок SP) условие для AP выполнено, причём та вершина, которую мы только рассмотрели, самая ранняя из возможных, а значит она и будет следующей AP.
    В итоге получаем, что нам достаточно хранить только AP и передвигать её. Обработки вершин при передвижении AP (создание перекрёсктов или добавление одного ребра к уже существующему) будет достаточно для построения дерева.

    Поздравляю! Если вы дочитали до этого места и почти всё поняли, то вы уже можете сами написать работующую реализацию алгоритма Укконена. Для большего понимания выкладываю псевдокод этого алгоритма:
    
    .... Основная процедура .....
    создаём root и blank с необходимыми ребрами и ссылкой;
    SP <- root;
    k = 0;
    while (c = текущий k-тый символ строки) {
      while (у SP нет ребра на символ c)  {
        добавить из SP ребро с метками [k,oo];
        SP <- переход по ссылке из SP;
      }
      SP <- переход по ребру с символом C на 1 символ;
      k++;//переход к следующему символу;
    }
    
    .... Переход по ссылке из вершины V ....
    U <- предок V;
    S <- часть ребра от U до V;
    U <- suff(U); // переход по прямой суффиксной ссылке
    while (S не пуста) {
      C <- первый символ S;
      if (длина ребра, начинающегося на C == длине S) {
        переходим в потомка и возвращаем его;
      }
      else if (длина ребра, начинающегося на C > длины S){
        смещаемся по ребру на нужную длину;
        возвращаем текущую позицию;
      }
      else { //длина ребра, начинающегося на C < длины S
        переходим по ребру в потомка;
        удалаем из S начало длины, равной длине пройденного ребра;
      }
    }
    


    Но остался последний вопрос. Почему асимптотика этого алгоритма O(N)? Несмотря на то, что эти оптимизации позволяют работать со всеми суффиксами не более 2N раз (каждый суффикс мы либо обрабатываем и идём дальше, либо остаёмся на этом суффиксе и смотрим следующий символ; каждого из этих случаев не более N), у нас ещё остались переходы по суффиксным ссылкам, для которых совсем не очевидно, что суммарно переходов по ним будет O(N).

    Доказательство асимптотики


    Т.к. переход по прямой ссылке работает за O(1), а их не более N, то достаточно только рассмотреть переход вниз по рёбрам. Для этого рассмотрим длину смещения по ребру, по которому мы поднялись к предку. Пусть она равна L. Тогда при каждом прохождении во рёбрам вниз эта длина уменьшается хотя бы на 1. А увеличивается она только в основоной процедуре при проходе по ребру по символу C, причём не более чем на 1 за раз. А таких проходов N. Конечное значение смещения лежит в диапазоне [0,N], количество удлинений N, то и суммарное количество сокращений может быть не более 2N. Значит, суммарное количество продвижений вниз при переходе по суффикной ссылке O(N). В итоге, количество каждого вида действий O(N), а значит и суммарное количество всех действий O(N). Асимптотика доказана.

    Применение суффиксных деревьев



    Первая, и возможно самая распространённая, практическая задача, связанная с суффиксными деревьями, это нахождение включения одной строки в текст. Для этой задачи есть и другие алгоритмы, но если мы её немного модифицируем, например, нужно будет искать много раз, но мы не может обработать все запросы заранее, как в алгоритме Ахо-корасика, то тогда просто идя по дереву по символам из поискового запроса, мы либо попытаемся выйти из дерева, тогда ответ отрицательный, либо, если запрос закончился, ответ положительный. Если дополнительно к дереву хранить, во сколько листьев можно прийти из этой вершины, а к тексту в конце приписать уникальный символ, чтобы каждому суффиксу соответствовал именно лист, то так же можно будет сказать и количество вхождений запроса в текст.

    Наибольшая общая подстрока двух или более строк.
    Условие задачи просто: дан набор строк (мы рассмотрим случай, когда их две), и требуется найти их наибольшую общую подстроку за линейное время. Для этого надо построить обобщённое суффиксное дерево этих подстрок. Каждый лист этого дерева — суффикс некоторого набора данных строк. Тогда, если мы для каждой развилки укажем, суффиксы какого набора строк начинаются на строку этой вершины, то для нахождения наибольше подстроки достаточно пройтись по всем вершинам и, если в вершине указан набор из всех строк, то сравнить её длину и длиной уже найдённого ответа.

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

    PS. Если найдутся желающие, могу написать статью по алгоритму Ахо-Корасика.
    PSS. Если вдруг остались какие неочевидные моменты, пишите, буду обьяснять более понятно.
    Поделиться публикацией
    Комментарии 25
      –1
      если у нас есть несколько рёбер подряд, между которыми вершины только с одним предком
      потомком, наверное?
        0
        Только сдал экзамен по информатике, но все равно спасибо за интересную статью :) кстати, я тоже с физтеха)
          +2
          Может, вы оба даже с одного курса? :)
            +1
            А вы, почти наверное, один из наших экзаменаторов и ассистент на факультете :)
              +3
              Эх, спалился :((
          +1
          Отличный пост! Спасибо.

          Аха-Корасика да, можно)
            +1
            Раз появились желающие… Но вообще-то я считаю, что алгоритм Ахо-Корасика более простой, чем Укконен, да и найти его описание тоже можно в больших местах. Но вот алгоритм Укконена я долго не мог найти, за исключением возможно всего пары мест: Ден Гасфилд «Строки, деревья и последовательности в алгоритмах» (причём там не очень понятно написано, и для тех, кто решил ознакомится с этим алгоримом впервые, будет сложно разобраться в нём), и как ниже указано, есть конспект Лифшица, но который я раньше не встечал. Поэтому и решил, что ещё одно описание алгоритму Укконена будет не лишним, что не могу сказать об алгоритме Ахо-Корасика.

            PS. Возможно, через недельку-две смогу написать и про Ахо-Корасика.
            +3
            Мне кажется, имеет смысл добавить ссылку на оригинал алгоритма и на конспект Юрия Лифшица.

            Также надо учитывать, что решение зависит линейно от размера a алфавита (O(na) ). В отличие от, например, суффиксного массива.
              0
              А может кто-то выложит полные лекции годного универа (типа МФТИ) по Computer Science? Было бы здорово. Уверен, многие бы скачали и почитали.
                0
                Я не в праве выкладывать такую информацию. Считаю, что это работа преподавателей, и им решать, где и что они хотят выложить в общественное пользование. Ведь у каждого ВУЗа есть свои секреты
                  0
                  А контакты кого-нибудь из ваших преподавателей можно в личку? Я б пообщался с ними, возможно они бы поделились своими наработками.
                  0
                  Сайт итмо по вики-конспектам
                  По крайней мере, думаю, вас заинтересуют алгоритмы 1-2, а также 3-4 семестров
                +5
                Неплохо бы привести графические схемы и примеры. Так будет нагляднее и понятнее.
                  0
                  Когда писал библиотеку для поиска фраз в тексте, остановился на суффиксном массиве, так как он эффективно решал мою задачу и при этом оказался гораздо проще суффиксного дерева в понимании. Интересно, на сколько суффиксное дерево лучше/хуже суффиксного массива в плане скорости поиска строки в тексте по готовому дереву/массиву?
                    0
                    Если Вы строите массив за линейное время (например, алгоритм Фарача), то он лучше — время и память не зависят от размера алфавита. Особенно важно последнее обстоятельство. Но это нетривиальный алгоритм. Тот алгоритм построения массива, который чаще встречается и проще в реализации, строит за O(NlogN), что медленнее, чем построение дерева.

                    Вообще, массив вроде как и появился для оптимизации потребления памяти.
                    0
                    О! Интересные темы пошли.

                    Может быть, кто-нибудь предложит тогда хороший алгоритм поиска похожего слова: например, у нас есть 1 млн. слов, на вход подается слово, похожее на одно (или несколько) из них, задача найти на какие. Естественно, тупо перебирать и считать для каждой пары editing distance или похожую функцию неэффективно.

                    Или, если упростить эту задачу: имеем цепочки чисел от 1 до N, где N в пределах 1000, выстроенных по возрастанию:

                    1 4 56 67
                    1 3 35 56 145
                    1 2 3

                    И на вход алгоритма подаем цепочку, к примеру 1 4 23 56 67

                    Задча: найти наиболее близкие к образцу цепочки.
                    +1
                    Хорошая статья!
                    Просто ради интереса — а тебе ведь в ЛКШ рассказали этот алгоритм?

                    Теперь можно еще и про суффиксный автомат рассказать — он сложнее для понимания, зато пишется очень просто и работает весьма быстро!:)
                      +1
                      Этот алгоритм где мне только не рассказывали, но в ЛКШ тоже было дело. Но идея возникла только сейчас, при подготовке к сессии. А что, про него рассказывали этой зимой?
                      0
                      > Очевидно, что сумма длин всех суффиксов строки пропорциональна квадрату длины самой строки.

                      Может кубу? Количество суффиксов — N^2, длина — N.
                        0
                        Вы ошиблись. Видимо, вы имели ввиду количество всех «подстрок» N^2. А мы рассматриваем только суффиксы. Суффикс — подстрока, конец которой совпадает с концом нашей строки. Таким образом, суффикс определяется своим началом, которых N
                          +1
                          Да, меня сбило с толку то, что в русском языке суффикс не обязательно находится в конце.
                          А со строковыми алгоритмами почти не работал, так что не привык к этой терминологии.
                        0
                        Если бы был указан список задач где можно решить етим алгоритмом — было бы замечательно!
                          0
                          Если кому-то интересно, сейчас появился алгоритм построения суффиксного дерева по-проще — это модификация старого алгоритма Вейнера. Можно посмотреть тут: habrahabr.ru/post/258121 (с исходником) или тут www.youtube.com/watch?v=q9bPAVSmzfA

                          Короткую реализацию алгоритма Укконена можно найти тут: codeforces.com/blog/entry/16780?locale=ru

                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                          Самое читаемое