Tracer des chaînes de caractères vers des nombres en conservant l'ordre lexicographique.

Question

Je cherche un algorithme ou une fonction capable de faire correspondre une chaîne de caractères à un nombre de telle sorte que les valeurs résultantes correspondent à l'ordre lexicographique des chaînes de caractères. Exemple :

"book" -> 50000
"car"  -> 60000
"card" -> 65000
"a longer string" -> 15000
"another long string" -> 15500
"awesome" -> 16000

En tant que fonction, elle devrait être du type : f(x) = y, de sorte que pour tout x1 < x2 => f(x1) < f(x2), où x est une chaîne de caractères arbitraire et y un nombre.

Si l'ensemble des entrées de x est fini, alors je pourrais toujours faire un tri et assigner les valeurs appropriées, mais je cherche quelque chose de générique pour un ensemble d'entrées de x illimité.

Answer 1

Si vous souhaitez que f sont des entiers, c'est impossible.

Supposons qu'il existe une telle carte f . Considérons les chaînes de caractères a , aa , aaa , etc. Considérons les valeurs f(a) , f(aa) , f(aaa) , etc. Comme nous exigeons que f(a) < f(aa) < f(aaa) < ... nous constatons que f(a_n) tend vers l'infini lorsque n tend vers l'infini ; j'utilise ici la notation évidente que a_n est le caractère a répétées n fois. Considérons maintenant la chaîne b . Nous exigeons que f(a_n) < f(b) pour tous n . Mais f(b) est un entier fini et nous venons de montrer que f(a_n) va à l'infini. Nous sommes en présence d'une contradiction. Une telle carte n'est pas possible.

Peut-être pourriez-vous nous dire pourquoi vous en avez besoin ? C'est assez abstrait et nous pourrions peut-être vous suggérer quelque chose de plus approprié. En outre, ne vous préoccupez pas nécessairement de résoudre "ça" en général. YAGNI et tout le reste.

Answer 2

En corollaire à Réponse de Jason Si vous pouvez faire correspondre vos chaînes de caractères à des nombres rationnels, une telle correspondance est très simple. Si code(c) est le code ASCII du caractère c y s[i] est le i ème caractère de la chaîne de caractères s Il suffit de faire la somme suivante :

result <- 0
scale  <- 1
for i from 1 to length(s) 
  scale <- scale / 26
  index <- (1 + code(s[i]) - code('a'))
  result <- result + index / scale
end for
return result

Cela permet de faire correspondre la chaîne vide à 0, et toutes les autres chaînes à un nombre rationnel compris entre 0 et 1, en conservant l'ordre lexicographique. Si vous disposez de nombres décimaux à virgule flottante de précision arbitraire, vous pouvez remplacer la division par des puissances de 26 par des puissances de 100 et continuer à obtenir des nombres exactement représentables ; avec des nombres binaires à virgule flottante de précision arbitraire, vous pouvez diviser par des puissances de 32.

Answer 3

Ce que vous demandez, c'est une suspension temporaire du principe du trou de pigeon ( http://en.wikipedia.org/wiki/Pigeonhole%5Fprinciple ).

Les cordes sont les pigeons, les chiffres sont les trous. Il y a plus de pigeons que de trous, on ne peut donc pas mettre chaque pigeon dans son propre trou.

Answer 4

Vous feriez mieux d'écrire un comparateur que vous pouvez fournir à une fonction de tri. Le comparateur prend deux chaînes de caractères et renvoie -1, 0 ou 1. Même si vous pouviez créer une telle carte, vous devriez toujours la trier. Si vous avez besoin à la fois d'un "hachage" et de l'ordre, conservez les données dans deux structures : l'une qui préserve l'ordre et l'autre qui permet un accès rapide.

Answer 5

Peut-être un Radix Tree est ce que vous recherchez ?

Un arbre radix, Patricia trie/tree, ou arbre de bits crit est une structure de données de données spécialisée basée sur le trie qui est utilisée pour stocker un ensemble de chaînes de caractères. En Contrairement à un triangle normal, les arêtes d'un arbre Patricia sont étiquetées par des séquences de caractères plutôt que plutôt qu'avec des caractères uniques. Ceux-ci peuvent être des chaînes de caractères, des chaînes de bits telles que des nombres entiers ou des adresses IP, ou des séquences généralement arbitraires de d'objets dans l'ordre lexicographique. Les noms arbre radix et arbre de bits crit ne s'appliquent qu'aux arbres stockant des entiers et Patricia trie est conservée pour des entrées plus plus généraux, mais la structure fonctionne fonctionne de la même manière dans tous les cas.

LWN.net propose également un article décrivant l'utilisation de ces structures de données dans le noyau Linux. .