Teema 5 - sufiksipuud, tabelid ja automaadid

1. Ülesandepüstitus ja sissejuhatus
2. Sufiksipuu
3. Sufiksipuu rakendusi
4. Sufiksitabel
5. Sufiksiautomaat
6. Sufiksikaktus jt.
7. Rakendusi: Oxford English Disctionary

Lisakirjandust

• Artikleid sufiksipuude, tabelite jmt kohta

• Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology by Dan Gusfield. Hardcover - 534 pages 1st edition (January 15, 1997). Cambridge Univ Pr (Short); ISBN: 0521585198.

Ülesandepüstitus

Võtame näitesõna: S=mississippi. Nüüd: miss on prefix, ippi on sufix ja issi on alamstring mis esineb kahes kohas (issi on sufiksite ississippi ja issippi prefiks!).

T1  = mississippi 
T2  = ississippi
T3  = ssissippi
T4  = sissippi
T5  = issippi
T6  = ssippi
T7  = sippi
T8  = ippi
T9  = ppi
T10 = pi
T11 = i
T12 =               (tühi)

T11 = i
T8  = ippi
T5  = issippi
T2  = ississippi
T1  = mississippi
T10 = pi
T9  = ppi
T7  = sippi
T4  = sissippi
T6  = ssippi
T3  = ssissippi

Vaatame näidet:

Pane tähele, et $ ∉ Σ on pandud S lõppu selleks et oleks lihtsam eristada sisesõlmi ja lehti (vrdl. A ja A$).

Kuidas otsida sellest struktuurist?

Otsimise keerukus: O(|P|)

Otsimise keerukus ei sõltu enam S suurusest!

Kuid see eeldab lisaindeksi olemasolu igast tipust vastava alampuu vasakpoolsesse lehte. See on aga triviaalne.

Tagasi

Sufiksipuu

Definition A suffix tree T for an m-character string S is a rooted directed tree with exactly m leaves numbered 1 to m. Each internal node, other than the root, has at least two children and each edge is labeled with a nonempty substring of S. No two edges out of a node can have edge-labels beginning with the same character. The key feature of the suffix tree is that for any leaf i, the concatenation of the edge-labels on the path from the root to leaf i exactly spells out the suffix of S that starts at position i. That is, it spells out S[i..m]. Kuid puu on ikka veel O(n²)?
Esitame kaartel olevad nimed omakorda konstantse pikkusega:

• Osutub, et lisaks kompaktsele kujule O(n), on kompaktne sufiksipuu võimalik ka koostada lineaarse O(n) ajaga!

• Peter Weiner (Peter Weiner: Linear Pattern Matching Algorithms. Proc. 14 th IEEE SWAT (old name of FOCS) pp. 1-11; 1973) proposed the suffix tree (he called it a position-tree).

• Edward M. McCreight: A Space-Economical Suffix Tree Construction Algorithm. JACM 23(2): 262-272 (1976)

• Esko Ukkonen: On-Line Construction of Suffix Trees. Algorithmica 14(3): 249-260 (1995)

• See (Robert Giegerich, Stefan Kurtz: From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction. Algorithmica 19(3): 331-353 (1997)) for a unified view of these algorithms.

• There exists also a simpler, O(n²) algorithm - Write Only Top Down (previously called "lazy")

• Robert Giegerich, Stefan Kurtz, Jens Stoye: Efficient Implementation of Lazy Suffix Trees. In Proceedings of the Third Workshop on Algorithmic Engineering (WAE99), Lecture Notes in Computer Science 1668, Springer Verlag, pages 30-42, 1999.

• Vt. artikleid

Ukkonen'i konstruktsioon

Algoritm: On-line sufiksipuu konstruktsioon (Ukkonen)
Sisend: Tekst S
Väljund: Sufiksipuu ST.

1. Konstrueeri puu algus

2. for i = 1 .. m-1 do   { lisa positsioon i+1 }
3.      for j = 1 .. i+1 { laiendus j }
4.          Leia sellise tee lõpp mis vastaks juurest S[j..i] -le.
5.          Kui vaja, jätka seda teed tähega S[i+1] veendumaks
            et S[ j .. i+1 ] oleks ka puus

Sama näide sufiksipuu peal:

Alternatiivne esitusviis kus lehed on pakitud, on ka efektiivne:

• Implementation (kohalik)

• Loengukonspekt sufiksipuudest (Lloyd Allison) (kohalik)

• Fast String Searching With Suffix Trees by Mark Nelson Dr. Dobb's Journal, August, 1996 (kohalik)

Sufiksipuu rakendusi

APL1: Exact String Matching

Otsi stringi P sufiksipuust O(|P|) ajaga

APL2: Exact set matching

APL3: substring problem for a database of patterns

Olgu antud stringide hulk S=S1, ... , Sn (Andmebaas tekstidega) Otsi stringi P kõikidest nendest tekstidest. Tehtav üldistatud sufiksipuust mis sisaldab iga teksti kõiki sufikseid "ülestikku". Päring võtab ikka O(|P|) aja. Indekseerimine aga S kogupikkus (st. andmebaasi suuruse suhtes lineaarse aja)

APL4: Longest common substring of two strings

Leie kahe stringi S ja T pikim ühine osasõne. Potentsiaalselt on neid ju n² tükki kus n on lühema stringi pikkus. Donald Knuth esitas kunagi oma hüpoteesi, et see ei ole lahendatav lineaarse ajaga kahe stringi pikkuse summa suhtes. On aga selge, et sufiksipuid kasutades on see lineaarse ajaga teostatav - konstrueeri sufiksipuu S ja T tarbeks korraga. Käi see puu läbi j väljasta sügavaima tipuni viivate kaarte pikkus kus tipus on veel nii S kui ka T alamstringid.

APL5: Recognizing DNA contamination

Sekveneerimisel võib sattuda sisse vale DNA (näiteks bakteritest mida kasutatakse DNA ettevalmistamiseks), siis saab andmebaasist leida need jupid mis on selgelt teisest organismist.

APL6:Common substrings of more than two strings

See on APL4 üldistus, teostatav samuti kõikide sringide ühispikkuse suhtes lineaarse ajaga.

APL7: Building a smaller directed graph for exact matching

Sufiksipuu on paljude alampuude osas identne, need saab esitada vaid ühekordselty ning teha niimodoi graafi kus pole dubleeritud alampuid. Nii saab küll otsida kuid ei tea täpset asukohta kui ei pea arvet kus positsioonidest algasid vastavad sufiksid.

APL8: A reverse role for suffix trees, and major space reduction

APL10: All-pairs suffix-prefix matching

Kõik kÕigi vastu...

APL11: Finding all repetitive structures in molecular strings

APL12: Circular string linearization

APL13: Suffix arrays - more space reduction

APL14: Suffix trees in genome-scale projects

APL15: A Boyer-Moore approach to exact set matching

APL16: Ziv-Lempel data compression

APL17: Minimum length encoding of DNA

Additional applications

Mostly exercises...

Extra feature: CONSTANT time lowest common ancestor retrieval (LCA)

Andmestruktuur mis võimaldab leida konstantse ajaga alumist ühist vanemat (see vastab pikimale ühisele prefixile!) on võimalik koostada lineaarse ajaga.

APL: Longest common extension: a bridge to inexact matching

APL: Finding all maximal palindromes in linear time

Palindroom on keksmisest positsioonist edasi kui ka tagasi pikim ühine prefiks. (palindroomi eest taha ja tagant ette lugedes on ikka üks ja sama: kirik, saippuakivikauppias.

Tehes sufiksipuu edasi-tagasi suunas (aabcbad => aabcbad#dabcbaa ) ja kasutades LCA konstruktsiooni saab küsida positsioonidest 4 ja (2n-4) algavat pikimat ühist prefiksit konstantse ajaga. Ehk, kogu ülesanne lahendatav O(n) ajaga.

APL: Exact matching with wild cards

APL: The k-mismatch problem

Approximate palindromes and repeats

Faster methods for tandem repeats

A linear-time solution to the multiple common substring problem

And many-many more ...

Sufiksitabel

• Sufiksipuu probleem on tema suurus, sõltuvalt realisatsioonist saab olla ökonoomne puu esituse suhtes kuid ikkagi on tegu ca 15-20 korda algse teksti suuruse struktuuriga

• Kas saaks indekseerida väiksemas ruumis?

• Gonnet et al (OED project) and Manber and Meyers (Udi Manber, Eugene W. Myers: Suffix Arrays: A New Method for On-Line String Searches. SIAM J. Comput. 22(5): 935-948 (1993); also SODA 1990) demonstrated the importance of this structure, and a cut-down form of it, for large scale text indexing.

• Udi Manber - publications (sufiksitabeli artikkel)

    1  2  3  4  5  6  7  8  9  10 11
T=  m  i  s  s  i  s  s  i  p  p  i

T11 = i
T8  = ippi
T5  = issippi
T2  = ississippi
T1  = mississippi
T10 = pi
T9  = ppi
T7  = sippi
T4  = sissippi
T6  = ssippi
T3  = ssissippi

Suffix array:  11 8 5 2 1 10 9 7 4 6 3

   123456789
S= TATTATTAA$

SA= 8 5 2 9 7 4 1 6 3

Kahendotsimine sufikistabelist

• Olgu ≤^m kuni m tähe pikkuste stringide võrdlusoperatsioon vastavalt táhestikulisele järjekorrale.

• All on abastraktne otsimis-algoritm. Seda ei ole optimeeritud. Samuti pole hetkel kindel et kõik indeksid alati korrektseks saaks.

Algoritm: Otsimine sufiksitabelist 
Input: Tekst S, |S|=n, sufiskitabel SA, otsitav sõne P, |P|=m
Output: P esinemiste algpositsioonid S-is

I: Otsi P vasakpoolsed esinemised

1. L=1; R=n
2. while R-L > 0
3.    M = (L+R)/2
4.    if   P ≤m S[ SA[M] ] then R = M
5.    else L = M
6. 

II: Otsi P parempoolsed esinemised (analoogselt)

III: Kui LP ≤ RP väljasta algospositsioonid 
     SA[LP] .. SA[RP]

• Otsimine sufiksitabelist

• Otsimine on O(m log n)

• Aga saab ka kiiremini, O( m + log n )

• See arvestab asjaolu, et kahendotsimine seab alati piirid et kumba kahest võimalikust positsioonist võrreldakse järgmiseks.

• Abitabelis saab öelda kui mitu märki on võrreldavate sufiksite alguses samad, seega võrreldakse P märke mitte alates esimesest positsioonist vaid sellest kus vajalik.

• Longest Common prefix (LCP)

• Konstruktsioon

• Sufiksitabeli saab konstrueerida otse sufiksipuust, st. O(n) ajaga.

• Kuid sufiksipuu probleem oli ju selle suurus

• Lihtne sorteerimine pole n log n kuna kahe pika sufiksi võrdlemine ei võta mitte O(1) vaid O(n). Seega oleks triviaalne meetod O(n² log n).

• Paremad meetodid on realiseeritud originaalartiklis, nn. Karp-Miller-Rosenberg sorteerimistehnika (sufiksitabeli artikkel)

Tagasi

Teised lahendused

1. Hübriidsüsteemid
   • Sufiksi kaktus - (Kärkkäinen) - kuidas täiendada sufiksitabelit minimaalselt informatsiooniga mis lubaks kõiki funktsioone sufiksipuuga võrdse ajaga

   • Stefan Kurtz etal. - samuti tabeli esitamine optimaalselt pakitud viisil

   • Veli Mäkinen: Compact Suffix Array, In Proc. 11th Annual Symposium on Combinatorial Pattern Matching (CPM 2000), Springer-Verlag LNCS VOL. 1848, pp. 305-319, Montréal, June 2000. Vt. artikleid

Rakendusi - Oxford English Disctionary

• Oxford English Disctionary

• Example - Word of the Day , Fourth

• PAT index - välja arendanud Gaston Gonnet (ta on samuti Maple tarkvara üks loojatest ning hiljem molekulaarbioloogia tarkvarapaketi väljatöötajaid)

• PAT index on sisuliselt sama mis sufiksitabel. Ruumi kokkuhoiu mõttes indekseeriti alguses iga sõna algustähest.

• XML-märgenduses (õieti, tol ajal SGML) teksti puhul indekseeriti ka märgendust seal kus vaja

• Teatud väljade jaoks (näiteks otsi sõna sõnaartikli häälduse väljalt) kasutasid eraldi indeksit: bitivektorit, mis ütleb iga positsiooni kohta 0/1 kas on häälduse märgendite vahel, või mitte.

• Peamine mure oli tol ajal teha asi CD pealt kiireks. Kokku pidi lugema mitu pöördumist kulub keskmiselt iga päringu peale.

• Aeglase meedia puhul on ka 15-20 juhuslikku kettapöördumist "liig"

• G. H. Gonnet, R. A. Baeza-Yates, and T. Snider, Lexicographical indices for text: Inverted files vs. PAT trees, Technical Report OED-91-01, Centre for the New OED, University of Waterloo, 1991.

Teised lahendused

Teised lahendused