LCP массив

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

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

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

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

Дополняя массив суффиксов с массивом LCP позволяет эффективно моделировать сверху вниз и снизу вверх обходы по дереву суффиксов , ^{[1] [2]} ускоряет сопоставление с образцом на суффиксе массиве ^[3] и является необходимым условием для сжатого суффикса деревья. ^[4]

История [ править ]

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

Определение [ править ]

Пусть будет суффиксным массивом строки длины , где - контрольная буква, уникальная и лексикографически меньшая, чем любой другой символ. Позвольте обозначить подстроку в диапазоне от до . Таким образом, это 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 = банан \ $}$

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

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

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

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

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

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

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

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

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

По состоянию на 2012 год ^[update]самый быстрый в настоящее время алгоритм построения массива 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 для запросов минимального диапазона . Таким образом, каждая проблема, которую можно решить с помощью алгоритмов дерева суффиксов, также может быть решена с помощью расширенного массива суффиксов. ^[2]

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

Массив LCP также является неотъемлемой частью сжатых деревьев суффиксов, которые обеспечивают полную функциональность дерева суффиксов, такую ​​как ссылки суффиксов и запросы наименьшего общего предка . ^{[5] [6]} Кроме того, его можно использовать вместе с массивом суффиксов для вычисления факторизации Лемпеля-Зива LZ77 во времени. ^{[2] [7] [8] [9]}${\displaystyle O(n)}$

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

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

Найдите количество вхождений шаблона [ править ]

Эта статья может потребовать очистки, чтобы соответствовать стандартам качества Википедии . Конкретная проблема заключается в следующем: этот раздел представляет собой прямую копию ответа StackOverflow, поэтому имеет форму ответа на вопрос. Пожалуйста, помогите улучшить эту статью, если можете. ( Июнь 2016 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

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

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

 М ...... М '...... R | мы знаем: lcp (P, M) == к

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

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

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

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

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

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

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

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

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

Построение суффиксного дерева [ править ]

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

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

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

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

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

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

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

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

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

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

Массив LCP содержит только длину самого длинного общего префикса каждой пары последовательных суффиксов в массиве суффиксов . Однако с помощью массива обратных суффиксов ( т. Е. Суффикс, который начинается с позиции in , сохраняется в позиции in ) и минимальных запросов диапазона с постоянным временем on , можно определить длину самого длинного общего префикса произвольных суффиксов. в время.${\displaystyle H}$${\displaystyle A}$${\displaystyle A^{-1}}$${\displaystyle A[i]=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[i,n]}$${\displaystyle S[j,n]}$${\displaystyle i}$${\displaystyle A^{-1}[i]}$${\displaystyle j}$${\displaystyle A^{-1}[j]}$${\displaystyle H[A^{-1}[i]+1,A^{-1}[j]]}$${\displaystyle H}$

При этом данная строка длины и две произвольные позиции в строке с , длина самого длинного общего префикса суффиксов и может быть вычислено следующим образом : .${\displaystyle S}$${\displaystyle n}$${\displaystyle i,j}$${\displaystyle S}$${\displaystyle A^{-1}[i]<A^{-1}[j]}$${\displaystyle S[i,n]}$${\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 .
• 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 .CS1 maint: ref=harv (link)
• Фишер, Йоханнес (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 .CS1 maint: ref=harv (link)
• Нонг, Ге; Чжан, Сен; Чан, Вай Хун (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 .
• 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-х .
• Фишер, Йоханнес; Мякинен, Вели; Наварро, Гонсало (2009). «Более быстрые сжатые суффиксные деревья с ограниченной энтропией». Теоретическая информатика . 410 (51): 5354. DOI : 10.1016 / j.tcs.2009.09.012 .
• Фишер, Йоханнес; Курпиц, Флориан (5 октября 2017 г.). «Разборка DivSufSort». Труды Пражской Stringology Conference 2017 . arXiv : 1710.01896 .

Внешние ссылки [ править ]

Викискладе есть медиафайлы, связанные с массивом LCP .

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