Text entschlüsseln

[DanielAC]

Hallo zusammen,

ich habe das Problem, dass ich einen unbekannten Text entschlüsseln möchte. Die Verschlüsselungsmethode ist einfaches Umsortieren der Buchstaben. Leider ist es keine offensichtliche Methode, d.h. das Wort "ist" kann an der einen Stelle mal als "sit" auftauchen und an einer anderen mal als "tis".

Meine Herangehensweise bis jetzt war, eine Liste mit (fast) allen deutschen Wörtern herunterzuladen, zu jedem zu entschlüsselnden Wort alle möglichen Permutationen von Buchstaben zu ermitteln und dann mit einem merge das richtige Wort (oder die möglichen Wörter) herauszufinden.
Mir ist klar, dass die Lösung nicht unbedingt eindeutig ist, z.B. sind "über" und "Rübe" mögliche Kandidaten für "ürbe" (die Groß- und Kleinschreibung habe ich mal ignoriert).

Prinzipiell funktioniert das auch. Praktisch treten hier allerdings zwei Hauptprobleme auf:
1.) Es ist ein sehr speicherintensives Vorgehen
2.) Etwas längere Wörter (z.B. ein Wort wie "natürlich") hat schon eine ganze Menge an Möglichkeiten, die Buchstaben neu zu sortieren, entsprechend ist das alles etwas zeitintensiv.

Hat jemand eine Idee, wie ich das intelligent verbessern kann?

Ist das hier überhaupt das richtige Unterforum?

VG
Daniel

[bigben]

Hallo Daniel,

Hier mein erster Gedanke: ich denke, Du kannst Dir das ganze Permutieren komplett ersparen und einfach die Buchstaben in jedem Wort alphabetisch sortieren.

Ich würde auch vermuten, dass merge nicht unbedingt die effizienteste Lösung ist. Jedenfalls solltest Du m. E. unbedingt mal die Hash-Funktionen probieren.

Du legst also einen Hash an in dem für jede alphabetisch sortierte Buchstabenfolge die dazu passenden deutschen Wörter hinterlegt werden.

Ist das eine Hausaufgabe oder eine Umschreibung für Dein eigentliches Problem oder geht es wirklich um eine Geheimschrift?

LG, Bernhard

[bigben]

Nachtrag: (ein paar Stunden später)

• Sortieren der Buchstaben in einem String einfach: https://stackoverflow.com/a/5904854 oder noch schneller mit dem Paket stringi: https://stackoverflow.com/a/61497842
• Wenn Du eine gute und frei zugängliche Liste deutscher Wörter kennst, vielleicht auch noch mit verschiedenen Konjugations-/Deklinationsformen, dann darfst Du gerne einen Link hierlassen
• Hashtable-Funktionen in R: https://stat.ethz.ch/R-manual/R-devel/l ... shtab.html , alternativ schauen, ob ein data.table schneller oder praktischer ist.
• "Ist das hier überhaupt das richtige Unterforum?" - Ich denke nicht. Aber schön, dass hier auch mal wieder jemand schreibt. Unterforum ist nicht wirklich wichtig.

[DanielAC]

Danke für die Tipps. Das muss ich mal ausprobieren.

Es handelt sich auch nicht um eine Hausaufgabe, sondern um persönliches Interesse

Die Liste der Wörter habe ich hierher: http://www.aaabbb.de/WordList/WordList.php

[bigben]

Coole Idee, die Wörter aus der Wikipedia zu holen. Was mit Konjugation/Deklaration ist, beschreibt die Seite nicht. Erzähl mal, wenn Du Erfahrungen damit gesammelt hast.

LG, Bernhard

[Athomas]

Was es in Wikipedia so alles gibt:

Code: Alles auswählen

          Wort
 1: artenliste
 2: inselratte
 3: lastentier
 4: lasttieren
 5: rasentitel
 6: ratsteilen
 7: reitlasten
 8: restanteil
 9: startleine
10: steinalter
11: steintaler

oder auch

Code: Alles auswählen

        Wort
1: angereist
2: eintrages
3: eisgarten
4: eisgraten
5: gastieren
6: nagetiers
7: stagniere
8: tiersagen
9: trageisen

[bigben]

Cool. Das allein sind schon elf Wörter mit zehn Buchstaben. Den ursprünglichen Plan, von allen Wörtern alle Permutationen zu bestimmen, den würde ich sein lassen.
Was sind "rasentitel"? Muss ich vielleicht mal in der Wikipedia nachschlagen.

LG, Bernhard


PS: Ich habe gefunden, dass ein Tennisspieler sich eine Meistettitel auf einem Rasenplatz holen kann und das ist dann ein Rasentitel.

[Athomas]

Das sind natürlich Extrembeispiele - ca. 95% der vorkommenden Wörter sind "Buchstabenhäufigkeitsunikate" (ein Wort, das es in Wikipedia gar nicht gibt )!

[bigben]

Hallo Athomas,

eigentlich hatte ich auf einen Beitrag von Dir gewartet in dem Du zeigst, dass data.table - Zugriffe schneller sind als getHash. Setzt Du das wortlos als gegeben voraus, oder was

Aber ernsthaft: Wenn ich jetzt eine sehr lange Liste von Wörtern und deren alphabetischer Buchstabensortierung habe, sagen wir in zwei Spalten in einem data.frame. Dann würde ich die für einen schnellen lookup entweder in ein data.table umwandeln, was mit setDT richtig schnell geht. Oder ich würde eine Hashtable aufbauen und müsste dafür m. W. für jedes Wertepaar in einer Schleife (apply als Schleife gezählt) einmal sethash aufrufen. Ist das ernsthaft so, oder übersehe ich eine Abkürzung, mit der man schleifenfrei Wertepaare, beispielsweise aus einem data frame, in die Hashtable kopieren kann??

Zweckdienliche Hinweise gerne in diesem Thread, denn das ist ja noch voll on topic.

LG,
Bernhard

[Athomas]

eigentlich hatte ich auf einen Beitrag von Dir gewartet in dem Du zeigst, dass data.table - Zugriffe schneller sind als getHash.

Aha!? Ich war tatsächlich dabei, etwas Ausführliches zu schreiben, das hat wohl der Forensoftware zu lange gedauert, sie hat mich 'rausgeschmissen, alles ist weg !

Hier erstmal ein rohes Progrämmchen ohne Kommentare - ich bin mir allerdings nicht sicher, ob es das macht, was Du vorhast...
Es ging mir auch darum, das Zusammenspiel zwischen "mclapply" aus "parallel" (nur für Linux sinnvoll!) und data.table - das ja die Parallelverarbeitung "eingebaut" hat - auszuprobieren.

Code: Alles auswählen

library(data.table)
library(stringr)
library(parallel)

Kerne      <- 1

alphabet   <- c(letters[1:26],"ä","ö","ü","ß")
Transl     <- function(wort) paste0(str_count(wort, alphabet), collapse="-")

DT         <- fread("P:/R/R Forum/Wortverdrehungen/word_list_german_spell_checked.txt", header=FALSE)
setnames(DT, "Wort")
DT.uni     <- unique(DT[  , Wort:=tolower(Wort)])

DT.uni[  , Uebersetzung:=unlist(mclapply(Wort, Transl, mc.cores=Kerne))]

DT.uni[  , lnr:=1:.N, by=Uebersetzung]
DT.uni[  , Gruppenname:=min(Wort), by=Uebersetzung]