Ich versuche momentan ein Rätsel zu knacken, bei dem ein deutscher Satz mit unbekanntem Alphabet dargestellt wurde, die Wortzahl aber viel zu gering für eine empirische Analyse ist. Bisher habe ich mir aus einem frei verfügbaren Deutsch-Englisch-Wörterbuch eine Wortliste mit 184.000 eindeutigen Wörtern erzeugt und eine einfache Datenbank dazu geschrieben, in der ich schnell nach folgenden Kriterien suchen kann:
- Wortlänge ab:2, abc:3, abcd:4, ...
- Anzahl der sich wiederholenden Symbole abcd:0, abbc:1, abbb: 1, aabb:2, ...
- Stellung der mehrfach vorkommenden Symbole abcd:1, aabc: 2*3, abbc:3*5, ...
letzteres Merkmal wird nach den Symbolstellen mit Primzahlen codiert, ebensogut könnte man hier jedoch bei genügender Bitlänge bitweise codieren, jedoch hatte ich die Primzahlen schneller zur Hand und ein Test mit Divisionsrest ist auf die Schnelle leichter implementiert als ein Bittest an beliebiger Stelle. Solange int64 reicht, dürfte das kein Problem darstellen.
Was allerdings ein Problem ist, sind die Permutationen bei mehr als einem mehrfach vorkommenden Symbol, denn abab:210, abba:210, baab:210, bbaa:210, ...
die nötigen Vergleiche auf Ungleichheit oder Wiederkehr von Symbolen füllen eine obere Dreiecksmatrix mit booleschen Werten und in dieser sollten alle Zellen wahr sein, wenn ein Wort auf das Suchmuster passt.
Was nun fehlt ist ein Maß für die Lage der sich wiederholenden Symbolgruppen, also eine komprimierte Darstellung der Gleichzeichen in der Matrix. Ich könnte nun, da auch nur pro Spalte ein Gleichzeichen vorkommen kann (alle weiteren sind redundant und werden unterdrückt) wieder pro Zelle ein Bit oder eine Primzahl zuweisen, aber selbst mit 256 bit komme ich nur in den Bereich von etwa 22 Symbolen. Wie soll ich diese Information eindeutig representieren?
zuletzt noch ein Beispiel: die
Suche nach "butterbrot" liefert momentan noch folgende Ergebnisse:
Code:
length: 10
repetitions: 3
repetition hash: 8523970
4cc: 1953789282
matching words: 8
_____________________
wollgewebe
soziussitz
prinzipien
einmummeln
butterbrot
breitbeile
ausspannen
asiatinnen
... kein weiteres der Worte erfüllt also das Suchmuster.
Eine reduzierte, aber dennoch vollständige Information wird gewonnen, wenn man drei Vergleiche innerhalb der Gruppe und drei zwischen den Gruppen sich wiederholender Symbole einbezieht:
Code:
butterbrot
x-----x--- gleiche Symbole (b_____b___)
--xx-----x gleiche Symbole (__tt_____t)
-----x-x-- gleiche Symbole (_____r_r__)
x-x------- ungleiche Symbole (b_t_______)
--x--x---- ungleiche Symbole (__t__r____)
x----x---- ungleiche Symbole (b____r____)
Wie könnte man diese Information durch wenige byte bei fester Länge ausdrücken?
Danke schonmal!
ps. eine Idee wäre, die anfallenden Vergleiche zur Laufzeit als Testfunktion zu compilieren und auf die verbliebenen Wörter anzuwenden, dennoch würde ich eine Representation mit 32 oder 64 bit bevorzugen.
Zitat
Baum-Darstellung
