Блог пользователя adamant

Автор adamant, 10 лет назад, По-русски

Всем привет! Меня всегда завораживало то, как хитро сплетены так называемые "строковые алгоритмы". Полгода назад я писал здесь статью о возможности быстрого перехода от Z-функции к префикс-функции и обратно. Некоторые опытные пользователи уже знают, что такие переходы возможны и между более сложными строковыми структурами — суффиксным деревом и суффиксным автоматом. Такой переход достаточно подробно описан на е-maxx.ru. Сейчас же я хотел бы в целом рассказать о такой структуре, как суффиксное дерево, а также поделиться достаточно простым (с теоретической точки зрения) способом его быстрого построения — получением суффиксного дерева из суффиксного массива.

Напомню, что суффиксное дерево — это бор, содержащий все суффиксы заданной строки. В самой простейшей реализации его построение потребует O(n2) времени и памяти — мы просто будем добавлять в бор все суффиксы по одному, пока не получим то, что получим. Чаще всего, такой расход времени и памяти оказывается слишком большим. Постараемся что-нибудь с этим сделать.

  1. Для начала сведём ассимптотику по памяти до O(n). Для этого нам потребуется следующая идея: если мы имеем группу рёбер, которые соединены последовательно и не имеют ответвлений, мы можем объединить их в одно, которому в соответствие будет представлена подстрока, а не отдельный символ. Таким образом, мы получим сжатый бор (также известный как radix tree или patricia tree). Но это ещё не всё. Наконец, мы можем заметить, что нам незачем целиком хранить подстроку на ребре, мы можем хранить лишь индексы её начала и конца в исходной строке. Именно это и даст нам желанную линейную ассимптотику. Ведь действительно, вершины в нашем дереве теперь будут появляться только в местах разделения следующих друг за другом лексикографически суффиксах, а таких мест будет не больше, чем n - 1.

  2. И, наконец, сведём к O(n) время построения дерева. Для этого нам подойдёт следующая стратегия:
    1) Добавляем в бор лексикографически минимальный суффикс.
    2) Для каждого следующего суффикса поднимаемся до точки lcp[i] и достраиваем его там.

    Удивительно, но этого будет достаточно. Это связано с тем, что действия, которые мы совершаем на самом деле идентичны обходу дерева в глубину, который, очевидно, выполняется за O(n).

"Постой-ка, но ведь в заголовке написано о построении за O(nlogn), а у тебя тут сплошные O(n), что за подстава?"

Действительно, на самом деле, имея массив lcp суффиксное дерево УЖЕ можно строить за O(n). Однако всё ещё остаётся одна проблема — массив lcp тоже надо посчитать. И именно здесь нам на помощь приходит суффиксный массив, по которому уже в свою очередь можно получить lcp. Сравнительно простой метод его получения описан на сайте e-maxx.ru. Мы также можем использовать алгоритм Касаи для получения массива lcp за линейное время. Если скомбинировать его с каким-нибудь линейным алгоритмом получения суффиксного массива, можно будет свести время построения суффиксного дерева таким способом к линейной.

Достоинства такого способа построения суффиксного дерева:

  • Просто для понимания.
  • Приемлемый расход времени и памяти.

Недостатки:

  • Алгоритм работает только в режиме оффлайн.
  • Объём кода. Мне потребовалось почти 300 строк (100 из которых — на получение суфф. массива) и целый вечер на то, чтобы сделать что-то приемлемое по такой схеме. Я впервые работал с суффиксным деревом, поэтому не могу точно сказать, можно ли построить его таким алгоритмом меньшей ценой.

Здесь можно также ознакомиться с примером кода, который совершает все эти злодеяния для создания суффиксного дерева. Всем удачи и до новых встреч, надеюсь, статья окажется интересной :)

Для проверки корректности кода были использованы следующие задачи:
1393 — проверка корректности построения lcp.
1590 — проверка корректности построения непосредственно суффиксного дерева.

  • Проголосовать: нравится
  • +82
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Долго не решался публиковать статью. Слишком трешовой лично мне казалась :)

Но всё же, опубликую. Посмотрим, что из этого выйдет.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

@adamant:Very Nice Tutorial.If possible can you write the comments in English so that other users are able to understand

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

    Если скомбинировать его с каким-нибудь линейным алгоритмом получения суффиксного массива, можно будет свести время построения суффиксного дерева таким способом к линейной.

    Наверное, это будет глупым выпросом, но что такое Sigma?

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

      .

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится

        Ну, конкретно в моей реализации используется обычный вектор. Когда нам нужно добавить суффикс, мы в соответствующем месте делаем push_back, что, очевидно, работает за O(1). Да, запрос будет умножаться за логарифм, но не непосредственно построение. Но у меня-то и построение оффлайновое, наверное, в онлайне так сделать не удастся.

        Кстати, unordered_map, ведь должен выдавать за O(1), не?

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится -16 Проголосовать: не нравится

          .

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится -8 Проголосовать: не нравится

            У меня поиск за O(|sigma|), но рёбра отсортированы лексикографически, так что можно бинарным поиском. Просто я добавляю суффиксы в лексикографическом порядке, а значит, когда я делаю push_back, этот суффикс гарантированно больше других уже добавленных.

            unordered_map, кстати, 100%-ый, насколько мне известно. Там же, вроде, с коллизиями как-то борятся. Но, как мне тут подсказывают, у него O(1) только в среднем.

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Здесь глупость, не читайте, плс

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Суффиксный массив можно строить за линию.

    Только для так называемых целочисленных алфавитов: когда буквы являются целыми числами из отрезка [1, n]. Алгоритм Фараха (1997) для построения суффиксного дерева тоже работает за O(n) для целочисленных алфавитов.

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      .

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится

        А разве за n log n мы не используем цифровую сортировку?

        А чем плох вариант по Укконену построить суфмас? Вроде там не используется факт про целочисленный алфавит.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится -8 Проголосовать: не нравится

          Алгоритм Укконена использует факт про алфавит константного размера :) Для произвольных алфавитов у него , а про модификацию для целочисленных не слышал.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится

        Если алфавит произвольный, то задачу сортировки можно свести к построению суффиксного дерева или массива. То есть — нижняя граница.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          .

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            .

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Да, надо бы поинтересоваться, что имеют ввиду авторы, говоря, что — "trivial lower bound") Алгоритмы, требующие целочисленный алфавит, тоже ведь сформулированы для RAM-модели. Может быть это нижняя граница для онлайновой задачи сортировки?

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Нет, алгоритм Фараха не онлайновый.

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    А никто не знает об онлайновых суффиксных массивах? За какую-то сложность ведь точно можно.

    Можно, за O(N log^2 N). Статья, автор Urbanowicz

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Когда писалась эта статья, я был плохо знаком с публикациями по теме. На самом деле в 2005 году было показано, как это делать за : Amihood Amir, Tsvi Kopelowitz, Moshe Lewenstein, Noa Lewenstein "Towards Real-Time Suffix Tree Construction". В статье это называется BIS (balanced indexing structure) и отличие в том, что используют специальную структуру для определения порядка за константу (Sleator, Dietz "Two Algorithms for Maintaining Order in a List").

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        сейчас еще поискал — вроде бы в этой статье (не нашел ее в открытом доступе) результат еще улучшили до

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Только это не является построением суффиксного массива, по крайней мере прямым.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          .

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Там просто обычное дерево на алфавите константного размера. Алгоритм Вайнера в таких условиях сам по себе работает быстрее — за линию, обрабатывая очередной суффикс за амортизированную O(1). А в этой работе показано, как превратить амортизированную O(1) в в худшем случае.

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              .

              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Бывает. Мне известны только две такие штуки: одна строит неполное суффиксное дерево, добавляя буквы в конце строки, другая — предназначена только для поиска всех вхождений. Обе с ограниченными приложениями. А для вариантов алгоритма Вайнера вроде как действительно нет.

»
10 лет назад, # |
Rev. 8   Проголосовать: нравится +10 Проголосовать: не нравится

There's also the possibility to build the suffix array in and then construct the suffix tree from that.

EDIT Nevermind, I see you are using that same idea already :) Although I don't see why you would need 100 LoC to implement suffix array + LCP in . Our implementation is a mere 24 lines, but it's since it does not contain a linear time sort.

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    Your implementation has memory complexity in spite of my . But anyway, your way to calculate suffix array is kinda interesting, thanks a lot!

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Isn't your suffix array build nlog2(n)? log(n) iteration in line 8 and nlog(n) for sorting in line 10. Correct me if i'm wrong.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes I changed the code in the meantime. It used to use LSB radix sort, but that seems slower in practice.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        If you really need better performance than this, which sometimes becomes necessity, you can use the one that implements bucket sort. Otherwise yours is way better, both to understand and code.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Допустим я каким-то образом построил суффмассив, то как тогда искать lcp? Например в алгоритме с емакса используется дополнительный массив, полученный в ходе построения, но не сам суффмассив.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Построить массив lcp соседних суффиксов в суфмассиве, а потом lcp(i, j) = min(lcp[i], lcp[i + 1]..., lcp[j]). Массив lcp можно построить за линию алгоритмом Касаи.

»
10 лет назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится

Дерево-то мы строить можем, но вот где и как его можно использовать? Ответ на этот вопрос намного интереснее статьи о построении дерева.

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

В любом случае, построение суфдерева через суфмассив — это неплохое упражнение. Так что, ИМХО, наибольшая польза от этой статьи не для сообщества, а для Вас лично.

Пусть у Вас сохранится мотивация к саморазвитию :).

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ну, где и как его использовать, как мне показалось, уже и так достаточно хорошо освещено, а ничего о таком методе его получения лично я раньше ни разу не встречал. Возможно, я ещё расскажу об использовании дерева подробнее, если решусь таки когда-нибудь освоить алгоритм Укконена и написать об этом отдельную статью.

    Кстати, меня вот недавно стал интересовать такой вопрос — а что вообще представляют собой задачи, которые решаются одной структурой, но не решаются другой?

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Как то раз в Петрозаводске была задача (деталей не помню, могу где-нибудь соврать, если есть желание можете поискать — была год или два назад на контесте Zhukov_Dmitry) дана строка, нужно найти количество различных подстрок, таких что у них есть как минимум 3 непересекающихся вхождения в исходную строку. И решением было какой-то хитрый обход суффиксного дерева.

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

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        длина строки до миллиона?

      • »
        »
        »
        »
        10 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

        не нашел контест с этой задачей, но вроде бы она легко решается.

        • построим суффиксный массив, массив LCP, и RMQ над LCP.

        • если подстрока (i, j) годится (т.е. у нее есть 3 непересекающихся вхождения), то (i, j - 1) тоже годится

        • если (i, j) не годится, то (i, j + 1) тоже не годится

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

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          Как я понял, ты предлагаешь для каждого i бинариком поискать наибольшее j, что у подстроки (i, j) будет 3 вхождения? Собственно сложность то в том, что не очевидно, как проверить есть ли три непересекающихся вхождения.

          Problem G. 3-substrings

          Petrozavodsk Summer Training Camp, Day 1 MIPT Contest, Friday, August 24, 2012

          You are given a string S of length N. For each K = 1, 2, ... , you should find the number of different substrings of S of length exactly K such that each of them has at least three pairwise non-overlapping occurrences in S. (3 ≤ |S| ≤ 105)

          Пример:

          In:                         Out:
          abracadabra              |  1 0 0
          abacabaabacabaabacaba    |  3 4 4 4 3 2 1
          
        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          Да, для заданных (i, j) можно за логарифм по RMQ над LCP найти границы подотрезка суфмассива, такие что LCP над всем отрезком будет >= j - i + 1. Да, можно найти минимум и максимум на этом же отрезка за еще один логарифм плюсом — соответственно самое первое вхождение нашей подстроки и последнее. Проверить, что эти вхождения не пересекаются. Но как понять что есть еще одно непересекающееся вхождение?

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Можно персистентным деревом отрезков на найденном отрезке суфмассива узнать, есть ли там суффикс, имеющий длину из нужного диапазона.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Мне вспомнилась одна притянутая за уши задача со сборов в Физтехе.

      Задача: для заданной строки найти количество различных левых контекстов.

      Определение левого контекста дам косвенно: две подстроки находятся в одном левом контексте тогда и только тогда, когда совпадают множества позиций вхождения их левых концов в исходную строку. Пример: строка 'abaa', левые контексты — [''], ['a'], ['aa'], ['ab', 'aba', 'abaa'], ['b', 'ba', 'baa'].

      Достаточно легко понять, что ответ на эту задачу равен суммарной степени вершин с исходящей степенью больше единицы (исключение: корень считаем в любом случае) в суфдереве, построенном по строке S + (разделитель).

      Если же захочется решить эту задачу суфмассивом, то придется обходить неявно построенное суфдерево, хотя формально в решении будет фигурировать только массив.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +15 Проголосовать: не нравится

        А это не кол-во состояний в автомате для rev(S) ?

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          Очевидно, что оно самое (на контесте сдал именно это). Но здесь речь идет про дерево и массив, поэтому я решил не упоминать про автомат.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          А не равно ли кол-во состояний в автомате для rev(S) кол-ву вершин в сжатом суфф дереве для S, раз уж на то пошло? Потому что если равно (а похоже на то), то его, судя по всему, можно найти таким образом:k + (|S| - T),
          где k — различных элементов в массиве lcp, T — количество таких позиций i, для которых n - i, то есть, длина суффикса, присутствует в массиве lcp.

          Обоснование: k — количество вершин во внутренней структуре дерева, (|S| - T) — количество листьев дерева.

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится

            А, нет, вру. Это в явном виде трудно записать. Но можно сделать так:

            Изначально в ответе 1 (корень дерева). Идём в цикле по массиву lcp. Если lcp[i - 1]==n - pos[i - 1], то здесь мы достраиваем новый лист. Добавляем к ответу 1. В противном случае нам надо знать, встречали ли мы lcp[i - 1] ранее и если да, то были ли все lcp между текущей "встречей" и предыдущей больше, чем lcp[i - 1]. Если да, то вершина здесь уже есть, опять таки, добавляем лист в дерево, а к ответу — единичку. В противном случае прийдётся расщеплять ребро, добавляем 2.

            В общем, это решение выглядит более правдоподобным, но оно, по сути, и есть обход неявного дерева.

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              А ещё, чтоб не извращаться с проверкой на минимум, можно при первой встрече (когда мы спускаемся по дереву) заносить lcp[i - 1] в стек, а когда будем подниматься, собственно, из стека доставать. Тогда нам будет достаточно проверить, является ли в данный момент число в вершине стека тем, которое мы хотим увидеть или нет.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have a question.

I build Suffix array (SA) and longest common prefix array (LCP) of a string ending in #, now I proceed to create suffix tree.

I can separate SA in buckets for first character, then, for each bucket I can insert first suffix in the tree but when I try to insert second item, can I get the node where I have to put new item in O(1)? I can only think in binary search saving each instance to inserted nodes for each item.

Example:

str = abaabbaaa#
idx:  0123456789
idx  SA      suffix     LCP
 0   9       #          N/A
 1   8       a#          0
 2   7       aa#         1
 3   6       aaa#        2
 4   2       aabbaaa#    2
 5   0       abaabbaaa#  1
 6   3       abbaaa#     1
 7   5       baaa#       0
 8   1       baabbaaa#   3
 9   4       bbaaa#      1

assume we inserted suffixes 0, 1, 2, 3 now, when I have to insert sa[4], what is the best way for getting node x (see picture)?

I hope my question is clear, thanks.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    You're such an artist X_X

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can I get the node where I have to put new item in O(1)?

    I don't know exactly but it looks like you can't. But as I said in the entry, if you will just move up on tree every time, it will be amortized because of its identity to dfs on tree. If you want to get moving to the next node non-amortized, you can keep for each node its ancestors that are pows of 2, i.e. 1, 2, 4, 8, 16, etc. Then you can get to the needed node in using this information.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I'm writing my algorithm but I get struggle in that part.

      What did you use in your implementation?

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        After adding some node to the tree I just move upward to the lcp[i] position and add next node there.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          After lots of debugging, I finally get an implementation (java) that seems to work (at least with my tests).

          But I can't pass TLE in this

          I wonder if is possible to use this trick in java.

          My suffix array is O(n log n)

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Can you show your code?

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              link

              It have comments.

              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Well, firstly I see that you always duplicate the node when inserting it. Maybe, you should do it only when you need (i.e. you shouldn't duplicate the node if it will be exact son). Also maybe you should try map<char,int> to get O(nlogk) instead of O(nk)

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I just understood that my entry has no useful pictures. Well, if somebody is interested in them, here is picture, showing suffix tree of k790alex's string made via GraphViz. * after the string means that this node can be the last in some suffix.