Discussion :

[druzy]

Bonjour,
je recherche une fonction de hachage efficace pour classer les mots français et bien sur que ma table de hachage contien a peu pres autant d'élément pour chaque partie.

Merci de vos réponses.

[M.Dlb]

Tu peux regarder du coté du MD5 ou du SHA-1

Il doit exister des librairies de crypto pour différents compilateurs.

[druzy]

Ce que je veux dire c'est que je dois avoir une fonction de hachage (f) qui prend un string( ici un mot français) et qui renvoi un numéro.
ma table de hachage est de type
hach : array[0..HTAILLE-1] of pointeur de liste.
où HTAILLE est un nombre premier assez grand.
ensuite je fais hach[f(mot) mod HTAILLE] pour savoir où placer mon mot dans le tableau.
Je recherche donc une fonction pour bien répartir un texte en francçais dans ma table de hachage.
md5 et l'autre ne me paraissent pas oportine(je sais pas comme ça s'écrit).

[Schpountz42]

j'ai le même problème et un master recherche m'a conseiller de fair une fonction qui prendrait en compte la taille du string et le nombre de voyelle par exemple, puis modulo la taille de la table de hachage.
Tout ca sans me donner de precision sur les calculs à faire.
Si quelqu'un a des idées...

[Graffito]

Bonjour,

hach : array[0..HTAILLE-1] of pointeur de liste.

Un CRC 16 bits devrait donner une répartition à peu prés équilibrée sur 65536 listes. Soit en moyenne 5 mots par liste ("collisions") pour un dictionnaire de 250000 mots.
Il est assez facile de faire l'histogramme du nombre d'entrées dans le tableau en fonction du nombre de mots par entrée et de vérifier l'homogenéité globale de la repartition. Le nombre d'entrées avec plus de 25 mots devrait être vraiment insignifiant.

md5 et l'autre ne me paraissent pas oportine(je sais pas comme ça s'écrit).

MD5 ou SHA modulo HTAILLE me paraissent convenir parfaitement...

[druzy]

peux tu expliquer ce que tu as dit car je n'ai rien compris

[droggo]

Muo,

j'ai le même problème et un master recherche m'a conseiller de fair une fonction qui prendrait en compte la taille du string et le nombre de voyelle par exemple, puis modulo la taille de la table de hachage.
Tout ca sans me donner de precision sur les calculs à faire.
Si quelqu'un a des idées...

C'est plutôt élémentaire comme algorithme, et tu vas obtenir de nombreuses collisions.
Cela étant dit, ça dépend de la taille du dictionnaire à gérer. Si elle est modeste, ça peut suffire, mais il ne faudra pas qu'elle augmente de trop.

Je sais bien qu'une table de hachage correctement conçue sait gérer les collisions, mais il ne faut pas oublier que chaque collision ralentit les recherches, sans même parler des collisions multiples, genre 10 mots en collision.

[Schpountz42]

En effet le nombre de mot recu devrait être assez limité (ce ne devrait pas ateindre le milier). C'est un petit projet^^
En ce qui concerne le MD5 ou SHA je ne sais pas l'utilisé en pascal.

[druzy]

pas d'accord avec shountpz
on doit avoir un texte français qui peux atteindre largement 3000 mot.
le probleme est vraiment la cle de hachage à utiliser en pascal.

[Schpountz42]

oui en théorie c'est possible les 3.000 mots mais je vois pas qui des correcteurs va se casser les ... à tester autant^^

et puis le modulo est la pour gérer en fonction du nombre de clé. Le problème est bien d'avoir une fonction qui repartisse bien sur chaque clé.

[druzy]

d'où la question.
quelqu'un a-t-il une idée d'algo?

[Dlieu]

Demande a Mr. Hankar

[Graffito]

Bonjour,

Ci joint le code d'un CRC 16bits utilisé dans l'aéronautique :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
Const crctab : Array[0..255] of Word = (
    $0000,  $1021,  $2042,  $3063,  $4084,  $50a5,  $60c6,  $70e7,
    $8108,  $9129,  $a14a,  $b16b,  $c18c,  $d1ad,  $e1ce,  $f1ef,
    $1231,  $0210,  $3273,  $2252,  $52b5,  $4294,  $72f7,  $62d6,
    $9339,  $8318,  $b37b,  $a35a,  $d3bd,  $c39c,  $f3ff,  $e3de,
    $2462,  $3443,  $0420,  $1401,  $64e6,  $74c7,  $44a4,  $5485,
    $a56a,  $b54b,  $8528,  $9509,  $e5ee,  $f5cf,  $c5ac,  $d58d,
    $3653,  $2672,  $1611,  $0630,  $76d7,  $66f6,  $5695,  $46b4,
    $b75b,  $a77a,  $9719,  $8738,  $f7df,  $e7fe,  $d79d,  $c7bc,
    $48c4,  $58e5,  $6886,  $78a7,  $0840,  $1861,  $2802,  $3823,
    $c9cc,  $d9ed,  $e98e,  $f9af,  $8948,  $9969,  $a90a,  $b92b,
    $5af5,  $4ad4,  $7ab7,  $6a96,  $1a71,  $0a50,  $3a33,  $2a12,
    $dbfd,  $cbdc,  $fbbf,  $eb9e,  $9b79,  $8b58,  $bb3b,  $ab1a,
    $6ca6,  $7c87,  $4ce4,  $5cc5,  $2c22,  $3c03,  $0c60,  $1c41,
    $edae,  $fd8f,  $cdec,  $ddcd,  $ad2a,  $bd0b,  $8d68,  $9d49,
    $7e97,  $6eb6,  $5ed5,  $4ef4,  $3e13,  $2e32,  $1e51,  $0e70,
    $ff9f,  $efbe,  $dfdd,  $cffc,  $bf1b,  $af3a,  $9f59,  $8f78,
    $9188,  $81a9,  $b1ca,  $a1eb,  $d10c,  $c12d,  $f14e,  $e16f,
    $1080,  $00a1,  $30c2,  $20e3,  $5004,  $4025,  $7046,  $6067,
    $83b9,  $9398,  $a3fb,  $b3da,  $c33d,  $d31c,  $e37f,  $f35e,
    $02b1,  $1290,  $22f3,  $32d2,  $4235,  $5214,  $6277,  $7256,
    $b5ea,  $a5cb,  $95a8,  $8589,  $f56e,  $e54f,  $d52c,  $c50d,
    $34e2,  $24c3,  $14a0,  $0481,  $7466,  $6447,  $5424,  $4405,
    $a7db,  $b7fa,  $8799,  $97b8,  $e75f,  $f77e,  $c71d,  $d73c,
    $26d3,  $36f2,  $0691,  $16b0,  $6657,  $7676,  $4615,  $5634,
    $d94c,  $c96d,  $f90e,  $e92f,  $99c8,  $89e9,  $b98a,  $a9ab,
    $5844,  $4865,  $7806,  $6827,  $18c0,  $08e1,  $3882,  $28a3,
    $cb7d,  $db5c,  $eb3f,  $fb1e,  $8bf9,  $9bd8,  $abbb,  $bb9a,
    $4a75,  $5a54,  $6a37,  $7a16,  $0af1,  $1ad0,  $2ab3,  $3a92,
    $fd2e,  $ed0f,  $dd6c,  $cd4d,  $bdaa,  $ad8b,  $9de8,  $8dc9,
    $7c26,  $6c07,  $5c64,  $4c45,  $3ca2,  $2c83,  $1ce0,  $0cc1,
    $ef1f,  $ff3e,  $cf5d,  $df7c,  $af9b,  $bfba,  $8fd9,  $9ff8,
    $6e17,  $7e36,  $4e55,  $5e74,  $2e93,  $3eb2,  $0ed1,  $1ef0
);

Function  UpdateCRC(crc:Word;data:Byte):Word;
begin UpDateCRC := ((crc SHL 8) and $FFFF) XOR ( CRCtab[ (crc SHR 8) XOR data] ); end;

function CRCcalc(s:String) : word ;
var I : smallint   ;
    Finalcrc : word ;
begin
 FinalCRC := $FFFF;
 (* calc CRC MSB to LSB *)
 For I:=1 to length(s) do FinalCRC := UpdateCRC(FinalCRC, ord(s[I]));
 (* Final remainder complement *)
 CRCcalc:=Not FinalCRC;
end ; (* CRCCalc *)

[druzy]

Déjà demander à MR HANCAR et il nous a donné un algo mais je sais pas si on peux l'utiliser et il nous a dit de chercher sur la toile