Hashberechnung der Topologie eines Wortes - wie?

[helgew]

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.

[Blup]

Da es sich um eine Information variabler Länge handelt, die Information selbst aber nicht relevant ist und nur auf Gleichheit geprüft werden muss, würde ich einen Hashwert bilden (z.B. mit CRC32). Aber das steht ja auch schon im Titel des Beitrags, also wo ist das Problem?

[helgew]

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.

[negaH]

Zitat:

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.

Interessante Aufgabenstellung. Kannst du mehr Hintergründe liefern, zB. den ominösen deutschen Satz um den es geht ?
Ich denke da nämlich das es auch andere algorithmische Ansätze geben wird die eventuell im Endeffekt effizienter sein könnten. Du suchst ja einen Algorithmus der kombinatorisch mit Hilfe einer Wortdatenbank die alphabetische Transposition = Verschlüsselung knacken kann. Nun ich denke das mein DAWG = Directed Acyclic Word Graph, eine effiziente Baumstruktur für Wortdatenbanken eventuell ein verwertbarer Bestandteil des Algos. sein könnte. Mein DAWG benutzte ich zb. für eine Scrable Engine, parallele Wortsuchen, Kreuzworträtsel Generatoren usw. Dh. in all diesen Fällen ist es wichtig in wenigen Millisekunden mögliche Wörter aus einem Set von Buchstaben zu suchen, wobei man zb. auch Wörter mit fester Länge suchen kann. Man kann die Suchfunktion des DWAGs so umschreiben das sogar die Position eines Buchstaben innerhalb des Wortes als Suchmaske benutzt wird.

Ich meine also das man solche Strukturen wie DAWGs und deren Suchfunktionen so umschreiben könnte das die Gesamtkomplexität des Algos. sehr gut wird weil man die Suchfunktionen so schreiben kann das sie kombinatorisch höchst effizient sucht. Sprich: macht man es richtig so wird es keine doppeldeutigen/mehrfachen und damit sinnlosen Suchen in der Wortliste geben.

Wie gesagt, schreib mal konkreter über deine Aufgabenstellung.

Gruß Hagen

PS: DAWG Source -> http://www.delphipraxis.net/internal...=546436#546436

[helgew]

wenn ich doch nur eine Vergleichsphrase als Klartext und Code hätte... anbei eine der Phrasen aus dem Rätsel, ich möchte auch nicht alles zugänglich machen, da es sich noch immer um ein persönliches Geburtstagsgeschenk handelt (jep, aber so etwas habe ich mir auch gewünscht, selbst schuld ^^) und ich keine Ahnung habe, was drinstehen könnte.

Momentan arbeite ich mit einer recht flachen Datenstruktur, in der die Worte zunächst nach Länge sortiert sind und noch durch ihre Metainformationen (die die oben genannte Information zur Wiederholungshäufigkeit und -Position enthalten) durchsucht werden können. Für andere Strukturen kann ich von einer Mutterklasse erben und andere Suchfunktionen implementieren.


Die Leserichtung habe ich bisher richtig geraten (aus dem Kontext des Schriftstücks, sprich der Orientierung des Textes im Couvertfenster), einige der Striche gehören ihrer Häufigkeit und Stellung nach zu urteilen zu Vokalen und folgen einer bestimmten Grammatik, die ich noch nicht ergründet habe.

[negaH]

Tja, das hilft mir leider nicht weiter ;(

hast du schonmal drüber nachgedacht einfach eine Häufigkeitsanalyse der vorkommenden Buchstaben zu machen ? Also du zählst das Vorkommen jedes "Symboles" in deiner Nachricht. Dann zählst du die Häufigkeit jedes Buchstabens aller deiner deutschen Wörter. Du solltest feststellen können das der Buchstabe "e" am häufigsten vorkommt. Setze nun diesen Buchstaben in deiner Nachricht an der Stelle des "Symbols" mit der größten Häufigkeit ein. Gehe so weiter vor.

Dh. du knackts den Text nicht durch eine Wortanalyse sondern Symbolhäufigkeitsanalyse. [edit] Die Wortdatenbank dient dir dann nur noch als Verifikation der korrekten Häufigkeitsanalyse. [/edit]

Oder gib mal deine Phrasen bei Google ein. Eventuell hast du nur einen Satz in Klingon, oder einer anderen Kunstsprache vor dir und deine "Freunde" haben es sich leicht gemacht. Achso, meine Freunde schenken mir da andere Sachen und das nenne ich mal freundlich

Weiter kann ich dir auch nicht helfen.

Gruß Hagen

[negaH]

Zitat:

Momentan arbeite ich mit einer recht flachen Datenstruktur, in der die Worte zunächst nach Länge sortiert sind und noch durch ihre Metainformationen (die die oben genannte Information zur Wiederholungshäufigkeit und -Position enthalten) durchsucht werden können. Für andere Strukturen kann ich von einer Mutterklasse erben und andere Suchfunktionen implementieren.

Ja das hatte ich schon so verstanden. Meine Erfahrung sagt mir aber das du schon viel zu viele und zu strikte Annahmen für deinen Algorithmus triffst. Wenn du dir sicher bist das der Text wirklich nur eine Transposition/Substitutionsverschlüsselung darstellt, also zb. ein einfacher Csaesarcipher, dann würden deine Annahmen für die beste Arbeitsweise deines Algos ja noch anwendbar sein. Sollte es sich aber um ein anderes Verfahren handeln so wirst du meiner Meinung nach mit deinem Verfahren keinen Erfolg haben können. Zb. enthalten die Metainformation die Länge des Wortes und Positionen/Häufigkeiten gleicher Buchstaben. Nehmen wir aber nun an das der Buchstabe "e" substituiert wurde durch die Kombination "z?" wobei das Fragezeichen sich berechnet aus vorherigen Buchstabensubstitutionen dann wird dir klar werden das die Metainformation "Länge" und "Buchstabenpositionen gleicher Buchstaben" und "Häufigkeit gleicher Buchstaben" untaugliche Kriterien für deine Suche darstellen.

Ich denke also das du Schritt für Schritt deine Analyse machen solltest. Dh. erstmal statistische Informationen sammeln wie zb. die Häufigkeitsanalsyse der vorkommenden Symbole. Wenn du dort ein deutliches Ungleichgewicht zwischen den Häufigkeiten feststellen solltest dann besteht eine Chance für deinen Algo. Wenn aber alle Symbole annähernd gleichverteilt vorkommen kann ich dir jetzt schon sagen das keine einfache Transposition/Substitutions-Verschlüsselung benutzt wurde. Bei starken Verschlüsselungen sollte sich so ein Bild ergeben. Desweiteren bittest du um einen Tipp bei deinen "Freunden" wenn du nicht weiterkommst. Gute Verschlüsselungen knackt man nicht mit wenigen bis keinerlei Informationen.

Gruß Hagen

[himitsu]

Hab auch mal ein bissl gespielt (jetzt steckt mich Hagen schon mit seinen Primzahlen an )

Nja, rausgekommen ist sowas, welches hoffentlich aus den doppelten Buchstaben/Zeichen 'ne Zahl erstellt, welche das zugrundeliegende Verteilungsmuster enthält.

Delphi-Quellcode:

{$OVERFLOWCHECKS ON}
{$RANGECHECKS    ON}

function CreateID(S: String): UInt64;
const
  Prim: array[1..30] of Integer = (2,  3,  5,  7, 11,  13,  17,  19,  23,  29,
                                  31, 37, 41, 43, 47,  53,  59,  61,  67,  71,
                                  73, 79, 83, 89, 97, 101, 103, 107, 109, 113);
var
  i, i2: Integer;
begin
  Result := 0;
  S := AnsiLowerCase(S);
  for i := 1 to Length(S) do
  begin
    i2 := i;
    while PosEx(S[i], S, i2 + 1) > 0 do
    begin
      i2 := PosEx(S[i], S, i2 + 1);
      Result := Result + Trunc(Power(Prim[i], i2 - i));
      // [edit] vielleicht doch lieber so? :gruebel:
      // Result := Result + Trunc(Power(Prim[i], Prim[i2 - i + 1])); 
    end;
  end;
end;

procedure TForm1.FormCreate(Sender: TObject);
var
  S: String;
begin
  S := 'Butterbrot';
  ShowMessage(Format('%d-%d', [Length(S), CreateID(S)]));
end;

Das -i im Power ist nur da, um das Ergebnis ein bissl kleiner werden zu lassen, da hier nicht der Gesamtoffset im String, sondern nur das Offset zum 1. gleichen Zeichen verwendet wird.

[helgew]

Hi himitsu,
bisher habe ich mich mit dem code zurückgehalten, da wie Hagen schon sagte, man damit sehr schnell spezifisch wird. Da ich aber ohnehin auf die Sortierung nach der Wortlänge angewiesen sein werde, habe ich schonmal so weit es geht, zu coden angefangen. Mein Profiler erzeugt eine Zahl der "entarteten" Symbole und einen Hashwert, um deren Position festzulegen:

Delphi-Quellcode:

  type TMetaListEntry = record
    len : integer;    // trivial length
    repchars: integer; // count reoccuring characters
    rephash: int64; // assign ascending prime numbers to character places, form product
    fourcc: cardinal; // first four characters as bytes
  end;

const primetable : array [1..58] of integer = (
  2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,
 61,67,71,73,79,83,89,97,101,103,107,109,113,127,
 131,137,139,149,151,157,163,167,173,179,181,191,
 193,197,199,211,223,227,229,233,239,241,251,257,
 263,269,271);
var charhistogram: array[0..255] of byte;

function WordProfile(w: string): TMetaListEntry;
var
  i: integer;
  pa: PByteArray;
  pc: ^Cardinal absolute pa;
  o: integer;
begin
  result.len := length(w);
  ZeroMemory(@charhistogram[0],256);
  result.repchars := 0;
  result.rephash := 1;

  for i := 1 to result.len do
  begin
    o := ord(w[i]);
    inc(charhistogram[o]);
    if charhistogram[o] = 2 then inc(result.repchars);
  end;

  for i := 1 to result.len do
  begin
    if charhistogram[ord(w[i])] > 1 then
       result.rephash :=  result.rephash * primetable[i];
  end;

  pa := @w[1];
  case result.len of
    1: result.fourcc := pa[0];
    2: result.fourcc := pa[0] + pa[1]*$100;
    3: result.fourcc := pa[0] + pa[1]*$100 + pa[2]*$10000;
    else result.fourcc := pc^;
  end;
end;

ich schau mir mal eben deinen Vorschlag an

edit: eine Schleife eliminiert.

[negaH]

Hi Himitsu,

ich meine eben das es noch zu früh ist sich auf einen Algo festzulegen. Er soll erstmal eine Häufigkeitsanalyse machen. Der erste und einfachste Schritt: alle Symbole zählen und mit der Buchstabenhäufigkeiten der deutschen Sprache vergleichen. Dann diese Analyse erweitern indem man die zusätzlich Häufigkeiten/Wahrscheinlichkeiten von Doppelbuchstaben ermittelt. Also wie oft kommt es vor das vor oder nach einem "e" der Buchstabe "i" vorkommt. Gleiches für die Symbolhäufigkeiten der Nachricht. Das kann man so immer weiter treiben also Dreierbruchstabenkombinationen usw. usw. Hat man diesen Baum erzeugt kann man so auch jedes deutsche Wort klassifizieren. Nun hat man zwei Bäume von Wahrscheinlichkeiten zu den Symbolen/Wörtern der Nachricht in Vergleich zur Wortdatenbank der deutschen Wörter. Welche konkreten Symbole/Buchstaben benutzt wurden ist eine Information die wir über die Häufigkeitsbäume eliminiert haben. Nun sucht man einfach in beiden Bäumen die Worte mit übereinstimmenend Häufigkeits-Signaturen und subsituiert diese Symbolgruppe durch das deutsche Wort. Bei dieser Substitution kann man die Transpositionstabelle von Symbolen im Wort zu deuschen Buchstaben im ausgewählten Wort ausrechnen. Alle nachfolgenden Symbolgruppen die mit deutschen Wörtern ausgetauscht werden, müssen exakt dieser Transpositiontabelle entsprechen. Die Suchschleife bricht dann ab wenn so alle Symbolgruppen in deutsche Wörter umgewandelt wurden und alle mit der gleichen Transpositionstabelle gearbeitet haben. Die Suchfunktion beginnt von neuem wenn dies nicht der Fall ist, man wählt also das nächst beste passende deutsche Wort für die erste Symbolgruppe, berechnet die sich ergeben Transpositionstabelle der ausgetauschten Buchstaben und macht weiter mit der restlichen Nachricht mit gleicher Tabelle.

Gruß Hagen