Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11

Recherche de chaines de caractères (Was: Quel système de BD utiliser?)

5 réponses
Avatar
Jean-Marc
Hello,

j'ouvre un nouveau thread pour rebondir sur la question de Douns.
La question était de savoir comment retrouver une chaine de caractères
parmi un nombre important de chaine.

Le moyen le plus efficace dans ce cas (sans utilisation de BD) est
certainement
l'utilisation de table de hachage. C'est simple à programmer en VB et on
fait
difficilement plus efficace, à part peut être les arbres de lettres.

Ce mécanisme de table de hachage est universellement utiliser, pour toute
sorte d'applications. Les OS en font un grand usage.

Principe des tables de hachage:
- on dimensionne un tableau avec plus ou moins le même nombre d'éléments
que le nombre de chaines de caractères à insérer
- Pour chaque chaine de caractère à ajouter, on calcule une "clé de
hachage",
qui va donner la position de stockage dans le tableau.
- Si il y a déjà quelque chose à cette position (cela peut arriver car
plusieurs
chaines peuvent donner la même clé), on gère cette situation (cela s'appelle
une
collision). On peut gérer cela de plein de façons, je donnerais ici un
exemple.
En général, si la taille du tableau est boen choisie, on n'a que peu de
collisions,
et une gestion correcte de celles ci ne pénalisent pas ou peu les
performances.

Pour donner une idée, le code suivant permet l'insertion de 100.000 mots en
moins de
1 seconde, et la recherche d'une chaine est si rapide que c'est difficile à
mesurer.
L'odre de grandeur est de quelques millisecondes, dans l'IDE.

Quelques précisions importantes:
- N_HASH doit toujours être un nombre premier
- B_HASH doit être une puissance de 2 (256 convient dans tous les cas)

Je donne le code ici à titre d'exemple:

Option Explicit

Const N_HASH = 240007
Const B_HASH = 256

Dim size_Hash_Col As Long

Type tHash
value As String
posCol As String
bCollision As Boolean
End Type

Dim tabHash() As tHash
Dim tabHashCol() As String
Dim FastFreePos As Long
Dim max_col As Long


Public Function InitHash() As Integer

ReDim tabHash(N_HASH)

size_Hash_Col = Int(N_HASH / 10)
ReDim tabHashCol(N_HASH)
FastFreePos = 1

InitHash = 0
End Function

Public Function IsInHashTable(s As String) As Boolean
Dim vHash As Long
Dim t() As String
Dim i As Long
Dim sColString As String

vHash = hash(s)

If tabHash(vHash).value = s Then
IsInHashTable = True
Exit Function
Else
If tabHash(vHash).bCollision Then
sColString = tabHash(vHash).posCol
' en VB5, remplacer split() par une boucle de Instr
t() = Split(sColString, ",")
For i = LBound(t) To UBound(t)
If tabHashCol(Val(t(i))) = s Then
IsInHashTable = True
Exit Function
End If
Next i
End If
End If
End Function

Public Sub InsertHash(s As String)
Dim vHash As Long
Dim i As Long
Dim t() As String
Dim nc As Long
Dim p As Integer

vHash = hash(s)
If (tabHash(vHash).value = "") Or (tabHash(vHash).value = s) Then
' simple insert
tabHash(vHash).value = s
Exit Function
Else
' is it the first collision ?
If tabHash(vHash).bCollision Then
t = Split(tabHash(vHash).posCol, ",")
'find from here for a double
For i = LBound(t()) To UBound(t())
If tabHashCol(Val(t(i))) = s Then
' already inserted (doublon)
Exit Function
End If
Next i
tabHash(vHash).posCol = tabHash(vHash).posCol & "," &
Trim$(Str$(FastFreePos))
Else
tabHash(vHash).bCollision = True
tabHash(vHash).posCol = Trim$(Str$(FastFreePos))
End If
' and insert it
tabHashCol(FastFreePos) = s
FastFreePos = FastFreePos + 1
If FastFreePos > size_Hash_Col Then
' arf! time to resize tabHashCol
size_Hash_Col = size_Hash_Col * 2
ReDim Preserve tabHashCol(size_Hash_Col)
End If
End If
End Function

Private Function hash(s As String) As Long
Dim v As Long
Dim i As Long

For i = 1 To Len(s)
v = (v * B_HASH + Asc(Mid$(s, i, 1))) Mod N_HASH
Next i
hash = v
End Function


Conclusion:
En programmation, et plus encore en algorithmique, 90% de la solution
d'un problème est en général dans la STRUCTURE des données.

Dans ce contexte, l'utilisation d'une base de donnée me semble overkill,
un peu comme un marteau pilon pour écraser une mouche.

--
Jean-marc
"There are only 10 kind of people
those who understand binary and those who don't."
mailto: remove '_no_spam_' ; _no_spam_jean_marc_n2@yahoo.fr

5 réponses

Avatar
Fred
Dans : news:42f26a0c$0$627$,
Jean-Marc disait :
Hello,



Bonsoir ;-)

j'ouvre un nouveau thread pour rebondir sur la question de Douns.
La question était de savoir comment retrouver une chaine de caractères
parmi un nombre important de chaine.



Comment retrouver les chaînes qui *contiennent* celle recherchée ;-)
Dans son cas les clés de hachage sont inefficaces.

Mais c'est très intéressant ! Merci pour le code et la démonstration.

[...]


PS :
Allez, on est que jeudi mais ça me démange.
Passez au .NET, tout est déjà fait, il n'y a plus qu'à ... /paramétrer/
:-D

--
Fred
http://www.cerbermail.com/?3kA6ftaCvT
Avatar
Jean-Marc
"Fred" a écrit dans le message de
news:
Dans : news:42f26a0c$0$627$,
Jean-Marc disait :
> Hello,

Bonsoir ;-)



Hello,


> j'ouvre un nouveau thread pour rebondir sur la question de Douns.
> La question était de savoir comment retrouver une chaine de caractères
> parmi un nombre important de chaine.

Comment retrouver les chaînes qui *contiennent* celle recherchée ;-)
Dans son cas les clés de hachage sont inefficaces.



Dans son cas, les chaines sont séparés par un séparateur, comme ceci:

toto;tutu titi;tutu;tata;tyty
on stocke donc:
"toto", "tutu titi", "tutu", "tata", "tyty"

C'est tout à fait adapté.

Si on cherche des sous chaines (chaines dans une autre chaine) comme par
exemple
chercher "toto" dans "bonjour toto et titi", alors bien sur on n'utilise pas
de hashtable, il y a d'autres techniques, par exemple une recherche de
pattern
avec un algo rapide genre "boyer moore" ou autre.

Mais c'est très intéressant ! Merci pour le code et la démonstration.



De rien!

--
Jean-marc
"There are only 10 kind of people
those who understand binary and those who don't."
mailto: remove '_no_spam_' ;
Avatar
Fred
Dans : news:42f27392$0$20695$,
Jean-Marc disait :
"Fred" a écrit dans le message de
news:

Dans son cas, les chaines sont séparés par un séparateur, comme ceci:

toto;tutu titi;tutu;tata;tyty
on stocke donc:
"toto", "tutu titi", "tutu", "tata", "tyty"



D'après un de ses posts, j'ai cru comprendre qu'il pouvait justement
rechercher «titi» (pour reprendre ton exemple).
Ce qui avait d'ailleurs été traduit en requête SQL par l'utilisation d'un
«Like» dans un autre post.


--
Fred
http://www.cerbermail.com/?3kA6ftaCvT
Avatar
[___FreGoLi___]
Salut,

Des algo de recherche de sous chaine dans une chaine, il y en a plein, mais
pourquoi se faire chier quand la fonction instr le fait très bien et très
vite. (j'imagine qu'elle implémente un algorithme efficace et qu'elle ne fait
pas naïvement du caractère par caractère, comme d'ailleurs le "select * where
zone like "xyz"").

en une instruction (instr) on implémente un algorithme optimisé, sinon au
milliardième de seconde, du moins au 5 milliardième.
Il ne faut pas se torturer le cerveau en inventant l'eau chaude.

Mais pour ceux que cela interresse, deux adresses sur les alogorithme de
recherche de chaine:

http://www.site.uottawa.ca/~stan/talks/public/8chaines4.0.ppt
http://diuf.unifr.ch/courses04-05/progr3a/
Slides/handouts/progr3A10-RechChaine.pdf

Bonne lecture
Avatar
Jean-Marc
"[___FreGoLi___]" a écrit dans le
message de news:
Salut,



Hello,

Des algo de recherche de sous chaine dans une chaine, il y en a plein,


mais
pourquoi se faire chier quand la fonction instr le fait très bien et très
vite. (j'imagine qu'elle implémente un algorithme efficace et qu'elle ne


fait
pas naïvement du caractère par caractère, comme d'ailleurs le "select *


where
zone like "xyz"").



Efficace: Oui, relativement. Le plus efficace: Non, et loin s'en faut.

en une instruction (instr) on implémente un algorithme optimisé, sinon au
milliardième de seconde, du moins au 5 milliardième.



???

Il ne faut pas se torturer le cerveau en inventant l'eau chaude.



Certes, mais ça vaut parfois le coup, face à un problème donné, de chercher
si il n'y a pas moyen de faire mieux que l'existant.


La fonction Instr de VB est certe efficace, mais pas "la plus efficace".
Elle n'est pas du tout au milliardième de seconde comme tu le dis,
puis qu'une simple recherche d'une chaine de 20 caractères à la fin d'un
buffer de 20000 a un ordre de grandeur de 6.10-5 secondes (on est loin
du milliardième).

Pour le fun, j'ai implémenté en VB une recherche avec Boyer Moore
et j'ai fait quelques tests, en cherchant des patterns de 20 caractères dans
un buffer de 20 ko (20000 caractères).

Mon implémentation (naïve = non optimisée) de BM est 2,5 fois plus
rapide que Instr, et si on augmente la taille du buffer de recherche,
BM est de plus en plus rapide (ie: meilleur que Instr) (de façon
exponentielle).

<remarque>
Une implémentation optimisée, en particulier si on recherche fréquemment
le même pattern, sera de 2 à 10 fois encore meilleure, selon les cas.
</remarque>

Il est clair que cela n'a d'intérêt que pour un programme qui fait
un usage massif de Instr(), dans des buffers de taille assez grande.

<exemple>
Un programme dont le but est de rechercher des patterns particuliers
dans des fichiers html (cas typique de grand fichier texte).
</exemple>

En tout cas, c'est une erreur de croire que VB implémente systématiquement
les algos les meilleurs pour toutes les fonctions.

--
Jean-marc
"There are only 10 kind of people
those who understand binary and those who don't."
mailto: remove '_no_spam_' ;