webentwicklung-frage-antwort-db.com.de

Zeichenfolge für eindeutiges ganzzahliges Hashing

Ich versuche, ein System zu entwickeln, das meine Zeichenfolge in einen eindeutigen Integralwert umwandeln kann. Das bedeutet, dass beispielsweise das Word "Konto" einen verschlüsselten numerischen Wert von 0891 hat und kein anderes Word möglicherweise mit demselben Konvertierungsprozess in 0891 konvertiert werden kann nicht muss jedoch in der Lage sein, die generierte Ganzzahl in eine Zeichenfolge umzuwandeln.

Gleichzeitig hängt es von den Word-Strukturregeln ab. Bedeutet, dass Wörter wie "Genauigkeit" und "Ankündigung" eine generierte Nummer größer als 0891 haben, und Wörter wie "a", "Abakus" und "Abkürzung" eine generierte Anzahl von weniger als 0891.

Der Zweck dieser Anwendung besteht darin, ähnlich einem Index oder Primärschlüssel zu dienen. Der Grund, warum ich keinen inkrementellen Index verwende, ist aus Sicherheitsgründen und hängt mit der Abhängigkeit der Indizes von der Anzahl der Daten in der Gruppe zusammen

(z.B.)

[0] A, [1] B, [2] C, [3] D, [4] E, [5] F

Die obigen Buchstaben haben jeweils einen entsprechenden Index, E hat den Index von 4

Wenn jedoch die Daten plötzlich erhöht oder gesenkt werden, werden sie sortiert

[0] A, [1] AA, [2] AAB, [3] C, [4] D, [5] DA, [6] DZ, [7] E, [8] F

E hat jetzt den Index von 7

Jedes Wort muss ein eindeutiges unabhängiges integrales Äquivalent haben und die entsprechenden Gewichtungen haben.

Ich muss wissen, ob es einen Algorithmus gibt, der das oben genannte kann.

Jede Hilfe wird geschätzt.

17
Treize

Dies ist bei den von Ihnen gegebenen Einschränkungen nicht möglich, es sei denn, Sie legen eine maximale Länge fest.

Nehmen Sie an, dass k("a") und k("b") die Codes dieser beiden Zeichenfolgen sind.

Mit Ihren Einschränkungen suchen Sie nach einer eindeutigen Ganzzahl, die zwischen diesen beiden Werten liegt, aber k("a") < k("a....a") < k("b"). Da es eine unendliche Anzahl von Zeichenfolgen des Stils "a....a" (und "akjhdsfkjhs") gibt, die zwischen die beiden Codes passen müssten, kann ein solcher Reihenfolgeerhalt allgemeiner, eindeutiger Code fester Länge für Zeichenfolgen beliebiger Länge nicht existieren. Da Sie so viele ganze Zahlen benötigen wie Strings, und da Strings nicht an die Länge gebunden sind, kann dies nicht funktionieren.

Löschen Sie entweder general (also das Einfügen neuer Zeichenfolgen nicht zulassen), unique (Kollisionen zulassen - verwenden Sie z. B. die ersten vier Buchstaben als Code!), Die unbegrenzte Länge (z. B. 3 Zeichen) oder die Eigenschaft, die die Reihenfolge beibehält.

10
Erich Schubert

Der Einfachheit halber gehe ich davon aus, dass a bis z die einzigen in Wörtern zulässigen Zeichen sind.

Ordnen Sie uns bis zu 2 Zeichenketten zu:

String Value
a      0
aa     1
ab     2
...
az     26
b      27
ba     28
bb     29
...
bz     53
c      54
...

Wenn Sie nun nur das betrachten, sollten Sie in der Lage sein, zu verstehen, dass Sie zur Bestimmung des Versatzes einer beliebigen Zeichenfolge mit kürzerer Länge die maximal zulässige Länge benötigen. Nehmen wir an, wir kennen diese Nummer.

Zur Vereinfachung der Algorithmen würden wir lieber mit 27 beginnen: (Sie können es gerne mit 0 anfangen, Sie benötigen einige Sonderfälle.)

String Value
a      27
aa     28
ab     29
...

Im Wesentlichen trägt das am weitesten links stehende Zeichen einen Wert 27*(1-26) (für a-z) bei, und das nächste Zeichen rechts, falls vorhanden, trägt 1-26 (für a-z) zu dem Wert einer Zeichenfolge bei.

Dies kann nun verallgemeinert werden, um zu sagen, dass die am weitesten links stehende Zahl (1-26)*27^(len-1), der nächste (1-26)*27^(len-2) usw. bis (1-26)*27^0 beitragen würde.

Was mich zu etwas Java-Code führt:

long result = 0;
for (int i = 0; i < s.length(); i++)
   result += pow(27, MAX_LENGTH - i - 1)*(1 + s.charAt(i) - 'a');

Testausgabe:

a                    =   150094635296999121
aa                   =   155653695863554644
aaa                  =   155859586995649293
aaaa                 =   155867212593134280
aaaaa                =   155867495022670761
abacus               =   161447654121636735
abbreviation         =   161763445236432690
account              =   167509959568845165
accuracy             =   167554723653128367
announcement         =   230924421746611173
z                    =  3902460517721977146

Online Demo .

Ja, das sind ziemlich große Zahlen für nur bis zu 13 Strings, aber ohne sequentielles Zuweisen von Wörtern zu Wörtern in einem Wörterbuch können Sie nichts Besseres tun (außer, dass Sie bei 0 beginnen können, was relativ ist , ein kleiner Unterschied), da es so viele Möglichkeiten für Buchstabenfolgen gibt.

8
Dukeling

Für die Eindeutigkeit beginnen Sie mit der Zuweisung von Primzahlen zu den Buchstaben: A -> 2, B -> 3, C -> 5, D -> 7 usw.

Um den "Schlüssel" eines bestimmten Buchstabens in einem Wort zu berechnen, erhöhen Sie den Primzahlwert auf den Positionsindex im Wort. Um den "Schlüssel" des ganzen Wortes zu erhalten, multiplizieren Sie alle Buchstabenschlüssel.

Zum Beispiel das Word CAB:

C -> 5 ^ 1 = 5
A -> 2 ^ 2 = 4
B -> 3 ^ 3 = 81
CAB -> 5 * 4 * 81 =  1620.

Kein anderes Wort wird dir als Schlüssel 1620 geben. 

Hinweis: Sie müssen nicht mit A -> 2 beginnen oder den Zeichen des Alphabets in der Reihenfolge Primzahlen zuweisen, solange Sie das Mapping verfolgen. Bedenken Sie auch, dass die Ergebnisse sehr schnell sehr groß werden.

Beachten Sie jedoch die anderen Anmerkungen zur Sicherheit - dies ist kein besonders sicherer Algorithmus. 

3
Vicky

Wenn Sie keine Begrenzung für die Anzahl der Bytes haben, die diese Ganzzahlen belegen können, erhalten Sie durch die darunter liegenden Bytecodes (z. B. Ascii) für jedes Zeichen eine Ganzzahldarstellung. Weisen Sie entsprechend 0 = A, 1 = B bis Z = 25 zu, und dann ist das Wort selbst die ganze Zahl in der Basis 26.

2
Stochastically

Du kannst das:

SEPARETOR = '000'
string_to_hash = "some_string"
hashed_result = int(SEPARETOR.join(list(str(ord(character)) for character in string_to_hash)))

Genießen!

1
Yuval Pruss

Weisen Sie jedem Alphabet in aufsteigender Reihenfolge einen eindeutigen Primwert zu (Reihenfolge nicht erforderlich).

Bitte beachten Sie: Da die Multiplikation der Primzahlen ein eindeutiges Ergebnis ist, das nur mit diesen Zahlen multipliziert werden kann, erhalten Sie für jedes Wort eindeutige Werte.

Algorithmus: 

int hash = 0;
forEach (int i = 0 ; i < Word.length ; i++)
{ 
   hash *= (prime[c[i]] ** (length - i)); 
}

prime - Ein Array, in dem jeweils Primwerte gespeichert werden

powered to (length - 1), um der Stelle, an der dieses Zeichen auftritt, einen Wert zu geben, um eine Wörterbuchreihenfolge zu erhalten.

Dieser Algorithmus gibt ausreichend große Werte, die Ihr Array überschreiten

Außerdem: words werden mit kleineren Längen zu niedrigeren Werten führen als einige Wörter mit größerer Länge. Dies kann sich auf die Wörterbuchreihenfolge auswirken

1
Rahul

Ja, aber meistens nein.

Ja, wie in der Antwort von Stochastically. Durch das Einrichten einer Basis 26 (oder der Basis 128 für alle ASCII-Zeichen) können Sie theoretisch jeden String eindeutig kennzeichnen.

Auf der anderen Seite ist dies nicht praktikabel, da nicht nur die Zahlen für die meisten Sprachen zu groß werden würden, sondern dies wäre wahrscheinlich ein unglaublich aufwendiger Prozess. Wenn Strings unendlich sein dürfen, kann außerdem eine Form von Cantors Diagonalargument angewendet werden, die diesen Algorithmus "bricht". Es ist nicht möglich, eine Eins-zu-Eins-Zuordnung eines Satzes mit Kardinalität aleph-one (Zeichenfolgen) zu einem Satz von Kardinalität aleph-null (ints) zu erstellen.

0
tox123