algo sur chaine

Le titre n'est pas clair, alors voici l'explication de texte :

imaginons un fichier contenant 5000 lignes (des articles).

Je recherche un algo me permettant d'identifier de façon unique le texte de chaque ligne sous une forme numérique ou alphanum. Là, vous allez me dire qu'il suffit de créer un index. Sauf que le fichier n'est pas indexé et que je ne peux y rajouter que des articles, et aucun champ de plus. De plus, j'ai des raisons personnelles pour ne pas créer d'index

Le but de cet algo serait de calculer une sorte de checksum dépendant de la nomenclature de chaque article. Ainsi, si deux nomenclatures ne sont différentes ne serait-ce que d'un espace, alors les checksums seraient différents.

Je sais que c'est un truc bizarre, mais je n'ai pas la maitrise du fichier initial (c'est celui d'un fournisseur et il est stocké sur son site de production).

Tout ça pour me faciliter la phase de traitement de ce fichier et pour en faire une utilisation à ma sauce. Par exemple, la recherche de doublons ou autres serait plus simple (pour info, chaque article est identifié par une nomenclature comprenant de 53 à plus de mille caractères... Quand je vous dis que c'est un truc bizarre ;) )

Donc si quelqu'un avait ce genre d'algo, une lib/compo utilisable sous Delphi ou au moins une piste de recherche, j'en serais reconnaissant.

PS : je suis nul en maths (4 au bac de Math, coef 9 :aie: - pas fait mieux depuis)

Vous pouvez calculer la somme des codes ASCII de tous les caractères de chaque nomenclature.

Ton truc m fait penser a des problemes de cryptographie.....

As tu pensée à utiliser des fonctions de hachage? Un hash sur l'article, et normalement si les articles sont différents, le hash sera différent....

Avec des hash correct t'as que 1 chance sur 2^80 ou 2^160 d'avoir pour 2 articles différents un hash identique...

Je pense qu'effectivement, parcourir le fichier ligne à ligne depuis delphi, et pour chaque ligne générer un hash stoqué dans un tableau, puis dédoublonner le tableau pourrait suffire.

merci pour vos conseils. Je n'ai pas les connaissances mathématiques nécessaires à l'élaboration d'une fonction de hachage (en fait, je ne sais absolument pas comment faire).

Je me suis renseigné, et en furetant à droite/gauche, j'ai trouvé une unité "MD5.pas" utilisable sous D4. Je vais essayé de voir si je peux l'adapter à mon Delphi.

Autrement, si quelqu'un arrive à m'expliquer en langage "mathématiques pour les nuls" la façon dont marche une fonction de hashage... j'ai regardé dans ma bibliothèque (wikipédia + google :D ), mais j'ai un peu de mal. J'essairais de relire tout ça à tête reposée. (les bouts de pseudo-code sont les bienvenus :P )

En plus, dans tous les cas, si je crée un hash, j'ai cru comprendre qu'il me fallait un index car création d'une table...

@Nadiri : cela n'est pas possible car certaines nomenclatures contiennent strictement les mêmes caractères, mais dans un ordre différent (ex : P15-RFPN-59 et R9N1-P-PF55)

@Sebus : c'est quoi un hash 'correct' ? est-ce qu'on peut en obtenir un sur des chaines de moins de 100 caractères ?

Edit :
PS : n'y aurait-il pas quelque part des cours d'algo accessible aux débutants. j'en ai trouvé, mais à moins d'être ingénieur ou d'avoir fait math sup, c'est souvent 'raide' ?

Citation:

---

Envoyé par diam's

@Nadiri : cela n'est pas possible car certaines nomenclatures contiennent strictement les mêmes caractères, mais dans un ordre différent (ex : P15-RFPN-59 et R9N1-P-PF55)

---

oui même avec une fonction de hachage plus compliquée comme :
S=s0s1..sn-1
h(S) = (s0B^(n-1) + s1B^(n-2) + .. + s(n-1)B^1) mod N
(N: taille de la table de hachage, B une puissance de 2)
la possibilité que deux nommeclatures soient associées à la même clé se présente toujours.
La solution est de prévoir une comparaison supplémentaire pour traiter le cas des collisions(si deux nomenclautres ont les mêmes clés)

Normalement on crée une table supplémentaire qui contient les enregsitrements ayant la même clé.

Bonjour,

Citation:

---

la possibilité que deux nommeclatures soient associées à la même clé se présente toujours.
La solution est de prévoir une comparaison supplémentaire pour traiter le cas des collisions(si deux nomenclautres ont les mêmes clés)

---

+1

Pour la clé, un checksum (CRC) polynomial sur 16, 32 ou 64 bits fait l'affaire, MD5 par exemple.