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 :wall: )

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

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

[himitsu]

Wie Hagen schon erwähnte: Bist du dir wenigstens sicher, daß jedes Zeichen genau einem bestimmten Buchstaben entspricht? (ich hoffe ja mal, deine Freunde haben es dir nicht zu schwer gemacht)

PS: Im Notfall gibt es ja noch sowas, das nennt sich Bruteforce. :mrgreen:
Alle möglichen Kombinationen durchprobieren und jedesmal die entstandenen Wörter mit deinem Wörterbuch vergleichen ... je mehr Wörter im Wörterbuch gefunden werden, desto wahrscheinlicher ist es, daß es sich um die Lösung handelt.

@Hagen: Es ist ja nicht direkt ein Algo ... es soll nur eine Möglichkeit darstellen, um einen "kleinen" Wert zu erhalten, welcher die Positionsabfrage aus Post #1 ermöglichst.

[negaH]

Achso eines noch: falls deine "Freunde" ein komplett zufälliges Passwort benutzt haben das auch noch exakt so lang wie deine Nachricht ist dann hast du die klassische OTP Verschlüsselung, One Time Pad. Das wirst du dann nie knacken können, bzw. alle deine für dich richtigen Lösungen sind gleichwertig korrekte mögliche Lösungen des Problemes. Du wirst also alle möglichen deutschen Sätze die so lange wie deine Nachricht sind erzeugen können und hast keinerlei Chance zu erkennen welche die richtige Nachricht nun ist.

Gruß Hagen

[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

[helgew]

Hagen, meine bisherige Überlegung war es, zu den möglichen Kombinationen eine Liste aller Möglichkeiten zu erzeugen ( später kommen noch vordefinierte Zeichen hinzu, die das ganze weiter einschränken) und zu diesen im Wörterbuch zu suchen. Ein entscheidender Schritt ist dabei in dem Falle, dass wenn man eine Symbolvariante herausgegriffen hat, zu dieser der Struktur nach passende Wörter finden kann und diese im Kontext der restlichen Wörter auf Übereinstimmung des Alphabets testen kann.

Vielleicht ist diese Vorgehensweise auch ineffizient, da man mit der Festlegung des ersten Wortes das Unteralphabet schon in die Suchmasken für weitere Worte einbeziehen könnte, aber irgendwo muss man ja mal anfangen ^^

[helgew]

Zitat:

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...

[negaH]

Zitat:

@Hagen: Es ist ja nicht direkt ein Algo ... es soll nur eine Möglichkeit darstellen, um einen "kleinen" Wert zu erhalten, welcher die Positionsabfrage aus Post #1 ermöglichst.

Schon klar das ist ;) Aber wir wollen doch wissen was im Geburtstagsgruß drinnensteht und dafür sollte man analytisch korrekt vorgehen da ansonsten der TE unnötig Zeit mit dem falschen Algo. verschwendet. Oder: bei seinem konkreten Problem können wir ihm nicht helfen da wir nicht die Nachricht vorliegen haben, ergo können wir ihm nur Tipps geben wir man sowas in der Kryptoanalsyse richtig anpackt. Und da zählt als erstes die Häufigkeitsanalyse. Und erst wenn man diese vorliegen hat kann man entscheiden wie man weitermachen muß.

Gruß Hagen

[himitsu]

Zitat:

Zitat von negaH

Schon bei wenigen Worten steigt die Komplexität dieser Bruteforcesuche ins Unermeßliche an.

Ich hab nicht behaubtet, daß es schnell geht. :angel2:

Haben deine Freunde dir also nur den Zettel hingehalten "so mach mal" und sonst keinerlei Tipp gegeben?
(ohne zu wissen/ahnen, wie das Ganze eventuell verrechnet wurde, kann es ja nicht grad leicht lösbar sein, falls es das dann überhaupt jemals ist)

[negaH]

Zitat:

Zitat von helgew

Hagen, meine bisherige Überlegung war es, zu den möglichen Kombinationen eine Liste aller Möglichkeiten zu erzeugen ( später kommen noch vordefinierte Zeichen hinzu, die das ganze weiter einschränken) und zu diesen im Wörterbuch zu suchen. Ein entscheidender Schritt ist dabei in dem Falle, dass wenn man eine Symbolvariante herausgegriffen hat, zu dieser der Struktur nach passende Wörter finden kann und diese im Kontext der restlichen Wörter auf Übereinstimmung des Alphabets testen kann.

Vielleicht ist diese Vorgehensweise auch ineffizient, da man mit der Festlegung des ersten Wortes das Unteralphabet schon in die Suchmasken für weitere Worte einbeziehen könnte, aber irgendwo muss man ja mal anfangen ^^

Nein nein, nicht ineffizient weswegen ich ja mein DAWG oben ansprach das dieses Problem effizient lösen könnte. Das problem was ich sehe ist das die Entscheidung es so zu versuchen einfach verfrüht ist.

Mach mal eine, wie oben angesprochene, Häufigkeitsanalsyse der Symbole in deiner Nachricht und poste sie hier, also die häufigsten Symbole sind ausreichend. Dann können wir weiter sehen.

[edit]
Nochwas: wenn du denkst das du mit einem Algo. das Problem sofort lösen kannst dann ist das falsch. Normalerweise wendet man auf eine solche Nachricht sukzessive verschiedene Algo. an und entscheidet an Hand deren Resultate welcher Algo. also nächstes ausprobiert wird.
[/edit]

Gruß Hagen

[helgew]

Zitat:

Zitat von himitsu

Haben deine Freunde dir also nur den Zettel hingehalten "so mach mal" und sonst keinerlei Tipp gegeben?

So ein Rätsel gab es schonmal und bei mir hat man es wohl etwas zu gut gemeint, nach dem Motto: der schafft das eh... (wohlgemerkt ohne dass derjenige, der sich das ausgedacht hat die Machbarkeit geprüft hat..)

[negaH]

Zitat:

(wohlgemerkt ohne dass derjenige, der sich das ausgedacht hat die Machbarkeit geprüft hat..)

Na cool, dh. es könnte auch durchaus sein das der Text so verschlüsselt wurde das es garkeine Entschlüssung dafür gibt ?

Gruß Hagen

[himitsu]

Zitat:

Zitat von negaH

Na cool, dh. es könnte auch durchaus sein das der Text so verschlüsselt wurde das es garkeine Entschlüssung dafür gibt ?

@Hagen: Hast du dir nicht schon immer sowas gewünscht?
100% Sicherheit :stupid:

[helgew]

hey sehts mal positiv, ich kann unter Umständen fehlende Informationen noch beschaffen. Ich gehe davon aus, dass sich zunächst viele Variationen des Teilsatzes generieren lassen. An der Stelle bedanke ich mich auch bei euch :thumb:

[helgew]

so, ich habe mich nun dazu entschlossen, maximal 15 sich wiederholende Zeichentypen zuzulassen, bevor Informationsverlust auftritt, dafür kann ich die Aussage in einen uint64 stopfen. Jedes sich wiederholende Zeichen wird mit 4 bit codiert, für en Fall, dass es mehr als 16 Wiederholungen gibt, gehe ich davon aus, dass es wenige Worte mit mehr als 16 verschiedenen Zeichen gibt. Kollisionen sind also sehr unwahrscheinlich und der Kostenfaktor für die Berechnung des Kontrollwertes ist nicht allzuhoch.

Delphi-Quellcode:

  type TMetaListEntry = packed record
    len : integer;    // trivial length
    rephash: uint64; // assign ascending prime numbers to character places, form product
    fourcc: cardinal; // first four characters as bytes
    seq: uint64;
    case fastaccess:boolean of
      true :(repchars         : dword); // count reoccuring characters as unique and in total
      false:(repunique,repcnt :  word);
  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;
  charID       : array[0..255] of byte;

function WordProfile(w: string): TMetaListEntry;
var
  i: integer;
  pa: PByteArray;
  pc: ^Cardinal absolute pa;
  o: integer;
  cid: integer; // repeated character ID (4-bit value), assume <=15 repeating chars
  seqshift: uint64;
begin
  result.len := length(w);
  ZeroMemory(@charhistogram[0],256);
  result.repchars := 0;
  result.rephash  := 1;
  result.seq      := 0;

  cid := 1;
  for i := 1 to result.len do
  begin
    o := ord(w[i]);
    inc(charhistogram[o]);
    if charhistogram[o] > 1 then
    begin
      inc(result.repcnt);
      if charhistogram[o] = 2 then
      begin
        inc(result.repunique);
        charID[o] := cid and $0F;
        inc(cid);
      end;
    end;
  end;

  seqshift := 1;
  for i := 1 to result.len do
  begin
    o := ord(w[i]);
    if charhistogram[o] > 1 then
    begin
       result.rephash :=  result.rephash * primetable[i];
       result.seq := result.seq or (charID[o] * seqshift);
       seqshift := seqshift shl 4;
    end;
  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;

als nächstes bräuchte ich einen Wortgenerator, der aus einer Art regulärer Ausdrücke Zeichenfolgen generiert und dann das processing für ganze Sätze. Es wird...

Anwendungsbeispiel: Suchwort "1234567268767", pro Zahl ein unbekannter Buchstabe

Code:

length: 13
repetitions: 5 (3)
rep hash: 740277849
sequ64: 0x0000000032321321

matching words: 1
_____________________
klavierlehrer

--------- Problem gelöst! ----------