Etwas andere Checksumme eines Wortes

Etwas andere Checksumme eines Wortes (13 Beiträge, 170 Mal gelesen)

Du bist nicht angemeldet. [ Login/Registrieren ]

An alle Nogrammierkollegen

Ich brauche eine Funktion, die mir eine Checksumme anhand der vorhandenen Buchstaben in einem Wort ermittelt.

Dabei darf es keine Rolle spielen, in welcher Reihenfolge die Buchstaben in diesem Wort angeordnet sind, sondern wenn in dem Wort zum Beispiel 2 mal der Buchstabe A vorkommt und 2 mal der Buchstabe B und 2 mal der Buchstabe C vorkommt, dann muss es immer die gleiche Checksumme ergeben.

Beispiele :

AABBCC
CCBBAA
AACCBB
BBCCAA
ABCABC
CBACBA
BACBAC

und so weiter....

Jetzt habe ich mir mal folgendes überlegt :

Meine Primzahlen, die ich verwenden will :

A = 7
B = 11
C = 13
D = 17
E = 19
F = 29
G = 31
H = 41
I = 43
J = 59
K = 61
L = 71
M = 73
N = 101
O = 103
P = 107
Q = 109
R = 137
S = 139
T = 149
U = 151
V = 179
W = 181
X = 191
Y = 193
Z = 197

1.) Ich zähle alle Buchstaben A in dem Wort und multipliziere sie mit dem ASCII-Code 65 (für A) und multipliziere sie mit der Primzahl 7.
2.) Ich zähle alle Buchstaben B in dem Wort und multipliziere sie mit dem ASCII-Code 66 (für B) und multipliziere sie mit der Primzahl 11.
3.) Ich zähle alle Buchstaben C in dem Wort und multipliziere sie mit dem ASCII-Code 67 (für C) und multipliziere sie mit der Primzahl 13.

Dies ergebe in diesem Fall :

1.) 2 mal A = 65 * 2 * 7 = 910
2.) 2 mal B = 66 * 2 * 11 = 1452
3.) 2 mal C = 67 * 2 * 13 = 1742

Nun addiere ich diese 3 Ergebnisse :

910 + 1452 + 1742 = 4104

Anderes Beispiel :

GEIZHALS
HALSGEIZ
GHEAILZS
SZLIAEHG
SLAHZEIG

und so weiter....

1.) 1 mal A = 65 * 1 * 7 = 455
2.) 1 mal E = 69 * 1 * 19 = 1311
3.) 1 mal G = 71 * 1 * 31 = 2201
4.) 1 mal H = 72 * 1 * 41 = 2952
5.) 1 mal I = 73 * 1 * 43 = 3139
6.) 1 mal L = 76 * 1 * 71 = 5396
7.) 1 mal S = 83 * 1 * 139 = 11537
8.) 1 mal Z = 90 * 1 * 197 = 17730

Nun addiere ich diese 8 Ergebnisse :

455 + 1311 + 2201 + 2952 + 3139 + 5396 + 11537 + 17730 = 44721

Bin ich jetzt auf dem richtigen Weg oder habe ich irgendwo einen Rechen- oder Denkfehler in meiner Rechnung um eine eindeutige Checksumme für ein Wort mit beliebig vielen Buchstaben (A-Z) zu errechnen.

Ich erwarte mir viele (sinnvolle) Antworten zu diesem Thema ...

mfg euer wappler

Hmm,

wie willstn das verwenden ?!?
Möchtest aus der Checksumme wieder auf den ursprünglichen Text ?

Checksumme 31 könnte z.B. G oder ABC sein.
Deckt das deine Anforderungen ab ?
Wennst es multiplizierst is es eindeutig.

Grundsätzlich könntest die Buchstaben im Wort alphabetisch sortieren,
wenn die Reihenfolge ein Problem ist.

Ich muss aallerdings auch gestehen, dass ich jetzt auf die Schnelle
keine brauchbare Checksum Funktion aus dem Ärmel schüttel kann.

Mal drüber nachgrübeln...

greetz
Walter

Uuups,

sorry, hab da ein paar wesentliche Details überlesen.

greetz
Walter

Kann man dann nicht einfach den String normieren, d.h. z.b. nach Buchstaben ordnen, und dann erst die Checksum berechnen?

Also das aus

AABBCC
CCBBAA
AACCBB
BBCCAA
ABCABC
CBACBA
BACBAC
immer

AABBCC
wird, und dann die Checksum davon berechnen?

Das Vergleichen ist das Ende des Glücks und der Anfang der Unzufriedenheit.

Søren Kierkegaard (1813 - 1855)

Interessante Aufgabenstellung

Darf ich fragen, wofür das dienen soll? Als Trapdooralgorithmus?

Ich schliesse mich Komplexler an, die Normierung macht als erster Schritt Sinn.

Mein nächster Schritt wäre, die Sache mit den Primzahlen zu vergessen.

Die Zuordnung von A = 7 ist ja bereits eindeutig, warum mit dem ASCII Wert multiplizieren?

Abgesehen davon würde ich die Prüfsummen basierend auf Polynomen errechnen.

Normierung kann ich nicht brauchen, zerstört mir das Wort. Es ist kein Problem, zuerst alle A zu zählen, dann alle B, dann alle C usw...

Es gibt keine Umlaute oder Sonderzeichen.

Aus der Checksumme das Wort rückbilden brauch ich nicht.

Im Prinzip geht es um ein Wortratespiel.

Ich habe 2 mal A und 2 mal B und 2 mal C, welche sinnvolle Worte kann ich damit bilden ?

Jetzt habe ich eine Datenbank und sage "Zeige mir alle Wörter mit Checksumme 4104" und muss bekommen

AABBCC
CCBBAA
AACCBB
BBCCAA
ABCABC
CBACBA
BACBAC

Anderes Beispiel :

"Zeige mir alle Wörter mit Checksumme 44721" und muss bekommen

GEIZHALS
HALSGEIZ
GHEAILZS
SZLIAEHG
SLAHZEIG

Direkt nach dem Wort kann ich nicht suchen, da ich nicht weiss, welche Worte sich mit AABBCC bilden lassen.

Den ASCII-Wert multipliziere ich nur so mal sicherheitshalber dazu.

Ich hoffe damit eure Fragen beantwortet zu haben.

mfg Wappler

Ok - jetzt ist mir klarer, was Du erreichen willst. Du hast also dann eine Datenbank mit (allen denkbaren) Wörtern und willst mit einer Abfrage ermitteln, welche Wörter sich mit einer bestimmten Buchstabenmenge bilden lassen?

Warum verzichtest dann komplett auf die Checksummen und speicherst zu jedem Wort noch die normierte Form (statt der Checksumme); dann kannst einfach nach der Buchstabenmenge suchen und erhältst alle passenden Wörter.

lg
mIstA

Lieber mIstA

Suchen nach Integer - Index geht um einiges schneller als nach Strings.
Bei z.B String mit 50 Zeichen habe ich 50 Zeichen normiert, bei Integer 4 Zeichen.

Ich dachte es geht um ein Wortratespiel - also um reale Wörter; wieviele gibts da mit 50 Zeichen?

Außerdem wirst Du es unmöglich schaffen für einen 50 Zeichen String eine Checksumme nach Deinen Vorgaben zu bilden, die den Wertebereich einer 32-Bit Integer nicht übersteigt; Du bräuchtest zumindest 66 Bit um alle möglichen Kombinationen einer eindeutigen Checksumme zuordnen zu können.

lg
mIstA

Hast du Obergrenzen? Checksum-Länge bzw Wortlänge? Wie schauts mit Sonderzeichen aus?
Wieso gehst du von 65-90?
Wirklich eindeutig ist deine Methode nicht. (Ein Wort mit 1311 "A" kommt auf die selbe Checksumme wie ein Wort mit 455 "B")

Suche im Forum
Suche im Internet (Google)
Was ist?
Forums-FAQa>
GH-Chat (IRC-Client muss installiert sein)
Kino 2004

Lieber Robert

1.) 1311 * 65 * 7 = 937365
2.) 455 * 66 * 11 = 330330

Also ganz verstehe ich deine Aussage nicht.

65-90 sind die ASCII-Codes

mfg Wappler

Dann nimm halt z.B. ein Wort aus 726 'A' und eines aus 455 'B'.

Wennst wirklich jeder möglichen (sortierten) Buchstabenfolge eindeutig eine Prüfsumme zuordnen willst, dann wird das vermutlich nur mit einer Multiplikation aller Buchstabencodes - die klarerweise Primzahlen sein müssen - funktionieren.

Also jedem Buchstaben eindeutig eine Primzahl zuordnen, wobei Du ruhig bei 2 statt erst bei 7 beginnen kannst und dann alle Zahlen, die den Buchstaben Deines Wortes entsprechen, aufmultiplizieren; die Prüfsummen können dabei allerdings durchaus sehr große Zahlen werden. Darum würde ich auch die Buchstaben nicht dem Alphabet nach den Primzahlen zuordnen (also A=2, B=3, C=5, ...) sondern mich eher an der Häufigkeit der Buchstaben orientieren, also E=2 usw.

Eine andere Möglichkeit wäre, zuerst die Buchstaben des Wortes alphabetisch zu sortieren und dann für den resultierenden String einen geeigneten Hash-Wert (z.B. MD5) als Prüfsumme zu berechnen; damit bleibt die Größe der Checksumme überschaubar und konstant, dafür gibts aber natürlich wieder mehrere Worte mit derselben Prüfsumme. Allerdings sollte es praktisch unmöglich sein 2 Worte mit identer Prüfsumme zu konstruieren.

lg
mIstA

Sorry, hab mich in deiner Liste verschaut.
Das Stichwort heisst aber kleinstes gemeinsames Vielfaches. Und darum kommst du nicht herum.

Bezüglich dem ASCII-Code: Das war mir schon klar, wie du auf die Zahlen kommst, aber welchen Sinn hat es die zu verwenden, ausser dass die Zahlen noch grössser werden?

Suche im Forum
Suche im Internet (Google)
Was ist?
Forums-FAQa>
GH-Chat (IRC-Client muss installiert sein)
Kino 2004

Dieses Forum ist eine frei zugängliche Diskussionsplattform.
Der Betreiber übernimmt keine Verantwortung für den Inhalt der Beiträge und behält sich das Recht vor, Beiträge mit rechtswidrigem oder anstößigem Inhalt zu löschen.
Datenschutzerklärung