Hashberechnung der Topologie eines Wortes - wie?

[helgew]

Zitat von negaH:

Zitat:

PS: Im Notfall gibt es ja noch sowas, das nennt sich Bruteforce.

Tja der Erfolg hängt dann aber auch von der Länge der Nachricht ab. Schon bei wenigen Worten steigt die Komplexität dieser Bruteforcesuche ins Unermeßliche an.

Gruß Hagen

bisher schätze ich den Aufwand als in der Größenordnung 10^9..10^11 Vergleiche liegend. Das ist immerhin schon berechenbar, wobei ich auch keine Lust habe, einen Tag vor schlechtem Code zu sitzen, bis er mal fertiggerechnet hat.


übrigens liegen die Buchstaben in ihrer Häufigkeit nur um 1-2% auseinander, wenn nicht noch weniger, dazu variieren die Verteilungen von Schriftsprache, Wörterbüchern, Onlineartikeln und Forenbeiträgen, sodass bei etwa 50 Symbolen, die ich habe, keine hinreichende Signifikanz erreicht wird. Eine Häufigkeitsanalys scheidet demnach aus. Ich habe als Hinweis bisher jedoch, dass Buchstaben eindeutig zugeordnet sind und umgekehrt. Gehen wir also davon aus, die Symbole seien bis auf Permutationen und Variationen hin bekannt, also etwa

ab(cde,edc,df)ghi

für cde, edc : verschiedene Interpretationen gestapelter Symbole
df : ein Teil der Symbole wird als anderes, neues Symbol interpretiert.

daraus würde ich

abcdeghi
abedcghi
abdfghi

erzeugen und entsprechend länger suchen, da ich dreimal mehr Kombinationen erhalte, unsere Methoden unterscheiden sich nun daran, ob ich unter einer generalisierten Suchmaske mehr Wörter finde oder ob ich drei Untergruppen finde und diese dann zusammenfüge.
Ein ungelöstes Problem ist jedoch noch das Wiederkehren von Variationen, denn das Interpretieren der Symbole ist ja nicht nur lokal, sondern entsprechend im nächsten Wort dann ebenfalls "df" oder "edc". Es kann aber auch wieder sein, dass eine Grammatik festlegt, wann die Symbolfolge (...) als df oder als edc intepretiert wird. Das muss man dann austesten...