Tabel med suffikser

En suffikstabel (undertiden kaldet en suffikstabel på engelsk : suffiks array ) er en datastruktur, der anvendes inden for datalogi og mere specifikt i ordkombinatorik og i bioinformatik . For et givet ord indeholder matrixen en liste over heltal, der svarer til startpositionerne for ordets suffikser, når de er sorteret i leksikografisk rækkefølge.

Formålet med tabellen er at tilvejebringe de samme søgefaciliteter som et suffiks-træ og samtidig reducere den anvendte hukommelsesstørrelse. Strukturen blev introduceret i 1990 af Manber og Myers og genopdaget i 1992.

Definition

Lad være et alfabet af endelig størrelse og en leksikografisk rækkefølge på dette alfabet. ${\ mathcal {A}}$

Lad der være et ord i alfabetet . Dette længdeord har suffikser. Disse suffikser kan ordnes i stigende grad i henhold til den leksikografiske rækkefølge. Hvert suffiks svarer til en startposition i ordet ; for eksempel er suffikset ved position 0 selve ordet . Når suffikserne er ordnet, danner deres tilsvarende startpositioner suffikstabellen . $w$ ${\ mathcal {A}}$ ${\ displaystyle | w | = n}$ $ikke$ $w$ $w$

Eksempel

Tag ordet = abracadabra. Dette ord , af længde 11, har de 11 suffikser abracadabra, bracadabra, racadabra, ..., a. Hvert af disse 11 suffikser kan arrangeres i stigende rækkefølge i leksikografisk rækkefølge. I nedenstående tabel er suffikserne anført i stigende rækkefølge. Den anden kolonne angiver startpositionen for suffikset i ordet: $w$ $w$

Suffiks	Startposition
på	10
abra	7
abracadabra	0
acadabra	3
adabra	5
bh	8
bracadabra	1
kadabra	4
dabra	6
ra	9
racadabra	2

Tabellen med suffikser T dannet ud fra ordet w består af startpositionerne for de 11 suffikser arrangeret i stigende leksikografisk rækkefølge, dvs.

T = {10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2}.

brug

Suffikstabellen bruges som et indeks til søgning efter mønstre i en tekst. At finde et mønster i en tekst svarer til at finde mønsteret som et præfiks for tekstsuffikser.

Tabellen er bygget ud fra teksten. Tabellen indeholder startpositionerne for tekstsuffikserne. Imidlertid er disse suffikser arrangeret i leksikografisk rækkefølge under konstruktionen af tabellen, derfor har suffikser, der starter med det søgte mønster, deres positioner i på hinanden følgende felter i tabellen. Det er dog oprindeligt ikke muligt at vide i hvilket afsnit af tabellen denne klynge af søgte positioner findes. Algoritmen bruger derfor en todelt søgning til at identificere denne klynge.

Algoritmiske aspekter

Kompleksitet

To kompleksiteter skal overvejes: det, der vedrører sorteringen af suffikser efter den leksikografiske rækkefølge (under opbygningen af tabellen), og det, der vedrører søgen efter et mønster ved dikotomi.

Suffiks sortering er en algoritme, der naivt tager gennemsnitlige sammenligninger (hvor er ordets længde), og hvor hver suffiks sammenligning tager det værste tilfælde . Så naiv sortering af suffikser tager i værste fald lang tid . Flere algoritmer forbedrer denne bund og tilbyder kompleksitet i størrelsesordenen eller endda . $O (n \ log n)$ $ikke$ $Vi)$ $O (n ^ {2} \ log n)$ $O (n \ log n)$ $\ Theta (n)$

( Li, Li og Huo 2016 ) gav den første kompleksitetssuffiks-array-konstruktionsalgoritme, der er optimal både tid og sted, hvor "på plads" betyder, at algoritmen kun har brug for plads yderligere ud over inputstrengen og output-suffiks-arrayet. En anden lineær algoritme er givet i 2016 af Uwe Baier. Ifølge monografien Construction of Fundamental Data Structures for Strings er algoritmen ( Li, Li og Huo 2016 ) sammenhængende med to algoritmer fra Nong et al. i 2009 (kaldet SAIS) og Nong i 2013 (kaldet SACA-K), som også er lineære. En Keisuke Goto-algoritme har den samme optimale kompleksitet (i tid og på plads). $Vi)$ $O (1)$

Kompression

For at reducere den plads, der optages af et suffiksarray, blev der oprettet to typer komprimerede datastrukturer : komprimerede suffiksarrays (en) og FM-indekset (baseret på Burrows-Wheeler-transformationen ).

Online

Bibliografi

Udi Manber og Gene Myers , "Suffix arrays: a new method for on-line string søgninger" , i First Annual ACM-SIAM Symposium on Discrete Algorithms ,1990( online præsentation ) , s. 319-327.
Gaston Gonnet , Ricardo Baeza-Yates og Tim Snider , "Nye indekser til tekst: PAT-træer og PAT-arrays" , i William B. Frakes og Ricardo A. Baeza-Yates (redaktører), Informationssøgning: datastrukturer og algoritmer , Prentice- Hall ,1992, s. 66–82
Zhize Li , Jian Li og Hongwei Huo , "Optimal sortering af suffikser på stedet ", i Proceedings of the 25th International Symposium on String Processing and Information Retrieval (SPIRE) , 268-284, koll. "Forelæsningsnotater inden for datalogi" ( nr . 11147),2016( ISBN 978-3-030-00478-1 , DOI 10.1007 / 978-3-030-00479-8_22 , arXiv 1610.08305 ) , s. 268-284

Reference

( Manber og Myers 1990 )
( Gonnet, Baeza-Yates og Snider 1992 )
Vi ignorerer suffikset med længde 0: det tomme ord.
(in) N. Jesper Larson og Kunihiko Sadakane , " Hurtigere suffiksortering " , Theoretical Computer Science , vol. 387, nr . 3,2007, s. 258-272 ( DOI 10.1016 / j.tcs.2007.07.017 , læs online ).
Uwe Baier, "Sortering af suffikser med lineær tid - En ny tilgang til konstruktion af suffiksarray" , i Roberto Grossi og Moshe Lewenstein (red.), 27. årlige symposium om kombinationsmønstertilpasning , Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, koll. "Leibniz International Proceedings in Informatics (LIPIcs)" ( nr . 54),2016( ISBN 978-3-95977-012-5 , DOI 10.4230 / LIPIcs.CPM.2016.23 , læs online ) , s. 123: 1-23: 12.
Felipe A. Louza, Simon Gog og Guilherme P. Telles, konstruktion af grundlæggende datastrukturer til strenge , Springer, coll. "Springer Briefs in Computer Science",2020, ix + 104 s. ( ISBN 978-3-030-55107-0 og 978-3-030-55108-7 , DOI 10.1007 / 978-3-030-55108-7 ).
Keisuke Goto, “Optimal tid og rumkonstruktion af suffiksarrays og LCP-arrays for heltal-alfabeter” , i Proc. Prag Stringology Conference ,2019, 111-125 s. ( læs online ).

Relaterede artikler

eksterne links