LCP-массив

LCP-массив
LCP-массив
Тип	Множество
Изобретён	Манбер и Майерс (1993)
Временная сложность и пространственная сложность в большой записи O

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

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

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

История

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

Определение

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

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

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

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

Пример

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

я	1	2	3	4	5	6	7
С [я]	б	а	н	а	н	а	$

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

я	1	2	3	4	5	6	7
А[я]	7	6	4	2	1	5	3

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

я	1	2	3	4	5	6	7
А[я]	7	6	4	2	1	5	3
С[А[i], n][1]	$	а	а	а	б	н	н
С[А[i], n][2]		$	н	н	а	а	а
С[А[i], n][3]			а	а	н	$	н
С[А[i], n][4]			$	н	а		а
С[А[i], n][5]				а	н		$
С[А[и], п][6]				$	а
С[А[и], п][7]					$

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

я	1	2	3	4	5	6	7
Привет]	неопределенный	0	1	3	0	0	2

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

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

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

Манбер и Майерс (1993) предлагают алгоритм для вычисления массива LCP вместе с массивом суффиксов в $O(n\log n)$ время. Кярккяйнен и Сандерс (2003) показывают, что их также можно изменить. $O(n)$ временной алгоритм, позволяющий также вычислять массив LCP. Касаи и др. (2001) представляют первый $O(n)$ алгоритм времени (FLAAP), который вычисляет массив LCP по тексту и массиву суффиксов.

Если предположить, что каждый текстовый символ занимает один байт, а каждая запись суффикса или массива LCP — 4 байта, то основным недостатком их алгоритма является большой объем занимаемого пространства. $13n$ байт, в то время как исходный вывод (текст, массив суффиксов, массив LCP) занимает только $9n$ байты. Поэтому Манзини (2004) создал усовершенствованную версию алгоритма Касаи и др. (2001) (lcp9) и сократили занимаемую площадь до $9n$ байты. Кярккяйнен, Манзини и Пуглиси (2009) предлагают еще одно усовершенствование алгоритма Касаи ( $\Phi$ -алгоритм), который улучшает время работы. Вместо фактического массива LCP этот алгоритм создает перестановочный массив LCP (PLCP), в котором значения отображаются в текстовом, а не в лексикографическом порядке.

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

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

Приложения

Как отметили Абуэльхода, Курц и Олебуш (2004), некоторые проблемы обработки строк можно решить с помощью следующих видов обхода дерева :

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

Касаи и др. (2001) снизу вверх, показывают, как моделировать обход суффиксного дерева используя только массив суффиксов и массив LCP. Абуэлхода, Курц и Олебуш (2004) расширяют массив суффиксов с помощью массива LCP и дополнительных структур данных и описывают, как этот расширенный массив суффиксов можно использовать для моделирования всех трех видов обхода суффиксного дерева. Фишер и Хойн (2007) сокращают требования к пространству расширенного массива суффиксов за счет предварительной обработки массива LCP для запросов минимального диапазона . Таким образом, каждая проблема, которую можно решить с помощью алгоритмов суффиксного дерева, также может быть решена с использованием расширенного массива суффиксов . ^{[ 2 ]}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

Ссылки

Абуэльхода, Мохамед Ибрагим; Курц, Стефан; Олебуш, Энно (2004). «Замена суффиксных деревьев расширенными суффиксными массивами» . Журнал дискретных алгоритмов . 2 : 53–86. дои : 10.1016/S1570-8667(03)00065-0 .
Манбер, Уди; Майерс, Джин (1993). «Суффиксные массивы: новый метод поиска строк в Интернете». SIAM Journal по вычислительной технике . 22 (5): 935. CiteSeerX 10.1.1.105.6571 . дои : 10.1137/0222058 . S2CID 5074629 .
Касаи, Т.; Ли, Г.; Аримура, Х.; Арикава, С.; Парк, К. (2001). Вычисление самого длинного общего префикса в суффиксных массивах за линейное время и его приложения . Материалы 12-го ежегодного симпозиума по комбинаторному сопоставлению с образцом. Конспекты лекций по информатике. Том. 2089. стр. 181–192. дои : 10.1007/3-540-48194-X_17 . ISBN 978-3-540-42271-6 .
Олебуш, Энно; Фишер, Йоханнес; Гог, Саймон (2010). КСТ++ . Обработка строк и поиск информации. Конспекты лекций по информатике. Том. 6393. с. 322. дои : 10.1007/978-3-642-16321-0_34 . ISBN 978-3-642-16320-3 .
Кярккяйнен, Юха; Сандерс, Питер (2003). Простое построение массива суффиксов линейной работы . Материалы 30-й международной конференции «Автоматы, языки и программирование». стр. 943–955 . Проверено 28 августа 2012 г.
Фишер, Йоханнес (2011). Стимуляция LCP-массива . Алгоритмы и структуры данных. Конспекты лекций по информатике. Том. 6844. стр. 374–385. arXiv : 1101.3448 . дои : 10.1007/978-3-642-22300-6_32 . ISBN 978-3-642-22299-3 .
Манзини, Джованни (2004). Два приема экономии места при вычислении массива LCP за линейное время . Теория алгоритмов - SWAT 2004. Конспекты лекций по информатике. Том. 3111. с. 372. дои : 10.1007/978-3-540-27810-8_32 . ISBN 978-3-540-22339-9 .
Кярккяйнен, Юха; Манзини, Джованни; Пуглиси, Саймон Дж. (2009). Перестановочный массив самых длинных общих префиксов . Комбинаторное сопоставление с образцом. Конспекты лекций по информатике. Том. 5577. с. 181. дои : 10.1007/978-3-642-02441-2_17 . ISBN 978-3-642-02440-5 .
Пуглиси, Саймон Дж.; Терпин, Эндрю (2008). Компромиссы пространства и времени для вычисления массива с самым длинным общим префиксом . Алгоритмы и вычисления. Конспекты лекций по информатике. Том. 5369. с. 124. дои : 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. дои : 10.1109/DCC.2009.42 . ISBN 978-0-7695-3592-0 .
Фишер, Йоханнес; Хойн, Волкер (2007). Новое краткое представление RMQ-информации и улучшения расширенного массива суффиксов . Комбинаторика, алгоритмы, вероятностные и экспериментальные методологии. Конспекты лекций по информатике. Том. 4614. с. 459. дои : 10.1007/978-3-540-74450-4_41 . ISBN 978-3-540-74449-8 .
Чен, Г.; Пуглиси, С.Дж.; Смит, ВФ (2008). «Факторизация Лемпеля – Зива с использованием меньшего времени и пространства». Математика в информатике . 1 (4): 605. дои : 10.1007/s11786-007-0024-4 . S2CID 1721891 .
Крочемор, М.; Илие, Л. (2008). «Вычисление самого длинного предыдущего фактора в линейном времени и приложениях». Письма об обработке информации . 106 (2): 75. CiteSeerX 10.1.1.70.5720 . дои : 10.1016/j.ipl.2007.10.006 . S2CID 5492217 .
Крочемор, М.; Илие, Л.; Смит, ВФ (2008). Простой алгоритм вычисления факторизации Лемпеля-Зива . Конференция по сжатию данных (dcc, 2008 г.). п. 482. дои : 10.1109/DCC.2008.36 . hdl : 20.500.11937/5907 . ISBN 978-0-7695-3121-2 .
Садакане, К. (2007). «Сжатые суффиксные деревья с полной функциональностью». Теория вычислительных систем . 41 (4): 589–607. CiteSeerX 10.1.1.224.4152 . дои : 10.1007/s00224-006-1198-x . S2CID 263130 .
Фишер, Йоханнес; Мякинен, Вели; Наварро, Гонсало (2009). «Быстрые сжатые суффиксные деревья, ограниченные энтропией» . Теоретическая информатика . 410 (51): 5354. doi : 10.1016/j.tcs.2009.09.012 .
Фишер, Йоханнес; Курпиц, Флориан (5 октября 2017 г.). «Демонтаж ДивСуфСорта». Материалы Пражской конференции по стрингологии 2017 . arXiv : 1710.01896 .

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

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

[FOOTNOTEKasaiLeeArimuraArikawa2001-1] Касаи и др. 2001 .

[FOOTNOTEAbouelhodaKurtzOhlebusch2004-2] Jump up to: ^а ^б ^с Абуэльхода, Курц и Олебуш, 2004 г.

[FOOTNOTEManberMyers1993-3] Jump up to: ^а ^б ^с ^д ^и Манбер и Майерс, 1993 .

[FOOTNOTEOhlebuschFischerGog2010-4] Олебуш, Фишер и Гог 2010 .

[FOOTNOTESadakane2007-5] Садакане 2007 .

[FOOTNOTEFischerMäkinenNavarro2009-6] Фишер, Мякинен и Наварро 2009 .

[FOOTNOTECrochemoreIlie2008-7] Крочемор и Илие 2008 .

[FOOTNOTECrochemoreIlieSmyth2008-8] Крочемор, Илие и Смит 2008 .

[FOOTNOTEChenPuglisiSmyth2008-9] Чен, Пуглиси и Смит 2008 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]