[tuto] Table de Hachage simplissime

Programmation d'applications complexes
Anonyme

[tuto] Table de Hachage simplissime

Message par Anonyme »

Suite à une discussion par MP avec l'un de nos membres , je me suis intéressé aux tables de hachages , qui, ma foi , mon l'air performantes , mais pas exempt de bug.

Le principe est simple , accélérer très rapidement une recherche dans un tableau.

pennons comme exemple un tableau de strings , qui contient bien évidement du texte , des noms par exemples,
imaginez maintenant que dans se tableau vous avez 5000 voir 10000 entrées avec des noms différents.

Admettons maintenant que l'entrée n°175 c'est monsieur Dupond
et que vous recherché cette personne.

qu'allez vous faire ?
Parcourir le grand tableau et comparer les chaînes avec la chaîne recherché ? la recherche va mettre un temps considérable... le top avant la recherche , c'est de connaître la position de l'élément recherché...
mais comment faire ?

Avec une fonction de hachage ! cette fonction calcule une position dans le tableau.

ex:

Pseudo code :
OnCherche$ = "Dupond"
Position = hash(OnCherche$)
Position = 175
C'est aussi simple que ca , on a plus qu'a aller à l'élément 175 pour accéder aux informations voulue.
c'est pas le top ca ?



J'ai pas réussi à trouvé un exemple concret de collisions , si une âme charitable arrive à me trouvé une faille , je suis preneur afin d'améliorer le hash

Code en entier :

Code : Tout sélectionner

; unsigned int = integer & 255
Macro unsigned_int
i
EndMacro

;@author Daniel J. Bernstein
Procedure.unsigned_int hash(string.s)
	hash.i = 5381
	char.c = #Null
	index.i= 0
		
	While index <> Len(String)
		char = PeekC(@string+index)
		hash = ((hash<<5) + hash) + char
		index+1
	Wend 
	
	ProcedureReturn hash & $FFFFFF
EndProcedure

Dim MonBigTableau.s(1<<24)


Macro addstring(string)
T$ = string
Hash = hash(T$)
MonBigTableau(Hash) = T$
EndMacro


; On ajoutes des éléments à la volée , peu importe la place dans le tableau...
addstring("Purebasic c'est de la bombe !")
addstring("Purebasic c'est de la bombe")
addstring("Okay , ca à l'air de marché...")
addstring("On va tester les collisions de la table de hachage")
addstring("OK")
addstring("d6")
addstring("d6 & OK on les même valeurs si on additionne la valeur ascii (d+6 == o+k) ")
addstring("A voir , si cela permet une accélération au seins d'une application 3D ( dans un pipeline de rendu par ex...)")


For i = 0 To 1000
If Len(MonBigTableau(i))>0
	Debug "HASH KEY = "+Str(i)+"         ||||    STRING STORED =  " +MonBigTableau(i)
EndIf 
Next 


Debug " "
Debug " "
Debug "Hash key == index du tableau , cet index est obtenu grâce à la fonction de hashage"

Edit :

Collision entre :
"Dupon?" et "On va tester les collisions de la table de hachage"
edit 2:

Merci Olivier , ca marche mieux
Dernière modification par Anonyme le mer. 01/avr./2009 20:33, modifié 1 fois.
kelebrindae
Messages : 579
Inscription : ven. 11/mai/2007 15:21

Message par kelebrindae »

Voilà qui peut être très pratique!

Il y a quand même deux choses que je ne comprends pas:
- La macro "unsigned_int" ne me paraît pas hyper-utile (pour le portage du code, peut-être?)
- La valeur retournée par la procédure Hash est renvoyée de cette façon: "ProcedureReturn hash & 255"
=> est-ce que cela ne borne pas cette valeur entre 0 et 255? Du coup, ton tableau dimensionné à 1000 ne sera pas utilisé complètement et le risque de collision est assez important... Non? :?
Anonyme

Message par Anonyme »

integer & 255 = unsigned int

PB ne gère pas nativement les nombres non signés ( cf: la doc )
les collisions sont énormes avec 2300 entrés ( j'ai fait des test )
je posterais plus tard , un hachage maison , avec une collision nulle.
kelebrindae
Messages : 579
Inscription : ven. 11/mai/2007 15:21

Message par kelebrindae »

Oui je sais, pour PB et les non signés, ce que je voulais dire, c'est que "&255" ça donne plutôt du unsigned byte. Pour du unsigned int, on serait plutôt sur du "&2147483647" (ou "& $FFFFFFF", si tu préfères) non?

Et du coup, pour les collisions nombreuses c'est normal vu que tu n'as que 256 résultats possibles quelle que soit la chaîne en entrée (et en plus tu n'utilises que 256 "slots" parmi les 1001 possibles dans ton tableau).
Anonyme

Message par Anonyme »

oui , mais sa plante , je ne sais pas encore pourquoi , je regarderais plus tard. :)
Avatar de l’utilisateur
GeBonet
Messages : 453
Inscription : ven. 29/févr./2008 16:17
Localisation : Belgique

Message par GeBonet »

Bonjour,

Si je m'invite, c'est qu'il y a très longtemps, j'ai travaillé avec des tables gérer par "hash codes"... Et c'était pour accéder en direct sur DD...
Nous n'avions pas la l'océan de mémoire d'aujourd'hui... :lol:

La solution pour éviter les collisions ou du moins les réduire c'est d'augmenter la taille du tableau...
(ou la prédétermination du nombre d'enregistrement sur disque).

Exemple pour 1000 entrée créer un tableau de 1500...
Et pour que cela fonctionne bien créer le rapport entre les deux
Soit ici ce serait 1500/1000= 1.5. Et faire intervenir cet indice dans le calcul de la position donné par la technique de hachage employé...

Comme les techniques de haschage reposent sur une forme de calcul des éléments de composition des clefs à classer,
l'introduction de cet indice à pour effet d'éclater les espaces et donc diminuer les collisions...
Et surtout aménager des trous recevoir le résultat des collisions
Plus la chaine de la clef sera longue et donc la probabilité de calcul d'un même point plus rare, et plus l'indice pourra être faible.

Puis si collision => Écriture/lecture séquentielle... J'ai bien un code ou l'autre qui traine...
Mais je pense qu'il y en a plus sur le net ou sur le site US que dans ma tête... ou avant de le retrouver...

Lier à ce sujet:

Moi je suis sérieusement embêté par le fait de ne pas pouvoir ReDimensionner toutes les dimensions d'un tableaux...
Redim Chose(Var1, Var2, 10, Var3), les Varn étant de nouvelle valeurs... (PB= Seulement la dernière :( )

Car cela m'empêche de convertir mon "Indexé séquentiel" en PureBasic, qui en l'occurrence est largement plus performant que le Hash Code...

Qu'en dites vous ?
Anonyme

Message par Anonyme »

Mise en pratique , ca marche parfaitement.

a peu près 2300 entrées , 1 ms pour une recherche en moyenne :D

Code : Tout sélectionner

; NOTRE SUPERBE BASE DE DONNEES ::

Dim DB_Name$(50)
DB_Name$(0)="ABBEVILLE (d"+Chr(39)+") , ADDENIN , AILLY (d"+Chr(39)+") , AIMÉE , ALENÇON (d"+Chr(39)+") , ALEXANDRE , ALLAIN , ALLUISON , ALSACE (d"+Chr(39)+") , AMIENS (d"+Chr(39)+") , AMORY , ANJOU (d"+Chr(39)+") , ANNEQUIN (d"+Chr(39)+") , AQUITAINE (d"+Chr(39)+") , ARDRES (d"+Chr(39)+") , ARGENTON (d"+Chr(39)+") , ARGIES (d"+Chr(39)+") , ARLES (d"+Chr(39)+") , ARNAUD , ARRAULT , ASPREMONT (d"+Chr(39)+") , ASSIGNIES (d"+Chr(39)+") , ASSONLEVILLE (d"+Chr(39)+") , AUBIGNY (d"+Chr(39)+") , AUBOUARE , AUCHOEL (d"+Chr(39)+") , AUGENDRE , AUGER , AUGONNET , AUMALE (d"+Chr(39)+") , AUSTINE , AUVERGNE (d"+Chr(39)+") , AUXY (d"+Chr(39)+") , AVANTIGNY (d"+Chr(39)+") , AVERHOUST (d"+Chr(39)+") , AVESNES (d"+Chr(39)+") , AZINCOURT (d"+Chr(39)+")"
DB_Name$(1)="BACHELIER , BACQUEHEM (de) , BAES , BAILLEUL (de) , BAILLOT , BAILLY , BALLOT , BAR (de) , BARAT de LA HAYE , BARBANÇON (de) , BARBAT , BARBIER , BARCELONE (de) , BARDEAU , BARRAUT , BATHEREAU , BAUDART (de) , BAUDEMENT (de) , BAUGÉ (de) , BAUGENCY (de) , BAULIER , BAUX (de) , BEAUFREMEZ (de) , BEAUFREMONT , BEAUJEAN , BEAUJEU (de) , BEAUMONT (de) , BEAUPARISIS (de) , BEAUVAIS (de) , BECQUET , BELLAY , BELLEVAL (de) , BELLON(E) , BENARD , BÉRENGER (de) , BERGHES (de) , BERLAND , BERNARD , BERNÂTRE (de) , BERNICOURT (de) , BERRY , BERTIER , BERTIN , BERTRAND , BESANÇON , BESQUE , BÉTHENCOURT (de) , BÉTHUNE (de) , BEUGNET , BEUGNON , BEURIOT , BEUVRY (de) , BEZOU , BIENASSIS , BIENCOURT (de) , BIENQUE (de) , BILLEMONT (de) , BIRAGUE (de) , BLANCHARD , BLANCHER , BLANDY (de) , BLOIS (de) , BLONDEL , BOICHOT , BOILEAU , BOIS (du) , BOIS de HOVES (du) , BOISEAUX , BOISSARD , BOISSEAU , BOISVILLIERS (de) , BOMEZ (de) , BOMMEZ , BONARD , BONNAFAU (de) , BORDELET , BORDET , BOS (du) , BOSEVENT , BOUBERS (de) , BOUCHER , BOUDET , BOUDOU , BOULAT , BOULE , BOULLENCOURT (de) , BOURBON (de) , BOURBOURG (de) , BOURGEOIS , BOURGOGNE (de) , BOURGOIN , BOURNEL , BOURNONVILLE (de) , BOURRIS (de) , BOURSIN , BOUSSARD , BOUTERY , BOUVILLE (de) , BOYAVAL (de) , BRABANT (de) , BRAQUE , BRENETOT , BRESOT , BRETAGNE (de) , BRETEUIL (de) , BRIENNE (de) , BRIGNAC (de) , BRILLE , BRIQUOIS , BRISSIER , BRISSON , BRISTEL (de) , BROCELANCE (de) , BROSSARD , BROUTIN , BRULLOZ , BRUMARE , BRUNET , BUNEL"
DB_Name$(2)="CADET , CADY , CAILLAT , CALLEMENT , CALONNE (de) , CAMBRIN (de) , CAMBUZAT , CANCER (de) , CANDAVENE , CANIVET , CANTRELLE , CARINTHIE (de) , CARIOT , CARPENTIER , CARRE , CARRETTE , CARUE , CASSEL , CASSEMICHE , CASTELLOISE (de) , CASTILLE (de) , CATHELAIN , CATHEU (de) , CAUDRELIER , CAUMESNIL (de) , CERCUEIL , CERF (de) , CHALON (de) , CHAMPAGNE (de) , CHAMPIGNY (de) , CHANE , CHANTEREAU , CHANTOCÉ (de) , CHARDON , CHARENTON (de) , CHARLOT , CHARRIE , CHARTIER , CHASLOUP (de) , CHASSENNEAU , CHASTEL (du) , CHASTILLON (de) , CHÂTEAULANDON (de) , CHÂTEAUNEUF (de) , CHÂTELLERAULT (de) , CHATENET , CHAUMERON , CHAUMONT (de) , CHENERY (de) , CHENU (de) , CHERBUY , CHERISY (de) , CHERON , CHEVALIER , CHEVILLON , CHEVILLOT , CHEVRETTE , CHOPPIN , CHOUQUET , CHOURSES (de) ,CLAIRET , CLÉMANDORT , CLÉMENT , CLERMONT (de) , CLÉRY (de) , COLACHOT , COLBEAU , COLLAS , COLLET , COLOMBAT , COMMANVILLE , COMNÈNE , CONJEAUD , CONVERSAT , COQUIBUS , COQUILLE , CORDES (de) , CORICHON , CORNU , COSSON , COTARD , COTTENSIN , COTTREL (de) , COUCY (de) , COUDRET , COUPPIN , COURCELLE , COURGENOUL (de) , COURONNEL , COURROUX , COURTENAY (de) , COUTHRIER , CRAON (de) , CRÉCY (de) , CREPIN , CRÉQUY (de) , CRESPIN , CRESSON , CRESTE (de) , CREUZET , CROCHOT , CUINGEN (de) , CUNCHY (de) , CUSANI"
DB_Name$(3)="DABRIAS , DAIRE , DALLEMAGNE , DAMIENS , DAMOIS , DAMOISEAU , DAMPIERRE (de) , DAMPMARTIN (de) , DARLEY , DARLOT , DAUTHON , DAUVISSAT , DAVID de CONFLANS , DEBERNARD , DEBUIRE , DEFRANCE , DEGUION , DEGUY , DEHAY , DELACOUR , DELANOY , DELAPIERRE , DELAPORTE , DELAROQUE , DELATTRE , DELAVEAU , DELCROIX , DELHOMME , DELORME , DELVIGNE , DEMEAUX , DEMERY , DEMORY , DENIS , DEPAIR , DERANCOURT , DERCKEL , DERIENCOURT , DEROME , DERY , DERUY , DERVILLERS , DESBOEUFS , DESCAMPS , DESCHAINTRE , DESCLUZEAUX , DESCOURS , DESGRANGES , DESMOLINS , DESPONCHEAUX , DEVEAU , DEVILLE , DEY , DIZIER , DONJON (du) , DONZY (de) , DORE , DOUTREMEPUICH , DREUX (de) , DREVILLE ,  DUBUISSON , DUBUSC , DUCLOS , DUCROT , DUDOUT , DUGON , DUISYE , DUPAS , DUPONT , DUPUICH , DURAND , DURVILLE , DUVAL , DUVEAU"
DB_Name$(4)="ESCABILLON , ESCLAIBES (d"+Chr(39)+") , ESNE (d"+Chr(39)+") , EU (d"+Chr(39)+") , EVE , EVRAT , ÉVREUX (d"+Chr(39)+")"
DB_Name$(5)="FAUCONNIER , FAY (de) , FEVRE , FIENNES (de) , FILLEU , FIQUET , FLANDRES (de) , FLEURIGNY (de) , FLOS (du) , FONTAINE , FONTY , FORCALQUIER (de) , FOREST (de) , FOUCHER , FOUET , FOUILLAUX , FOUQUAY , FOURNEAU , FOURNIER , FOURREY , FOURSY , FRAMECOURT (de) , FRANCE (de) , FRANQUIN (de) , FREAUD , FRICAMPS (de) , FROMON , FUZIER"
DB_Name$(6)="GALBART , GALVEUX , GAMARD , GANNEAU , GAQUEREL , GARDIN (du) , GARES , GARLANDE (de) , GARNY , GAUCHER , GAUDRY , GAUGUIER , GAUTHERIN , GAYOT (de) , GEOFFROY , GERMAIN , GERMIGNY (de) , GHERQUIER , GHISTELLES (de) , GILARDIN , GIRAUDON , GISORS (de) , GOFFERT (de) , GOMMEGNIES (de) , GOMMETS (de) , GOMOT , GOUGEARD , GOURLOT , GOUY (du) , GRAÇAY (de) , GRANDPRÉ (de) , GRANDSIRE , GRANGE , GRARD , GRAVEREAU , GREBERT (de) , GRÉGOIRE , GRENET , GRIBOVAL (de) , GRIGNARD , GRILLOT , GRIMIER , GRIMOIN , GROSPRÉ (de) , GUELDRES (de) , GUENAND , GUENECH (de) , GUENIER , GUENIN , GUERCHY (de) , GUERREAU , GUESSET , GUICHARD , GUIDAMOUR , GUIDON , GUIDOU , GUILBERT , GUILLAUME , GUILLÉ , GUILLEMIN , GUILLEMOT , GUILLOT , GUINBERT , GUINES (de) , GUINIÈRE , GUINOT , GUISARME , GUISE (de)"
DB_Name$(7)="HABARCQ (de) , HABERT , HACK , HALLENGUES (de) , HALLWIN (de) , HAM (de) , HAMELIN , HANGEST (de) , HARCHIES (de) , HARCOURT (d"+Chr(39)+") , HARDENTHUN (de) , HARRY , HAVESKERQUE (de) , HAYNAUT (de) , HÉBUTERNE (de) , HEILLY (de) , HENAU (de) , HENRION , HENRY , HÉRAT , HERBET , HERGOT , HERMER , HERVIEUX , HESQUES (de) , HINGETTES (de) , HOLLANDE (de) , HOULIER , HUBERT , HUGOT , HUGUET , HUOT , HUQUEDIEU , HURE , HURET"
DB_Name$(8)="JACOB , JACQUET , JAMET , JANNETON , JANNIOT , JARCY , JASQUIER , JAUSSE (de) , JAY , JEANNEAU , JEANNIN , JOIGNY (de) , JOSSE , JOUSSOT , JULLY , JUMELLE (de)"
DB_Name$(9)="La BARRE (de) , La BROSSE (de) , La CAILLE (de) , La CHAPELLE (de) , LACHAUME , LA CROIX (de) , LA DEULLE (de) , LADMIRAL , LA FORGE (de) , LAINE , LALAING (de) , LAMARRE , LAMBERSAT (de) , LAMBLIN ,  LAMPOGNANI , LAMY , LANCHÈRES (de) , LANGHEMEERSCH (de) , LANIER , LANNOY (de) , LANTHIER , LA RIVIÈRE (de) , LA ROCHE (de) , LA ROCHE-DRONION (de) , LA ROCHEGUYON (de) , La ROSIÈRE (de) , LA ROUË (de) , LA SALLE (de) , La TRÉMOILLE (de) , LATROYE , LAUNAY (de) , LAURENT , LAURIN , LA VACQUERIE (de) , LAVAL (de) , LA VERNADE (de) , LE CARON , LE CAUCHIE (de) , LECERF , LE CHANGEUR , LECLAIR , LE CLEF , LECLERC , LECLERCQ , LE COEUR , LECOMTE , LE COURTOIS , LEDOUX , LE DROUAIS , LE FEBURE , LEFEBVRE , LE FEUTRE , LE FORT , LEGAGE , LEGAR , LEGAY , LEGRAND , LEGUEUX , Le JART , LEJEUNE , LEJONG , LELEU , LE MACHON , LEMAIRE , LE MERLE , LEMORT , LENFANT , LENFERNAT (de) , LENS (de) , LÉON (de) , LEPARGNEUX , LEROUX , LEROY , LE RUELLE (de) , LESAGE , LE SAULX (de) , LESAUVAGE , LESENNE , LESLEIN (de) , LESSOPIER , LESTRIOT , LE TELLIER , LETERME , LETOURNEAU , Le VASSEUR , LEVESIER , LEVESQUE , LEVIS (de) , LE VISEUX , L"+Chr(39)+"HOSPITAL (de) , LHOSTE , LIGER , LIORET , LISQUES (de) , LOISEAU , LOISELET , LONGUEVAL (de) , LONGVILLIERS (de) , LONNEL , L"+Chr(39)+"ORFÈVRE , LORRAINE (de) , LORRY (de) , LOURDEREAU ,  LOUTRE , LOUVAIN (de) , LOWEZ (de) , LUCAS , LUFORT , LUSIGNAN (de) , LUXEMBOURG (de) , LUYTON (du)"
DB_Name$(10)="MACHY de COCQUEREL (de) , MAGNY , MAHEUT , MAILLAULT , MAILLY (de) , MALICORNE , MALLET , MALVAULT , MANDION , MANIGOT , MANIVOIRE , MANOURY , MARCHAIS (des) , MARCHAND , MARCHEVILLE (de) , MARÉCHAL , MARTIN , MARTROIS (du) , MARY , MASSE , MASSIET (de) , MATHET , MATHIEU , MAUGRAS , MAUNOIR , MAUPETIT , MAY (de) , MEHUN (de) , MELLO (de) , MELUN (de) , MÉRANIE (de) , MERAT , MERLE , MESTIVIER , MEULLENT (de) , MEZ (du) , MICHAUD , MIGNARD , MIGUET , MILLY (de) , MINE , MIZIER , MOCQUOT , MOIREAU , MOISETTE , MOLEMBAIS (de) , MOLIENS (de) , MONCHY (de) , MONTBELLIARD (de) , MONTDIDIER (de) , MONTFAUCON (de) , MONTFERRAT (de) , MONTFORT (de) , MONTHOMER (de) , MONTIGNY (de) , MONTJAY (de) , MONTLHÉRY (de) , MONTMORENCY (de) , MOREAU , MOREL , MOREUIL (de) , MORILLON , MORIN , MOTHERE , MOUCY (de) , MOULIN (du) , MOUTON , MOVEN (de) , MULLER"
DB_Name$(11)="NAMUR (de) , NANGIS (de) , NANTEUIL (de) , NASLOS , NAUDET , NAULIN , NÉDONCHEL (de) , NEEL , NEMOURS (de) , NESLE (de) , NEUFMEZ (de) , NEUVILLE (de) , NEVERS , NIELLES (de) , NOËL , NOEUX (de) , NORMANDIE (de)"
DB_Name$(12)="OCCRE , OISELAY (d"+Chr(39)+") , OLHAIN (d"+Chr(39)+") , OPPENOT , OSTREL (d"+Chr(39)+") , OSTRICQUE (d"+Chr(39)+") , OUDIN , OUTRELEAU (d"+Chr(39)+")"
DB_Name$(13)="PACY (de) , PAISAN , PAMPELUNE (de) , PAQUIER , PARIS (de) , PARMENTIER , PARTY , PASQUEAU , PASQUERON , PATE , PAULVE , PAVIAULT , PÉCHENOT , PENEL , PÉROT , PERRIGNON , PERRIGOT , PERRIN , PERROCHE , PERTAT , PERTHUIS (du) , PESCHEUX , PETIT , PETITJEAN , PETITPAS , PEZÉ , PHILIPPON , PICARD , PICQUIGNY (de) , PIENNES (de) , PINAUD , PINET , PINGOT , PLESSIS (du) , PLUSQUELLEC (de) , POINLANE , POINTEAU , POIRIÉ , POISSON , POITIERS (de) , POIX (de) , POLLE , POLLET , POLLIARD (de) , PONTHIEU (de) , PONTROHART (de) , PORCHEROT , POTHERAT , POUILLAUDE , POULAIN , POUPET , POURCHOT , PRÉAULX (de) , PRETZ (des) , PRÉVOST , PROCHASSON , PROTARD , PROU , PRUVOST , QUAROUBLE (de) , QUESNEL , QUESNES (des) , QUESNOY (du) , QUINQUET (de) , QUIRAULT"
DB_Name$(14)="RANCON (de) , RAPIN , RASOIR , RATILLON , RAULIN , RAVAULT , RAYNEVAL (de) , REGNARD , REGNAULT ,  RELY (de) , RENARD , RENOUX , RENVOYÉ , RETHEL (de) , RICAMETZ (de) , RIGOUT , RIMBERT , RIVELOIS , RIVERSE (de) , ROBERT , ROBIN , ROBINET , ROBLOT , ROCHEFORT (de) , ROEULX (du) , ROGER , ROLLAINCOURT (de) , RONNELLE , ROSE , ROSMADEC (de) , ROTY , ROUCY (de) , ROUHY (de) , ROULLIER , ROUSSEAU , ROUSSEL , ROUSSELET , ROUSSET , ROY , ROYE (de) , ROYER , RUETTE , RUSSIE (de) "
DB_Name$(15)="SABRAN (de) , SACQUESPÉE (de) , SAILLY (de) , SAINT-BLIMOND (de) , SAINT-ESPRIT (de) , SAINT-GEORGES , SAINT-OMER (de) , SAINT-PAUL (de) , SAINT-VALERY (de) , SAINT-VENANT (de) , SAINT-VÉRAIN (de) , SAINVILLE , SALIN , SALLEY , SANCERRE (de) , SARS (de) , SART (du) , SAUSSERON , SAVARY , SAVERY , SAVOIE (de) , SAXE (de) , SECHELLES (de) , SEGUIN , SEGUINOT , SENESTRE , SEURAT , SIMON , SODADE , SOICHET (du) , SOISSONS (de) , SOMAING (de) , SOUABE (de) , SOUDÉ , SOUGER , SOULHAC (de) , SOYER , SPINOLA , STAVELE (de) , STEUER , SULLY (de)"
DB_Name$(16)="TARTINVILLE , TELLIER , TÉNEVEAU , TENIERE , TENREMONDE (de) , TESSEL , TESTAT , THIEMBRONNE (de) , THIENNES (de) , THIERN (de) , THIERRY , THIES , THIEURY , THIMONIER , THOMAS , THOROTE (de) , THUILLIER , THUREAU , TILLOU ,  TILLOY , TINGRY (de) , TONNERRE (de) , TOUCY (de) , TOULOUSE (de) ,  TOURMIGNIES (de) , TRANCHELION (de) , TRASIGNIES (de) , TRAVES (de) , TRECY , TREMBLAY (de) , TRESSAULT , TRIBAUDAUT , TRIE (de) , TRIVULCE , TROILLARD , TRUCHY , TUPINIER , TURENNE (de) , TURQUIS , TYREL"
DB_Name$(17)="VAAST , VARENTE , VASSE , VAUDEMONT (de) , VAUDRICOURT (de) , VEAU , VENDEUIL (de) , VENDÔME (de) , VENIZY (de) , VERGNON , VERMANDOIS (de) , VERMEILLES (de) , VÉRON , VERROLOT , VIANDEN (de) , VIAULT , VIEILLARD , VIENNE (de) , VIENNOIS (de) , VIGREUX , VILLAIN , VILLARD , VILLE (de) , VILLEBÉON (de) , VILLEHARDOUIN (de) , VILTARD , VINCENT , VINÇON , VINOT , VIR (de) , VITRÉ (de) , VITUROT , VOUHEC (de) , VOYSINES (de) , WALLINS , WANDRINGHEM (de) , WARGNY (de) , WAVRANS (de) , WAVRIN (de) , XAVIER , YGER , YPRES (d"+Chr(39)+") , YSSELSTEIN (d"+Chr(39)+")"
DB_Name$(18)="ABRAHAM, ACHON, ADAM, AIDE-CRÉQUY, ALAIN, ALAIRE, ALARD, ALBOEUF, ALLAIN, ALLAIRE, ALLARD, AMIOT, ANDREVILLE, ANGUILLE, ANNEVILLE, ANSQUER, ANTHONY, ARCHAMBAULT, ARDOUIN, ARNAUD, ARNOULT, ARRIVÉ, ARSENEAU, ARTAUT, AUBÉ, AUBERT, AUBIN, AUBINEAU, AUCÉAUME, AUCLAIR, AUCLER, AUDET, AUDIGOU, AUFFRET, AUFRET, AUFROY, AUGEARDE, AUGER, AUREGAN, AUSTIN, AUVRAY, AVISSE, AYMARD, AYMART, AYOTTE"
DB_Name$(19)="BABIN, BACHAND, BACHELOT, BACON, BADEAU, BAILLARGEON, BAILLY, BALAN, BANQUET, BANVILLE, BARABÉ, BARAULT, BARBEAU, BARBOT, BARDIN, BARDON, BARETTE, BARIL, BARITEAU, BARON, BARRE, BARRETTE, BARY, BASTIEN, BAUDAIN, BAUDET, BAUDONNIER, BAUGUET, BEAUDOIN, BEAUHARNOIS, BEAULIEU, BEAUMONT, BEAUPRÉ, BEAUVILLAIN, BÉDARD, BÉGIN, BÉLANGER, BELIN, BELLANGER, BELLEAU, BELLEHACHE, BELLEJAMBE, BELLEVILLE, BELZIL, BÉNARD, BENOIT, BÉRARD, BERDELOU, BEREZAY, BERGERON, BERGEVIN, BERNAQUEZ, BERNARD, BERSEVOYSE, BERTRAND, BESNARD, BEZEAU, BIBEAU, BIDÉGARÉ, BIDET, BIETTRY, BIGOT, BINAUDIÈRE, BINEAU, BIRÉ, BIRET, BIRRA, BISSONNET, BITOUSET, BIVILLE, BIZIEN, BLAIS, BLANCHARD, BLANCHE, BLANCHET, BLANCHETTE, BLANCHON, BLANQUET, BLAY, BLONDEAU, BLOUARD, BOBET, BOCHER, BODELEAU, BOESLO, BOGUELIER, BOIGEON, BOILEAU, BOILLEROT, BOILY, BOISSELLE, BOISVERT, BOIVIN, BOLDIEU, BOLDUC, BOLPER, BONHOMME, BONNARD, BONNET, BORDUAS, BOSCHÉ, BOSSÉ, BOTCAZO, BOTCAZOU, BOTRIC, BOUCHARD, BOUCHART, BOUCHER, BOUCHEROT, BOUDEMER, BOUFARD, BOULANGER, BOULAY, BOULET, BOUNILOT, BOURASSA, BOURBEAU, BOURDELLE, BOURDON, BOURÉ, BOUREL, BOURGEOIS, BOURRET, BOUTEILLET, BOUTET, BOUTIN, BOUVIER, BRANCHE, BRAS, BRASSARD, BRETON, BRIAS, BRIDAULT, BRIÈRE, BRIGANT, BRIOLET, BRISSON, BROCHU, BROSSEAU, BROUILLARD, BROUSSEAU, BRUNEL, BRUNELLE, BUREL, BUSENESTRE"
DB_Name$(20)="CABON, CADIEU, CADOT, CAER, CALLAREC, CAM, CAMPAGNA, CAMPEAU, CAMPION, CANTIN, CANTON, CARBONNET, CARET, CARIS, CARLUER, CARON, CARRÉ, CARREAU, CARRIÈRE, CARTIER, CARTIGNIER, CARUEL, CAUCHON, CAUCHY, CAUSSADE, CAYER, CAZEAU, CAZOULAT, CHABOT, CHAÎNÉ, CHALIFOU, CHALIFOUR, CHALINE, CHALLE, CHAMPAGNE, CHAMPOUX, CHANSON, CHANTAL, CHAPEAU, CHAPELAIN, CHAPELIER, CHARLES, CHARLOT, CHARPENTIER, CHARRON, CHARTIER, CHARTRÉ, CHASTEL, CHAUVEL, CHAUVIN, CHAVERLANGE, CHAYÉ, CHAYER, CHEVALIER, CHEVALLEREAU, CHORET, CHOUART, CHRÉTIEN, CILLARD, CILLART, CILLART SILLERT, CIMON, CLASTRO, CLECH, CLEMENS, CLÉMENT, CLOAREC, CLOAREC LeCLERC, CLOS, CLOUTIER, COADALEN, COANT, COATANMANACH, COATAREL, COCHON, COCHU, COCQUIN, COEUR, COINTEREL, COIRIER, COJAN, COLCANAP, COLINET, COLLÉTER, COLLIN, CONAN, CONGNET, CONILLE, CONSTANCINEAU, CONTANT, CONVENT, CONWAY, COQUART, COR, CORDELETTE, CORIOU, CORMONT, CORNIÈRE, COROLLO, COROLLOU, CORRE, CORRIVEAU, CORVE, COSSETTE, COSTÉ, CÔTÉ, COTEL, CÔTES, COTTEL, COTTY, COUDRAY, COUILLARD, COURIER, COURTEMANCHE, COUSIN, COUSTURE, COUTARD, COUTAULT, COUTURE, COUTURIER, COUVENT, COZ, CRAIG, CRAMPON, CRAS, CRECEVEUR, CRENEL, CRÉPEAU, CRESTE, CRÈTE, CRÊTE, CRÈTE, CRETIEN, CROCQ, CROISET, CROM, CROTEAU, CROUSETTE, CRUGEON, CUDENEC, CUDENNEC"
DB_Name$(21)="DAGNET, DAIGLE, DALLAIRE, DAMIZÉ, DANCAUSE, DANIAU, DANIEL, DANOS, DAOULAS, DAVENNE, DAVID, DAVIGNON, DE BAUBISE, de COATANZAL JEZEQUEL, DE LA HAYE, DE LACOUR, DE LAVOYE, DEBIEN, DEBRIE, DECHAUX, DECHOS, DECOZE, DEFOY, DEGRÉS, DEGUISE, DELAUNAY, DELAVOYE, DELCOURT, DELISLE, DELONGVAL, DELUGRÉ, DEMAN, DEMERS, DENÉ, DENEAULT, DENIS, DENYS, DeRAASP, DERAINVILLE, DERLOT, DERRIEN, DERROT, DÉRY, DESCHALETS, DESCHALLOUX, DESCHAMPS, DESFOSSÉS, DESHAIES, DESHAYES, DÉSILETS, DESMARETS, DESPORTES, DESPRÉS, DESROCHES, DESRY, DES_GRANGES, DEVOISSY, DÉZIEL, DE_BIEN, DE_GUISE, DE_LA_HAYE, DE_LA_MARE, DE_LA_PRÉE, DE_LA_RUE, DE_LA_VOYE, DE_LISLE, DE_LOMELLE, DIGNARD, DION, DIONNE, DODIER, DOIGT, DORBELLE, DORÉ, DORIBELLE, DORION, DORVAL, DOUCINET, DOUVILLE, DOYLE, DOYON, DRAPEAU, DRAPON, DRILLARD, DROLET, DRONIOU, DROUIN, DRUGEON, DUBASQUES, DUBAU, DUBÉ, DUBOIS, DUBREUIL, DUBRIOT, DUBUC, DUCAS, DUCHESNE, DUCQ, DUFOUR, DUFRENÇOYS, DUFRESNE, DUGAST, DUGUAY, DUHAULT, DUMAS, DUMAY, DUMETS, DUMONT, DUPONT, DUPRAC, DUPRAT, DUPUIS, DURAND, DUSSAULT, DUTEAU, DUTERTRE, DUTREMBLE, DUVAL, DU_VEAU"
DB_Name$(22)="ÉLIE, EMARD, ESNEAU, ESPINON, EUFFLAM, ÉVRARD"
DB_Name$(23)="FAFART, FAIGNOU, FALARDEAU, FANUEL, FASCHE, FAUCONNIER, FAUMOLEAU, FAUTIEN, FAVEUR, FAYEL, FAYETTE, FEBVRIER, FEGEAN, FEREC, FERLAND, FERMERY, FESTOU, FEUILLART, FIJEAN, FILION, FIOT, FISET, FLEURY, FONTAINE, FORBAN, FORGET, FORGUES, FORSAN, FORTIER, FORTIN, FORZIC, FOURESTIER, FOURNIER, FOURREAU, FOVIER, FOYE, FRANÇOIS, FRASER, FRÉCHET, FRÉCHETTE, FRÉDÉRICK, FREDETTE, FRÉROT, FRESSET"
DB_Name$(24)="GABORAULT, GABOURI, GADOIS, GAGNÉ, GAGNESSE, GAGNON, GAIGNEUX, GAILLARD, GALAYS, GALLET, GAMACHE, GAMBIER, GARCEAU, GAREMAN, GARGOTTINE, GARION, GARNAUD, GARNAUT, GARNEAU, GARNIER, GASCHET, GASNIER, GAUDIN, GAUDREAU, GAUDREAULT, GAUDRY, GAUGÉ, GAULIN, GAULTIER, GAUTHIER, GAUTIER, GAUVREAU, GAYON, GEFFROY, GENEST, GENOIS, GERMAIN, GERVAIS, GIBOU, GIGUÈRE, GILBERT, GINGRAS, GINGREAU, GIRARD, GIRAULT, GIRAUX, GITON, GLINEL, GLOT, GOAS, GOAZ, GOBEIL, GOBERON, GODBOUT, GODEFROY, GODEQUIN, GODIN, GOFFIC, GOLLE, GONGEAUTÉ, GONTHIER, GORON, GORRIC, GOSRÉ, GOSSELIN, GOUDEAU, GOUJET, GOULET, GOURBREIN, GOURHANT, GOUZIEN, GRALL, GRAND, GRANDIN, GRATON, GRAVEL, GRAVELLE, GRAVET, GRÉGOIRE, GRENIER, GRENON, GRESLON, GRESSU, GRIGNON, GRIMOT, GRIMOULT, GRINON, GRISOT, GROMELIN, GRONDIN, GUAY, GUÉ, GUEGUEN, GUELTAS, GUENEGAN, GUÉNET, GUENNEC, GUÉRIC, GUÉRIN, GUERNIGOU, GUÉRY, GUEZENEC, GUEZENNEC, GUIASTRENNEC, GUIBORD, GUICHAUT, GUICHEBARON, GUICHEBAROU, GUILBAULT, GUILBAUT, GUILBEAU, GUILBEAULT, GUILLARM, GUILLEBOURG, GUILLEBOUT, GUILLEMETTE, GUILLEMIN, GUILLIN, GUILLOCHEAU, GUILLOIS, GUILLOT, GUILLOU, GUILLOUX, GUIMOND, GUIMONT, GUION, GUYOMAR, GUYON"
DB_Name$(25)="HALAY, HAMEL, HAMELIN, HAMEURY, HAMON, HARACE, HAYET-RADISSON, HAYOT, HÉBERT, HÉLIE, HELO, HENEQUIN, HENRI, HENRY, HÉRAULT, HERLAYS, HÉROUX, HERSON, HERVÉ, HILAREST, HIOUT, HIR LeLONG, HIRT, HONDÉARD, HONG, HOUART, HOUDE, HUART, HUBERT, HUBOUST, HUDDE, HUDDES, HUDON, HUET, HUGUET, HUNETTE, HUON, HUOT, HUPÉ, HURDOUIL, HUREAU"
DB_Name$(26)="INCONNU, ISABEAU"
DB_Name$(27)="JACOB, JACQUET, JALADON, JALLOT, JAOUEN, JAOUEN JANNEN, JAROUSSEL, JEAN, JEGOU, JEHAN, JÉRÉMIE, JEZEQUEL, JOANNET, JOBIN, JOHNSTON, JOINAULT, JOLICOEUR, JOLIN, JOLY, JOSSET, JOUAN, JOUANNE, JOUINEAU, JOUY, JULIEN, JUNEAU, JUSTE"
DB_Name$(28)="KANE, KELLY, KERBORIOU, KERIRFIN, KERLAN, KERMAIDIC, KERVREN, KIROUAC, KOHLHAGEN"
DB_Name$(29)="LABARBE, LABERGE, LABRECQUE, LABRIE, LACHANCE, LACHIVER, LACOMBE, LACOURSE, LACROIX, LADMIRANT, LAFFETER, LAFLAMME, LAFLEUR, LAFOREST, LAGEAT, LAHELLEC, LAIRET, LAISNÉ, LALIBERTÉ, LAMAIN, LAMBERT, LAMERI, LAMOUREUX, LANCIAR, LANCIEN, LANCTOT, LANDRY, LANGEVIN, LANGLOIS, LAPERRIÈRE, LAPOINTE, LAPÔTRE, LAPRADE, LARCHER, LARCHEVÊQUE, LARIVIÈRE, LAROUCHE, LARUE, LASCORNET, LATOUR, LAUNAY, LAUREGAN, LAURION, LAUZON, LAVER DURE, LAVOIE, LAVOYE, LAVYE, LA_BRECQUE, LA_ROUSSIÈRE, Le ?, LE GRAND, LE ROUGE, LeBAIL, LeBAILL, LeBALAN, LeBARBIER, LeBARS, LeBATARD, LeBEAUDOUR, LeBELLEC, LeBERGUEILLEC, LEBEUF, LeBIDEAU, LeBIHAN, LeBILLON, LEBLANC, LeBORGNE, LeBOT, LeBOUDER, LeBOUGEANT, LeBOURCHIS, LeBOURDONNEC, LeBOURVA, LeBOZEC, LeBRANNELEC, LeBRAS, LEBRET, LeBRETON, LeBRIGANT, LeBRIS, LeBUHANEC, LeCALVEZ, LeCAM, LeCAZOULAT, LeCHAPELAIN, LECHEF, LeCIVILLON, LECLAIR, LeCLECH, LeCLEI, LECLERC, LeCOAT, LeCOCQ, LECOMBE, LeCOQ, LeCORRE, LeCORVE, LeCOULS, LeCOZ, LeCUZIAT, LEDAN, LeDANNOT, LeDANTEC, LeDEIST, LEDESLIÉ, LEDET, LeDILASSER, LeDIOURIS, LeDISEZ, LeDOARÉ, LeDOCHAER, LeDOCHER, LEDOUX, LeDRET, LEDUC, LeFAOU, LeFAOUR, LEFEBVRE, LeFLAMANC, LeFLAMMANC, LeFLOCH, LeFOLL, LeFOURNIS, LEFRANÇOIS, LeFUSTEC, LeGALL, LeGALLOU, LeGAOUIER, LÉGARÉ, LeGARS, LeGENNEC, LÉGER, LeGERRON, LeGIOLLOU, LeGLORION, LeGOARCON, LeGOAREGUER, LeGOAS, LeGOFF, LeGOFFIC, LeGORREC, LeGOUIER, LEGRAND, LeGRIS, LeGUEN, LeGUENNEC, LeGUERN, LeGUEZ, LeGUILLOU, LeGUILLOUX, LeGUIVEN, LeGUYADER, LEHOUX, LeJAOUA, LeJEUNE, LeJOSEPH, LELABOUREUR, LeLAGADEC, LeLAN, LeLANNOU, LeLAY, LeLEVRON, LELIÈVRE, LÉLIOT, LeLIRZIN, LeLOUEDEC, LeMADEC, LeMAGUET, LeMAHÉ, LEMAISTRE, LeMANACH, LeMAO, LEMARCHÉ, LEMARIÉ, LEMARINIER, LeMARREC, LeMARRER, LEMAY, LEMEILLEUR, LEMELIN, LEMERCIER, LeMERER, LEMESLE, LeMEUR, LEMIEUX, LeMINEC, LEMIRE, LeMOAL, LeMOINE, LeMORELLEC, LeMORTELLEC, LeMORVAN, LeMOULLEC, LEMOYNE, LENORMAND, LEON, LEPAGE, LePENKAER, LePENVEN, LePERU, LÉPINE, LePLANTEC, LePONTHO, LePROVOST, LeQUELLEC, LeQUERE, LEQUINT, LeRAY, LEREAU, LeREGUER, LeREGUERE, LeREMEUR, LEROUGE, LeROUX, LeROY, LeRUMEUR, LESAGE, LeSAUX, LESCALIER, LeSEVERE, LESIDANER, LESIEUR, LESOT, LESPAGNOL, LESQUEVEN, LESSARD, LeTaillandier, LeTANEAU, LETARTE, LETARTRE, LETELLIER, LÉTOURNEAU, LeTURLUER, LEVASSEUR, LÉVEILLÉ, LEVERDIER, LEVERT, LeVINCENT, LeVOT, LE_CHEVALIER, LE_COCQ, LE_DOUX, LE_GARDEUR, LE_MAÎTRE, LE_PARMENTIER, LE_TARDIF, LE_TELLIER, LE_VASSEUR, LHENORET, LHÉRAULT, LHEREAU, LHEUREUX, LHOSTIE, LHOSTIS, LHUET, LINTANF, LINTAULT, LINTEAU, LIRETTE, LOIGNON, LOPES, LORD, LORIENTE, LORIOU, LOUSCHE, LOUVAIS, LOYSEAU, LOYSEL, LOZACH, LOZEACH, LUCAS"
DB_Name$(30)="MACARD, MACART, MACÉ, MADIGOU, MAGNAN, MAGNON, MAGUET, MAHE, MAHEU, MAHEUST, MAILLOU, MAILLOUX, MAINFRAI, MAINGUY, MALET, MALIER, MALLEDANT, MALLEVAULT, MALO, MANACH, MAOUT, MARAUD, MARCEAU, MARCHADOUR, MARCHAND, MARCOTTE, MARETTE, MARGES, MARIÉ, MARION, MAROIS, MAROIST, MARQUIS, MARTEL, MARTIN, MARTINEAU, MARZIN, MASSE, MATHIEU, MATTE, MAUFAIT, MAUGÉ, MAUGER, MAUGIS, MAZOUÉ, McKEE, McNICOLL, MELAINE, MÉLIOT, MENDOSE, MENGUY, MENOU, MERAND, MERCER, MERCIER, MERIADEC, MÉRY, MESNAGE, MÉTAYER, METEYÉ, MÉTHOT, MEUNIER, MEURIC, MEZERAY, MÉZERÉ, MICHEL, MICHELET, MIGNIER, MILHOMME, MILLEHOMME, MILLET, MILLOUER, MILOT, MINEC, MINGUY, MINOUS, MINOUX, MIRVAL, MIVILLE, MODIOU, MOISAN, MOLEUR, MONCION, MONERON, MONFORT, MONIN, MONNACHAU, MONNIER, MONTENU, MONTIGNY, MORAN, MORAND, MOREAU, MOREL, MORIN, MORINEAU, MORISSET, MOUILLARD, MOUZER, MOV"
DB_Name$(31)="NADEAU, NAINTEAU, NAOULET, NAUD, NAVARRE, NAVER S, NÉDÉLEC, NEPVEU, NÉRON, NIARD, NICOL, nicolas, NIEMI, NINTEAU, NOÉ, NOËL, NOLIN, NORMAND, NYEULLÉ"
DB_Name$(32)="OFFRET, OLIVIER, OLLIVIER, OMELET, OMNES, OUELLET, OUINVILLE, OURLAY, OUVRARD"
DB_Name$(33)="PAGÉ, PAGEAU, PAIN, PAJOT, PANNETON, PAQUET, PAQUIN, PARADIS, PARANT, PARÉ, PARENT, PARIS, PARLICOT, PASQUIER, PATOINE, PAUL, PAULET, PAULLET, PAULO, PEACHY, PELCHAT, PELETER, PÉLISSON, PELLAND, PELLETIER, PELTIER, PENE, PENEAU, PENQUER, PÉPIN, PERF, PÉRINNE, PERJADEC, PEROL, PERON, PEROT, PERRET, PERRIN, PERRON, PERROT, PERSON, PESCHEVINET, PETIT, PETITCLERC, PETITPAS, PEZRON, PHILIPPAUX, PHILIPPE, PHILIPPEAU, PICHÉ, PICHERON, PICHODO, PICHODOU, PICHON, PICHOURON, PICON, PIERES, PIGNON, PIJART, PILON, PILOTE, PILOTTE, PINAU, PINEAU, PINEL, PINET, PINGUET, PITAU, PIVAIN, PIVETEAU, PLAMONDON, POÊTE, POILEU, POIRIER, POISSON, POITIERS, POITRAS, POLET, POSÉ, POTVIN, POUGNYE, POUILLOT, POUIZE, POULAIN, POULIN, POULIOT, POUSSARDE, POUVREAU, PRÉVIRAULT, PRÉVOST, PRIGENT, PROTEAU, PROU, PROULX, PROVOST, PRUAL"
DB_Name$(34)="QUEHEREC, QUEHERREC, QUEINNEC, QUEMENER, QUENNEC, QUENTIN, QUERE, QUEREC, QUERRE, QUESCEVER, QUIGUER, QUINIOU"
DB_Name$(35)="RACINE, RAICHE, RAINVILLE, RANNO, RATÉ, RATEL, RATTÉ, RAVIOT, REED, REGNEAULT, REGOURDE, REMONDIÈRE, RENARD, RENAUD, RENAUDIN, RENAULT, RENNON, RENON, RICARD, RICE, RICHARD, RICHER, RIOPEL, RIOU, RIOUX, RIVAUT, RIVET, RIVIÈRE, RIVOAL, RIVOALEN, ROBERTSON, ROBIN, ROBITAILLE, ROCHE, ROCHERON, ROCHETTE, ROCHON, ROGER, ROGNON, ROÏC, ROLAND, ROLLAND, ROLLET, ROLLIN, RONDEAU, ROPARS, ROUDOT, ROUILLARD, ROULOIS, ROUSSE, ROUSSEAU, ROUSSEL, ROUSSIN, ROUTIER, ROY, RUBEUS, RUEL, RUET, RUTAUT"
DB_Name$(36)="SAILLANT, SAINT-LÔ, SALIOU, SALLIOU, SAMOSION, SANFAÇON, SANSCARTIER, SARAZIN, SAUMUR, SAUVIN, SAVARD, SAVONET, SCALZO, SCLOUV, SCRIGNAC, SÉBASTIEN, SÉDILOT, SÉGUIN, SELLIER, SENAT, SÉNÉCAL, SÉNÉCHAL, SENLER, SERRE, SEVESTRE, SÉVIGNY, SICARD, SIMARD, SIMON, SIMONEAU, SINDECO, SINOTTE, SIOUI, SLOANE, SORGEAU, SOSEAUX, SOULANGE, SOULARD, SOUMANDE, SQUIN, ST-AMAND, ST-JEAN, ST-LOUIS, STEEN, SUIRE, SURGET"
DB_Name$(37)="T..., TALBO, TALBOT, TALONNEAU, TANCRÈDE, TANGUI, TANGUY, TANO, TARDIF, TARRÉ, TAUPIER, TAVERNIER, TESSIER, TESSIER ou TEXIER ou ÉRINGUÉ, TESTU, TEURNIER, TEXIER, THÉBERGE, THEPOT, THIBAULT, THIBEAULT, THOMAS, THORY, THOS, TINION, TINON, TISEDRES, TOCQUE, TOCQUER, ToËNEN, TONART, TOUCHERAINE, TOUCHETELLE, TOUDIC, TOUPIN, TOURAUDE, TOUREAU, TOUTAIN, TREMBLAY, TREMEL, TRÉPAGNY, TRÉPANIER, TRIOT, TRUDEL, TRUDELLE, TUDAL, TURGEON, TUTOR, TYSDEL"
DB_Name$(38)="VACHON, VADOIS, VAINE, VALLÉE, VALLET, VALLIÈRES, VANASSE, VANDAL, VANNIER, VARIN, VATEAU, VAVASSEUR, VEDIÉ, VEILLETTE, VEILLON, VENET, VERDON, VÉRON-GRND-MÉNIL, VERRET, VERRIER, VÉSINA, VÉZINA, VIEILLOT, VIENS, VIETTE, VIGNEAU, VIGNEAUX, VILLEDAY, VILLENEUVE, VINCENT, VIVAIS, VIVIER, VOIDY, VOYER"
DB_Name$(39)="WEBSTER, WERMUTH, WOLFE"


; GENERATION D'ADRESSE BIDON

Procedure$ GenerationAdresseBidon()


Number = 1+Random(1024)
adresse$ = Str(Number)+ " "

Select Random(4)
	Case 0: adresse$ + "impasse "
	Case 1: adresse$ + "rue "
	Case 2: adresse$ + "boulevard "
	Case 3: adresse$ + "chemin "
	Case 4: adresse$ + "allée "
EndSelect

Select Random(16)
	Case 0: adresse$ + "de la république"
	Case 1: adresse$ + "Anatole France"
	Case 2: adresse$ + "Fréderic Laboureur"
	Case 3: adresse$ + "de strasbourg"
	Case 4: adresse$ + "de paris"
	Case 5: adresse$ + "de cavée verte"
	Case 6: adresse$ + "de l'Amiral Mouchez"
	Case 7: adresse$ + "du Général de gaule"
	Case 8: adresse$ + "de Jacque Chirac"
	Case 9: adresse$ + "de Nicolas Sarkozy"
 Case 10: adresse$ + "de Barack Obama"
 Case 11: adresse$ + "des paons"
 Case 12: adresse$ + "des peupliers"
 Case 13: adresse$ + "du temple"
 Case 14: adresse$ + "André messager"
 Case 15: adresse$ + "de la gare"
 Case 16: adresse$ + "Jean Maridor"
EndSelect

ProcedureReturn adresse$
EndProcedure


Procedure$ GenerationTelephoneBidon()

A$ = "0"+Str(Random(5)+1)
B$ = LSet(Str(Random(99)),2,"0")
C$ = LSet(Str(Random(99)),2,"0")
D$ = LSet(Str(Random(99)),2,"0")
E$ = LSet(Str(Random(99)),2,"0")

ProcedureReturn A$+"."+B$+"."+C$+"."+D$+"."+E$
EndProcedure

; FONCTION DE HACHAGE
;@author Daniel J. Bernstein
Procedure.i hash(string.s)
   hash.i = 5381
   char.c = #Null
   index.i= 0
      
   While index <> Len(String)
      char = PeekC(@string+index)
      hash + ((hash<<5) + hash) + char
      index+1
   Wend
   
   ProcedureReturn hash & $FFFFFF
EndProcedure




; Structure des clients :
Structure MesClients
	Name$
	Adresse$
	Tel$
	PositionInGadget.i
	HashKey.i
EndStructure



Global Dim MaClientele.MesClients(1<<24)
Global Col=0
Global dta$
Procedure addstring(Hash,string.s)


 If Len(MaClientele(Hash)\Name$)>0 
   dta$ + "collision entre " + string +" & "+MaClientele(Hash)\Name$+" " + Str(Hash) 
 Col+1 
 EndIf 
 
 
 MaClientele(Hash)\HashKey = Hash
 MaClientele(Hash)\Name$   = string
EndProcedure


Declare SearchByName(name$)

OpenWindow(0,0,0,640,480,"CLIENTELE")

ListIconGadget(0,10,10,620,380,"Nom du client",150)
AddGadgetColumn(0,1,"Adresse",300)
AddGadgetColumn(0,2,"Téléphone",620-450)
AddGadgetColumn(0,3,"Name Hash Key",620-450)
TextGadget(1,10,390,160,30,"")

StringGadget(2, 10, 420, 200, 30 ,"")
ButtonGadget(3,220,420,120,30,"Search")



n=1

; Mise en place dans le tableau :
 For i = 0 To 39
	Line$ = DB_Name$(i)
		For j = 1 To CountString(Line$,",")+1
			Name$ = Trim(StringField(Line$,j,","))
			HashKey = Hash(Name$)
			addstring(HashKey,Name$)
			MaClientele(hashKey)\Adresse$ = GenerationAdresseBidon()
			MaClientele(hashKey)\Tel$     = GenerationTelephoneBidon()
			MaClientele(hashKey)\PositionInGadget = n
	 
			AddGadgetItem(0,-1,Name$+Chr(10)+MaClientele(hashKey)\Adresse$+Chr(10)+MaClientele(hashKey)\Tel$+Chr(10)+Str(HashKey))			

			n+1
		Next 
 Next 

SetGadgetText(1,Str(n)+" nombres d'entrées")




;SearchByName("ROBIN")



Repeat
	event = WindowEvent()

		If event = #PB_Event_Gadget 
			gid = EventGadget()
			
			
			If gid=3
			SearchByName(GetGadgetText(2))
			EndIf 
			
		EndIf 
		


Until event = #PB_Event_CloseWindow






; Fonction de recherche par le nom :

Procedure SearchByName(name$)


TimeA = ElapsedMilliseconds()

HashSearch.i = hash(name$)
If MaClientele(HashSearch)\Name$ = name$
		CompilerIf #PB_Compiler_OS = #PB_OS_Windows
        SendMessage_(GadgetID(0), #LVM_ENSUREVISIBLE, MaClientele(HashSearch)\PositionInGadget-1, 0)
    CompilerElse 
				SetGadgetState(0,MaClientele(HashSearch)\PositionInGadget-1)
		CompilerEndIf
EndIf 


TimeB = ElapsedMilliseconds()


MessageRequester("Search value : ",Str(TimeB-TimeA))

EndProcedure
Guimauve
Messages : 1015
Inscription : mer. 11/févr./2004 0:32
Localisation : Québec, Canada

Message par Guimauve »

Bonjour à tous,

Si vos données sont triées par ordre alphabétique une fouille dichotomique est d'une rapidité extrême. Voici le principe de fonctionnement :
Fouille dichotomique et linéaire

La fouille dichotomique est plus rapide que la fouille linéaire. Elle permet de faire une recherche sans consulter toutes les données. Exemple, pour un tableau de 20 éléments, on compare la valeur recherché avec la valeur du 10e élément. Si sa valeur est plus petite que la valeur recherchée alors l'index du 10e élément sera l'index du début et l'index du 20e élément, la fin. Le milieu entre 10 et 20 est 15. Donc on compare la valeur recherché avec la valeur du 15e élément et ainsi de suite jusqu'à ce qu'on trouve la valeur. Dès que la zone de recherche est égale à 1 et que la valeur est différente de la valeur recherchée alors elle n'est pas présente dans le tableau.

Dans le pire des cas on compare avec le 10e, le 15e, le 18e, le 19e et le 20e élément avant de se rendre compte que la valeur recherchée n'est pas dans le tableau. (Seulement 5 tests) Avec une fouille linéaire, 20 tests auraient été nécessaire pour effectuer la même vérification.

La fouille dichotomique est plus rapide certe mais il y a un prix à payer. Le tableau doit obligatoirement être trié dans l'ordre croissant ou ascendant. S'il ne peut être trié alors la fouille linéaire est la seule option possible.

!!! IMPORTANT !!!

Dans le cas d'un tableau de chaîne de caractère avec la fouille dichotomique. Si le tableau à été trié avec l'option sensible à la case alors la fouille doit également être sensible à la case. Dans le cas contraire, la fouille risque de ne pas fonctionner correctement, voir même pas du tout.
A+
Guimauve
Backup
Messages : 14526
Inscription : lun. 26/avr./2004 0:40

Message par Backup »

heu !!

pour que ça entre dans le cadre d'un tuto, faudrai au moins un minimum d'explication :)

ce qu'est un hachage , une collision, etc ...

le principe du hachage , et aussi la technique employé pour l'exemple

bref , un tuto , se doit d'être au minimum construit , ce serai cool pour les débutants, qui tombe la dessus !!

de plus je nettoierai ce tuto de tout les messages en dehors de ceux qui on un rapport avec le tuto ...


et ce tuto entrera dans la liste des tuto :)

en esperant etre compris sur ce point :)


ps : peut etre a réediter le premier message avec le deuxieme code ..????

ou carrement a refaire un post a neuf :)

bref voila voila :)
Avatar de l’utilisateur
GeBonet
Messages : 453
Inscription : ven. 29/févr./2008 16:17
Localisation : Belgique

Message par GeBonet »

@Dobro C'est tout à fait vrai,

Dans le Post : Optimiser une procédure, comparaison listes chaînées
( http://www.purebasic.fr/french/viewtopi ... ge&start=0)

Fred était intervenus pour conseiller une technique de Hachages
et Olivier a fourni cette adresse (ci dessous) pour expliquer ce que c'était et qui explique très bien ce qu'est cette technique...
Mais comme il y existe plusieurs algo de calcul, il faut d'abord comprendre ce que c'est que la technique et Wikipedia le fait très bien ?
Quand aux Algo il faut un peu aller à la pêche. A la limite je pourrais en fournir un... Mais il est vieux, et on a certainement fait mieux depuis.
Tout comme à partir de la technique "chacun" pourrait créer son algorithme et même faire des concours :idea:
Ollivier a écrit :@Fred
Merci d'avoir trouvé le terme technique adéquat!
Grâce à ça, on trouve une explication plus conventionnelle sur wikipedia.
Ollivier
Voilà, le raccord que je peu fournir... Et à partir de ça voir si effectivement il n'y a pas moyen de faire un TuTo cohérent, avec l'explication de la technique, un exemple d'algorythme de calcul et une application qui utiliserai cet algorithme qui doit forcément reposer sur une table ou un fichier assez important. (comme c'est le cas posté par Cpl.Bator mais qui devrait être commenté).
Ollivier
Messages : 4197
Inscription : ven. 29/juin/2007 17:50
Localisation : Encore ?
Contact :

Message par Ollivier »

@Gebonnet

Ouais ben moi je veux bien te croire! Sauf que le sujet en question il est parti en quenouille de grenouille. Donc merci à Cpl.Bator d'avoir rouvert le chapitre de manière plus clean! Par contre, comme dit Dobro, le titre va pas, car c'est évident, que le débutant il aura un petit peu de mal à trouver le chemin. Disons qu'ici, on peut déjà rassembler les idées pour un futur tuto.

Ollivier
Répondre