Version imprimable
Bonjour
Je recherche un algo capable de compresser une chaine de caractere (26c) en un entier (ou numerique), par contre il faut que cet algo conserve l ordre de trie de la chaine .
Le faite que des chaines <> donne le meme nombre n est pas genant .
Un petit exemple
AAAAAAAAAA => 0
AAAAABBBBB => 0
ABBBBBBBBB => 1
CCCCCCCCC => 1
merci de votre aide
Ce n'est pas un algorithme de compression que tu cherches, mais une fonction de hachage...
Je ne crois pas qu'il soit possible d'en trouver une correspondant à tes critères, surtout pas de manière généraliste en tout cas.
As-tu des contraintes connues sur tes chaînes ? Longueur maximale, par exemple, caractères utilisables (OK, 26 lettres, mais y'a-t-il des espaces ou des chiffres ? Ou des minuscules ?), nombre maximal de chaînes, etc...
Est-ce que tes chaînes sont déjà triées à la base ? Ont-elles toutes la même longueur ? Si c'est du texte ou des mots, en quelle langue est-ce ?
salut
Sans rentrer trop dans les details
La chaine de 26 carac. correspond a une concatenation de plusieurs zones alpha et/ou numerique , mais je cherche un algo general .
Cette chaine correspond a l'ordre de trie d'une liste , selon les criteres de ma la liste celle ci peut etre tres.tres. volumineuse , la selection + le trie est beaucoup trop long (malgres les index) .
Le but est de pouvoir rajouter le resultat de l algo (le nombre) dans l'index (dans les index j ai privilégié la selection pas le trie) .
Grasse a un tel algo (si ca existe) le nombre le plus petit correspond forcement aux premieres lignes a afficher (avec un petit trie) .
Pour un fonctionnement optimal il faudrait que pour chaque chiffre on est en correspondance 1000 cas de chaine de 26 carac differente (mais la je pense qu il y a pas d algo)
Ben justement, il faudrait... ;-)Citation:
Envoyé par polux
J'ai bien compris ton besoin, ça n'a fait que confirmer ce que je pensais au premier post. C'est bel et bien une fonction de hachage (avec collisions, d'ailleurs) dont tu as besoin.
Mais ça ne m'aide absolument pas pour envisager la moindre fonction de hachage : pour ça, j'ai vraiment besoin des caractéristiques des chaînes, telles que celles que je t'ai demandées précédemment...
1) Peux-tu me préciser ces éléments ?
2) Peux-tu poster, ici, une vingtaine (pas plus) de chaînes "caractéristiques", histoire de voir un peu la tête qu'elles ont ?
Salut
Si ca peut d aider quelques cas (la chaine fait 23 caract)
----+----1----+----2---
FR00001333081027801001
FR00001333081027801010
FR00001333081027801047
FR00001333081027801223
FR00001333081027801683
FR00001333083056819904
FR00001333083056819905
FR00001333084097800001
FR00001400141027801223
FR00001653261027801683
FR00001708621562902618
FR00001808041003733182
FR00001812991027801010
FR00001841601027800111
FR00001841603002717001
FR00001845331027801223
FR00001845333006610181
FR00001845334097800001
FR00001880131027801683
FR00001882861003733001
FR00001882861027800111
FR00001882861027800190
FR00001882861027801001
FR00001882861027801010
FR00001882861027801047
FR00001882861027801683
FR00001882861231918064
FR00001883283006610925
FR00001883284553900951
FR00001889894553900951
FR00001892761027800111
----+----1----+----2---
0000019176141027801683
0000019176141027807212
0000019176141180800910
0000019176141558932002
0000019176143002717001
0000019176143056800526
0000019176144381909095
0000019177821027800111
0000019177821027801223
0000019177841027801001
0000019177841558932003
0000019177841558932004
0000019177844378909090
0000080009273006610925
0000080009513006610925
0000080010433006610925
0000080010443006610925
0000080010453006610925
0000080011021027801683
BBE00037961343006610151
BBE00037961343006610181
BBE00037961343006610191
BBE00037961343006610201
On le voie pas mais les premiers cas commencent par un blanc
C'est normal, il aurait fallu placer tes chaînes entre balises code et /code pour le voir.Citation:
Envoyé par polux
Bon, le seul et unique algo que j'entrevois n'est pas génial (taux de collisions phénoménal), mais bon, il peut peut-être résoudre ton problème...
1) Trouver une fonction de hachage unitaire HC(C) qui associe à un caractère donné un nombre entre 0 et 15 (sur 4 bits).
2) Initialiser un nombre E à 64 bits à zéro (si tu n'as que des nombres 32 bits sous la main, ce sera 8 caractères et pas 16).
3) Parcourir les 16 premiers caractères de la chaîne, en appliquant la règle suivante : E = (E*16)+HC(Ci) , Ci étant le Ième caractère de la chaîne. Ceci concatène tes fonctions de hachage unitaires (4 bits de longueur) en mettant le 1er caractère en poids fort.
4) Le résultat final constitue l'empreinte (=le hachage) de ta chaîne.
Pour la fonction HC(C), il faut connaître les caractères possibles : j'ai recensé, d'après ton exemple :
- L'espace,
- Les lettres (en majuscules), soit 26 caractères,
- Les chiffres, soit 10 caractères.
Total : 37 caractères, sachant que l'on doit arriver à 15 maximum. Le taux de collision est donc de 1,6875 caractères par valeur numérique.
Le "truc", c'est de répartir les caractères en fonction de leur ordre : tu vas donc partitionner ton espace des caractères vers ton espace de hachage.
Exemple :
Bien sûr, il faudra certainement adapter la fonction HC(C) à tes besoins, en fonction de la fréquence réelle des caractères... La fonction peut éventuellement dépendre non seulement du caractère, mais également de son indice. Tu peux aussi optimiser un peu le hachage en utilisant un nombre variables de bits, mais pour respecter le critère de tri, il faut que le Ième caractère soit codé sur un nombre constant de bits.Code:
2
3
4
5
6
7
8
9
OK, tu vois le principe ?