Chaîne à un hachage d'entier unique

Je suis en train de développer un système qui peut changer d'une chaîne en une unique valeur intégrale, sens disons, par exemple, le mot "compte", a chiffré la valeur numérique de 0891 et pas d'autre mot peut éventuellement être converti au 0891 avec le même processus de conversion, il ne pas doivent cependant être en mesure d'être reconverti générés entier en chaîne de caractères.

En même temps, il dépend de la structure des mots de règles, le sens des mots tels que "précision" et "annonce" aura un numéro généré plus de 0891 et des mots tels que "un", "abacus" et "abréviation" aura un numéro généré de moins de 0891.

Le but de cette application est de servir semblable à un index ou de la clé primaire. La raison pour laquelle je ne suis pas en utilisant un incrément d'indice pour des raisons de sécurité et est due à l'index de la dépendance du nombre de données dans l'ensemble

(par exemple)

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

Les lettres ci-dessus a chaque index correspondant, E a pour indice de 4

Cependant, si les données est soudainement augmenté ou diminué ensuite triés

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

E a maintenant l'indice de 7

Chaque mot doit avoir un unique indépendant intégrale équivalente et a le même poids.

J'ai besoin de savoir si il existe un algorithme qui peut faire le ci-dessus.

Toute aide sera appréciée.

source d'informationauteur Treize

  1. 10

    Ce n'est pas possible avec les contraintes que vous avez donné, à moins d'imposer un maximum de longueur.

    Supposer que k("a") et k("b") sont les codes de ces deux chaînes.

    Avec vos contraintes, vous êtes à la recherche pour un nombre entier qui tombe entre ces deux valeurs, mais k("a") < k("a....a") < k("b"). Comme il existe un nombre infini de chaînes de style "a....a" (et "akjhdsfkjhs") qui aurait besoin d'ajustement entre les deux codes, un tel afin de préserver général, unique, de longueur fixe code n'existe pas pour les chaînes de caractères de longueur arbitraire. Car vous auriez besoin d'autant de nombres entiers comme des chaînes de caractères, et depuis que les chaînes ne sont pas délimitée par la longueur cela ne peut pas fonctionner.

    Baisse générale (afin de ne pas permettre l'insertion de nouvelles chaînes), unique (permettre collissions - par exemple, utiliser les quatre premières lettres du code!), la surabondance de la longueur (par exemple à 3 caractères) ou l'ordre de la préservation de la propriété.

  2. 7

    Pour des raisons de simplicité, je vais supposer a à z sont les seuls caractères autorisés dans les mots.

    Nous allons attribuer les numéros jusqu'à la longueur de 2 chaînes:

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

    Maintenant, simplement en la regardant, vous devriez être en mesure de comprendre que, pour déterminer le décalage d'une plus courte chaîne de longueur, vous auriez besoin de la longueur maximale autorisée. Supposons que nous savons ce numéro.

    À algorithmique simplicité, nous préférons commencer à 27: (n'hésitez pas à essayer de le comprendre, pour partir de 0, vous aurez besoin de quelques cas particuliers)

    String Value
a      27
aa     28
ab     29
...

    Donc, essentiellement, le plus à gauche personnage contribue à une valeur 27*(1-26) (a-z) et le caractère suivant le droit, s'il en existe, contribue 1-26 (a-z) de la valeur d'une chaîne de caractères.

    Maintenant, ceci peut être généralisé à-dire que la gauche-le plus grand nombre de contribuer (1-26)*27^(len-1)la prochaine (1-26)*27^(len-2)et ainsi de suite, jusqu'à ce que (1-26)*27^0.

    Ce qui m'amène à certains de code Java:

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

    Test de sortie:

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

    Démo en ligne.

    Oui, ceux sont quelques raisonnablement grands nombres pour seulement jusqu'à la longueur de 13 cordes, mais, sans séquentiellement l'attribution des numéros de mots dans un dictionnaire, vous ne pouvez pas faire mieux (sauf que vous pouvez commencer à 0, ce qui est, relativement parlant, une petite différence), car il y a beaucoup de possibilités de séquences de lettres.

  3. 2

    Si vous n'avez pas de limite sur le nombre d'octets que ces entiers peuvent occuper, puis le sous-jacent (par exemple, Ascii) octets de codes pour chaque personnage va vous donner une représentation entière. De manière équivalente, d'attribuer 0=A, 1=B jusqu'à Z=25, puis le mot lui-même est le nombre entier en base 26.

  4. 2

    De l'unicité, de commencer à l'attribution de primes aux lettres:
    A -> 2, B -> 3, C -> 5, D -> 7 etc.

    Pour calculer la "clé" d'une lettre dans un mot, augmenter la prime à la puissance de l'index de position dans le mot. Pour obtenir la "clé" de l'ensemble de la parole, de multiplier toutes les touches de lettre ensemble.

    Par exemple le mot de la CABINE:

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

    Aucun autre mot ne sera jamais vous donner 1620 comme une clé.

    Remarque: vous n'avez pas à démarrer avec Un -> 2 ou attribuer des primes aux caractères de l'alphabet dans l'ordre tant que vous garder une trace de la cartographie. Aussi garder à l'esprit que les résultats de cette obtiendrez de grandes très rapidement.

    Toutefois, il faut garder à l'esprit les autres commentaires au sujet de la sécurité - ce n'est pas particulièrement sûr de l'algorithme.

  5. 1

    D'assigner une première valeur de chaque alphabet dans l'ordre croissant(de l'ordre n'est pas nécessaire).

    Veuillez Noter: multiplication des nombres premiers est un résultat unique qui ne peut être multipliée par ces chiffresil vous donnera des valeurs uniques pour chaque mot.

    Algorithme : 

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

    premier - Un tableau pour stocker le premier des valeurs correspondant à chaque

    alimenté (longueur - 1) pour donner de la valeur à l'endroit où ce caractère se produit pour maintenir un ordre du dictionnaire.

    Cet algorithme donnera suffisamment grandes valeurs qui dépassement votre tableau.

    Aussi : mots les plus petites longueurs peuvent donner des valeurs inférieures à celles de certains mots avec plus de longueur et il peut affecter votre ordre du dictionnaire mais je ne suis pas sûr pourquoi voulez-vous un dictionnaire afin que le caractère unique sera maintenue ici.

  6. 1

    Vous pouvez faire ceci:

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

    Profitez-en!

  7. 0

    Oui, mais surtout pas.

    Oui, comme Stochastiquement de réponse. Par la mise en place d'une base de 26 ans (ou de la base de 128 pour tous ASCII), vous pourriez théoriquement de hachage de chaque chaîne unique.

    D'autre part, cela est impossible, non seulement les numéros de devenir trop grand pour la plupart des langues, mais aussi, cela pourrait être une incroyablement longue. En outre, si les chaînes sont autorisées à être infinie, puis une forme de Chantre de l'argument de la diagonale peut être appliqué aussi "casser" cet algorithme. Il est impossible de créer un one-to-one mapping de cardinalité aleph-un (chaînes de caractères) à un ensemble de cardinalité aleph-zéro (ints).