Suffix array - Suffix array

Suffix -array
Type	Array
Opfundet af	Manber & Myers (1990)
Tidskompleksitet; i stor O -notation

Inden for datalogi er et suffiks array et sorteret array af alle suffikser i en streng . Det er en datastruktur, der blandt andet bruges i fuldtekstindekser, datakomprimeringsalgoritmer og bibliometriområdet .

Suffix -arrays blev introduceret af Manber & Myers (1990) som et simpelt, rumeffektivt alternativ til endetræer . De var uafhængigt blevet opdaget af Gaston Gonnet i 1987 under navnet PAT array ( Gonnet, Baeza-Yates & Snider 1992 ).

Li, Li & Huo (2016) gav den første tidssuffiks-array-konstruktionsalgoritme på stedet, der er optimal både i tid og rum, hvor in-place betyder, at algoritmen kun har brug for ekstra plads ud over inputstrengen og output-suffiks-arrayet. ${\ displaystyle {\ mathcal {O}} (n)}$ ${\ displaystyle {\ mathcal {O}} (1)}$

Enhanced suffix arrays (ESA'er) er suffiksarrays med ekstra tabeller, der gengiver fuldfunktionaliteten af suffixtræer, der bevarer samme tid og hukommelseskompleksitet. Endelsen array for en delmængde af alle suffikser i en streng kaldes sparsomt suffiks array . Flere probabilistiske algoritmer er blevet udviklet for at minimere den ekstra hukommelsesforbrug inklusive en optimal tids- og hukommelsesalgoritme.

Definition

Lad være en -streng og lad betegne delstrengen fra alt til inklusiv. ${\ displaystyle S = S [1] S [2] ... S [n]}$ ${\ textstyle n}$ ${\ displaystyle S [i, j]}$ ${\ displaystyle S}$ ${\ displaystyle i}$ ${\ displaystyle j}$

Endelsen vifte af nu defineret til at være et array af heltal leverer udgangspositioner suffikser af i leksikografisk rækkefølge . Dette betyder, en post indeholder startpositionen af th mindste suffiks i og dermed for alle : . ${\ displaystyle A}$ ${\ displaystyle S}$ ${\ displaystyle S}$ ${\ displaystyle A [i]}$ ${\ displaystyle i}$ ${\ displaystyle S}$ ${\ displaystyle 1 <i \ leq n}$ ${\ displaystyle S [A [i-1], n] <S [A [i], n]}$

Hver endelse af shows op i præcis én gang. Suffikser er simple strenge. Disse strenge sorteres (som i en papirordbog), før deres startpositioner (heltalsindeks) gemmes i . ${\ displaystyle S}$ ${\ displaystyle A}$ ${\ displaystyle A}$

Eksempel

Overvej teksten = der skal indekseres: ${\ displaystyle S}$ banana$

jeg	1	2	3	4	5	6	7
${\ displaystyle S [i]}$	b	-en	n	-en	n	-en	$

Teksten slutter med det særlige vagtpostbrev, $der er unikt og leksikografisk mindre end nogen anden karakter. Teksten har følgende suffikser:

Tillæg	jeg
banan $	1
anana $	2
nana $	3
ana $	4
efter $	5
en $	6
$	7

Disse suffikser kan sorteres i stigende rækkefølge:

Tillæg	jeg
$	7
en $	6
ana $	4
anana $	2
banan $	1
efter $	5
nana $	3

Suffiksarrayet indeholder startpositionerne for disse sorterede suffikser: ${\ displaystyle A}$

jeg =	1	2	3	4	5	6	7
${\ displaystyle A [i]}$ =	7	6	4	2	1	5	3

Suffiksarrayet med suffikserne skrevet lodret nedenunder for klarhedens skyld:

jeg =	1	2	3	4	5	6	7
${\ displaystyle A [i]}$ =	7	6	4	2	1	5	3
1	$	-en	-en	-en	b	n	n
2		$	n	n	-en	-en	-en
3			-en	-en	n	$	n
4			$	n	-en		-en
5				-en	n		$
6				$	-en
7					$

Så indeholder for eksempel værdien 4, og refererer derfor til suffikset, der starter ved position 4 indenfor , som er suffikset . ${\ displaystyle A [3]}$ ${\ displaystyle S}$ ana$

Korrespondance til suffiks træer

Suffix -arrays er nært beslægtet med suffix -træer :

Suffix-arrays kan konstrueres ved at udføre en dybde-første traversal af et suffix-træ. Suffiksarrayet svarer til bladetiketterne i den rækkefølge, hvor disse besøges under gennemgangen, hvis kanter besøges i leksikografisk rækkefølge af deres første karakter.
Et endetræ kan konstrueres i lineær tid ved hjælp af en kombination af endelse array og LCP array . For en beskrivelse af algoritmen, se det tilsvarende afsnit i LCP -arrayartiklen .

Det er blevet vist, at hver endelse -træ -algoritme systematisk kan erstattes med en algoritme, der bruger et suffiks -array, der er forbedret med yderligere information (f.eks. LCP -arrayet ) og løser det samme problem på samme tidskompleksitet. Fordele ved suffiksarrays frem for suffixtræer inkluderer forbedrede pladsbehov, enklere lineære tidsopbygningsalgoritmer (f.eks. Sammenlignet med Ukkonens algoritme ) og forbedret cachelokalitet.

Pladseffektivitet

Suffix -arrays blev introduceret af Manber & Myers (1990) for at forbedre pladsbehovet for suffix -træer : Suffix -arrays gemmer heltal. Forudsat at et helt tal kræver bytes, kræver et suffiksarray i alt bytes. Dette er betydeligt mindre end de bytes, der kræves af en omhyggelig implementering af suffiksetræ. ${\ displaystyle n}$ ${\ displaystyle 4}$ ${\ displaystyle 4n}$ ${\ displaystyle 20n}$

I visse applikationer kan pladsbehovet for suffiksarrays dog stadig være uoverkommeligt. Analyseret i bits kræver et suffiks array plads, mens den originale tekst over et alfabet i størrelse kun kræver bits. For et menneskeligt genom med og endelsen array ville derfor optage omkring 16 gange mere hukommelse end selve genomet. ${\ displaystyle {\ mathcal {O}} (n \ log n)}$ ${\ displaystyle \ sigma}$ ${\ displaystyle {\ mathcal {O}} (n \ log \ sigma)}$ ${\ displaystyle \ sigma = 4}$ ${\ displaystyle n = 3,4 \ gange 10^{9}}$

Sådanne uoverensstemmelser motiverede en tendens til komprimerede suffiksarrays og BWT- baserede komprimerede fuldtekstindekser såsom FM-indekset . Disse datastrukturer kræver kun plads inden for tekstens størrelse eller endnu mindre.

Konstruktion algoritmer

Et endetræ kan bygges ind og kan konverteres til et suffiks array ved at krydse trædybden-først også i , så der findes algoritmer, der kan bygge et suffiks array i . ${\ displaystyle {\ mathcal {O}} (n)}$ ${\ displaystyle {\ mathcal {O}} (n)}$ ${\ displaystyle {\ mathcal {O}} (n)}$

En naiv tilgang til at konstruere et suffiks array er at bruge en sammenligningsbaseret sorteringsalgoritme . Disse algoritmer kræver sammenligning af suffikser, men en suffiks sammenligning kører i tide, så den samlede driftstid af denne tilgang er . ${\ displaystyle {\ mathcal {O}} (n \ log n)}$ ${\ displaystyle {\ mathcal {O}} (n)}$ ${\ displaystyle {\ mathcal {O}} (n^{2} \ log n)}$

Mere avancerede algoritmer drager fordel af, at de suffikser, der skal sorteres, ikke er vilkårlige strenge, men er relateret til hinanden. Disse algoritmer stræber efter at nå følgende mål:

minimal asymptotisk kompleksitet ${\ displaystyle \ Theta (n)}$
let i rummet, hvilket betyder lidt eller ingen arbejdshukommelse ved siden af teksten og selve endelsen array er nødvendig
hurtigt i praksis

En af de første algoritmer til at nå alle mål er SA-IS-algoritmen for Nong, Zhang & Chan (2009) . Algoritmen er også ret enkel (<100 LOC ) og kan forbedres til samtidig at konstruere LCP -arrayet . SA-IS-algoritmen er en af de hurtigste kendte algoritmer til konstruktion af endelser. En omhyggelig implementering af Yuta Mori overgår de fleste andre lineære eller superlinjære konstruktionstilgange.

Foruden tid og rumkrav differentieres endelser til konstruktion af algoritmer også med deres understøttede alfabet : konstante alfabeter, hvor alfabetstørrelsen er bundet af en konstant, heltals alfabeter, hvor tegn er heltal i et område afhængigt af og generelle alfabeter, hvor kun tegn sammenligninger er tilladt . ${\ displaystyle n}$

De fleste algoritmer til konstruktion af suffiks -array er baseret på en af følgende fremgangsmåder:

Præfiks -fordoblingsalgoritmer er baseret på en strategi fra Karp, Miller & Rosenberg (1972) . Ideen er at finde præfikser, der ærer den leksikografiske rækkefølge af suffikser. Den vurderede præfikslængde fordobles i hver iteration af algoritmen, indtil et præfiks er unikt og giver rangen til det tilhørende suffiks.
Rekursive algoritmer følger tilgangen til suffiks træbygningsalgoritmen af Farach (1997) for rekursivt at sortere en delmængde af suffikser. Denne delmængde bruges derefter til at udlede et suffiksarray af de resterende suffikser. Begge disse suffiksarrays flettes derefter for at beregne det endelige suffiksarray.
Inducerede kopieringsalgoritmer ligner rekursive algoritmer i den forstand, at de bruger et allerede sorteret undersæt til at fremkalde en hurtig slags af de resterende suffikser. Forskellen er, at disse algoritmer favoriserer iteration frem for recursion for at sortere det valgte endelsesundersæt. En undersøgelse af denne mangfoldige gruppe af algoritmer er blevet sammensat af Puglisi, Smyth & Turpin (2007) .

En velkendt rekursiv algoritme til heltalsalfabeter er DC3 / skæv algoritmen for Kärkkäinen & Sanders (2003) . Det kører i lineær tid og er med succes blevet brugt som grundlag for parallelle og eksterne hukommelsesuffiks -array -konstruktionsalgoritmer.

Nyligt arbejde af Salson et al. (2010) foreslår en algoritme til opdatering af suffikset array af en tekst, der er blevet redigeret i stedet for at genopbygge et nyt suffiks array fra bunden. Selvom den teoretiske værst tænkelige tidskompleksitet er , ser det ud til at fungere godt i praksis: eksperimentelle resultater fra forfatterne viste, at deres implementering af dynamiske suffiksarrays generelt er mere effektiv end genopbygning, når man overvejer at indsætte et rimeligt antal bogstaver i original tekst. ${\ displaystyle {\ mathcal {O}} (n \ log n)}$

I praktisk open source- arbejde var en almindeligt anvendt rutine for endelse af arraykonstruktion qsufsort, baseret på Larsson-Sadakane-algoritmen fra 1999. Denne rutine er blevet afløst af Yuta Moris DivSufSort, "den hurtigste kendte endelse -sorteringsalgoritme i hovedhukommelsen" fra 2017. Den kan også ændres til at beregne et LCP -array. Den bruger en induceret kopiering kombineret med Itoh-Tanaka. I 2021 blev en hurtigere implementering af algoritmen præsenteret af Ilya Grebnov, som i gennemsnit viste 65% forbedring af ydelsen i forhold til DivSufSort -implementering på Silesia Corpus.

Generaliseret Suffix Array

Begrebet suffiks array kan udvides til mere end en streng. Dette kaldes et generaliseret suffiks array (eller GSA), et suffiks array, der indeholder alle suffikser for et sæt strenge (f.eks. Og er leksikografisk sorteret med alle suffikser i hver streng. ${\ displaystyle S = S_ {1}, S_ {2}, S_ {3}, ..., S_ {k}}$

Ansøgninger

Endelsen af en streng kan bruges som et indeks til hurtigt at lokalisere hver forekomst af et understrengsmønster i strengen . At finde hver forekomst af mønsteret svarer til at finde hvert suffiks, der begynder med delstrengen. Takket være den leksikografiske rækkefølge vil disse suffikser blive grupperet sammen i endelsen array og kan findes effektivt med to binære søgninger . Den første søgning finder intervallets startposition, og den anden bestemmer slutpositionen: ${\ displaystyle P}$ ${\ displaystyle S}$

n = len(S)
def search(P: str) -> Tuple[int, int]:
    """
    Return indices (s, r) such that the interval A[s:r] (including the end
    index) represents all suffixes of S that start with the pattern P.
    """
    # Find starting position of interval
    l = 0  # in Python, arrays are indexed starting at 0
    r = n
    while l < r:
        mid = (l + r) // 2  # division rounding down to nearest integer
        # suffixAt(A[i]) is the ith smallest suffix
        if P > suffixAt(A[mid]):
            l = mid + 1
        else:
            r = mid
    s = l
    
    # Find ending position of interval
    r = n
    while l < r:
        mid = (l + r) // 2
        if suffixAt(A[mid]).startswith(P):
            l = mid + 1
        else:
            r = mid
    return (s, r)

Det tager tid at finde delstrengsmønsteret i længden i længden , da en sammenligning af enkelt suffiks skal sammenligne tegn. Manber & Myers (1990) beskriver, hvordan denne grænse kan forbedres til tid ved hjælp af LCP -oplysninger. Ideen er, at en mønstersammenligning ikke behøver at sammenligne visse tegn igen, når det allerede er kendt, at disse er en del af det længste fælles præfiks for mønsteret og det aktuelle søgeinterval. Abouelhoda, Kurtz & Ohlebusch (2004) forbedrer grænsen endnu mere og opnår en søgetid på som kendt fra suffiksetræer . ${\ displaystyle P}$ ${\ displaystyle m}$ ${\ displaystyle S}$ ${\ displaystyle n}$ ${\ displaystyle {\ mathcal {O}} (m \ log n)}$ ${\ displaystyle m}$ ${\ displaystyle {\ mathcal {O}} (m+\ log n)}$ ${\ displaystyle {\ mathcal {O}} (m)}$

Suffiks -sorteringsalgoritmer kan bruges til at beregne Burrows – Wheeler -transformen (BWT) . Den BWT kræver sortering af alle cykliske permutationer af en streng. Hvis denne streng ender i et særligt slut-af-streng-tegn, der er leksikografisk mindre end alle andre tegn (dvs. $), svarer rækkefølgen af den sorterede roterede BWT- matrix til rækkefølgen af suffikser i et suffiksarray. Det BWT kan derfor beregnes i lineær tid ved først at konstruere et suffiks vifte af teksten og så udlede af BWT streng: . ${\ displaystyle BWT [i] = S [A [i] -1]}$

Suffix-arrays kan også bruges til at slå op på substrater i eksempelbaseret maskinoversættelse , hvilket kræver meget mindre opbevaring end en hel sætningstabel som brugt i statistisk maskinoversættelse .

Mange yderligere applikationer af suffiks -arrayet kræver LCP -arrayet . Nogle af disse er detaljerede i sidstnævnte applikationsafsnit .

Noter

Referencer

Manber, Udi ; Myers, Gene (1990). Suffix-arrays: en ny metode til onlinestrengsøgninger . Første årlige ACM-SIAM-symposium om diskrete algoritmer. s. 319–327.
Manber, Udi ; Myers, Gene (1993). "Suffix-arrays: en ny metode til onlinestrengsøgninger" . SIAM Journal on Computing . 22 (5): 935–948. doi : 10.1137/0222058 . S2CID 5074629 .
Gawrychowski, Paweł; Kociumaka, Tomasz (januar 2017). "Sparsomt suffiks trækonstruktion i optimal tid og rum". Procedurer for de otteogtyvende årlige ACM-SIAM-symposium om diskrete algoritmer . Philadelphia, PA: Society for Industrial and Applied Mathematics: 425–439. arXiv : 1608.00865 . doi : 10.1137/1.9781611974782.27 . ISBN 9781611974782. S2CID 6608776 .
Li, Zhize; Li, Jian; Huo, Hongwei (2016). Optimal in-place suffiks sortering . Proceedings of the 25. International Symposium on String Processing and Information Retrieval (SPIRE). Forelæsningsnotater i datalogi. 11147 . Springer. s. 268–284. arXiv : 1610.08305 . doi : 10.1007/978-3-030-00479-8_22 . ISBN 978-3-030-00478-1.
Shi, Fei (1996). Suffix-arrays for flere strenge: En metode til online-søgning efter flere strenge . Forelæsningsnotater i datalogi. 1179 . Springer Berlin Heidelberg. s. 11–22. doi : 10.1007/BFb0027775 . ISBN 978-3-540-62031-0.
Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2002). Enhanced Suffix Array og dets anvendelser til genomanalyse . Algoritmer i bioinformatik. Forelæsningsnotater i datalogi . 2452 . doi : 10.1007/3-540-45784-4_35 . ISBN 978-3-540-44211-0.
Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (marts 2004). "Udskiftning af suffiksetræer med forbedrede suffiksarrays" . Journal of Discrete Algorithms . 2 (1): 53–86. doi : 10.1016/S1570-8667 (03) 00065-0 . ISSN 1570-8667 .
Gonnet, GH; Baeza-Yates, RA; Snider, T (1992). "Nye indekser for tekst: PAT -træer og PAT -arrays" . Informationssøgning: Datastrukturer og algoritmer .
Kurtz, S (1999). "Reducering af pladsbehovet for endelser af træer". Software-praksis og erfaring . 29 (13): 1149–1171. doi : 10.1002/(SICI) 1097-024X (199911) 29:13 <1149 :: AID-SPE274> 3.0.CO; 2-O . HDL : 10338.dmlcz / 135.448 .
Puglisi, Simon J .; Smyth, WF; Turpin, Andrew H. (2007). "En taksonomi af suffiks -array -konstruktionsalgoritmer" . ACM Computing Surveys . 39 (2): 4. doi : 10.1145/1242471.1242472 . S2CID 2653529 .
Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). Linear Suffix Array Construction ved næsten ren induceret sortering . 2009 Datakomprimeringskonference. s. 193. doi : 10.1109/DCC.2009.42 . ISBN 978-0-7695-3592-0.
Fischer, Johannes (2011). Fremkalder LCP-Array . Algoritmer og datastrukturer. Forelæsningsnotater i datalogi. 6844 . s. 374. arXiv : 1101.3448 . doi : 10.1007/978-3-642-22300-6_32 . ISBN 978-3-642-22299-3.
Salson, M .; Lecroq, T .; Léonard, M .; Mouchard, L. (2010). "Dynamiske udvidede endelsesarrays" . Journal of Discrete Algorithms . 8 (2): 241. doi : 10.1016/j.jda.2009.02.007 .
Burkhardt, Stefan; Kärkkäinen, Juha (2003). Hurtig letvægts suffiksopbygning og kontrol . Kombinerende mønster matchende. Forelæsningsnotater i datalogi. 2676 . s. 55. doi : 10.1007/3-540-44888-8_5 . ISBN 978-3-540-40311-1.
Karp, Richard M .; Miller, Raymond E .; Rosenberg, Arnold L. (1972). Hurtig identifikation af gentagne mønstre i strenge, træer og arrays . Fortsættelse af det fjerde årlige ACM -symposium om computerteori - STOC '72. s. 125. doi : 10.1145/800152.804905 .
Farach, M. (1997). Optimal konstruktion af suffiksetræ med store alfabeter . Proceedings 38th Annual Symposium on Foundations of Computer Science. doi : 10.1109/SFCS.1997.646102 . ISBN 0-8186-8197-7.
Kärkkäinen, Juha; Ukkonen, Esko (1996). Sparsomme endelser træer . Forelæsningsnotater i datalogi. 1090 . Springer Berlin Heidelberg. s. 219–230. doi : 10.1007/3-540-61332-3_155 . ISBN 978-3-540-61332-9.
Kärkkäinen, Juha; Sanders, Peter (2003). Simple Lineær Work Suffix Array Konstruktion . Automata, sprog og programmering. Forelæsningsnotater i datalogi. 2719 . doi : 10.1007/3-540-45061-0_73 . ISBN 978-3-540-40493-4.
Dementiev, Roman; Kärkkäinen, Juha; Mehnert, Jens; Sanders, Peter (2008). "Bedre ekstern hukommelsesuffiks -array -konstruktion" . Journal of Experimental Algorithmics . 12 : 1–24. doi : 10.1145/1227161.1402296 . S2CID 12296500 .
Kulla, Fabian; Sanders, Peter (2007). "Skalerbar parallel suffiks array -konstruktion". Parallel computing . 33 (9). doi : 10.1016/j.parco.2007.06.004 .

Languages

In other projects