Discussion:
Stringmuster
(zu alt für eine Antwort)
Hans-Peter Diettrich
2017-03-25 10:04:49 UTC
Permalink
Raw Message
Nach Boyer-Moore et al. kann die Suche nach einem Muster in einem String
abgekürzt werden, indem der Vergleich beim letzten Zeichen des Musters
beginnt. Dann kann aus der Anzahl der verglichenen (gleichen) Zeichen
[Hits] und dem davor liegenden (unpassenden) Zeichen [Miss] ermittelt
werden, wieviele Zeichen vor dem nächsten Vergleich mit dem Muster
übersprungen werden können.

Beim Versuch, die Tabelle für die Sprungweiten aufzubauen, bin ich über
das Muster "abracadabra" gestolpert. Wieviele Fälle sollten hier
berücksichtigt werden?

Hier der Anfang meiner Tabelle:
Hits Miss Shift
0 r 1
0 b 2
0 c 6
0 d 4
1 d 3
1 c 5
...
Alle übrigen 11

DoDi
Burkart Venzke
2017-03-26 22:20:26 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Nach Boyer-Moore et al. kann die Suche nach einem Muster in einem String
abgekürzt werden, indem der Vergleich beim letzten Zeichen des Musters
beginnt. Dann kann aus der Anzahl der verglichenen (gleichen) Zeichen
[Hits] und dem davor liegenden (unpassenden) Zeichen [Miss] ermittelt
werden, wieviele Zeichen vor dem nächsten Vergleich mit dem Muster
übersprungen werden können.
Beim Versuch, die Tabelle für die Sprungweiten aufzubauen, bin ich über
das Muster "abracadabra" gestolpert. Wieviele Fälle sollten hier
berücksichtigt werden?
Hits Miss Shift
0 r 1
0 b 2
0 c 6
0 d 4
1 d 3
1 c 5
...
Alle übrigen 11
DoDi
Ich fürchte, deine Beschreibung ist nicht verständlich genug, dass man
sie verstehen kann.
Vielleicht hilft eine detailliertere Beschreibung zu "abracadabra"?

Was mir an dem Algorithmus nicht klar ist, warum von
Bad-Character-Heuristik und Good-Suffix-Heuristik gesprochen wird.
Eine Heuristik ist doch "mit begrenztem Wissen (unvollständigen
Informationen) und wenig Zeit dennoch zu wahrscheinlichen Aussagen oder
praktikablen Lösungen zu kommen".
Aber soll der Algorithmus nicht perfekt ein Sting-Muster finden?

Gruß, Burkart
Tom Bola
2017-03-26 22:36:53 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Boyer-Moore
https://de.wikipedia.org/wiki/Boyer-Moore-Algorithmus

https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
Hans-Peter Diettrich
2017-03-27 07:18:30 UTC
Permalink
Raw Message
Post by Tom Bola
Post by Hans-Peter Diettrich
Boyer-Moore
https://de.wikipedia.org/wiki/Boyer-Moore-Algorithmus
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
Erst nachdem ich meine eigene Version implementiert hatte, habe ich die
Beschreibung von Good Suffix in der englischen Version halbwegs
verstanden. Aber die Beispiel-Implementierung scheint mir unvollständig
zu sein. Was mich stört ist die ausschließliche Abhängigkeit von delta1
vom gefundenen (schlechten) Zeichen, und von delta2 von der Länge des
gefundenen (guten) Suffix. Müßte nicht auch ein Suffix berücksichtigt
werden, das aus dem guten Suffix *und* dem schlechten Zeichen besteht?

Kann mir jemand erklären bzw. beweisen, daß die zwei Tabellen in der
gezeigten Form ausreichend sind?

Wenn nach meiner Tabelle ein 'd' einmal in einer Verschiebung um 4
resultiert ("d"), oder um 3 ("da"), dann können diese beiden Ergebnisse
doch nicht mit einem einzigen Eintrag delta1['d'] erschlagen werden.
Noch weniger ein "dra", das im Pattern überaupt nicht vorkommt, und
daher zu einer Verschiebung um 11 (Pattern-Länge) führen sollte.

Habe ich eine Verbesserung des Boyer-Moore Algorithmus gefunden, oder wo
liegt der Fehler?

DoDi
Tom Bola
2017-03-27 11:50:44 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Post by Tom Bola
Post by Hans-Peter Diettrich
Boyer-Moore
https://de.wikipedia.org/wiki/Boyer-Moore-Algorithmus
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
Boyer-Moore Algorithmus
Hier erklärt Moore seinen Algorithmus interaktiv:

http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/fstrpos-example.html
Tom Bola
2017-03-27 12:55:52 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Nach Boyer-Moore et al. kann die Suche nach einem Muster in einem String
abgekürzt werden, indem der Vergleich beim letzten Zeichen des Musters
beginnt. Dann kann aus der Anzahl der verglichenen (gleichen) Zeichen
[Hits] und dem davor liegenden (unpassenden) Zeichen [Miss] ermittelt
werden, wieviele Zeichen vor dem nächsten Vergleich mit dem Muster
übersprungen werden können.
Nun gib doch endlich einmal die Quelle an, auf die du dich oben und in
Post by Hans-Peter Diettrich
Beim Versuch, die Tabelle für die Sprungweiten aufzubauen, bin ich über
das Muster "abracadabra" gestolpert. Wieviele Fälle sollten hier
berücksichtigt werden?
Es gibt jede Menge Möglichkeiten die Funktion zu implementieren, die
den aktuellen Shift-Vorschlag macht (oder absolut pro Text) und DAZU
gibt es dann noch mehr Möglichkeiten, ein Preprocessing durchzuführen,
das für jeden Pattern, das gesucht wird (im Rahmen des betrachteten
Alphabets) konstant ist.
Post by Hans-Peter Diettrich
Hits Miss Shift
0 r 1
0 b 2
0 c 6
0 d 4
1 d 3
1 c 5
...
Alle übrigen 11
Hans-Peter Diettrich
2017-03-27 22:48:06 UTC
Permalink
Raw Message
Post by Tom Bola
Nun gib doch endlich einmal die Quelle an, auf die du dich oben und in
Die Quelle bin ich, inspiriert von der Erklärung der Boyer-Moore Heuristik.

Aber ich sehe schon, daß ich da eine Erweiterung von Boyer-Moore
entwickelt habe, mit der sich niemand beschäftigen möchte.
Wahrscheinlich wurde diese Variante auch schon untersucht, so daß sich
damit kein Blumentopf mehr gewinnen läßt. Das war ja auch nicht der
Anlaß für meine Frage in dieser Gruppe, aber die Resonanz ist doch etwas
<ähm...> ernüchternd :-(

DoDi
Tom Bola
2017-03-28 05:10:57 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Post by Tom Bola
Nun gib doch endlich einmal die Quelle an, auf die du dich oben und in
Die Quelle bin ich, inspiriert von der Erklärung der Boyer-Moore Heuristik.
Ich meine die sprachliche Definition, die du verwendet hast.

Hier steht alles in perfektem Deutsch:
http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/bm.htm
Post by Hans-Peter Diettrich
Aber ich sehe schon, daß ich da eine Erweiterung von Boyer-Moore
entwickelt habe, mit der sich niemand beschäftigen möchte.
Und hier sind die gebräuchlichsten Varianenten genaustens beschrieben:
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/
Post by Hans-Peter Diettrich
Wahrscheinlich wurde diese Variante auch schon untersucht, so daß sich
damit kein Blumentopf mehr gewinnen läßt. Das war ja auch nicht der
Anlaß für meine Frage in dieser Gruppe, aber die Resonanz ist doch etwas
<ähm...> ernüchternd :-(
Du hättest genau sagen sollen, wie dein Tabelle zustande kam.
Hans-Peter Diettrich
2017-03-28 17:18:02 UTC
Permalink
Raw Message
Post by Tom Bola
Post by Hans-Peter Diettrich
Post by Tom Bola
Nun gib doch endlich einmal die Quelle an, auf die du dich oben und in
Die Quelle bin ich, inspiriert von der Erklärung der Boyer-Moore Heuristik.
Ich meine die sprachliche Definition, die du verwendet hast.
Die Bezeichnungen Hits und Miss habe ich selbst erfunden, weil sie mir
im Kontext unverwechselbar und schön kurz und prägnant erschienen.
Post by Tom Bola
http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/bm.htm
Post by Hans-Peter Diettrich
Aber ich sehe schon, daß ich da eine Erweiterung von Boyer-Moore
entwickelt habe, mit der sich niemand beschäftigen möchte.
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/
Mein Verfahren scheint da nicht dabei zu sein.
Post by Tom Bola
Post by Hans-Peter Diettrich
Wahrscheinlich wurde diese Variante auch schon untersucht, so daß sich
damit kein Blumentopf mehr gewinnen läßt. Das war ja auch nicht der
Anlaß für meine Frage in dieser Gruppe, aber die Resonanz ist doch etwas
<ähm...> ernüchternd :-(
Du hättest genau sagen sollen, wie dein Tabelle zustande kam.
Durch Überlegung. Über die Implementierung habe ich mir auch schon
Gedanken gemacht, aber zuvor möchte ich wissen, was in einer
vollständigen Tabelle drinstehen sollte, d.h. welche Kombinationen von
Good Suffix (Hits) und Bad Character (Miss) zur Beschleunigung der Suche
beitragen.

DoDi
Tom Bola
2017-03-28 18:00:49 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Post by Tom Bola
Post by Hans-Peter Diettrich
Post by Tom Bola
Nun gib doch endlich einmal die Quelle an, auf die du dich oben und in
Die Quelle bin ich, inspiriert von der Erklärung der Boyer-Moore Heuristik.
Ich meine die sprachliche Definition, die du verwendet hast.
Die Bezeichnungen Hits und Miss habe ich selbst erfunden, weil sie mir
im Kontext unverwechselbar und schön kurz und prägnant erschienen.
Post by Tom Bola
http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/bm.htm
Post by Hans-Peter Diettrich
Aber ich sehe schon, daß ich da eine Erweiterung von Boyer-Moore
entwickelt habe, mit der sich niemand beschäftigen möchte.
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/
Mein Verfahren scheint da nicht dabei zu sein.
Post by Tom Bola
Post by Hans-Peter Diettrich
Wahrscheinlich wurde diese Variante auch schon untersucht, so daß sich
damit kein Blumentopf mehr gewinnen läßt. Das war ja auch nicht der
Anlaß für meine Frage in dieser Gruppe, aber die Resonanz ist doch etwas
<ähm...> ernüchternd :-(
Du hättest genau sagen sollen, wie dein Tabelle zustande kam.
Durch Überlegung. Über die Implementierung habe ich mir auch schon
Gedanken gemacht, aber zuvor möchte ich wissen, was in einer
vollständigen Tabelle drinstehen sollte, d.h. welche Kombinationen von
Good Suffix (Hits) und Bad Character (Miss) zur Beschleunigung der Suche
beitragen.
Dann lies also weiter, Literatur ist ja üppig vorhanden und online
zugänglich.
Hans-Peter Diettrich
2017-03-28 23:56:31 UTC
Permalink
Raw Message
Post by Tom Bola
Dann lies also weiter, Literatur ist ja üppig vorhanden und online
zugänglich.
Danke für diesen wertvollen Beitrag zu meinen Fragen :-]

DoDi
Tom Bola
2017-03-29 08:17:34 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Post by Tom Bola
Dann lies also weiter, Literatur ist ja üppig vorhanden und online
zugänglich.
Danke für diesen wertvollen Beitrag zu meinen Fragen :-]
Hier noch einige Implementierungen
http://www.codecodex.com/wiki/Boyer-Moore_Algorithm_Examples

und eine ganz besonders gut zu verstehendes Beispiel:
http://yukcaracari.blogspot.de/2016/05/source-code-algooritma-boyer-moore-c.html

Falls du noch Fragen entwickelst, dann bezieh dich bitte auf dieses paper:
http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/bm.htm
Andreas Leitgeb
2017-03-29 09:40:44 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Nach Boyer-Moore et al. kann die Suche nach einem Muster in einem String
abgekürzt werden, indem der Vergleich beim letzten Zeichen des Musters
beginnt. Dann kann aus der Anzahl der verglichenen (gleichen) Zeichen
[Hits] und dem davor liegenden (unpassenden) Zeichen [Miss] ermittelt
werden, wieviele Zeichen vor dem nächsten Vergleich mit dem Muster
übersprungen werden können.
Beim Versuch, die Tabelle für die Sprungweiten aufzubauen, bin ich über
das Muster "abracadabra" gestolpert. Wieviele Fälle sollten hier
berücksichtigt werden?
Hab den bisherigen Dialog kurz überflogen...

Mir (und wenn ich ihn nicht falsch gelesen habe auch dem Tom Bola) ist die
folgende Tabelle ziemlich unklar, was sie denn nun erfassen sollte, und
wie sie konstruiert ist.

Die zwei Kriterien, Hits und Miss sind zueinander orthogonal, denn
welches "Miss"-Zeichen im "Heuhaufen" an einer Stelle auftritt, hat nichts
mit dem Suchwort, bzw der Länge des partiellen "Hits" zu tun, der zum Finden
des Miss-Zeichens führte. Das nun in einer Tabelle zusammenzufassen hat nur
geringe Aussicht auf Erfolg.

Was nun die "Miss"es angeht, kann man bei einem "y" nicht automatisch
das Suchwort um seine volle Länge weiterverschieben, sondern nur soweit,
bis das Wort hinter diesem "Miss"-Buchstaben platziert ist:

Heuhaufen: abracayabracadabra
SuchString: abracadabra

Wenn also das "y" als Miss gefunden wird, ist der "Shift" nicht 11
sondern nur 7.

Mag sein, dass ich da jetzt auch nur wieder einiges falsch verstanden habe.
Im Zweifelsfall, probier einfach, deinen Ansatz zu implementieren, und lass
ihn suchen. Falls deine Tabelle nicht algorithmisch berechenbar ist, oder
die Berechnung der Tabelle gar vom Heuhaufen abhängt, dann ist der Ansatz
ja leider sowieso nur von theoretischer Bedeutung, wenn überhaupt...
Post by Hans-Peter Diettrich
Hits Miss Shift
0 r 1
0 b 2
0 c 6
0 d 4
1 d 3
1 c 5
...
Alle übrigen 11
Hans-Peter Diettrich
2017-03-29 13:57:18 UTC
Permalink
Raw Message
Post by Andreas Leitgeb
Post by Hans-Peter Diettrich
Nach Boyer-Moore et al. kann die Suche nach einem Muster in einem String
abgekürzt werden, indem der Vergleich beim letzten Zeichen des Musters
beginnt. Dann kann aus der Anzahl der verglichenen (gleichen) Zeichen
[Hits] und dem davor liegenden (unpassenden) Zeichen [Miss] ermittelt
werden, wieviele Zeichen vor dem nächsten Vergleich mit dem Muster
übersprungen werden können.
Beim Versuch, die Tabelle für die Sprungweiten aufzubauen, bin ich über
das Muster "abracadabra" gestolpert. Wieviele Fälle sollten hier
berücksichtigt werden?
Hab den bisherigen Dialog kurz überflogen...
Mir (und wenn ich ihn nicht falsch gelesen habe auch dem Tom Bola) ist die
folgende Tabelle ziemlich unklar, was sie denn nun erfassen sollte, und
wie sie konstruiert ist.
Die 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.

Beispiel zu "abracadabra":
Substring im Text "ba" --> Hits=1 (Suffix "a"), Miss='b'

Dieser Substring kommt im Muster nicht vor, also kann das Muster um 10
Positionen verschoben werden. Die Bad Character Regel alleine schlägt
hier eine Verschiebung um nur 1 Zeichen vor, Good Suffix alleine nur
eine Verschiebung um 3 Zeichen.

Dieser Teil der Tabelle läßt sich im Prinzip durch Suche nach allen
möglichen Substrings (Bad Character+Good Suffix) mit dem Suchmuster
konstruieren. Die endgültige Konstruktionsvorschrift kann erst angegeben
werden, wenn die Konstruktion aller zu berücksichtigenden Regeln bekannt
ist, einschließlich Good Prefix [Galil].
Post by Andreas Leitgeb
Die zwei Kriterien, Hits und Miss sind zueinander orthogonal, denn
welches "Miss"-Zeichen im "Heuhaufen" an einer Stelle auftritt, hat nichts
mit dem Suchwort, bzw der Länge des partiellen "Hits" zu tun, der zum Finden
des Miss-Zeichens führte. Das nun in einer Tabelle zusammenzufassen hat nur
geringe Aussicht auf Erfolg.
Siehe oben, eine Erhöhung von 3 auf 10 Schiebe-Positionen halte ich für
durchaus erfolgreich.
Post by Andreas Leitgeb
Was nun die "Miss"es angeht, kann man bei einem "y" nicht automatisch
das Suchwort um seine volle Länge weiterverschieben, sondern nur soweit,
Heuhaufen: abracayabracadabra
SuchString: abracadabra
Wenn also das "y" als Miss gefunden wird, ist der "Shift" nicht 11
sondern nur 7.
In diesem Beispiel wird Hits=4 und Miss='y' gefunden, das wäre Teil der
ausgelassenen "..." in der angegebenen (unvollständigen) Tabelle. Ich
trage diesen Fall in die Tabelle unten ein, mit '?' als Joker für alle
Zeichen, die im Muster nicht vorkommen.
Post by Andreas Leitgeb
Mag sein, dass ich da jetzt auch nur wieder einiges falsch verstanden habe.
Im Zweifelsfall, probier einfach, deinen Ansatz zu implementieren, und lass
ihn suchen.
Das habe ich bereits erledigt, funktioniert so weit. Ich hätte aber
gerne eine Tabelle, in der *alle* möglichen Abkürzungen enthalten sind,
und nicht nur die, welche meine derzeitige Implementierung findet.
Vielleicht ist ja der Algorithmus noch verbesserungsbedürftig? Deshalb
hätte ich gerne Vorschläge, welche Fälle noch in die Tabelle eingetragen
werden sollten.
Post by Andreas Leitgeb
Falls deine Tabelle nicht algorithmisch berechenbar ist, oder
die Berechnung der Tabelle gar vom Heuhaufen abhängt, dann ist der Ansatz
ja leider sowieso nur von theoretischer Bedeutung, wenn überhaupt...
Post by Hans-Peter Diettrich
Hits Miss Shift
0 r 1
0 b 2
0 c 6
0 d 4
1 d 3
1 c 5
...
4 ? 7 (Good Suffix Regel für Hits=4..10)
Post by Andreas Leitgeb
Post by Hans-Peter Diettrich
...
Alle übrigen 11
Was 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?

DoDi
Tom Bola
2017-03-29 16:04:35 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
hätte ich gerne Vorschläge, welche Fälle noch in die Tabelle eingetragen
werden
Das steht ja alles in der Literatur, und besser geht es nicht.
Wenn du über Einzelheiten sprechen willst, dann musst du dich
KONKRET darauf beziehen und notfalls deinen Pseudo-Code oder
Code unter Remarking auf den gebrauchten Algorithmus nennen.

Z.Bl.:

"Der Suchalgorithmus vergleicht die Zeichen des Musters von rechts nach
links mit dem Text. Bei vollständiger Übereinstimmung wird das Muster
anschließend so weit geschoben, wie es sein Rand zulässt. Nach einem
Mismatch wird das Muster um das Maximum der Werte geschoben, die sich
aus der Gutes-Ende- und der Schlechtes-Zeichen-Strategie ergeben. "
...

Rand: (*)

"
Definition:  Sei A ein Alphabet und  x = x0 ... xk-1,  k     ein Wort
der Länge k über A.
 
Ein Präfix von x ist ein Teilwort u mit
u  =  x0 ... xb-1   wobei  b  {0, ..., k},
also ein Anfangswort der Länge b von x.
 
Ein Suffix von x ist ein Teilwort u mit
u  =  xk-b ... xk-1   wobei  b  {0, ..., k},
also ein Endwort der Länge b von x.
 
Ein Präfix u von x bzw. ein Suffix u von x heißt echt,
wenn u ≠ x ist, d.h. wenn die Länge b<k ist.
 
(*)
Ein Rand von x ist ein Teilwort r mit

r  =  x0 ... xb-1  und  r  =  xk-b ... xk-1
wobei  b  {0, ..., k-1}
 
Ein Rand von x ist also ein Wort, das gleichzeitig echtes
Präfix und echtes Suffix von x ist.
Die Länge b wird als die Breite des Randes r bezeichnet.

Beispiel:  Sei x = abacab. Die echten Präfixe von x sind
ε, a, ab, aba, abac, abaca.
 
Die echten Suffixe von x sind
ε, b, ab, cab, acab, bacab.
 
Ränder von x sind
ε, ab.
 
Der Rand ab hat die Breite 2.
Stets ist das leere Wort ε ein Rand von x,  x  A+. Lediglich ε selbst
hat keinen Rand.

In folgendem Beispiel wird deutlich, wie mithilfe des Begriffes "Rand" die
Schiebe­distanz beim Knuth-Morris-Pratt-Algorithmus ermittelt wird.

Beispiel:  
...

Die Zeichen an den Positionen 0, ..., 4 haben überein­gestimmt. Der
Vergleich c-d an Position 5 ergibt einen Mismatch. Das Muster kann
bis Position 3 weiter­geschoben werden, und der Vergleich wird ab
Position 5 des Textes fortgesetzt.
Die Schiebedistanz richtet sich nach dem breitesten Rand des
über­einstimmenden Präfixes des Musters. In diesem Beispiel ist
das über­einstimmende Präfix abcab; es hat die Länge j = 5. Sein
breitester Rand ist ab mit der Breite b = 2. Die Schiebe­distanz beträgt
j – b  =  5 – 2  =  3.
Die im Vorlauf zu gewinnende Information besteht also darin, für jedes
Präfix des Musters die Länge seines breitesten Randes zu bestimmen. "
Ralf Goertz
2017-03-30 07:00:21 UTC
Permalink
Raw Message
Am Wed, 29 Mar 2017 18:04:35 +0200
Post by Tom Bola
Beispiel:  
...
Die Zeichen an den Positionen 0, ..., 4 haben überein­gestimmt. Der
Vergleich c-d an Position 5 ergibt einen Mismatch. Das Muster kann
bis Position 3 weiter­geschoben werden, und der Vergleich wird ab
Position 5 des Textes fortgesetzt.
Hm, vielleicht verstehe ich ja Deine Beschreibung nicht, aber was ist
mit

Text: aaaaaab
Suchstring: aaaaab
___________________
Position: 0123456

In diesem Fall würde ich mit Deinem Algorithmus den Suchstring nicht
finden oder?
Tom Bola
2017-03-30 08:53:46 UTC
Permalink
Raw Message
Post by Ralf Goertz
Post by Tom Bola
Beispiel:  
...
Da http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/bm.htm
steht dann noch

0 1 2 3 4 5 6 7 8 9 ...
a b c a b c a b d
a b c a b (d)
a b c a b d

was ich nicht abgetippt hatte.
Post by Ralf Goertz
Post by Tom Bola
Die Zeichen an den Positionen 0, ..., 4 haben überein­gestimmt. Der
Vergleich c-d an Position 5 ergibt einen Mismatch. Das Muster kann
bis Position 3 weiter­geschoben werden, und der Vergleich wird ab
Position 5 des Textes fortgesetzt.
Hm, vielleicht verstehe ich ja Deine Beschreibung nicht,
Dir fehlt Information, weil du das Paper nicht gelesen hast. Ich wollte
durch das Zitat nur *andeuten*, dass wegen der üppig vorbildlich guten
Literatursituation "ein vages Vermuten" alos nicht nötig ist,

Nach
Beispiel:  
0 1 2 3 4 5 6 7 8 9 ...
a b c a b c a b d
a b c a b (d)
a b c a b d

in der Quelle steht dann weiter zitiert im Posting:

"Die Schiebedistanz richtet sich nach dem breitesten Rand des
übereinstimmenden Präfixes des Musters.

In diesem Beispiel ist
das übereinstimmende Präfix abcab; es hat die Länge j = 5. Sein
breitester Rand ist ab mit der Breite b = 2. Die Schiebedistanz beträgt
j – b  =  5 – 2  =  3.
Die im Vorlauf zu gewinnende Information besteht also darin, für jedes
Präfix des Musters die Länge seines breitesten Randes zu bestimmen. "
Post by Ralf Goertz
aber was ist
mit
Text: aaaaaab
Suchstring: aaaaab
___________________
Position: 0123456
In diesem Fall würde ich mit Deinem Algorithmus den Suchstring nicht
finden oder?
In deinem Fall das Teilwort "aaaaab" sicherlich das mit dem Suchtext
übereinstimmende Präfix aaaaa mit Breite 5, und (d.h. hier aber) dein
Suchmuster "aaaaaab" hat die echten Prefixe
a, aa, aaa, aaaa, aaaaa und die echten Suffixe
b, ab, aab, aaab, aaaab und damit einen (leeren) Rand der Breite 0,
so dass du folglich lediglich immer nur eine Position schieben kannst.
Hans-Peter Diettrich
2017-03-30 10:18:19 UTC
Permalink
Raw Message
Post by Tom Bola
Post by Ralf Goertz
Hm, vielleicht verstehe ich ja Deine Beschreibung nicht,
Dir fehlt Information, weil du das Paper nicht gelesen hast. Ich wollte
durch das Zitat nur *andeuten*, dass wegen der üppig vorbildlich guten
Literatursituation "ein vages Vermuten" alos nicht nötig ist,
Die Literatur gibt aber auch keine Begründung her, warum man sich mit 3m
bis 5m Vergleichen zufrieden gab, wenn das auch mit worst case 1m
Vergleichen möglich ist.

DoDi
Tom Bola
2017-03-30 11:04:41 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Post by Tom Bola
Post by Ralf Goertz
Hm, vielleicht verstehe ich ja Deine Beschreibung nicht,
Dir fehlt Information, weil du das Paper nicht gelesen hast. Ich wollte
durch das Zitat nur *andeuten*, dass wegen der üppig vorbildlich guten
Literatursituation "ein vages Vermuten" alos nicht nötig ist,
Die Literatur gibt aber auch keine Begründung her, warum man sich mit 3m
bis 5m Vergleichen zufrieden gab, wenn das auch mit worst case 1m
Vergleichen möglich ist.
Hast du das schon gelesen?
http://www.cs.utexas.edu/~moore/publications/fstrpos.pdf

Hier dürfte es sicherlich drin stehen:
http://www.cs.nyu.edu/cs/faculty/cole/papers/CHPZ95.ps
Hans-Peter Diettrich
2017-03-30 14:52:54 UTC
Permalink
Raw Message
Post by Tom Bola
Post by Hans-Peter Diettrich
Post by Tom Bola
Post by Ralf Goertz
Hm, vielleicht verstehe ich ja Deine Beschreibung nicht,
Dir fehlt Information, weil du das Paper nicht gelesen hast. Ich wollte
durch das Zitat nur *andeuten*, dass wegen der üppig vorbildlich guten
Literatursituation "ein vages Vermuten" alos nicht nötig ist,
Die Literatur gibt aber auch keine Begründung her, warum man sich mit 3m
bis 5m Vergleichen zufrieden gab, wenn das auch mit worst case 1m
Vergleichen möglich ist.
Hast du das schon gelesen?
http://www.cs.utexas.edu/~moore/publications/fstrpos.pdf
Danke, das beschreibt genau den Algorithmus, den ich aus der
Beschreibung in Wikipedia abgeleitet und verbessert habe. Offensichtlich
bezieht sich Wikipedia noch auf die erste Version des Boyer-Moore
Algorithmus, ohne diese Verbesserung.

Danke für das Wühlen in der Literatur :-)

DoDi
Tom Bola
2017-03-30 15:18:43 UTC
Permalink
Raw Message
Danke, das beschreibt genau den Algorithmus ...
Hier ist der start in die Welt der Genome:
https://www.ncbi.nlm.nih.gov/genome/doc/ftpfaq/

Was du haben willst ist eine *bare sequence* aus irgendeinem Chromosom.

Die .agp Files sind Textfiles und die Sequenz-Rohdaten werden ("oft")
jeweils als *FASTA-Sequenz* gespeichert, siehe hier:
https://blast.ncbi.nlm.nih.gov/Blast.cgi?CMD=Web&PAGE_TYPE=BlastDocs&DOC_TYPE=BlastHelp


Und hier ein Beispiel, fertig zum benutzen:

https://www.ncbi.nlm.nih.gov/genbank/samplerecord/

;)
Tom Bola
2017-03-30 15:58:00 UTC
Permalink
Raw Message
...
Hier ist das Endergebnis, wie du am besten an "bare sequence"s kommst:

1) Such dir hier ein Chromosom aus, zBl [1] :
https://www.ncbi.nlm.nih.gov/projects/mapview/maps.cgi?taxid=9606

2) Klicke rechts oben auf Download/View Sequence/Evidence dann bist du hier:
https://www.ncbi.nlm.nih.gov/projects/mapview/seq_reg.cgi?taxid=9606&chr=1&from=1&to=248956422

3) Wähle recht oben Sequence Format: FASTA

4) Klicke Display oder Save to Disk
Hans-Peter Diettrich
2017-03-31 15:51:49 UTC
Permalink
Raw Message
Post by Tom Bola
...
https://www.ncbi.nlm.nih.gov/projects/mapview/maps.cgi?taxid=9606
https://www.ncbi.nlm.nih.gov/projects/mapview/seq_reg.cgi?taxid=9606&chr=1&from=1&to=248956422
3) Wähle recht oben Sequence Format: FASTA
4) Klicke Display oder Save to Disk
Danke für die ausführliche Gebrauchsanweisung, genau sowas habe ich
gesucht :-)

Allerdings konnte ich nach "Save to Disk" keine Datei finden, man muß
die Seite wohl explizit im Firefox speichern. Mit dem Format "FASTA
(text)" bekommt man die Daten ohne viel Dekoration.

Jetzt muß ich mir wohl was einfallen lassen, um Umbrüche zu
überspringen. Sind die Leerzeilen wirklich nur optische Trenner, oder
wird da ein Teil des Genoms übersprungen? Oder stammen die von WordPad?

Und dann die Tabellen an das kleine Alphabet anpassen. AFAIR sollten
dafür sogar Tripel benutzt werden, nicht einzelne Zeichen. Mal sehen...

DoDi
Tom Bola
2017-03-31 16:03:48 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Post by Tom Bola
...
https://www.ncbi.nlm.nih.gov/projects/mapview/maps.cgi?taxid=9606
https://www.ncbi.nlm.nih.gov/projects/mapview/seq_reg.cgi?taxid=9606&chr=1&from=1&to=248956422
3) Wähle recht oben Sequence Format: FASTA
4) Klicke Display oder Save to Disk
Danke für die ausführliche Gebrauchsanweisung, genau sowas habe ich
gesucht :-)
Allerdings konnte ich nach "Save to Disk" keine Datei finden, man muß
die Seite wohl explizit im Firefox speichern. Mit dem Format "FASTA
(text)" bekommt man die Daten ohne viel Dekoration.
Jetzt muß ich mir wohl was einfallen lassen, um Umbrüche zu
überspringen. Sind die Leerzeilen wirklich nur optische Trenner, oder
wird da ein Teil des Genoms übersprungen? Oder stammen die von WordPad?
Und dann die Tabellen an das kleine Alphabet anpassen. AFAIR sollten
dafür sogar Tripel benutzt werden, nicht einzelne Zeichen. Mal sehen...
Die Anweisung in html ist (in Firefox Kontext-Menu "Inspect Element (Q)":
"a href="javascript:SaveToFile('NT_077402.3',1,197666,'+')">Save to Disk</a"

Du musst deinem Browser also nur (Java-) Scripting erlauben.
Ralf Goertz
2017-03-31 17:25:26 UTC
Permalink
Raw Message
Am Fri, 31 Mar 2017 17:51:49 +0200
Post by Hans-Peter Diettrich
Danke für die ausführliche Gebrauchsanweisung, genau sowas habe ich
gesucht :-)
Also ich habe ein wenig mit erzeugten Zufallswerten in C++ gespielt
(nachdem ich es erst mit π versucht hatte, was aber wegen des 10
ziffrigen Alphabets nicht so geeignet schien), der Text 10 Millionen
Zeichen (Alphabet 4 Zeichen) und Suchstring ungefähr 200 Zeichen. Der
Unterschied zwischen einer naiven Suche und dem Boyer-Moore-Algorithmus
war nicht berauschend, etwa 3,2 Sekunden naiv und 2,8 clever. Der naive
Algorithmus ist einfach string.find()

http://www.cplusplus.com/reference/string/string/find/

und der andere die Implementation in boost.

http://www.boost.org/doc/libs/1_63_0/libs/algorithm/doc/html/algorithm/Searching.html#the_boost_algorithm_library.Searching.BoyerMoore

Das mag daran liegen, dass es immer noch zu kleine Texte/Muster sind.
Aber vermutlich werde ich den Algorithmus im täglichen Leben nicht
brauchen.
Post by Hans-Peter Diettrich
Jetzt muß ich mir wohl was einfallen lassen, um Umbrüche zu
überspringen. Sind die Leerzeilen wirklich nur optische Trenner, oder
wird da ein Teil des Genoms übersprungen? Oder stammen die von WordPad?
Mit einem guten Texteditor kriegst Du die leicht weg. In vim zum
Beispiel sollte

:%s/\v[ \n]+//

sowohl Leerzeichen als auch Zeilenumbrüche entfernen.
Hans-Peter Diettrich
2017-04-01 09:25:21 UTC
Permalink
Raw Message
Post by Ralf Goertz
Am Fri, 31 Mar 2017 17:51:49 +0200
Post by Hans-Peter Diettrich
Danke für die ausführliche Gebrauchsanweisung, genau sowas habe ich
gesucht :-)
Also ich habe ein wenig mit erzeugten Zufallswerten in C++ gespielt
(nachdem ich es erst mit π versucht hatte, was aber wegen des 10
ziffrigen Alphabets nicht so geeignet schien), der Text 10 Millionen
Zeichen (Alphabet 4 Zeichen) und Suchstring ungefähr 200 Zeichen. Der
Unterschied zwischen einer naiven Suche und dem Boyer-Moore-Algorithmus
war nicht berauschend, etwa 3,2 Sekunden naiv und 2,8 clever. Der naive
Algorithmus ist einfach string.find()
Ich habe eine Versuchsreihe vor, mit stetig wachsender Länge des
Suchstrings. Was mich dabei interessiert ist die Anzahl der dabei
getätigten Vergleiche. Schließlich bin ich ja selbst draufgekommen, die
Suchstrategie zu verbessern, und möchte nun wissen, wieviel das
ausmacht. Wie sich die Modifikationen real (Suchzeit) auswirken, scheint
tatsächlich nicht so wesentlich zu sein, möglicherweise bremst da
wirklich die Tabellensuche den Cache aus.
Post by Ralf Goertz
Das mag daran liegen, dass es immer noch zu kleine Texte/Muster sind.
Aber vermutlich werde ich den Algorithmus im täglichen Leben nicht
brauchen.
Scheint mir auch so.
Post by Ralf Goertz
Post by Hans-Peter Diettrich
Jetzt muß ich mir wohl was einfallen lassen, um Umbrüche zu
überspringen. Sind die Leerzeilen wirklich nur optische Trenner, oder
wird da ein Teil des Genoms übersprungen? Oder stammen die von WordPad?
Mit einem guten Texteditor kriegst Du die leicht weg. In vim zum
Beispiel sollte
:%s/\v[ \n]+//
sowohl Leerzeichen als auch Zeilenumbrüche entfernen.
Im Prinzip ja, aber mit Kommandozeilen stehe ich auf Kriegsfuß. Merken
kann ich mir die Tools und ihre Kommandos nicht, ich brauche einfach ein
GUI. Mit Delphi ist es ja ein Klacks (10 Zeilen), die Dateien in der
gewünschten Form in den Speicher zu bringen, und dann kann die Suche
losgehen.

DoDi
Volker Borchert
2017-04-01 19:01:29 UTC
Permalink
Raw Message
Post by Ralf Goertz
Also ich habe ein wenig mit erzeugten Zufallswerten in C++ gespielt
(nachdem ich es erst mit ?? versucht hatte, was aber wegen des 10
ziffrigen Alphabets nicht so geeignet schien), der Text 10 Millionen
Zeichen (Alphabet 4 Zeichen) und Suchstring ungefähr 200 Zeichen. Der
Unterschied zwischen einer naiven Suche und dem Boyer-Moore-Algorithmus
war nicht berauschend, etwa 3,2 Sekunden naiv und 2,8 clever. Der naive
Algorithmus ist einfach string.find()
http://www.cplusplus.com/reference/string/string/find/
und der andere die Implementation in boost.
http://www.boost.org/doc/libs/1_63_0/libs/algorithm/doc/html/algorithm/Searching.html#the_boost_algorithm_library.Searching.BoyerMoore
Das mag daran liegen, dass es immer noch zu kleine Texte/Muster sind.
Eher daran, daß du nur kurze partial matches hast. KMP und BM bringen
dann was, wenn du schon hundert Zeichen deines zweihundertzeichigen
Suchstrings gematcht hast und beim hundertersten "Sch...." denkst,
indem sie einen Teil der Information aus den schon gematchten Zeichen
weiterverwenden. Wenns immer schon beim zweiten Zeichen schiefgeht,
ist da nicht viel zu gewinnen.
--
"I'm a doctor, not a mechanic." Dr Leonard McCoy <***@ncc1701.starfleet.fed>
"I'm a mechanic, not a doctor." Volker Borchert <***@despammed.com>
Ralf Goertz
2017-04-01 20:19:05 UTC
Permalink
Raw Message
Am 1 Apr 2017 19:01:29 GMT
Post by Volker Borchert
Post by Ralf Goertz
Das mag daran liegen, dass es immer noch zu kleine Texte/Muster sind.
Eher daran, daß du nur kurze partial matches hast. KMP und BM bringen
dann was, wenn du schon hundert Zeichen deines zweihundertzeichigen
Suchstrings gematcht hast und beim hundertersten "Sch...." denkst,
indem sie einen Teil der Information aus den schon gematchten Zeichen
weiterverwenden. Wenns immer schon beim zweiten Zeichen schiefgeht,
ist da nicht viel zu gewinnen.
Ja, sowas habe ich auch schon gedacht. Aber wann kommt das schon mal
vor? Ich muss öfter mal nach bestimmten Mustern in Texten suchen, aber
ein solches Szenario ist *mir* irgendwie bisher nicht untergekommen.
Aber ich arbeite ja auch nicht mit Genen. Vielleicht ist es bei der
Frage „Stammt diese Probe vom Verdächtigen oder einem nahen
Angehörigen?“ gang und gäbe?
Detlef Müller
2017-04-02 22:39:01 UTC
Permalink
Raw Message
Post by Ralf Goertz
Post by Volker Borchert
Post by Ralf Goertz
Das mag daran liegen, dass es immer noch zu kleine Texte/Muster sind.
Eher daran, daß du nur kurze partial matches hast. KMP und BM bringen
dann was, wenn du schon hundert Zeichen deines zweihundertzeichigen
Suchstrings gematcht hast und beim hundertersten "Sch...." denkst,
indem sie einen Teil der Information aus den schon gematchten Zeichen
weiterverwenden. Wenns immer schon beim zweiten Zeichen schiefgeht,
ist da nicht viel zu gewinnen.
Ja, sowas habe ich auch schon gedacht. Aber wann kommt das schon mal
vor? Ich muss öfter mal nach bestimmten Mustern in Texten suchen, aber
ein solches Szenario ist *mir* irgendwie bisher nicht untergekommen.
Das dürfte z.B. passieren, wenn eine neue Gensequenz mit einem
bestimmten Muster eingeleitet und beendet wird - was nicht
unplausibel scheint, da ja die Schnittstellen zwischen den Sequenzen
von Enzymen erkannt werden müssen.

So wie man in einer Datei mit Personenbeschreibungen z.B. nach
"braune Haare" sucht und nicht nach "ne Haa", kann ich mir gut
vorstellen, daß man im Genom eher nach einer Sequenz suchen wird,
die sich nur in einigen markanten Stellen von ansonsten häufig
vorkommenden Sequenzen unterscheidet.

Gruß,
Detlef

Hans-Peter Diettrich
2017-04-02 10:51:04 UTC
Permalink
Raw Message
Post by Ralf Goertz
Am Fri, 31 Mar 2017 17:51:49 +0200
Also ich habe ein wenig mit erzeugten Zufallswerten in C++ gespielt
(nachdem ich es erst mit π versucht hatte, was aber wegen des 10
ziffrigen Alphabets nicht so geeignet schien), der Text 10 Millionen
Zeichen (Alphabet 4 Zeichen) und Suchstring ungefähr 200 Zeichen. Der
Unterschied zwischen einer naiven Suche und dem Boyer-Moore-Algorithmus
war nicht berauschend, etwa 3,2 Sekunden naiv und 2,8 clever. Der naive
Algorithmus ist einfach string.find()
Diese Zahlen kann ich nicht bestätigen. Möglicherweise werden da 2,7s
für's Einlesen der Daten verwendet? Zumindest bekomme ich bei meiner
Suche in 16MB DNA-Daten Zeiten im ms Bereich, wenn das Chromosom schon
im Speicher liegt.

Bei der Suche nach Duplikaten des Textanfangs komme ich
bei 1 Zeichen auf 12,6M Vergleiche und 3M Fundstellen,
bei 3 Zeichen auf 9M Vergleiche und 50k Fundstellen,
bei 6 Zeichen auf 8M Vergleiche und 444 Fundstellen,
bei 9 Zeichen auf 5M Vergleiche und 10 Fundstellen,
bei 12 Zeichen auf 3,5M Vergleiche und 1 Fundstelle (nur am Anfang),
bei 36 Zeichen 1M Vergleiche,
bei 74 Zeichen 500k Vergleiche,
bei 210 Zeichen 200k Vergleiche,
danach fast nur noch Rauschen zwischen 300k und 1M Vergleichen. Zuerst
dachte ich an einen Fehler in meinem Programm, doch dann stellte sich
heraus, daß schon am Anfang ein Suffix "CACACCA" wiederholt auftritt,
das unabhängig von der Musterlänge nur eine Verschiebung um 7 Zeichen
zuläßt. Später treten Wiederholung des Suffix "TAACCC" auf. Gehören
diese Folgen zur Junk-DNA, zwischen den einzelnen Genen?

Zumindest konvergieren die Vergleiche beim Chromosom 1 viel schöner, bis
runter auf 4000 Vergleiche.

DoDi
Ralf Goertz
2017-04-02 14:42:04 UTC
Permalink
Raw Message
Am Sun, 2 Apr 2017 12:51:04 +0200
Post by Hans-Peter Diettrich
Post by Ralf Goertz
Am Fri, 31 Mar 2017 17:51:49 +0200
Also ich habe ein wenig mit erzeugten Zufallswerten in C++ gespielt
(nachdem ich es erst mit π versucht hatte, was aber wegen des 10
ziffrigen Alphabets nicht so geeignet schien), der Text 10 Millionen
Zeichen (Alphabet 4 Zeichen) und Suchstring ungefähr 200 Zeichen.
Der Unterschied zwischen einer naiven Suche und dem
Boyer-Moore-Algorithmus war nicht berauschend, etwa 3,2 Sekunden
naiv und 2,8 clever. Der naive Algorithmus ist einfach
string.find()
Diese Zahlen kann ich nicht bestätigen. Möglicherweise werden da 2,7s
für's Einlesen der Daten verwendet? Zumindest bekomme ich bei meiner
Suche in 16MB DNA-Daten Zeiten im ms Bereich, wenn das Chromosom
schon im Speicher liegt.
Ja, sorry, habe mich um eine Zehner-Potenz vertan. Es waren 320 ms und
280 ms. Und ja, das Einlesen ist dabei, so dass die Werte relativ
gesehen wohl besser sind. Aber selbst wenn ich 100 ms dafür ansetze, bin
ich immer noch bei 220/180=11/9. Ich habe deshalb nicht genauer
gemessen, weil das Verlängern des Suchstrings so gut wie keine
Auswirkungen hatte, was Volker in seinem Post ja auch plausibel machen
konnte.

Verstehe mich nicht falsch, ich glaube schon, dass der Algorithmus gut
ist und unter bestimmten Umständen etwas bringt. Nur sind diese Umstände
offenbar jenseits meiner normalen Suchwelt.
Tom Bola
2017-04-02 15:27:11 UTC
Permalink
Raw Message
Post by Ralf Goertz
Ich habe deshalb nicht genauer
gemessen, weil das Verlängern des Suchstrings so gut wie keine
Auswirkungen hatte, was Volker in seinem Post ja auch plausibel machen
konnte.
Verstehe mich nicht falsch, ich glaube schon, dass der Algorithmus gut
ist und unter bestimmten Umständen etwas bringt. Nur sind diese Umstände
offenbar jenseits meiner normalen Suchwelt.
Für Suchzeit-Rekorde in der Praxis sollte man schauen, ob eine gegebene
Struktur von Text und Pattern eine prinzipielle Optimierung zulässt. In
der Theorie wird ja zunächst von möglichst zufälligen Texten und Patterns
ausgegangen, mit der Ausnahme, dass man bei Texten in einer "Natursprache"
wie Englisch die relative Häufigkeit des Vorkommens von Buchstaben und
Silben berücksichtigt.
Wenn eine definierte (oder gut definierbare) Struktur der Eingaben
vorliegt, dann kann man sich überlegen (und ausprobieren!), ob ein
Signaturverfahren o.ä. signifikant schneller ist (Shift-And, Karp-Rabin)
oder besonders auch eine Kombination verschiedener Verfahren. Der
Idealfall wäre ja ein Muster (oder eine Signatur), nach dem der Text
bereits gezielt beim Einlesen in einen ideal dazu passenden Baum
eingehängt wird, der dann noch maximal schnell binär durchsucht wird.
Tom Bola
2017-03-31 19:41:04 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Allerdings konnte ich nach "Save to Disk" keine Datei finden,
Ja, nach Einstellen von Fasta (text) kannst du rechts oben die
Dropownliste *Send To* benutzen und erhältst 4 Destinations zur Wahl,

File, Clipboard, Collection, Analysis Tool

mit letzterem kannst du Blast wählen, das hat ein SEHR reiches Interface,
da wirst sich auch das Alphabet finden,

und wenn du Text wählst erhältst du eine Dropdownbox mit einer ganzen
Reihe von möglichen Formaten, zBl neben FASTA auch XML, was du dann
mit deinem Default-Handler öffnen kannst (zBl Texteditor) oder einen
File "kreieren" kannst...
Tom Bola
2017-03-31 19:48:44 UTC
Permalink
Raw Message
Post by Tom Bola
File, Clipboard, Collection, Analysis Tool
mit letzterem kannst du Blast wählen
NOPE, Blast ist eher zum Suchen.
Hans-Peter Diettrich
2017-04-01 09:25:06 UTC
Permalink
Raw Message
Post by Tom Bola
Post by Hans-Peter Diettrich
Allerdings konnte ich nach "Save to Disk" keine Datei finden,
Ja, nach Einstellen von Fasta (text) kannst du rechts oben die
Dropownliste *Send To* benutzen und erhältst 4 Destinations zur Wahl,
File, Clipboard, Collection, Analysis Tool
Da muß man auch erst mal draufkommen :-(
Post by Tom Bola
mit letzterem kannst du Blast wählen, das hat ein SEHR reiches Interface,
da wirst sich auch das Alphabet finden,
Blast konnte ich da nirgends mehr finden :-(

Zu Firefox konnte ich nur finden, daß Java nicht mehr unterstützt wird.
Falls es also daran liegen sollte...

Alternativ IE, der weigert sich kategorisch, auf die Seiten überhaupt
zuzugreifen. Bevor ich mich da jetzt durch die Einstellung wühle, bleibt
der weiter in Quarantäne :-]

Ich gehe jetzt den einfachen Weg, Hauptsache die Dateien kommen
irgendwie auf die Platte, und dann passe ich das Format beim Einlesen
ins Suchprogramm an.

DoDi
Tom Bola
2017-04-01 11:34:25 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Blast konnte ich da nirgends mehr finden :-(
Es ist zum Suchen/Analysieren aber falls du ohnedies mal schauen willst

Send To -> Analysis Tools -> Blast / PrimerBlast

Dann wird verzweigt zu einer URL mit neuen Reitern, zBl
https://blast.ncbi.nlm.nih.gov/Blast.cgi?PAGE=Nucleotides&PROGRAM=blastn&DATABASE=nr&MEGABLAST=on&BLAST_PROGRAMS=megaBlast&LINK_LOC=nuccore&PAGE_TYPE=BlastSearch&QUERY=NT_077402.3
Tom Bola
2017-03-31 20:19:43 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Allerdings konnte ich nach "Save to Disk" keine Datei finden
Es gibt in der (2.) oberen Leiste mit URL und Menü ganz rechts einen
"dicken Pfeil abwärts" < Display the progress of ... Downloads >
mit einer ausführlichen Liste auch für das Anzeigen im richtigen
Ordner deines Filexplorers!

Ich weiss jetzt nicht, ob der "Save To Disk" Ort damit sichtbar gemacht
werden kann; es funktioniert aber alles bestens mit dem "Send To" Interface.
Hans-Peter Diettrich
2017-04-01 09:29:08 UTC
Permalink
Raw Message
Post by Tom Bola
Post by Hans-Peter Diettrich
Allerdings konnte ich nach "Save to Disk" keine Datei finden
Es gibt in der (2.) oberen Leiste mit URL und Menü ganz rechts einen
"dicken Pfeil abwärts" < Display the progress of ... Downloads >
mit einer ausführlichen Liste auch für das Anzeigen im richtigen
Ordner deines Filexplorers!
Ich weiss jetzt nicht, ob der "Save To Disk" Ort damit sichtbar gemacht
werden kann; es funktioniert aber alles bestens mit dem "Send To" Interface.
Ja, mit Send To und File funktioniert das alles wie gewohnt. Das
funktioniert aber auch schon mit FASTA (text) und Seite speichern...,
und dabei auch gleich noch mit aussagekräftigen Dateinamen :-)

DoDi
Tom Bola
2017-03-30 11:57:30 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Post by Tom Bola
Post by Ralf Goertz
Hm, vielleicht verstehe ich ja Deine Beschreibung nicht,
Dir fehlt Information, weil du das Paper nicht gelesen hast. Ich wollte
durch das Zitat nur *andeuten*, dass wegen der üppig vorbildlich guten
Literatursituation "ein vages Vermuten" alos nicht nötig ist,
Die Literatur gibt aber auch keine Begründung her, warum man sich mit 3m
bis 5m Vergleichen zufrieden gab, wenn das auch mit worst case 1m
Vergleichen möglich ist.
Vielleicht findest du in den Massen hier eine (historische) Erklärung:
http://www-igm.univ-mlv.fr/~lecroq/string/

Hier http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140
steht übrigens:

Boyer-Moore algorithm

Main features

performs the comparisons from right to left;

preprocessing phase in O(m+) time and space complexity;

searching phase in O(mn) time complexity;

3n text character comparisons in the worst case when searching
for a non periodic pattern;

O(n / m) best performance.
Tom Bola
2017-03-30 12:06:33 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Die Literatur gibt aber auch keine Begründung her, warum man sich mit 3m
bis 5m Vergleichen zufrieden gab, wenn das auch mit worst case 1m
Vergleichen möglich ist.
Hier sind 3 Boyer-Moore Varianten incl. c-code "erwähnt":


(1) http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140

Boyer-Moore algorithm
Main features

performs the comparisons from right to left;
preprocessing phase in O(m+) time and space complexity;
searching phase in O(mn) time complexity;
3n text character comparisons in the worst case when searching
for a non periodic pattern;
O(n / m) best performance.

(2) http://www-igm.univ-mlv.fr/~lecroq/string/node15.html#SECTION00150


Turbo-BM algorithm
Main features

variant of the Boyer-Moore;
no extra preprocessing needed with respect to the Boyer-Moore algorithm;
constant extra space needed with respect to the Boyer-Moore algorithm;
preprocessing phase in O(m+) time and space complexity;
searching phase in O(n) time complexity;
2n text character comparisons in the worst case.


(3) http://www-igm.univ-mlv.fr/~lecroq/string/tunedbm.html#SECTION00195

Tuned Boyer-Moore algorithm
Main features

simplification of the Boyer-Moore algorithm;
easy to implement;
very fast in practice.


...
S.a. http://www-igm.univ-mlv.fr/~lecroq/string/node2.html#SECTION0020
Andreas Leitgeb
2017-03-29 16:55:39 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Die 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.
Das gleiche in etwas anderen Worten:

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.

Die Tabelle für den leeren Suffix entspricht dann genau der originalen
Miss-Tabelle, Die Tabelle zum 1-langen Suffix "a" des Suchwortes
abracadabra enthält dann etwa die Einträge:
'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.

Ja, das könnte die Suche durchaus beschleunigen. Tut leid für die Zweifel
vorhin.

Meine 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.
Post by Hans-Peter Diettrich
Was 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...
Tom Bola
2017-03-29 17:40:33 UTC
Permalink
Raw Message
Post by Andreas Leitgeb
Meine 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.
Nein, sondern es wurde mit der Zeit genau gezeigt und sogar bewiesen,
welches Laufzeitverhalten für gegen welchen Speicherplatztbedarf getradet
wurde und auch das steht in Wikipedia oder den dortigen vertiefenden
Links. Trotzdem weiter viel Spass beim "vagen Vermuten" durch deine
WM-Methodik das Lesen zu vermeiden.
Hans-Peter Diettrich
2017-03-29 22:51:35 UTC
Permalink
Raw Message
Post by Andreas Leitgeb
Post by Hans-Peter Diettrich
Die 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 Leitgeb
Die 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 Leitgeb
Ja, 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 Leitgeb
Meine 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 Leitgeb
Post by Hans-Peter Diettrich
Was 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
Tom Bola
2017-03-29 23:15:52 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Post by Andreas Leitgeb
Post by Hans-Peter Diettrich
Die 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 Leitgeb
Die 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.
Ein Automat HAT keine konstanten Abkürzungen, sondern muss sie
per Laufzeit errechnen und deshalb kann ein Automat nur simuliert
werden, was zur Aussage führt, dass der String erfolgreich gesucht wurde.
Post by Hans-Peter Diettrich
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 Leitgeb
Ja, 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 :-]
Richtig, denn dass du dich selbst intern beteiligst ist nicht zu erwarten.
Post by Hans-Peter Diettrich
Post by Andreas Leitgeb
Meine 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 :-)
Ihr habt mich vom Qwert eures Bauchgefühls bekehrt, und ohne dass ich
wüsste wovon - vielen Dank euch Zwei!
Post by Hans-Peter Diettrich
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.
Ja, zusammen entsteht die Frage nach der Zahl der Tabellen (funktionen),
die man "online/offline" (live oder preprocessed) benutzen kann.
Post by Hans-Peter Diettrich
Wenn zu einem konkreten Hit-Wert eine Tabelle existiert (wie oben von
Dir angegeben), diese verwenden. Andernfalls die Good Suffix Tabelle
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.
OK, das kann dann nun festgelegt werden.
Post by Hans-Peter Diettrich
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.
Ja, das kauft man mit dem Betriebssystem, aber das hilft dann bei der
Abstraktion regularypatterns nicht viel, immerhin zählt das Detail falls
davon etwas abhängt, jeder kennt diese wunderbaren und grossartigen Krimis.
Post by Hans-Peter Diettrich
Damit wäre auch eine vollständige 2D Tabelle nicht mehr 256*11 Elemente
groß, sondern nur noch 6*11.
Post by Andreas Leitgeb
Post by Hans-Peter Diettrich
Was 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.
Das hat mich berührt!
Post by Hans-Peter Diettrich
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.
Der Einwand war ähnlich.
Tom Bola
2017-03-29 23:30:43 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
DNA Datei zum Testen von langen Mustern suche.
Kompakter code für Richtung embedded (wenig Speicher).

char *search( pat, text, n )
char *pat, *text;
int n;

{ int i, j, k, m, skip[MAXCHAR];

m = strlen(pat);
if( m==0 ) return( text );
for( k=0; k<MAXCHAR; k++ ) skip[k] = m;
for( k=0; k<m-1; k++ ) skip[pat[k]] = m-k-1;

for( k=m-1; k < n; k += skip[text[k] & (MAXCHAR-1)] ) {
for( j=m-1, i=k; j>=0 && text[i] == pat[j]; j-- ) i--;
if( j == (-1) ) return( text+i+1 );
}
return( NULL );
}
Tom Bola
2017-03-30 14:53:14 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
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?
Das humane Genom gibts hier in aller Pracht:
https://www.ncbi.nlm.nih.gov/genome/gdv/browser/?context=genome&acc=GCF_000001405.36

Downloaden kannst du alles hier:
ftp://ftp.ncbi.nlm.nih.gov/genomes/H_sapiens/

zBl. Chromosom 1
ftp://ftp.ncbi.nlm.nih.gov/genomes/H_sapiens/CHR_01/

Du hast dann .gz gepackte Files in welchen wiederum die .agp Files
drinstecken.

Die Specs von AGP (AGP steht für 'A Golden Path') ist hier:
https://www.ncbi.nlm.nih.gov/assembly/agp/AGP_Specification/


Hier ist noch eine andere Quelle:
http://www.sanger.ac.uk/science/data/zebrafish-genome-project
Loading...