tablica LCP

tablica LCP
tablica LCP
Typ	Szyk
Wynalezione przez	Manber i Myers (1993)
Złożoność czasowa i przestrzenna w notacji dużego O

W informatyce najdłuższa wspólna tablica prefiksów ( tablica LCP ) jest pomocniczą strukturą danych w stosunku do tablicy sufiksów . Przechowuje długości najdłuższych wspólnych przedrostków (LCP) między wszystkimi parami kolejnych sufiksów w posortowanej tablicy sufiksów.

Na przykład, jeśli A := [ aab , ab , abaab , b , baab ] jest tablicą sufiksów, najdłuższy wspólny przedrostek między A [1] = aab i A [2] = ab to a o długości 1, więc H [2] = 1 w tablicy LCP H . Podobnie LCP dla A [2] = ab i A [3] = abaab to ab , więc H [3] = 2.

przechodzenia drzewa sufiksów z góry na dół i z dołu do góry , przyspiesza dopasowywanie wzorców w tablicy sufiksów i jest warunkiem wstępnym dla skompresowanych drzew sufiksów.

Historia

Tablica LCP została wprowadzona w 1993 roku przez Udi Manbera i Gene'a Myersa wraz z tablicą sufiksów w celu poprawy czasu działania ich algorytmu wyszukiwania ciągów.

Definicja

Niech $będzie$ tablicą sufiksów łańcucha $} \ $}$ ${\ Displaystyle S = s_ {1}, s_ {2}, \ ldots s_ {n-$ o długości $displaystyle n}$ $\$ , gdzie jest wartowniczym, który jest unikalny i leksykograficznie mniejszy niż jakikolwiek inny znak. Niech ${\ Displaystyle S [i, j]}$ oznaczają podłańcuch ${\ Displaystyle S}$ w zakresie od ${\ displaystyle i}$ do ${\ displaystyle j}$ . Tak więc, jest $[A [$ sufiksem $ZA [ ja ] , n ] {$ Displaystyle $}$

Niech ${\ Displaystyle \ operatorname {lcp} (v, w)}$ oznacza długość najdłuższego wspólnego przedrostka między dwoma łańcuchami $i$ { $displaystyle w}$ . Wtedy tablica LCP $n$ tablicą liczb całkowitych o rozmiarze $]$ , że $\ Displaystyle H [$ jest nieokreślony i ${\ Displaystyle H [i] = \ operatorname {lcp} (S [A [i-1], n], S [A [i], n])}$ na każde ${\ Displaystyle 1 <i \ równoważnik n}$ . Zatem ${\ displaystyle H [i]}$ przechowuje długość najdłuższego wspólnego przedrostka leksykograficznie $.$ sufiksu i jego poprzednika w tablicy sufiksów

Różnica między tablicą LCP a tablicą sufiksów:

Tablica sufiksów: reprezentuje rangę leksykograficzną każdego sufiksu tablicy.
Tablica LCP: zawiera dopasowanie prefiksu o maksymalnej długości między dwoma kolejnymi sufiksami po ich posortowaniu leksykograficznym.

Przykład

Rozważ ciąg ${\ Displaystyle S = {\ textrm {banan \ $}}}$ :

I	1	2	3	4	5	6	7
Si]	B	A	N	A	N	A	$

i odpowiadająca jej posortowana tablica sufiksów ${\ displaystyle A}$ :

I	1	2	3	4	5	6	7
A[i]	7	6	4	2	1	5	3

Tablica sufiksów z sufiksami wypisanymi pod spodem pionowo:

I	1	2	3	4	5	6	7
A[i]	7	6	4	2	1	5	3
S[A[i], n][1]	$	A	A	A	B	N	N
S[A[i], n][2]		$	N	N	A	A	A
S[A[i], n][3]			A	A	N	$	N
S[A[i], n][4]			$	N	A		A
S[A[i], n][5]				A	N		$
S[A[i], n][6]				$	A
S[A[i], n][7]					$

Następnie tablica LCP jest konstruowana przez porównanie leksykograficznie kolejnych sufiksów w celu określenia ich najdłuższego wspólnego przedrostka: ${\ displaystyle H}$

I	1	2	3	4	5	6	7
Cześć]	nieokreślony	0	1	3	0	0	2

Na przykład ${\ Displaystyle H [4] = 3}$ to długość najdłuższego wspólnego przedrostka ${\ Displaystyle {\ tekst {ana}}}$ wspólny dla sufiksów ${\ Displaystyle A [3] = S [4,7] = {\ textrm {ana \ $}}}$ i ${\ Displaystyle A [4] = S [2,7] = {\ textrm {anana \ $}}}$ . Zauważ, że $niezdefiniowany$ , ponieważ nie ma

Wydajne algorytmy konstrukcyjne

Algorytmy konstrukcji tablic LCP można podzielić na dwie różne kategorie: algorytmy, które obliczają tablicę LCP jako produkt uboczny tablicy sufiksów oraz algorytmy, które wykorzystują już skonstruowaną tablicę sufiksów w celu obliczenia wartości LCP.

$sufiksów$ ) dostarczają algorytm do obliczania tablicy LCP wraz w Kärkkäinen i Sanders (2003) pokazują $że$ możliwa jest również modyfikacja ich algorytmu czasowego w taki sposób obliczał również tablicę LCP Kasai i in. (2001) przedstawiają pierwszy ${\ Displaystyle O (n)}$ algorytm czasu (FLAAP), który oblicza tablicę LCP na podstawie tekstu i tablicy sufiksów.

Zakładając, że każdy symbol tekstowy zajmuje jeden bajt, a każdy wpis sufiksu lub tablicy LCP zajmuje 4 bajty, główną wadą ich algorytmu jest duże zajęcie miejsca wynoszące 13 bajtów, podczas gdy oryginalne wyjście $($ sufiks $tablica$ tablica LCP) zajmuje tylko . Dlatego Manzini (2004) stworzył udoskonaloną wersję algorytmu Kasai et al. ( $lcp9$ ) ( ) i zmniejszył zajmowaną przestrzeń do . $2009$ ) przedstawiają kolejne udoskonalenie algorytmu Kasai ( -algorytm), które poprawia czas działania. Zamiast rzeczywistej tablicy LCP algorytm ten buduje permutowaną tablicę LCP (PLCP), w której wartości pojawiają się w kolejności tekstowej, a nie leksykograficznej.

Gog i Ohlebusch (2011) podają dwa algorytmy $) były$ które chociaż teoretycznie były powolne ( w praktyce

Począwszy od 2012 r., obecnie najszybszy algorytm budowy macierzy LCP w czasie liniowym pochodzi od Fischera (2011) , który z kolei jest oparty na jednym z najszybszych algorytmów konstrukcji macierzy sufiksów (SA-IS) autorstwa Nong, Zhang & Chan (2009) . Fischer & Kurpicz (2017) oparty na DivSufSort Yuty Mori jest jeszcze szybszy.

Aplikacje

Jak zauważyli Abouelhoda, Kurtz i Ohlebusch (2004), kilka problemów związanych z przetwarzaniem ciągów znaków można rozwiązać za pomocą następujących rodzajów przechodzenia przez drzewo :

przechodzenie od dołu do góry przez całe drzewo sufiksów
przechodzenie z góry na dół poddrzewa drzewa sufiksów
przechodzenie przez drzewo sufiksów za pomocą łączy sufiksów.

Kasai i in. (2001) pokazują, jak symulować przechodzenie od dołu do góry drzewa sufiksów przy użyciu tylko tablicy sufiksów i tablicy LCP. Abouelhoda, Kurtz i Ohlebusch (2004) rozszerzają tablicę sufiksów o tablicę LCP i dodatkowe struktury danych oraz opisują, w jaki sposób ta ulepszona tablica sufiksów może być wykorzystana do symulacji wszystkich trzech rodzajów przechodzenia drzewa sufiksów. Fischer i Heun (2007) zmniejszają wymagania przestrzenne dla ulepszonej tablicy sufiksów poprzez wstępne przetwarzanie tablicy LCP dla zapytań o minimalny zakres . Zatem, każdy problem, który można rozwiązać za pomocą algorytmów drzewa sufiksów, można również rozwiązać za pomocą rozszerzonej tablicy sufiksów .

$}$ wzorzec o długości $jest$ podłańcuchem łańcucha ${\$ długości $n$ ${\ Displaystyle O (m\log n)}$ zajmuje czas, jeśli używana jest tylko tablica sufiksów. Wykorzystując dodatkowo informacje LCP, to ograniczenie można poprawić do ${\ displaystyle O (m + \ log n)}$ czas. $,$ (2004) pokazują jak jeszcze bardziej poprawić ten czas pracy, aby osiągnąć czas Tak więc, używając tablicy sufiksów i informacji o tablicy LCP, na zapytanie decyzyjne można odpowiedzieć tak szybko, jak przy użyciu drzewa sufiksów .

Tablica LCP jest również istotną częścią skompresowanych drzew sufiksów, które zapewniają pełną funkcjonalność drzewa sufiksów, taką jak łącza sufiksów i zapytania o najniższego wspólnego przodka . Co więcej, $czasie$ użyć razem z tablicą sufiksów do obliczenia faktoryzacji Lempel Ziv LZ77 w

Najdłużej $powtarzający$ $tablicy$ problem z podłańcuchem łańcucha o długości można rozwiązać w sufiksów, jak $i$ $displaystyle$ i tablicę LCP. $,$ aby znaleźć jej maksymalną wartość jej indeks ${\ displaystyle i}$ gdzie jest przechowywany ${\ displaystyle v_ {max}} .$ Najdłuższy podciąg, który występuje co najmniej dwa razy, jest wtedy dany przez ${\ Displaystyle S [A [i], A [i] + v_ {max} -1]}$ .

W pozostałej części tej sekcji wyjaśniono bardziej szczegółowo dwa zastosowania tablicy LCP: W jaki sposób tablica sufiksów i tablica LCP łańcucha mogą być użyte do skonstruowania odpowiedniego drzewa sufiksów i jak można odpowiadać na zapytania LCP dotyczące dowolnych sufiksów przy użyciu zakresu minimalne zapytania w tablicy LCP.

Znajdź liczbę wystąpień wzoru

Aby znaleźć liczbę wystąpień danego ciągu ${$ długość $\ displaystyle m}$ ) w tekście (długość $\ displaystyle T$ ${$ }

$P}$ względem tablicy sufiksów, aby znaleźć pozycję początkową i końcową wszystkich wystąpień $displaystyle$ .
Teraz, aby przyspieszyć wyszukiwanie, używamy tablicy LCP, a konkretnie specjalnej wersji tablicy LCP (LCP-LR poniżej).

Problem z użyciem standardowego wyszukiwania binarnego (bez informacji LCP) polega na tym, że w każdym z porównań, które $wykonać$ wpisem suffix array, co oznacza pełne porównanie ciągów do m znaków. Więc złożoność jest ${\ Displaystyle O (m \ log N)}$ .

Tablica LCP-LR pomaga to poprawić w następujący sposób: ${\ Displaystyle O (m + \ log N)}$

W dowolnym momencie algorytmu wyszukiwania binarnego bierzemy pod uwagę, jak zwykle, zakres tablicy sufiksów i jej centralny punkt ${\ Displaystyle (L, \ kropki, R$ $}$ i zdecyduj, czy kontynuujemy nasze poszukiwania w lewym podzakresie ${\ Displaystyle (L, \ kropki, M)}$ , czy w prawym podzakresie ${\ Displaystyle (M,\kropki ,R)}$ . Aby podjąć decyzję, porównujemy z ciągiem w $displaystyle$ $M}$ . Jeśli $jest$ z $.$ nasze wyszukiwanie jest zakończone $P}$ jeśli nie, porównaliśmy już pierwsze $\$ z $displaystyle P}$ , a następnie zdecydowaliśmy, czy jest leksykograficznie mniejszy czy większy niż $displaystyle$ . Załóżmy, że wynik jest taki, że $M}$ większy niż $displaystyle$ . Tak więc w następnym kroku rozważamy i nowy punkt środkowy w środku ${\ Displaystyle (M, \ kropki,$ $}$

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

Sztuczka polega teraz na tym, że LCP-LR jest wstępnie obliczany tak, że -lookup mówi nam najdłuższy wspólny przedrostek i $displaystyle$ $M}$ $displaystyle M '$ } ${\ Displaystyle \ operatorname {lcp} (M, M ')}$ .

Wiemy już (z poprzedniego kroku), że sam ma przedrostek $\ displaystyle P$ wspólnych z: ${$ $}$ : $P} styl wyświetlania \mathrm {lcp} (P,M)=k}$ . Teraz są trzy możliwości:

Przypadek 1: ${\ Displaystyle k <\ operatorname {lcp} (M, M ')}$ $,$ tj ma mniej znaków przedrostka wspólnego z M niż M ma wspólne z M'. Oznacza to, że (k+1)-ty znak M' jest taki sam jak znak M, a ponieważ P jest leksykograficznie większy niż M, musi być także leksykograficznie większy niż M'. Więc kontynuujemy w prawej połowie (M',...,R).
Przypadek 2: ${\ Displaystyle k> \ operatorname {lcp} (M, M ')}$ $Displaystyle$ tj. ma więcej wspólnych znaków przedrostka z $M$ ${\$ niż ma wspólnego z $}$ $\ displaystyle M$ . W konsekwencji, gdybyśmy porównali do ${\ displaystyle P}$ ${\ displaystyle M'}$ , wspólny przedrostek byłby mniejszy niż $więc$ a byłby leksykograficznie większy niż $\ displaystyle M$ bez faktycznego porównania, $'}$ kontynuujemy w lewej połowie ${\ Displaystyle (M, \ kropki, M')}$ .
Przypadek 3: $\ Displaystyle k = \ operatorname {lcp} (M, M ')}$ . $Tak$ $więc$ i M 'są identyczne z pierwszymi . Aby zdecydować ${\ Displaystyle M '},$ czy będziemy kontynuować w lewej, czy w prawej połowie, wystarczy porównać do $zaczynając$ od ${\ Displaystyle (k + 1)}$ ten znak.
Kontynuujemy rekurencyjnie.

Ogólny efekt jest taki, że żaden znak nie $jest$ z jakimkolwiek znakiem tekstu więcej niż raz. Całkowita liczba porównań znaków jest ograniczona przez $log N)}$ więc całkowita złożoność jest rzeczywiście $N$ .

$dowolnymi$ obliczyć LCP-LR, aby był w stanie powiedzieć nam w dwoma wpisami tablicy sufiksów tablica LCP daje nam lcp tylko kolejnych wpisów, tj. $}$ $\ Displaystyle \ operatorname {lcp} (i-1, i)$ . Jednak ${\ Displaystyle M}$ i ${\ Displaystyle M'}$ w powyższym opisie niekoniecznie są kolejnymi wpisami.

Kluczem do tego jest uświadomienie sobie, że tylko niektóre zakresy $zaczyna$ $displaystyle (0,\dots ,N)}$ $wyszukiwania$ binarnego: Zawsze i dzieli to na środku, a następnie kontynuuje w lewo lub w prawo i ponownie dzieli tę połowę i tak dalej. Można na to spojrzeć w inny sposób: każdy wpis tablicy sufiksów występuje jako centralny punkt dokładnie jednego możliwego zakresu podczas wyszukiwania binarnego. Jest więc dokładnie N różnych zakresów ${\ Displaystyle (L \ kropki M \ kropki R)}$ , które mogą odgrywać rolę podczas wyszukiwania binarnego i wystarczy wstępnie obliczyć ${\ Displaystyle \ operatorname {lcp } (L, M)}$ i dla tych $Displaystyle$ zakresów $\ operatorname {lcp} (M, R)}$ Więc to $wstępnie$ $obliczone$ wartości, stąd LCP- ma

$wartości$ istnieje prosty algorytm rekurencyjny do obliczania $-$ LR w ze standardowej

Podsumowując:

Możliwe $_$ $LCP$ czasie _
Używanie LCP-LR podczas wyszukiwania binarnego pomaga przyspieszyć procedurę wyszukiwania od ${\ Displaystyle O (M \ log N)}$ do ${\ Displaystyle O (M + \ log N) }$ .
$,$ aby określić lewy i prawy koniec zakresu dopasowania dla a długość zakresu dopasowania odpowiada liczbie wystąpień P.

Konstrukcja drzewa sufiksów

$Displaystyle S = s_ {1}, s_ {2}, \ldots s_ {n} \ $}$ uwagę tablicę sufiksów $n$ tablicę LCP ciągu $znaków$ = długości ${\ Displaystyle n + 1} ,$ $Displaystyle$ drzewo sufiksów $O (n)}$ skonstruować w time w oparciu o następujący pomysł: Rozpocznij od częściowego drzewa sufiksów dla leksykograficznie najmniejszego sufiksu i wielokrotnie wstawiaj pozostałe sufiksy w kolejności podanej przez tablicę sufiksów.

Niech $Displaystyle 0 \$ częściowych sufiksów dla $i \ równoważnik n}$ . Ponadto $niech$ $ścieżek$ długością konkatenacji $etykiet$ do

Przypadek 1 (

{\ Displaystyle d (v) = H [i + 1]})

: Załóżmy, że przyrostki

{\ Displaystyle a \ $}

,

{\ displaystyle ana \ $}

,

\ displaystyle anana \ $}

i

{\ displaystyle banana \ $}

ciągu znaków

za

już dodane do drzewa sufiksów Następnie sufiks

do drzewa, jak pokazano

rysunku. Ścieżka po prawej stronie jest podświetlona na czerwono.

Zacznij od $korzenia$ składającego się tylko z Aby wstawić do $[i]}$ $idź$ ścieżką na prawo $]$ ostatnio wstawionego liścia $Displaystyle$ do korzenia, aż do najgłębszego węzła z ${\ displaystyle v}$ ${\ Displaystyle d (v) \ równoważnik H [i + 1]}$ został osiągnięty.

Musimy rozróżnić dwa przypadki:

${\ Displaystyle d (v) = H [i + 1]} :$ Oznacza to, że połączenie etykiet na ścieżce od korzenia do - v $\ displaystyle v}$ najdłuższy wspólny przedrostek przyrostków ${\ Displaystyle A [i]}$ i ${\ Displaystyle A [i + 1]}$ . W takim przypadku wstaw ${\ Displaystyle A [i + 1]}$ jako nowy liść ${\$ $Displaystyle v}$ i oznacz krawędź ${\ Displaystyle (v, x)}$ za pomocą ${\ Displaystyle S [A [i + 1] + H [i + 1], n]}$ . Tak więc etykieta krawędzi składa się z pozostałych znaków sufiksu
${\ Displaystyle A [i + 1]}$ , które nie są już reprezentowane przez połączenie etykiet ścieżki od korzenia do - ${\ displaystyle v}$ . Tworzy to częściowe drzewo sufiksów . ${\ Displaystyle ST_ {i + 1}}$ .

Przypadek 2 ( ${\ Displaystyle d (v) <H [i + 1]} )$ : Aby dodać sufiks ${\ Displaystyle nana \ $}$ krawędź do poprzednio wstawionego sufiksu ${\ displaystyle na \ $}$ musi zostać podzielona. Nowa krawędź nowego węzła wewnętrznego jest oznaczona najdłuższym wspólnym przedrostkiem przyrostków ${\ displaystyle na \ $$ } ${\ displaystyle nana \ $}$ . Krawędzie łączące dwa arkusze są oznaczone pozostałymi znakami sufiksu, które nie są częścią przedrostka.
${\ Displaystyle d (v) <H [i + 1]}$ : Oznacza to, że połączenie etykiet na ścieżce od korzenia do - ${\ displaystyle v}$ wyświetla mniej znaków niż najdłuższy wspólny przedrostek przyrostków i ZA $\ Displaystyle A [i]}$ i ZA $\ Displaystyle A [i + 1]}$
znaki są zawarte w etykiecie krawędzi skrajnej prawej krawędzi ${\ displaystyle v}$ . $Niech$ musimy podzielić $w$ następujący sposób: dzieckiem $.$ skrajnej prawej ścieżce

Usuń krawędź ${\ Displaystyle (v, w)}$ .
Dodaj nowy węzeł wewnętrzny $\$ nową krawędź $Displaystyle (v, y)}$ z etykietą ${\ Displaystyle S [A [i] + d (v), A [i] + H [i + 1] -1]}$ . Nowa etykieta składa się z brakujących znaki najdłuższego wspólnego przedrostka ${\ Displaystyle A [i]}$ i ${\ Displaystyle A [i + 1]}$ . Zatem połączenie etykiet ścieżki od korzenia $]$ wyświetla teraz najdłuższy wspólny przedrostek i ${\ Displaystyle A [i+1]}$ $\ Displaystyle A [i]}$ i .
Połącz się $,$ nowo utworzonym węzłem wewnętrznym $w)}$ krawędź $\ Displaystyle (y$ oznaczoną ${\ Displaystyle S [A [i] + H [i + 1], A [i] + d (w) -1]}$ . Nowa etykieta składa się z $(v, y)$ usuniętej krawędzi $y )$ które nie były używane jako etykieta krawędzi .
Dodaj za $\ Displaystyle A [i + 1]}$ jako nowy liść $y$ połącz go z nowym węzłem wewnętrznym $\ Displaystyle$ ( $} \displaystyle (y,x)}$ oznaczony jako ${\ Displaystyle S [A [i + 1] + H [i + 1], n]}$ . Zatem etykieta krawędzi $są już$ się z pozostałych znaków sufiksu, przez konkatenację etykiet korzenia do- ${\ displaystyle$ ścieżka.
Tworzy to częściowe drzewo sufiksów . ${\ Displaystyle ST_ {i + 1}}$ .

Prosty argument dotyczący amortyzacji pokazuje, że czas działania tego algorytmu jest ograniczony przez: ${\ Displaystyle O (n)$ }

Węzły, które są przemierzane w kroku, $są$ $górę$ $skrajnej$ prawej ścieżki ( oprócz ostatniego węzła usuwane ze na prawo , kiedy $dodawany$ . Te węzły nigdy nie zostaną ponownie pokonane przez wszystkie kolejne kroki ${\ displaystyle j> i}$ . Dlatego w sumie zostanie pokonanych co najwyżej węzły ${\ displaystyle 2n} .$

Zapytania LCP o dowolne sufiksy

Tablica LCP zawiera tylko $w$ najdłuższego wspólnego przedrostka każdej pary kolejnych sufiksów $tablicy$ . Jednak za pomocą odwrotnej tablicy sufiksów ( $ja$ $A^{-1}[j]=i}$ $j \$ , czyli sufiks ${\ Displaystyle S [j, n]}$ , który zaczyna się na pozycji ${\ displaystyle j}$ w ${\ displaystyle S}$ jest przechowywany na pozycji $]}$ ${\ Displaystyle A ^ {- 1} [$ $j$ w zapytaniach minimalnych o stałym zakresie czasu $możliwe$ jest długości najdłuższego wspólnego przedrostka dowolnych sufiksów w ${\ Displaystyle O (1)}$ czas.

Ze względu na porządek leksykograficzny tablicy sufiksów, każdy wspólny przedrostek sufiksów ma ${\ Displaystyle S [i, n]}$ i ${\ Displaystyle S [j, n]}$ być wspólnym przedrostkiem wszystkich $jot$ $}$ $tablicy$ sufiksów i pozycja w tablicy przyrostków ${\ Displaystyle A ^ {- 1} [j]}$ . Dlatego długość najdłuższego przedrostka, który jest wspólny dla wszystkich tych przyrostków, jest minimalną wartością w przedziale ${\ Displaystyle H [A ^ {- 1}[i]+1,A^{-1}[j]]}$ . Wartość tę można znaleźć w czasie stałym, jeśli ${\ displaystyle H}$ jest wstępnie przetwarzany dla zapytań o minimalny zakres.

${\ Displaystyle A ^ {-1} [i] <A ^ {-1} [j]}$ uwagę łańcuch o długości ${\ displaystyle$ $n}$ dwie dowolne pozycje ${\ displaystyle i, j}$ $w$ łańcuchu z , długość najdłuższego wspólnego przedrostka przyrostków ${\ Displaystyle S [i, n]}$ i ${\ Displaystyle S [j, n]}$ można obliczyć w następujący sposób: ${\ Displaystyle \ nazwa operatora {LCP} (i, j) = H [\ nazwa operatora {RMQ} _ {H} (A ^ {-1} [i] + 1, A ^ {-1} [j])]}$ .

Notatki

Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2004). „Zastępowanie drzew sufiksów ulepszonymi tablicami sufiksów” . Dziennik algorytmów dyskretnych . 2 : 53–86. doi : 10.1016/S1570-8667(03)00065-0 .
Manber, Udi; Myers, Gene (1993). „Tablice sufiksów: nowa metoda wyszukiwania ciągów on-line” . SIAM Journal o informatyce . 22 (5): 935. CiteSeerX 10.1.1.105.6571 . doi : 10.1137/0222058 . S2CID 5074629 .
Kasai, T.; Lee, G.; Arimura, H.; Arikawa, S.; Park, K. (2001). Obliczanie najdłuższego wspólnego przedrostka w czasie liniowym w tablicach sufiksów i jego zastosowania . Materiały z 12. dorocznego sympozjum na temat dopasowywania wzorów kombinatorycznych. Notatki z wykładów z informatyki. Tom. 2089. s. 181–192. doi : 10.1007/3-540-48194-X_17 . ISBN 978-3-540-42271-6 .
Ohlebusch, Enno; Fischer, Johannes; Gog, Szymon (2010). CST++ . Przetwarzanie ciągów znaków i wyszukiwanie informacji. Notatki z wykładów z informatyki. Tom. 6393. str. 322. doi : 10.1007/978-3-642-16321-0_34 . ISBN 978-3-642-16320-3 .
Kärkkäinen, Juha; Sanders, Piotr (2003). Prosta liniowa konstrukcja tablicy sufiksów roboczych . Materiały z 30. międzynarodowej konferencji na temat automatów, języków i programowania. s. 943–955 . Źródło 2012-08-28 .
Fischer, Johannes (2011). Indukowanie tablicy LCP . Algorytmy i struktury danych. Notatki z wykładów z informatyki. Tom. 6844. s. 374–385. ar Xiv : 1101.3448 . doi : 10.1007/978-3-642-22300-6_32 . ISBN 978-3-642-22299-3 .
Manzini, Giovanni (2004). Dwie sztuczki oszczędzające miejsce do obliczania macierzy LCP w czasie liniowym . Teoria algorytmów - SWAT 2004. Notatki z wykładów z informatyki. Tom. 3111. str. 372. doi : 10.1007/978-3-540-27810-8_32 . ISBN 978-3-540-22339-9 .
Kärkkäinen, Juha; Manzini, Giovanni; Puglisi, Simon J. (2009). Permutowana tablica najdłuższego wspólnego prefiksu . Dopasowywanie wzorców kombinatorycznych. Notatki z wykładów z informatyki. Tom. 5577. str. 181. doi : 10.1007/978-3-642-02441-2_17 . ISBN 978-3-642-02440-5 .
Puglisi, Simon J.; Turpin, Andrew (2008). Kompromisy czasoprzestrzenne dla obliczeń tablicowych z najdłuższym wspólnym prefiksem . Algorytmy i obliczenia . Notatki z wykładów z informatyki. Tom. 5369. str. 124. doi : 10.1007/978-3-540-92182-0_14 . ISBN 978-3-540-92181-3 .
Gog, Szymon; Ohlebusch, Enno (2011). Szybkie i lekkie algorytmy konstrukcji macierzy LCP (PDF) . Proceedings of the Workshop on Algorithm Engineering and Experiments, ALENEX 2011. s. 25–34 . Źródło 2012-08-28 .
Nong, Ge; Zhang Sen; Chan, Wai Hong (2009). Liniowa konstrukcja tablicy sufiksów przez prawie czyste sortowanie indukowane . Konferencja dotycząca kompresji danych 2009. P. 193. doi : 10.1109/DCC.2009.42 . ISBN 978-0-7695-3592-0 .
Fischer, Johannes; Heun, Volker (2007). Nowa zwięzła reprezentacja informacji RMQ i ulepszeń w rozszerzonej tablicy sufiksów . Kombinatoryka, algorytmy, metodologie probabilistyczne i eksperymentalne. Notatki z wykładów z informatyki. Tom. 4614. str. 459. doi : 10.1007/978-3-540-74450-4_41 . ISBN 978-3-540-74449-8 .
Chen, G.; Puglisi, SJ; Smyth, WF (2008). „Faktoryzacja Lempela-Ziva przy użyciu mniejszej ilości czasu i miejsca”. Matematyka w informatyce . 1 (4): 605. doi : 10.1007/s11786-007-0024-4 . S2CID 1721891 .
Crochemore, M.; Ilie, L. (2008). „Obliczanie najdłuższego poprzedniego czynnika w czasie liniowym i aplikacjach”. Listy dotyczące przetwarzania informacji . 106 (2): 75. CiteSeerX 10.1.1.70.5720 . doi : 10.1016/j.ipl.2007.10.006 . S2CID 5492217 .
Crochemore, M.; Ilie, L.; Smyth, WF (2008). Prosty algorytm obliczania faktoryzacji Lempla Ziva . Konferencja dotycząca kompresji danych (dcc 2008). P. 482. doi : 10.1109/DCC.2008.36 . hdl : 20.500.11937/5907 . ISBN 978-0-7695-3121-2 .
Sadakane, K. (2007). „Skompresowane drzewa sufiksów z pełną funkcjonalnością” . Teoria systemów komputerowych . 41 (4): 589–607. CiteSeerX 10.1.1.224.4152 . doi : 10.1007/s00224-006-1198-x . S2CID 263130 .
Fischer, Johannes; Mäkinen, Veli; Navarro, Gonzalo (2009). „Szybsze skompresowane drzewa sufiksów ograniczone entropią” . Informatyka teoretyczna . 410 (51): 5354. doi : 10.1016/j.tcs.2009.09.012 .
Fischer, Johannes; Kurpicz, Florian (5 października 2017). „Demontaż DivSufSort” . Materiały Praskiej Konferencji Stringologicznej 2017 . ar Xiv : 1710.01896 .

Linki zewnętrzne

Lustro implementacji ad-hoc kodu opisanego w Fischer (2011)
SDSL: Succinct Data Structure Library — udostępnia różne implementacje tablic LCP, struktury obsługi zapytań o minimalny zasięg (RMQ) i wiele innych zwięzłych struktur danych
Emulacja przechodzenia drzewa sufiksów od dołu do góry przy użyciu tablicy sufiksów i tablicy LCP (Java)
Projekt indeksowania tekstu (konstrukcja drzew sufiksów w czasie liniowym, tablic sufiksów, tablicy LCP i transformacji Burrowsa-Wheelera)