>Der Quasar fu�t auf einer gro�en Vorprozessierung der Datenbank.
>Wie du richtig gesagt hast wird auf ihr erstmal ein Suffixarray aufgebaut. Dieses gibt ja sortiert die "Fundstellen" aller Suffixe in der Datenbank aus.
>Des Weiteren wird eine zweite Tabelle ben�tigt. Dieses speichert f�r jedes m�gliche q-gramm die Stelle des Suffixarrays, an der das q-gramm zum ersten mal (von "oben") macht. Es wird quasi der Lp jedes q-gramms bezogen auf die Datenbank gespeichert.
>Weil eine Tabelle, die sowohl das q- Gramm als auch den Verweis auf das i vom Suffix array unn�tig gro� ist, gibt es hier noch einen Trick. Wenn man geschickt jedes q-Gramm einer Stelle in dieser Tabelle zuweist, braucht man nur die Stelle in der Tabelle zu kennen, um auch das q- Gramm zu kennen. Es darin noch zu speichern ist dann unn�tig.
>Was ich meine ist folgendes: Wenn ich alle 4er q-Gramme sortiere, beginnend mit AAAA, dann kommt da nach AAAC, dann AAAG. Diese haben also die Stellen 0, 1 und 2. Interpretiert man die q-Gramme als Zahlen zur Basis 4, kommt man leicht auf die Stelle in dieser Tabelle.
>AAAA wird zu [0000] = 0, AAAG zu [0002] = 2 und bspw. CATG wird zu [1032] = 1*4^3+0*4^2+3*4^1+2*4^0 = 64+12+2= 78, wodurch jedes q-gramm ganz eindeutig seine Stelle in dieser Tabelle zwischen 0 und 255 zugewiesen bekommt (f�r q = 4). Ihr solltet dies als hash-Funktion implementieren.
>Die Tabelle ist dann nur noch eindimensionales Array, dass die i's aus dem Suffixarray enth�lt. (Gleiches Spiel hier nat�rlich, i wird nicht im Suffixarray gespeichert, sondern ist nat�rlich nur die Stelle im dann eindimensionalen Array, das als Eintr�ge die sortierten Stellen in der Datenbank speichert.)
>
>Was haben wir nun? Gegeben irgendein Q-Gramm kannst du nun alle Fundstellen in der Datenbank ausgeben. Du "�bersetzt" das q- Gramm in die Zahl und kennst die Stelle an der das q-gramm in der Tabelle steht. Schaust du in dieser nach, erh�lst du den ersten Eintrag im Suffixarray, an dem dein q-Gramm Pr�fix eines Suffixes ist. Findest du jetzt noch die letzte Stelle im Suffixarray f�r das q-Gramm, dann sind all Stellen dazwischen hits.
>Wie kriegst du die letzte Stelle raus? Recht einfach, sie liegt einen Eintrag VOR dem ersten Eintrag des n�chsten q-gramms. Du nimmst also alle Eintr�ge von deinem Tabellenwert f�r das gesuchte q- Gramm bis (AUSSCHLIESSLICH) zum Tabellenwert f�r das n�chste q-Gramm.
>Beispiel:
>Du willst wissen, an welcher Stelle das q-Gramm AACT zu finden ist. Dieses steht an Stelle 7 der Tabelle.
>Du l�sst dir also die Tabellenwerte f�r die Stellen 7 und 8 ausgeben.
>Beispielsweise seien dies 123 und 127. Dies sind nun die erste Stelle im Suffixarray, in der das q- Gramm vorkommt und die erste Stelle in der das q- Gramm nicht mehr vorkommt.
>Alle Stellen 123, 124, 125, 126 im Suffixarray sind Treffer f�r das q-Gramm, denn das Suffixarray war sortiert.
>Das Ausgeben der Werte des Suffixarrays an besagten Stellen (zB. 1013, 25, 465, 39) gibt dir alle Stellen, an denen das q- Gramm in der Datenbank steht. Das ist schonmal ein m�chtiges Werkzeug.
>
>Als n�chstes m�ssen wir den Begriff der Buckets etwas fassbarer machen.
>Damit sind Bereiche, also Unterteilungen der gro�en Datenbank gemeint. Ihre Gr��e ist b und soweit ich wei� bei eurer Aufgabe 2*w, wobei w die Read- (Pattern-)l�nge ist.
>Jede Stelle in der Datenbank geh�rt zu mindestens einem Bucket, und zwar dann, wenn ein q-Gramm, dass an dieser Stelle anf�ngt noch vollst�ndig "Im bucket liegt".
>Da nach dieser Definition manche Stellen bei nur einer Reihe aneinander h�ngender Buckets keine Zuweisung haben (n�mlich die, wo die q- Gramme �ber die Grenze zwischen zwei buckets gehen), werden zwei Reihen Buckets konzipiert, bei der die eine Reihe um b/2 Stellen verschoben ist. So liegen auch alle Windows (Bei euch patterngro�e Suchfenster) sicher in einem Bucket.
>Die Buckets jedoch sind viel mehr ein Gedankenkonstrukt, als real implementiert. Tats�chlich sind nur 2 Sachen �ber die Buckets wichtig.
>Erstens: Ich brauche eine Zuordnung von Stelle in der Datenbank zu Bucket und zur�ck.
>F�r jede Stelle muss ich erfahren k�nnen, zu welchen Buckets sie geh�rt.
>Zu jedem Bucket muss ich wissen, welchen Bereich der Datenbank er abdeckt.
>ACHTUNG: Auch wenn es am Anfang komisch klingt, diese Definitionen sind nicht ganz deckungsgleich.
>F�r die Richtung Stelle->Bucket muss ich wie schon erw�hnt aus dem erdachten Abdeckungsfenster die hinteren Stellen raus nehmen, deren q- Gramme die Grenze �berschreiten.
>Die R�ckrichtung ist sp�ter nur noch f�r das Alignment wichtig, hier geh�ren ALLE abgedeckten Stellen rein, denn das Pattern kann ja auch am Ende eines Buckets stehen. Q-gramme, die dort ANFANGEN will ich nicht betrachten, aber die Buchstaben von Suchfenstern, die dort AUFH�REN sehr wohl.
>Das zweite, was gebraucht wird ist ein Z�hler f�r jeden Bucket, denn die interessante Frage ist ja: wie viele q- Gramme haben nun Pattern und Bucket gemeinsam? Und �berschreitet dies den Treshold, sodass der Bucket das Pattern enthalten k�nnte? Oder kann ich ihn vergessen f�r die genaue Suche.
>Als bucketcounter k�nnen einfach zwei int arrays dienen, deren Z�hler anfangs nat�rlich an jeder Stelle null ist.
>Die Vorher genannte zuweisung gibt dann also f�r jede Stelle in der Datenbank eine Stelle in den zwei counterarrays (2 f�r die beiden �berlappenden bucketreihen) an.
>Mit etwas Geschick geht das mit einer Funktion int zu int, die nur Minus, sowie div und mod benutzt.
>Die R�ckrichtung sollte noch einfacher sein. Die Ausgabe dieser Funktion muss dann weiter vom semi-globalen Aligner verarbeitet werden, aber dazu sp�ter.
>Erstmal zur�ck zum eigentlichen Quasar.
>Der ist jetzt n�mlich beinahe fertig. Was jetzt noch fehlt, ist der Algorithmus.
>Was TUT also der Quasar?
>Nun, zuerst macht er die besprochene vorprozessierung. Wie dir vermutlich aufgefallen ist, hat diese NUR mit der Datenbank, sowie mit der Windowsize zu tun, welche beide typischerweise patternunabh�ngig sind. Bei unserem Beispiel ist das window zwar das Pattern, aber der Wert ist bei allen deinen Pattern zum Gl�ck gleich.
>Nach dem Preprocessing werden folgende schritte gemacht:
>F�r jedes q- Gramm im Pattern do:
>- Q-Gramm in Zahl �bersetzen
>- diese Spalte sowie die nachfolgende in Tabelle auslesen.
>- Eintr�ge sind Spaltenindexe aus Suffixarray, dazwischenliegende Eintr�ge auslesen
>- mit Funktion f�r jede gefundene Stelle zugeh�rige Buckets (Array indizes) auslesen.
>- Counter an diesen Stellen um 1 erh�hen
>- Testen: Hat dieser Counter Treshold erreicht?
>- Wenn ja: Bucket markieren, Speichern oder was aus immer auch einf�llt.
>Wenn nein: Einfach weiter machen
>- wenn Pattern durchgelaufen:
>- Zu den markanten Buckets den abgedeckten Bereich an das semi- globale alignmenttool zusammen mit Pattern �bergeben.
>Alignment machen, hierbei: edit distance ist ein levenshtein mit match:0, gab:-1, missmatch -1.
>Frage: signifikantes Ergebnis gefunden? Wenn ja, ausgeben
>
>Dies kann man f�r mehrere Pattern wiederholen, die gleich lang sind, das Preprocessing muss dabei nur einmal gemacht werden. Deshalb auch die Effizienz.