Tabell over suffikser

En suffiks-tabell (noen ganger kalt en suffiks-tabell, på engelsk : suffiks array ) er en datastruktur som brukes i informatikk , og mer spesielt i ordkombinatorikk og i bioinformatikk . For et gitt ord inneholder matrisen en liste over heltall som tilsvarer startposisjonene til ordets suffikser, når de er sortert i leksikografisk rekkefølge.

Formålet med tabellen er å tilby de samme søkefasilitetene som et suffiks-tre mens du reduserer minnestørrelsen som brukes. Strukturen ble introdusert i 1990 av Manber og Myers og gjenoppdaget i 1992.

Definisjon

La være et alfabet av endelig størrelse og en leksikografisk rekkefølge på dette alfabetet. ${\ mathcal {A}}$

La det være et ord i alfabetet . Dette lengdeordet har suffikser. Disse suffiksen kan ordnes på en økende måte i henhold til leksikografisk rekkefølge. Hvert suffiks tilsvarer en startposisjon i ordet ; for eksempel er suffikset i posisjon 0 selve ordet . Når suffiksen er bestilt, danner de tilsvarende startposisjonene suffikstabellen . $w$ ${\ mathcal {A}}$ ${\ displaystyle | w | = n}$ $ikke$ $w$ $w$

Eksempel

Ta ordet = abracadabra. Dette ordet , med lengde 11, har de 11 suffiksene abracadabra, bracadabra, racadabra, ..., a. Hver av disse 11 suffiksene kan ordnes i økende rekkefølge i leksikografisk rekkefølge. I tabellen nedenfor er suffiksene oppført i stigende rekkefølge. Den andre kolonnen indikerer startposisjonen for suffikset i ordet: $w$ $w$

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

Tabellen over suffikser T dannet fra ordet w består av startposisjonene til de 11 suffiksen arrangert i økende leksikografisk rekkefølge, dvs.

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

bruk

Suffikstabellen brukes som en indeks for å søke etter mønstre i en tekst. Å finne et mønster i en tekst tilsvarer å finne mønsteret som et prefiks av tekstsuffikser.

Tabellen er bygget fra teksten. Tabellen inneholder startposisjonene for tekstsuffiksene. Imidlertid er disse suffiksene ordnet i leksikografisk rekkefølge under konstruksjonen av tabellen, derfor har suffiksen som starter med det søkte mønsteret sine posisjoner i påfølgende ruter i tabellen. Imidlertid er det i utgangspunktet ikke mulig å vite i hvilken del av tabellen denne klyngen av etterspurte posisjoner er funnet. Algoritmen vil derfor bruke et todelt søk for å identifisere denne klyngen.

Algoritmiske aspekter

Kompleksitet

To kompleksiteter skal vurderes: det som gjelder sortering av suffikser i henhold til leksikografisk rekkefølge (under konstruksjonen av tabellen), og det som gjelder søket etter et mønster ved dikotomi.

Suffiks sortering er en algoritme som naivt tar gjennomsnittlige sammenligninger (hvor er ordlengden), og hvor hver suffiks sammenligning tar verste fall . Så naivt sortering av suffikser tar i verste fall lang tid . Flere algoritmer forbedrer denne grensen, og tilbyr kompleksitet i størrelsesorden , eller til og med . $O (n \ log n)$ $ikke$ $Vi)$ $O (n ^ {2} \ log n)$ $O (n \ log n)$ $\ Theta (n)$

( Li, Li og Huo 2016 ) ga den første kompleksitetssuffiks array konstruksjonsalgoritme som er optimal både i tid og på plass, der "på plass" betyr at algoritmen bare trenger plass ekstra utover inngangsstrengen og output suffiks array. En annen lineær algoritme er gitt i 2016 av Uwe Baier. I følge monografien Construction of Fundamental Data Structures for Strings , er algoritmen til ( Li, Li og Huo 2016 ) sammenhengende med to algoritmer fra Nong et al. i 2009 (kalt SAIS) og Nong i 2013 (kalt SACA-K) som også er lineære. En Keisuke Goto-algoritme har samme optimale kompleksitet (i tid og på plass). $Vi)$ $O (1)$

Kompresjon

For å redusere plassen som er tatt opp av et suffiksarray, ble det opprettet to typer komprimerte datastrukturer : komprimerte suffiksarrayer (en) og FM-indeksen (basert på Burrows-Wheeler-transformasjonen ).

på nett

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 presentasjon ) , s. 319-327.
Gaston Gonnet , Ricardo Baeza-Yates og Tim Snider , “Nye indekser for tekst: PAT-trær og PAT-matriser” , i William B. Frakes og Ricardo A. Baeza-Yates (redaktører), Informasjonsinnhenting: datastrukturer og algoritmer , Prentice- Hall ,1992, s. 66–82
Zhize Li , Jian Li og Hongwei Huo , “Optimal sortering av suffiks på stedet”, i Proceedings of the 25th International Symposium on String Processing and Information Retrieval (SPIRE) , 268–284, koll. "Forelesningsnotater i Computer Science" ( n o 11147)2016( ISBN 978-3-030-00478-1 , DOI 10.1007 / 978-3-030-00479-8_22 , arXiv 1610.08305 ) , s. 268–284

Henvisning

( Manber og Myers 1990 )
( Gonnet, Baeza-Yates og Snider 1992 )
Vi ignorerer suffikset av lengde 0: den tomme ord.
(i) N. Jesper Larson og Kunihiko Sadakane , " Raskere suffiksortering ," Theoretical Computer Science , vol. 387, n o 3,2007, s. 258-272 ( DOI 10.1016 / j.tcs.2007.07.017 , les online ).
Uwe Baier, “Lineær tidssuffiksortering - en ny tilnærming for suffiksarrangementkonstruksjon” , i Roberto Grossi og Moshe Lewenstein (red.), 27. årlige symposium om kombinatorisk mønstermatching , Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, koll. "Leibniz Internasjonal Proceedings i Informatics (LIPIcs)" ( n o 54),2016( ISBN 978-3-95977-012-5 , DOI 10.4230 / LIPIcs.CPM.2016.23 , les online ) , s. 123: 1-23: 12.
Felipe A. Louza, Simon Gog og Guilherme P. Telles, Construction of Fundamental Data Structures for Strings , 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 romkonstruksjon av suffiksarrayer og LCP-arrays for heltallalfabet” , i Proc. Praha Stringology Conference ,2019, 111–125 s. ( les online ).

Relaterte artikler

Eksterne linker