HET BOUWEN
Suffix Trees en Substrings.
1
Suffix Trees en Substrings. Section Page Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 Het bouwen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1 Bomen en knopen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 4 De constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 Toevoegen van Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 6 De testprogramma. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 7 Het afdrukken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 7 Opdrachten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 10 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 11
Over het kweken van bomen en het sprokkelen van takken. † Piter Dykstra 14 december 2003
1. Inleiding. Tries zijn bomen waarin woord -en (strings) kunnen worden opgeslagen en die woorden kunnen heel effici¨ent, in een tijd die evenredig met de lengte van het woord toeneemt (O(n)), worden teruggezocht. Elke knoop − node stelt een letter van het woord voor. En het pad (of tak ) van de wortel − root is een woord van de trie. Een suffixtree is een trie van alle suffix -en van een tekst - database. Je vraagt je nu misschien af waarom men nou juist suffixen wil opslaan. Dat komt omdat elke substring een beginstuk of prefix is van een suffix . En wat we zoeken bij het blasten zijn eigenlijk substrings in een database. Het voordeel van een suffixtree is dus, dat je elke substring kunt terugzoeken in een tijd †
Handout nr 2. Kleine Programmeerpatronen thema6 Bioinformatica.
2
Suffix Trees en Substrings.
HET BOUWEN §1
die evenredig is met de lengte van de substring. En dus niet afhangt van de grootte van de database. 2. Het bouwen. Voordat je zo snel kunt zoeken moet moet een suffixtree eerst nog wel even gebouwd worden. Daarover gaat deze handout. Nadat we een Javaprogramma voor de bouw van suffixtrees hebben ontwikkeld, moet je in staat zijn om zelf een aantal uitbreidingen te realiseren, zoals het zoeken in suffixtrees (zie §11). Voor het bouwen van een suffixtree moeten alle suffixen van een string in een trie worden opgenomen. Alle suffixen van b.v. de string "abracad" zijn: 1. "abracad" 2. "bracad" 3. "racad" 4. "acad" 5. "cad" 6. "ad" 7. "d" Het opnemen van een string in een trie houdt in dat er een tak van knopen van de wortel naar een eindknoop ofwel blad moet komen; voor zover dat er tenminste niet is. Want als er al een string in de suffixtree is opgenomen, die een beginstuk, prefix , gemeen heeft met de string die we nu invoeren, kunnen we dat beginstuk voor beide strings gebruiken. We maken pas een nieuwe vertakking als we bij een knoop aankomen, die niet een kind heeft met een letter voor het volgende teken in de string. Zo kan een knoop nooit meer kinderen hebben dan er letters in het alfabet zijn. Dit klinkt allemaal veel ingewikkelder dan het is. Ik heb daarom fig. 1 opgenomen om de verschillende handelingen te laten zien voor de constructie van een suffixtree op basis van de string "abracad". † Opdracht:
Geef zelf aan waar de laatste suffix, "d", komt.
Als we aannemen dat het invoegen van een string in een suffixtree in een tijd proportioneel met de lengte van de string kan, dan schijnt het bouwen van een hele suffixtree dus O(n!) veel tijd te kosten, wat overeenkomt met O(mn ) ofwel exponentieel . Het programma dat we hier hebben presteert †
Je kunt een trie ook wel vergelijken met een woordenboek. De hoogste rij knopen zijn de
eerste letters A..Z, die op hun beurt ook weer onderverdeeld zijn in 26 onderdelen voor de tweede letter, enz...
§2
HET BOUWEN
(a)
Suffix Trees en Substrings.
(b) a b r a c a d
(c)
(d)
a
b
a
b
r
b
r
b
r
a
b
r
a
r
a
c
a
c
a
c
c
a
c
a
a
d
a
d
d
b
r
c
r
a
r
a
a
c
a
a
d
c
a
d
c
a
d
a
d
a
d
d
(e) a
(f) b
c
r a
b r
c a
a c a d
d
r a c a d
a d
b
c
r
r
a
a
a
d
c
a c a d
3
b
c
r
a
a
d
d
c a
c
a
a
d
d
d
Fig 1. De opeenvolgende stadia in het ontstaan van de suffixtree. (a) na invoeging van "abracad", (b) na "bracad", (c) na (d) na "acad", (e) na "cad" en (f) na "ad".
"racad",
4
BOMEN EN KNOPEN §2
Suffix Trees en Substrings.
ook niet beter en is daarom ook niet geschikt voor grote databases. Maar Ukkonen ‡ heeft een algoritme medacht dat het ook in O(n) tijd kan en dat juweeltje wordt in de praktijk gebruikt, maar ik vrees dat de bespreking daarvan helaas buiten de scope van onze opleiding valt. 3. Bomen en knopen. In ons geval bestaat een knoop uit een letter : value .† Een knoop kan een kind hebben voor elke letter van het alfabet. De eenvoudigste datastruktuur daarvoor is een array ter grootte van alphabetSize van ... SuffixTree ’s. suffixtree value : children :
<>
suffixtree
suffixtree
a
b
suffixtree
b
suffixtree
c Fig 2. De implementatie van de
SuffixTree-klasse.
Ja met bomen is iets merkwaardig aan de hand. Een boom bestaat uit een topknoop , waaronder subknopen (kinderen − children ) hangen, die zelf weer bomen zijn! ‡
E. Ukkonen: Online construction of suffix-trees. Algorithmica, 14:249-60,1995 Hij was overigens niet de eerste. Al in 1973 publiceerde Weiner ook een lineair algoritme, maar dat gebruikete veel meer geheugen: P.Weiner: Lineair pattern matching algorithms. Proc. of the 14th IEEE Symp. on Switching and Automata Theory, pp 1-11,1973
†
Dat kan effici¨ enter; zie Goodrich en Tomasi. We zouden de reeksen van niet vertakkende
knopen in ´ e´ en stringknoop kunnen samenvatten. Maar we zijn nu toch al zo ineffici¨ ent bezig dat dit er ook nog wel bij kan.
§3
DE CONSTRUCTORS
Suffix Trees en Substrings.
5
Dat leidt tot een bijzondere datastruktuur ; het gedefinieerde object, SuffixTree komt zelf in de definitie voor (fig. 2). We noemen zo’n struktuur een recursieve datastruktuur . Klassieke voorbeelden van recursieve strukturen zijn: 1. Het Droste-cacaublikje met een verpleegster erop met een dienblad, waarop, ... een Droste-cacaublikje,... 2. De afkorting GNU staat voor GNU is not Unix. Waar staat die G nou voor? ... Juist: GNU ... en dat staat voor ... 3. Idem KDE - informatici hebben iets met recursie - is de afkorting van KDE Desktop Environment. define alphabetSize ≡ 26 (SuffixTree.java 3) ≡ public class SuffixTree { char value ; SuffixTree [ ] children ← new SuffixTree [alphabetSize ]; h De constructors 5 i h Methoden voor het toevoegen van strings 4 i h Afdrukken van de SuffixTree 9 i } 4. De indexpositie van een element in het array wordt afgeleid van de ascii-waarde van value . En om het array ook vanaf 0 te vullen wordt van de ascii-waarde de ascii-waarde van’a’ afgetrokken. h Methoden voor het toevoegen van strings 4 i ≡ public int hashCode (char v) { return (int) v − (int) ’a’; } See also section 6. This code is used in section 3.
5. De constructors. Er zijn twee constructors; Een voor de topknoop die in fig 1 consequent met een zwart cirkeltje is aangegeven - dit is de enige knoop die niet een char-waarde heeft. Het ’woordenboek’ heeft zelf geen index! Om de topknoop te maken wordt methode SuffixTree (String s) gebruikt. Alle andere knopen worden gemaakt met de default constructor SuffixTree (), die, omdat we een zelfgedefinieerde constructor hebben, nu ook expliciet gedefinieerd moet worden.
6
Suffix Trees en Substrings.
TOEVOEGEN VAN STRINGS §5
Zo gauw de topknoop is aangemaakt wordt de database-string toegevoegd met de methode addString (s) (zie §6). h De constructors 5 i ≡ public SuffixTree () { } public SuffixTree (String s) { while (s.length () > 0) { addString (s); s ← s.substring (1, s.length ()); } } This code is used in section 3.
6. Toevoegen van Strings. Wanneer we een string aan een node toevoegen zijn er twee mogelijkheden: 1. E´en van de kinderen van deze knoop heeft een karakter dat gelijk is aan het eerste karakter van de string: if (t 6= null), in de method addString (String s). Zo ja, dan kijken we of dat kind een kind met een entry voor de tweede letter dfoor de methode t.addString ( s.substring (1, s.length ()) ) uit te voeren. - Misschien is de in te voeren string al een in de boom voorkomende string en hoeft er helemaal niets aangemaakt te worden. 2. children heeft nog geen entry. -dan moet er een subboom gemaakt worden, met newNode . Die maakt een nieuwe knoop aan met daaraan een hele keten knopen voor elke letter van de string. Dat doen we weliswaar met de methode addString , maar die voert voor elk teken weer de methode newNode uit. define nogTekensInTeVoegen ≡ (s.length () > 0) define heeftKind (kind ) ≡ (kind 6= null) h Methoden voor het toevoegen van strings 4 i+ ≡ public SuffixTree newNode (String s) { SuffixTree t ← new SuffixTree (); t.value ← s.charAt (0); t.addString (s.substring (1, s.length ())); return t; } public void addString (String s)
§6
HET AFDRUKKEN
Suffix Trees en Substrings.
7
{ if nogTekensInTeVoegen { int firstCharCode ← hashCode (s.charAt (0)); SuffixTree t ← children [firstCharCode ]; if (heeftKind (t)) t.addString (s.substring (1, s.length ())); else children [firstCharCode ] ← newNode (s); } } 7. Het is je misschien al opgevallen bij de methoden van §6, dat -hoewel er toch sprake is van een proces dat herhaald wordt (knopen maken)- er toch geen herhalingslus in deze methoden voorkomt. Het patroon dat drie keer is gebruikt is dat het eerste karakter van de string wordt verwerkt in een knoop. En de rest van de string wordt verwerkt door die rest mee te geven bij een aanroep van dezelfde methode. En dat terwijl de definitie van die methode nog niet eens af is! Dat kan! Zo’n methode, die zichzelf aanroept bij haar uitvoering, heet een recursieve methode en dat is heel gebruikelijk bij recursieve datastrukturen. Een voordeel van recursie is, dat de code er een stuk eenvoudiger uit komt te zien, waardoor programmeerfouten vermeden worden. Een nadeel is dat studenten vaak grote moeite hebben om in te zien dat er u ¨berhaupt een einde komt aan het proces van zichzelf aanroepen. -Maar dat nadeel is er om overwonnen te worden en geloof mij: je kunt echt een gelukkiger mens worden als je dit snapt! 8. Het testprogramma. Een testprogrammaatje staat in de file "TestTree.java": (TestTree.java 8) ≡ public class TestTree { public static void main (String [ ] args ) { SuffixTree t ← new SuffixTree ("abracad"); t.printSuffixTree (0); } } 9. Het afdrukken. define writeLn ≡ System .out .println define voorHeleAlfabet (i) ≡ int i ← 0; i < alphabetSize ; i++
8
Suffix Trees en Substrings.
HET AFDRUKKEN §9
h Afdrukken van de SuffixTree 9 i ≡ private static final String spaties ← "ÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃ"; public void printSuffixTree (int sp ) { . . . Voor alle tekens van het alfabet doe... for (int i ← 0; i < alphabetSize ; i++) { if (heeftKind (children [i])) { SuffixTree t ← children [i]; writeLn (spaties .substring (0, sp ) + t.value ); t.printSuffixTree (sp + 4); } } } This code is used in section 3.
10.
§10 HET AFDRUKKEN
Suffix Trees en Substrings.
9
Uit de uitvoer van printSuffixTree is een een beeld van de suffixtree te destilleren; je moet het plaatje 90◦ rechtsom draaien en spiegelen om de veritkale as (links ⇔ rechts), om hetzelfde beeld als fig. 1 te krijgen. a b r a c a d c a d d b r a c a d c a d d r a c a d
10
Suffix Trees en Substrings.
OPDRACHTEN §10
11. Opdrachten. 1. Maak een methode boolean zoekSubString (String s) waarmee je kunt bepalen of een bepaalde string s een substring van de database is, of niet. 2. We houden nog helemaal geen informatie bij op welke plaats(-en) in de database een bepaald character van node voorkomt. Dat is strikt genomen ook niet nodig, want die node maakt deel uit van een (aantal) suffix(-en) en de afstand tot het einde van een suffix is gelijk aan de afstand tot het einde van de database. De positie in de database is dus uit te rekenen. Toch is het, voor het gebruik met substrings b.v., handig om bij een bepaalde node wel te weten op welke positie in de database het karakter voorkomt. Wat moet je aan de SuffixTree klasse toevoegen om over die informatie te beschikken (produceren en reproduceren)? 3. Wat zou je aan het SuffixTree -object kunnen toevoegen om meerdere tekstbestanden in dezelfde tree op te kunnen slaan. 4. Ontwerp een methode addDatabase waarmee je een nieuwe database aan een bestaande suffixtree kunt toevoegen. addDatabase verschilt iets van addString . In addString wordt maar ´e´en string toegevoegd, terwijl in addDatabase alle suffixen van die string moeten worden toegevoegd. 5. Ontwerp een methode, printGemeneSubstrings , die geordend op lengte - de grootste voorop, de gemeenschappelijke substrings afdrukt.
§12 NAMES OF THE SECTIONS
Suffix Trees en Substrings.
12. Index. addDatabase 11. addString 5, 6, 11. alphabetSize [3], 9. args 8. beginstuk 1. blad 2. charAt 6. children 3, 6, 9. datastruktuur 3. eindknoop 2. exponentieel 2. firstCharCode 6. hashCode 4, 6. heeftKind [6], 9. kind 6. kinderen 3. knoop 1. length 5, 6. letter 3. main 8. methode 7. newNode 6. node 1. nogTekensInTeVoegen [6]. out 9. pad 1. prefix 1, 2. printGemeneSubstrings 11.
println 9. printSuffixTree 8, 9. programmeerfouten 7. recursie 7. recursieve 3, 7. root 1. sp 9. spaties 9. String 5, 6, 8, 9, 11. subknopen 3. substring 1, 5, 6, 9. suffix 1. suffixtree 1. SuffixTree 3, 5, 6, 8, 9, 11. System 9. tak 1. TestTree 8. topknoop 3. trie 1, 2. Tries 1. Ukkonen 2. value 3, 4, 6, 9. voorHeleAlfabet [9]. woord 1. wortel 1. writeLn [9]. zoekSubString 11.
Section names: (SuffixTree.java 3) (TestTree.java 8) h Afdrukken van de SuffixTree 9 i Used in section 3. h De constructors 5 i Used in section 3. h Methoden voor het toevoegen van strings 4, 6 i Used in section 3.
11
