>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.