Einzelnen Beitrag anzeigen

helgew

Registriert seit: 30. Jul 2008
125 Beiträge
 
#3

Re: Hashberechnung der Topologie eines Wortes - wie?

  Alt 21. Mai 2010, 13:19
Das Problem ist, dass ich aus

Code:
1 2 3 3 4 5 1 5 6 3
eindeutig das Wort "Butterbrot" finden muss und erst dann das Alphabet

Code:
1 -> b
2 -> u
3 -> t
4 -> e
5 -> r
6 -> o
ableiten kann. Da ich keine Klartexte vergleichen kann, muss ich die Indizierungen vergleichen. Wenn man noch erste Vorkommen unterdrückt, da diese sich automatisch ergeben, ist die Information
_ _ _ 3 _ _ 1 5 _ 3

oder bezogen auf die Stellen, an denen der Buchstabe steht

_ _ _ 3 _ _ 1 6 _ 3

diese Zeichenfolgen können nun per Definition max. 64 byte lang werden, der Informationsgehalt kann aber pro weiterem Zeichen anwachsen (die zweite Stelle ist 0: ein eigenständiges Zeichen oder 1: die Wiederholung vom ersten Zeichen; die dritte Stelle ist 0: ein eigenständiges Zeichen, 1: Wiederholung von Stelle 1, 2: Wiederholung von Stelle 2; ...) sodass sich aus n Zeichen, sofern ich mich nicht täusche, n! Kombinationen ergeben, was einer Bitwertigkeit von
Code:
N = log_2 (n!) = 1/ln(2) * ln(n!)= 1.443 * (n*ln(n) - n + 1/2 *ln (2*pi*n) + o(...))
Für 64 Zeichen benötigt man so runde 296 bit, das ist mehr als die Hälfte der Nutzdaten, jedoch müsste man viele Vergleiche ausführen, sodass es eigentlich darum geht, ob die Reduktion noch gerechtfertigt ist. der Schwerpunkt der Worthäufigkeit liegt bei etwa 6..22 Zeichen, lässt sich also fast auf 64 bit abbilden, aber sicher auf 10 byte.

Das Problem steckt darin, einen Algorithmus zu finden, der diese Information abstrahiert wiedergibt und das schnell und ohne Kollisionen - und ich bin noch nicht wirklich weiter, außer mit dem Verständnis

Vielleicht ist es wirklich das beste, die Wiederholungsinformation in voller Länge anzufügen oder aus dem Suchmuster eine Funktion zu generieren und diese zur Laufzeit anzuwenden.
Miniaturansicht angehängter Grafiken
stats1_757.png   stats1b_111.png  
  Mit Zitat antworten Zitat