Массив LCP - LCP array

LCP массив
Тип	Множество
Изобретено	Манбер и Майерс (1990)Ошибка harvtxt: цель отсутствует: CITEREFManberMyers1990 ( справка )
Временная сложность и пространство сложность в большой нотации O
	В среднем	Худший случай
Космос	${\ Displaystyle {\ mathcal {O}} (п)}$	${\ Displaystyle {\ mathcal {O}} (п)}$
Строительство	${\ Displaystyle {\ mathcal {O}} (п)}$	${\ Displaystyle {\ mathcal {O}} (п)}$

В информатике , то длинный общий массив префикса ( LCP массив ) является вспомогательной структурой данных для массива суффиксов . Он хранит длины самых длинных общих префиксов (LCP) между всеми парами последовательных суффиксов в отсортированном массиве суффиксов.

Например, если A  : = [ааб, ab, абааб, б, бааб] - это массив суффиксов, самый длинный общий префикс между A [1] =ааби A [2] =ab является акоторый имеет длину 1, поэтому H [2] = 1 в ЖКП массива H . Аналогично, LCP A [2] =abи A [3] =абааб является ab, поэтому H [3] = 2.

Дополняя массив суффиксов с массивом LCP позволяет эффективно моделировать сверху вниз и снизу вверх прохождения в дереве суффиксов , ускоряет сопоставление с образцом на массиве суффиксов и является необходимым условием для сжатых дерев суффиксов.

История

Массив LCP был введен в 1993 году Уди Манбером и Джином Майерсом вместе с массивом суффиксов, чтобы улучшить время работы их алгоритма поиска строк.

Определение

Позвольте быть суффиксным массивом строки длины , где - контрольная буква, уникальная и лексикографически меньшая, чем любой другой символ. Позвольте обозначить подстроку в диапазоне от до . Таким образом, это th наименьший суффикс . ${\ displaystyle A}$${\ Displaystyle S = s_ {1}, s_ {2}, \ ldots s_ {n-1} \ $}$${\ displaystyle n}$${\ Displaystyle \ $}$${\ Displaystyle S [я, j]}$${\ displaystyle S}$${\ displaystyle i}$${\ displaystyle j}$${\ Displaystyle S [А [я], п]}$${\ displaystyle i}$${\ displaystyle S}$

Позвольте обозначить длину самого длинного общего префикса между двумя строками и . Тогда массив LCP представляет собой целочисленный массив такого размера , который не определен и для каждого . Таким образом сохраняется длина самого длинного общего префикса лексикографически наименьшего суффикса и его предшественника в массиве суффиксов. ${\ displaystyle \ operatorname {lcp} (v, w)}$${\ displaystyle v}$${\ displaystyle w}$${\ displaystyle H [1, n]}$${\ displaystyle n}$${\ displaystyle H [1]}$${\ Displaystyle Н [я] = \ OperatorName {lcp} (S [A [i-1], n], S [A [i], n])}$${\ Displaystyle 1 <я \ Leq п}$${\ Displaystyle Н [я]}$${\ displaystyle i}$

Разница между массивом LCP и массивом суффиксов:

• Массив суффиксов: представляет лексикографический ранг каждого суффикса массива.
• Массив LCP: содержит совпадение префикса максимальной длины между двумя последовательными суффиксами после их лексикографической сортировки.

Пример

Рассмотрим строку : ${\ Displaystyle S = {\ textrm {банан \ $}}}$

и соответствующий ему отсортированный массив суффиксов  : ${\ displaystyle A}$

Массив суффиксов с суффиксами, написанными под ним по вертикали:

Затем создается массив LCP путем сравнения лексикографически последовательных суффиксов для определения их самого длинного общего префикса: ${\ displaystyle H}$

Так, например, длина самого длинного общего префикса, разделяемого суффиксами и . Обратите внимание, что это не определено, поскольку нет лексикографически меньшего суффикса. ${\ displaystyle H [3] = 3}$${\ displaystyle {\ text {ana}}}$${\ Displaystyle А [3] = S [4,7] = {\ textrm {ана \ $}}}$${\ Displaystyle А [4] = S [2,7] = {\ textrm {анана \ $}}}$${\ displaystyle H [1]}$

Эффективные алгоритмы строительства

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

Манбер и Майерс (1993) предлагают алгоритм для вычисления массива LCP вместе с массивом суффиксов во времени. Kärkkäinen & Sanders (2003) показывают, что также можно изменить их временной алгоритм, чтобы он также вычислял массив LCP. Kasai et al. (2001) представляют первый алгоритм (FLAAP), который вычисляет массив LCP по тексту и массиву суффиксов. ${\ Displaystyle О (п \ журнал п)}$${\ Displaystyle О (п)}$${\ Displaystyle О (п)}$

Предполагая, что каждый текстовый символ занимает один байт, а каждая запись суффикса или массива LCP занимает 4 байта, основным недостатком их алгоритма является большое пространство, занимаемое байтами, в то время как исходный вывод (текст, массив суффиксов, массив LCP) занимает только байтов. Поэтому Манзини (2004) создал усовершенствованную версию алгоритма Kasai et al. (2001) (lcp9) и уменьшил занимаемое пространство до байтов. Kärkkäinen, Manzini & Puglisi (2009) предлагают еще одно усовершенствование алгоритма Kasai (-алгоритм ), которое улучшает время выполнения. Вместо фактического массива LCP этот алгоритм строит массив переставленных LCP (PLCP), в котором значения отображаются в текстовом порядке, а не в лексикографическом порядке. ${\ displaystyle 13n}$${\ displaystyle 9n}$${\ displaystyle 9n}$${\ displaystyle \ Phi}$

Gog & Ohlebusch (2011) предоставляют два алгоритма, которые, хотя и были теоретически медленными ( ), на практике были быстрее, чем вышеупомянутые алгоритмы. ${\ Displaystyle О (п ^ {2})}$

По состоянию на 2012 год самый быстрый алгоритм построения массива LCP с линейным временем принадлежит Фишеру (2011) , который, в свою очередь, основан на одном из самых быстрых алгоритмов построения суффиксного массива (SA-IS) Нонга, Чжана и Чана (2009). . Fischer & Kurpicz (2017) на основе DivSufSort Юты Мори работает еще быстрее.

Приложения

Как отмечают Abouelhoda, Kurtz & Ohlebusch (2004), некоторые проблемы обработки строк могут быть решены с помощью следующих видов обходов дерева :

• обход полного дерева суффиксов снизу вверх
• обход поддерева суффиксного дерева сверху вниз
• обход дерева суффиксов с использованием суффиксных ссылок.

Kasai et al. (2001) показывают, как имитировать обход дерева суффиксов снизу вверх, используя только массив суффиксов и массив LCP. Abouelhoda, Kurtz & Ohlebusch (2004) расширяют массив суффиксов с помощью массива LCP и дополнительных структур данных и описывают, как этот расширенный массив суффиксов можно использовать для имитации всех трех видов обходов дерева суффиксов. Fischer & Heun (2007) уменьшают требования к пространству для расширенного массива суффиксов за счет предварительной обработки массива LCP для запросов с минимальным диапазоном . Таким образом, каждая проблема, которую можно решить с помощью алгоритмов дерева суффиксов, также может быть решена с использованием расширенного массива суффиксов .

Решение о том, является ли образец длины подстрокой строки длины, требует времени, если используется только массив суффиксов. За счет дополнительного использования информации LCP можно улучшить эту границу времени. Abouelhoda, Kurtz & Ohlebusch (2004) показывают, как еще больше улучшить это время работы для достижения оптимального времени. Таким образом, используя массив суффиксов и информацию о массиве LCP, на запрос решения можно ответить так же быстро, как с помощью дерева суффиксов . ${\ displaystyle P}$${\ displaystyle m}$${\ displaystyle S}$${\ displaystyle n}$${\ Displaystyle О (м \ журнал п)}$${\ Displaystyle О (м + \ журнал п)}$${\ Displaystyle О (м)}$

Массив LCP также является важной частью сжатых деревьев суффиксов, которые обеспечивают полную функциональность дерева суффиксов, такую ​​как ссылки суффиксов и запросы наименьшего общего предка . Кроме того, его можно использовать вместе с массивом суффиксов для вычисления факторизации Lempel-Ziv LZ77 во времени. ${\ Displaystyle О (п)}$

Проблема с самой длинной повторяющейся подстрокой для строки длины может быть решена вовремя, используя как массив суффиксов, так и массив LCP. Достаточно выполнить линейное сканирование по массиву LCP, чтобы найти его максимальное значение и соответствующий индекс, где хранится. Самая длинная подстрока, встречающаяся не менее двух раз, определяется как . ${\ displaystyle S}$${\ displaystyle n}$${\ Displaystyle \ Theta (п)}$${\ displaystyle A}$${\ displaystyle v_ {max}}$${\ displaystyle i}$${\ displaystyle v_ {max}}$${\ Displaystyle S [A [я], A [я] + v_ {max} -1]}$

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

Найдите количество вхождений шаблона

Чтобы найти количество вхождений данной строки (длины ) в текст (длина ), ${\ displaystyle P}$${\ displaystyle m}$${\ displaystyle T}$${\ displaystyle N}$

• Мы используем двоичный поиск по массиву суффиксов, чтобы найти начальную и конечную позиции всех вхождений .${\ displaystyle T}$${\ displaystyle P}$
• Теперь, чтобы ускорить поиск, мы используем массив LCP, а именно специальную версию массива LCP (LCP-LR ниже).

Проблема с использованием стандартного двоичного поиска (без информации LCP) заключается в том, что при каждом из необходимых сравнений мы сравниваем P с текущей записью в массиве суффиксов, что означает полное сравнение строк длиной до m символов. Так что сложность такая . ${\ Displaystyle О (\ журнал N)}$${\ Displaystyle О (м \ журнал N)}$

Массив LCP-LR помогает улучшить это следующим образом: ${\ Displaystyle О (м + \ журнал N)}$

В любой момент алгоритма двоичного поиска мы, как обычно, рассматриваем диапазон суффиксного массива и его центральную точку и решаем, продолжать ли наш поиск в левом поддиапазоне или в правом поддиапазоне . Чтобы принять решение, мы сравниваем строку в . Если совпадает с , наш поиск завершен. Но если нет, мы уже сравнили первые символы, а затем решили, является ли он лексикографически меньше или больше чем . Предположим, что результат больше, чем . Итак, на следующем шаге мы рассмотрим новую центральную точку посередине: ${\ Displaystyle (L, \ точки, R)}$${\ displaystyle M}$${\ Displaystyle (L, \ точки, M)}$${\ Displaystyle (М, \ точки, R)}$${\ displaystyle P}$${\ displaystyle M}$${\ displaystyle P}$${\ displaystyle M}$${\ displaystyle k}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle M}$${\ displaystyle P}$${\ displaystyle M}$${\ Displaystyle (М, \ точки, R)}$${\ displaystyle M '}$

             M ...... M' ...... R
             |
      we know:
         lcp(P,M)==k

Хитрость в настоящее время является то , что LCP-LR является предварительно вычислен таким образом, что -lookup говорит нам самый длинный общий префикс и , . ${\ displaystyle O (1)}$${\ displaystyle M}$${\ displaystyle M '}$${\ Displaystyle \ mathrm {lcp} (М, М ')}$

Мы уже знаем (из предыдущего шага) , что само по себе имеет префикс символов общего с : . Теперь есть три возможности: ${\ displaystyle M}$${\ displaystyle k}$${\ displaystyle P}$${\ Displaystyle \ mathrm {lcp} (P, M) = k}$

• Случай 1:, т.е. имеет меньше префиксных символов, общих с M, чем M имеет общих с M '. Это означает, что (k + 1) -й символ M 'такой же, как и символ M, и поскольку P лексикографически больше M, он также должен быть лексикографически больше M'. Итак, продолжаем в правой половине (M ', ..., R).${\ Displaystyle к <\ mathrm {lcp} (М, М ')}$${\ displaystyle P}$
• Случай 2:, т.е. имеет больше общих префиксных символов, чем имеет . Следовательно, если бы мы сравнивали с , общий префикс был бы меньше , и был бы лексикографически больше , поэтому, фактически не производя сравнения, мы продолжаем с левой половины .${\ Displaystyle к> \ mathrm {lcp} (М, М ')}$${\ displaystyle P}$${\ displaystyle M}$${\ displaystyle M}$${\ displaystyle M '}$${\ displaystyle P}$${\ displaystyle M '}$${\ displaystyle k}$${\ displaystyle M '}$${\ displaystyle P}$${\ Displaystyle (М, \ точки, М ')}$
• Случай 3: . Итак, M и M 'идентичны первым символам. Для того, чтобы решить , продолжать ли мы в левой или правой половине, достаточно сравнить с начиная с го символа.${\ Displaystyle к = \ mathrm {lcp} (М, М ')}$${\ displaystyle P}$${\ displaystyle k}$${\ displaystyle P}$${\ displaystyle M '}$${\ Displaystyle (к + 1)}$
• Продолжаем рекурсивно.

Общий эффект заключается в том, что ни один символ не сравнивается с каким-либо символом текста более одного раза. Общее количество сравнений символов ограничено , поэтому общая сложность действительно равна . ${\ displaystyle P}$${\ displaystyle m}$${\ Displaystyle О (м + logN)}$

Нам все еще нужно предварительно вычислить LCP-LR, чтобы он мог вовремя сообщить нам lcp между любыми двумя записями массива суффиксов. Мы знаем, что стандартный массив LCP дает нам lcp только последовательных записей, то есть для любых . Однако и в приведенном выше описании не обязательно идут последовательные записи. ${\ displaystyle O (1)}$${\ Displaystyle \ mathrm {lcp} (я-1, я)}$${\ displaystyle i}$${\ displaystyle M}$${\ displaystyle M '}$

Ключом к этому является осознание того, что во время двоичного поиска когда-либо будут встречаться только определенные диапазоны : он всегда начинается с и делит его в центре, а затем продолжается влево или вправо и снова делит эту половину и так далее. Другой способ взглянуть на это: каждая запись массива суффиксов является центральной точкой ровно одного возможного диапазона во время двоичного поиска. Таким образом, существует ровно N различных диапазонов, которые могут играть роль во время двоичного поиска, и для этих возможных диапазонов достаточно выполнить предварительное вычисление . Итак, это разные предварительно вычисленные значения, следовательно, LCP-LR имеет размер. ${\ Displaystyle (L, \ точки, R)}$${\ Displaystyle (0, \ точки, N)}$${\ Displaystyle (L \ точки M \ точки R)}$${\ Displaystyle \ mathrm {lcp} (L, M)}$${\ Displaystyle \ mathrm {lcp} (М, R)}$${\ displaystyle N}$${\ displaystyle 2N}$${\ Displaystyle О (Н)}$

Более того, существует простой рекурсивный алгоритм для вычисления значений LCP-LR во времени из стандартного массива LCP. ${\ displaystyle 2N}$${\ Displaystyle О (Н)}$

Подводить итоги:

• Из LCP можно вычислить LCP-LR во времени и пространстве.${\ Displaystyle О (Н)}$${\ Displaystyle О (2N) = О (N)}$
• Использование LCP-LR во время двоичного поиска помогает ускорить процедуру поиска от до .${\ Displaystyle О (М \ журнал N)}$${\ Displaystyle О (М + logN)}$
• Мы можем использовать два бинарных поиска, чтобы определить левый и правый конец диапазона совпадений , и длина диапазона совпадений соответствует количеству вхождений для P.${\ displaystyle P}$

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

Учитывая массив суффиксов и массив LCP строки длины , его суффиксное дерево может быть построено во времени на основе следующей идеи: начните с частичного дерева суффиксов для лексикографически наименьшего суффикса и несколько раз вставьте другие суффиксы в порядке, заданном следующим образом: массив суффиксов. ${\ displaystyle A}$${\ displaystyle H}$${\ Displaystyle S = s_ {1}, s_ {2}, \ ldots s_ {n} \ $}$${\ displaystyle n + 1}$${\ displaystyle ST}$${\ Displaystyle О (п)}$

Позвольте быть частичным суффиксным деревом для . Далее пусть будет длина конкатенации всех меток пути от корня до узла . ${\ displaystyle ST_ {i}}$${\ Displaystyle 0 \ Leq я \ Leq п}$${\ displaystyle d (v)}$${\ displaystyle ST_ {i}}$${\ displaystyle v}$

Случай 1 ( ): Предположим , суффиксы , , и струны уже добавлены к дереву суффикса. Затем к дереву добавляется суффикс, как показано на картинке. Крайний правый путь выделен красным цветом.${\ Displaystyle d (v) = H [я + 1]}$${\ Displaystyle а \ $}$${\ displaystyle ana \ $}$${\ Displaystyle анана \ $}$${\ displaystyle банан \ $}$${\ Displaystyle S = банан \ $}$${\ displaystyle na \ $}$

Начнем с дерева, состоящего только из корня. Чтобы вставить в , поднимитесь по крайнему правому пути, начиная с недавно вставленного листа, до корня, пока не будет достигнут самый глубокий узел с . ${\ displaystyle ST_ {0}}$${\ Displaystyle А [я + 1]}$${\ displaystyle ST_ {i}}$${\ Displaystyle А [я]}$${\ displaystyle v}$${\ Displaystyle d (v) \ Leq H [я + 1]}$

Нам нужно различать два случая:

• ${\ Displaystyle d (v) = H [я + 1]}$: Это означает, что объединение меток на пути от корня к пути равно самому длинному общему префиксу суффиксов и . В этом случае вставьте как новый лист узла и разметить край с . Таким образом, метка края состоит из оставшихся символов суффикса, которые еще не представлены конкатенацией меток пути от корня к пути. Это создает частичное дерево суффиксов .${\ displaystyle v}$${\ Displaystyle А [я]}$${\ Displaystyle А [я + 1]}$
  ${\ Displaystyle А [я + 1]}$${\ displaystyle x}$${\ displaystyle v}$${\ displaystyle (v, x)}$${\ Displaystyle S [А [я + 1] + Н [я + 1], п]}$${\ Displaystyle А [я + 1]}$${\ displaystyle v}$
  ${\ Displaystyle ST_ {я + 1}}$
  

  Случай 2 ( ): чтобы добавить суффикс , необходимо разделить край ранее вставленного суффикса . Новое ребро нового внутреннего узла помечается самым длинным общим префиксом из суффиксов и . Края, соединяющие два листа, помечены оставшимися суффиксными символами, которые не являются частью префикса.${\ Displaystyle d (v) <Ч [я + 1]}$${\ displaystyle nana \ $}$${\ displaystyle na \ $}$${\ displaystyle na \ $}$${\ displaystyle nana \ $}$
• ${\ Displaystyle d (v) <Ч [я + 1]}$: Это означает , что объединение меток на корневом-to пути отображает меньше символов , чем самый длинный общий префикс суффиксов и и недостающие символы , содержащиеся в краевой метке «s правого края. Следовательно, мы должны разделить это ребро следующим образом: Пусть будет дочерним элементом самого правого пути on .${\ displaystyle v}$${\ Displaystyle А [я]}$${\ Displaystyle А [я + 1]}$${\ displaystyle v}$
  ${\ displaystyle w}$${\ displaystyle v}$${\ displaystyle ST_ {i}}$

1. Удаляем край .${\ displaystyle (v, w)}$
2. Добавьте новый внутренний узел и новое ребро с меткой . Новая метка состоит из пропущенных символов самого длинного общего префикса и . Таким образом, объединение меток корня- пути теперь отображает самый длинный общий префикс и .${\ displaystyle y}$${\ displaystyle (v, y)}$${\ Displaystyle S [A [я] + d (v), A [я] + H [я + 1] -1]}$${\ Displaystyle А [я]}$${\ Displaystyle А [я + 1]}$${\ displaystyle y}$${\ Displaystyle А [я]}$${\ Displaystyle А [я + 1]}$
3. Подключитесь к вновь созданному внутреннему узлу с помощью помеченного края . Новая метка состоит из оставшихся символов удаленной кромки , которые не использовались в качестве метки кромки .${\ displaystyle w}$${\ displaystyle y}$${\ Displaystyle (у, ш)}$${\ Displaystyle S [A [я] + Н [я + 1], A [я] + d (ш) -1]}$${\ displaystyle (v, w)}$${\ displaystyle (v, y)}$
4. Добавьте как новый лист и соедините его с новым внутренним узлом с помощью обозначенного края . Таким образом, метка края состоит из оставшихся символов суффикса, которые еще не представлены конкатенацией меток пути от корня к пути.${\ Displaystyle А [я + 1]}$${\ displaystyle x}$${\ displaystyle y}$${\ Displaystyle (у, х)}$${\ Displaystyle S [А [я + 1] + Н [я + 1], п]}$${\ Displaystyle А [я + 1]}$${\ displaystyle v}$
5. Это создает частичное дерево суффиксов .${\ Displaystyle ST_ {я + 1}}$

Простой аргумент амортизации показывает, что время работы этого алгоритма ограничено : ${\ Displaystyle О (п)}$

Узлы, которые проходят по самому правому пути (кроме последнего узла ), удаляются из крайнего правого пути, когда они добавляются к дереву в качестве нового листа. Эти узлы больше никогда не будут проходить на всех последующих шагах . Таким образом, всего будет пройдено не больше узлов. ${\ displaystyle i}$${\ displaystyle ST_ {i}}$${\ displaystyle v}$${\ Displaystyle А [я + 1]}$${\ displaystyle j> i}$${\ displaystyle 2n}$

Запросы LCP для произвольных суффиксов

Массив LCP содержит только длину самого длинного общего префикса каждой пары последовательных суффиксов в массиве суффиксов . Тем не менее, с помощью массива обратного суффикса ( , то есть суффикса , который начинается в положении в хранятся в положении в ) и постоянная время минимального диапазона запросы на , то можно определить длину самого длинного общего префикса произвольных суффиксов в время. ${\ displaystyle H}$${\ displaystyle A}$${\ displaystyle A ^ {- 1}}$${\ Displaystyle A [я] = j \ Leftrightarrow A ^ {- 1} [j] = i}$${\ displaystyle S [j, n]}$${\ displaystyle j}$${\ displaystyle S}$${\ displaystyle A ^ {- 1} [j]}$${\ displaystyle A}$${\ displaystyle H}$${\ displaystyle O (1)}$

Из-за лексикографического порядка массива суффиксов каждый общий префикс суффиксов и должен быть общим префиксом для всех суффиксов между положением в массиве суффиксов и положением в массиве суффиксов . Следовательно, длина самого длинного префикса, общего для всех этих суффиксов, является минимальным значением в интервале . Это значение может быть найдено за постоянное время, если оно предварительно обработано для запросов с минимальным диапазоном. ${\ Displaystyle S [я, п]}$${\ displaystyle S [j, n]}$${\ displaystyle i}$${\ Displaystyle А ^ {- 1} [я]}$${\ displaystyle j}$${\ displaystyle A ^ {- 1} [j]}$${\ Displaystyle Н [A ^ {- 1} [я] + 1, A ^ {- 1} [j]]}$${\ displaystyle H}$

При этом данная строка длины и две произвольные позиции в строке с , длина самого длинного общего префикса суффиксов и может быть вычислено следующим образом : . ${\ displaystyle S}$${\ displaystyle n}$${\ displaystyle i, j}$${\ displaystyle S}$${\ Displaystyle A ^ {- 1} [я] <A ^ {- 1} [j]}$${\ Displaystyle S [я, п]}$${\ displaystyle S [j, n]}$${\ displaystyle \ operatorname {LCP} (i, j) = H [\ operatorname {RMQ} _ {H} (A ^ {- 1} [i] + 1, A ^ {- 1} [j])]}$

Заметки

Рекомендации

• Абуэльода, Мохамед Ибрагим; Курц, Стефан; Охлебуш, Энно (2004). «Замена суффиксных деревьев расширенными суффиксными массивами» . Журнал дискретных алгоритмов . 2 : 53–86. DOI : 10.1016 / S1570-8667 (03) 00065-0 .
• Манбер, Уди; Майерс, Джин (1993). «Суффиксные массивы: новый метод поиска строк в сети». SIAM Journal on Computing . 22 (5): 935. CiteSeerX  10.1.1.105.6571 . DOI : 10.1137 / 0222058 . S2CID  5074629 .
• Kasai, T .; Lee, G .; Arimura, H .; Arikawa, S .; Парк, К. (2001). Вычисление линейного времени с наибольшим общим префиксом в суффиксных массивах и его приложения . Труды 12-го ежегодного симпозиума по комбинаторному сопоставлению с образцом. Конспект лекций по информатике. 2089 . С. 181–192. DOI : 10.1007 / 3-540-48194-X_17 . ISBN 978-3-540-42271-6.
• Охлебуш, Энно; Фишер, Йоханнес; Гог, Саймон (2010). CST ++ . Обработка строк и поиск информации. Конспект лекций по информатике. 6393 . п. 322. DOI : 10.1007 / 978-3-642-16321-0_34 . ISBN 978-3-642-16320-3.
• Кярккяйнен, Юха; Сандерс, Питер (2003). Простое построение линейного массива рабочих суффиксов . Материалы 30-й международной конференции по автоматам, языкам и программированию. С. 943–955 . Проверено 28 августа 2012 .
• Фишер, Йоханнес (2011). Индукция LCP-Array . Алгоритмы и структуры данных. Конспект лекций по информатике. 6844 . С. 374–385. arXiv : 1101.3448 . DOI : 10.1007 / 978-3-642-22300-6_32 . ISBN 978-3-642-22299-3.
• Манзини, Джованни (2004). Два приема экономии места для вычисления массива LCP с линейным временем . Теория алгоритмов - SWAT 2004. Конспект лекций по информатике. 3111 . п. 372. DOI : 10.1007 / 978-3-540-27810-8_32 . ISBN 978-3-540-22339-9.
• Кярккяйнен, Юха; Манзини, Джованни; Пуглиси, Саймон Дж. (2009). Переставленный массив наиболее длинных общих префиксов . Комбинаторное сопоставление с образцом. Конспект лекций по информатике. 5577 . п. 181. DOI : 10.1007 / 978-3-642-02441-2_17 . ISBN 978-3-642-02440-5.
• Puglisi, Simon J .; Терпин, Эндрю (2008). Пространственно-временные компромиссы для вычисления массива с самым длинным общим префиксом . Алгоритмы и вычисления. Конспект лекций по информатике. 5369 . п. 124. DOI : 10.1007 / 978-3-540-92182-0_14 . ISBN 978-3-540-92181-3.
• Гог, Саймон; Охлебуш, Энно (2011). Быстрые и легкие алгоритмы построения LCP-массива (PDF) . Труды семинара по разработке алгоритмов и экспериментам, ALENEX 2011. С. 25–34 . Проверено 28 августа 2012 .
• Нонг, Ге; Чжан, Сен; Чан, Вай Хун (2009). Построение линейного массива суффиксов с помощью почти чистой индуцированной сортировки . Конференция по сжатию данных 2009 г. п. 193. DOI : 10,1109 / DCC.2009.42 . ISBN 978-0-7695-3592-0.
• Фишер, Йоханнес; Хойн, Волкер (2007). Новое краткое представление информации RMQ и улучшения в расширенном массиве суффиксов . Комбинаторика, алгоритмы, вероятностные и экспериментальные методологии. Конспект лекций по информатике. 4614 . п. 459. DOI : 10.1007 / 978-3-540-74450-4_41 . ISBN 978-3-540-74449-8.
• Chen, G .; Puglisi, SJ; Смит, ВФ (2008). "Факторизация Лемпеля – Зива с использованием меньшего количества времени и пространства". Математика в информатике . 1 (4): 605. DOI : 10.1007 / s11786-007-0024-4 . S2CID  1721891 .
• Crochemore, M .; Илие, Л. (2008). «Вычисление самого длинного предыдущего фактора в линейное время и приложения». Письма об обработке информации . 106 (2): 75. CiteSeerX  10.1.1.70.5720 . DOI : 10.1016 / j.ipl.2007.10.006 .
• Crochemore, M .; Ilie, L .; Смит, ВФ (2008). Простой алгоритм вычисления факторизации Лемпеля Зива . Конференция по сжатию данных (DC 2008). п. 482. DOI : 10,1109 / DCC.2008.36 . ЛВП : 20.500.11937 / 5907 . ISBN 978-0-7695-3121-2.
• Садакане, К. (2007). «Сжатые суффикс-деревья с полной функциональностью». Теория вычислительных систем . 41 (4): 589–607. CiteSeerX  10.1.1.224.4152 . DOI : 10.1007 / s00224-006-1198-х . S2CID  263130 .
• Фишер, Йоханнес; Мякинен, Вели; Наварро, Гонсало (2009). «Более быстрые сжатые суффиксные деревья с ограничением энтропии». Теоретическая информатика . 410 (51): 5354. DOI : 10.1016 / j.tcs.2009.09.012 .
• Фишер, Йоханнес; Курпиц, Флориан (5 октября 2017 г.). «Разборка DivSufSort». Труды Пражской Stringology Conference 2017 . arXiv : 1710.01896 .

Внешние ссылки

• Зеркало специальной реализации кода, описанного в Fischer (2011)
• SDSL: краткая библиотека структур данных - предоставляет различные реализации массивов LCP, структуры поддержки запроса минимального диапазона (RMQ) и многие другие краткие структуры данных.
• Обход дерева суффиксов снизу вверх, эмулируемый с использованием массива суффиксов и массива LCP (Java)
• Проект индексации текста (построение суффиксных деревьев, массивов суффиксов, массива LCP и преобразования Барроуза-Уиллера в линейном времени )