Post by Andreas LeitgebPost by Hans-Peter DiettrichDie Tabelle soll alle Substrings erfassen, die sich aus dem Good Suffix
(Hits) und dem dem Bad Character (Miss) als Prefix ergeben. Diese
Substrings sind 1 Zeichen länger als das Suffix alleine, und können
damit mehr überflüssige Vergleiche eliminieren als die Good Suffix Regel
alleine.
Substring im Text "ba" --> Hits=1 (Suffix "a"), Miss='b'
Ok, ich glaub ich habs jetzt im Prinzip kapiert.
Sei n die Länge des Suchwortes, dann hätten wir n Tabellen mit je
sovielen Zeilen, wie der bis dahin gematchte Suffix plus ein "Miss"
an weiteren Treffern im Inneren des Suchstrings hat.
So in der Art. Das könnte dem Ansatz mit einem Automaten entsprechen?
Der Automat hätte dann Zustände entsprechend der Länge des Musters
(einen für jedes Suffix), die er mit jedem guten Vergleich sequentiell
durchläuft, und beim Auftreten eines Bad Character eine Verschiebung
entsprechend obiger Tabellen vornimmt, und in den ersten Zustand (leeres
Suffix) übergeht. Meine angedachte 2D Tabelle entspricht dann einer
(vereinfachten) Übergangstabelle (transition table) des Automaten.
Post by Andreas LeitgebDie Tabelle für den leeren Suffix entspricht dann genau der originalen
Miss-Tabelle, Die Tabelle zum 1-langen Suffix "a" des Suchwortes
'd'->3, 'c'->5, ?->10 - Für 'r' ist hier kein Eintrag nötig.
Die zum 2-langen Suffix "ra" hat nur ?->10, da das b ja bereits
ge-nicht-matcht wurde.
Damit könnte man (erst mal) auf die Prüfung aller längeren Suffixe
verzichten, da die zusammen mit irgendeinem Bad Character garantiert
keine neuen Substrings mehr ergeben können. Wäre da nicht der Fall eines
Präfix (hier "abra"), bei dem das Bad Character keine Rolle spielt, weil
es nach der Verschiebung nie wieder verglichen wird. Über diesen Fall
bin ich erst mal gestolpert, bis ich diesen Teil der Suffix-Tabelle
begriffen hatte.
Post by Andreas LeitgebJa, das könnte die Suche durchaus beschleunigen. Tut leid für die Zweifel
vorhin.
Immerhin hast Du Dir die Mühe des Mitdenkens gemacht, und nicht nur auf
irgendwelche Literatur verwiesen :-]
Post by Andreas LeitgebMeine vage Vermutung ist, dass damals, als der bekannte Algorithmus formuliert
wurde, diese Tabellen zuviel Platz gebraucht hätten, und da ein Kompromiss
zwischen Laufzeit und Speicher-effizienz gemacht wurde.
Das sehe ich genauso, danke für die Bestätigung :-)
Bezüglich der Tabellengröße bin ich auch schon weiter. Dein Anstoß mit
den n Einzeltabellen (ich hätte die als Listen bezeichnet) könnte dazu
verwendet werden, Speicher für die jeweils redundanten Tabellen (hier
für Miss=2..n) zu sparen, und zusätzlich die Good Suffix Tabelle von
Boyer-Moore zu übernehmen, um den Sonderfall mit dem Match eines echten
Prefix zu abzudecken.
Etwas konkreter:
Wenn zu einem konkreten Hit-Wert eine Tabelle existiert (wie oben von
Dir angegeben), diese verwenden. Andernfalls die Good Suffix Tabelle
verwenden, die hier so aussähe:
Hit=0..3->3 (letztes 'a' wird erstes 'a' des Suffix "abra" für den
nächsten Vergleich)
Hit=4..10->7 (letztes 'a' wird letztes 'a' des Präfix "abra")
Mehr als 10 Hits kommen nicht vor, denn dann wurde das Muster mit 11
Hits gefunden.
Eine weitere drastische Reduktion der Tabellengröße ist möglich, wenn
das Eingabealphabet in die Menge aller Zeichen im Muster abgebildet
wird, plus der Ersatzdarstellung für alle übrigen Zeichen des Alphabets.
Konkret wäre das "abcdr?", wo die Bad Character Tabelle von Boyer-Moore
256 für Ansi-Zeichen bzw. 64K für UTF-16 Zeichen lang wäre.
Damit wäre auch eine vollständige 2D Tabelle nicht mehr 256*11 Elemente
groß, sondern nur noch 6*11.
Post by Andreas LeitgebPost by Hans-Peter DiettrichWas mir in dieser Tabelle noch aufgefallen ist: mit z.B. Miss='c' oder
'd' ergibt sich eine Verschiebung um n-Hits für Hits=0 oder 1. Ist das
Zufall, oder läßt sich das irgendwie (als Regel) verallgemeinern?
Erzeug die Tabelle(n) einfach für andere Suchwörter, und sieh nach, ob
sich das Muster wiederholt...
Kannst Du ein passendes Wort vorschlagen?
Als Praxistest hätte ich gerne eine DNA Datei gehabt, die ein kleines
Alphabet "CGRT" hat, in der aber lange Muster zu suchen wären. Weiß
jemand, von wo so eine Datei heruntergeladen werden kann? Es muß ja
keine humane DNA sein, nur irgendwas mit vergleichbarem Aufbau der
einzelnen Abschnitte. Draufgebracht hat mich Q. T. Jackson mit seinem
MetaS Parser und dessen Anwendung in der DNA Analyse.
Dann könnte ich auch feststellen, wie nahe mein Verfahren an die "linear
time execution" O(n) (wie bei Galil) herankommt. Momentan fällt mir dazu
nur ein, die Vergleiche auf den neuen (geshifteten) Teil des Textes und
den alten (noch nicht verglichenen) Teil vor dem Bad Character) zu
beschränken, und den zuvor gematchen Teil (Good Suffix) zu überspringen.
Dieses Verfahren dürfte aber nur bei langen Mustern einen positiven
Effekt haben, bei kürzeren Mustern könnte der Overhead überwiegen.
Und dann war noch der Einwand, daß die Verwendung von Tabellen den
Prozessor-Cache sprengen könnte, und eine sture lineare Suche
tatsächlich schneller sein könnte. Der gilt aber auch nur so lange, als
das Muster in diesen Cache paßt. Noch ein Grund, warum ich nach einer
DNA Datei zum Testen von langen Mustern suche.
DoDi