Algorithme soundex
Description
Algorithme Soundex C# / Soundex Algorithm C#
Historique :
-------------
Le terme Soundex remonte à 1918. Le premier algorithme de ce type a été inventé par Margaret O?Dell et Robert C. Russell, probablement à cause des problèmes liés au recensement américain. En effet, de part leur constitution, les États Unis d?Amérique sont tenus à recenser leur population tous les 10 ans. A la fin du siècle dernier, le problème du recensement était devenu un casse tête majeur. Traiter des informations concernant une population de plusieurs dizaines de millions d?américains à la main demandait un travail phénoménal. Le premier a en tirer parti fût un certain Hollerith, qui fabriqua et introduisit les premières machines mécanographiques comptables, réduisant ainsi les temps de traitement des informations de 75%. Dans ce même temps de nombreuses personnes trouvèrent des idées astucieuses pour trier, classer, rechercher parmi les données collectées. Il en fût sans doute ainsi du premier mécanisme de recherche par consonance, que ses auteurs appelèrent Soundex. Depuis, ce terme regroupe une famille d?algorithmes que nous allons détailler.
Principe :
-------------
Comment dans une liste de nom de personne arriver à retrouver un certain DUPONT ou DUPOND ou DUPAN ou encore DEPAIN ???
C?est simple, il suffit de se baser sur la consonance et non sur les mots eux-mêmes.
Tous les algorithmes de Soundex reposent sur un principe de base qui consiste à codifier le mot en éliminant les lettres en doubles, les lettres muettes (H en particulier) et en rapprochant les sons de certaines lettres. Une fois cette codification obtenue on la stocke auprès de la donnée de base et on effectue la recherche par comparaison directe entre le Soundex ainsi obtenu et le mot recherché codifié lui aussi en Soundex.
La recherche en est donc très performante puisqu?elle aboutit à une requête dont le critère est l?égalité, et pour peu que l?on place un index sur le champ qui stocke le code du soundex, alors elle s?avère aussi rapide que de trouver un enregistrement pas sa clef.
--------------------------------------------------------------------------------------------
source de ces textes et explication de l'algo : http://www-lium.univ-lemans.fr/~carlier/recherche/soundex.html
Pratiquement, si on associe un algorithme soundex avec un algorithme de levenstein (http://www.csharpfr.com/codes/LEVENSHTEIN-DISTANCE-ALGORITHME_39298.aspx) on arrive à avoir des résultats qui sont très pertinents. Je propose dans cette source le Soundex et le Soundex2 (une amélioration de celui-ci).
J'ai également ajouté un projet qui permet de tester les deux algos (Levenshtein et soudex). Je vous laisse le soin de faire quelques testes pour voir que ça marche assez bien ;-)
Commentaires constructifs et idées d'améliorations pour que ça soit plus performant sont les bienvenus !
Historique :
-------------
Le terme Soundex remonte à 1918. Le premier algorithme de ce type a été inventé par Margaret O?Dell et Robert C. Russell, probablement à cause des problèmes liés au recensement américain. En effet, de part leur constitution, les États Unis d?Amérique sont tenus à recenser leur population tous les 10 ans. A la fin du siècle dernier, le problème du recensement était devenu un casse tête majeur. Traiter des informations concernant une population de plusieurs dizaines de millions d?américains à la main demandait un travail phénoménal. Le premier a en tirer parti fût un certain Hollerith, qui fabriqua et introduisit les premières machines mécanographiques comptables, réduisant ainsi les temps de traitement des informations de 75%. Dans ce même temps de nombreuses personnes trouvèrent des idées astucieuses pour trier, classer, rechercher parmi les données collectées. Il en fût sans doute ainsi du premier mécanisme de recherche par consonance, que ses auteurs appelèrent Soundex. Depuis, ce terme regroupe une famille d?algorithmes que nous allons détailler.
Principe :
-------------
Comment dans une liste de nom de personne arriver à retrouver un certain DUPONT ou DUPOND ou DUPAN ou encore DEPAIN ???
C?est simple, il suffit de se baser sur la consonance et non sur les mots eux-mêmes.
Tous les algorithmes de Soundex reposent sur un principe de base qui consiste à codifier le mot en éliminant les lettres en doubles, les lettres muettes (H en particulier) et en rapprochant les sons de certaines lettres. Une fois cette codification obtenue on la stocke auprès de la donnée de base et on effectue la recherche par comparaison directe entre le Soundex ainsi obtenu et le mot recherché codifié lui aussi en Soundex.
La recherche en est donc très performante puisqu?elle aboutit à une requête dont le critère est l?égalité, et pour peu que l?on place un index sur le champ qui stocke le code du soundex, alors elle s?avère aussi rapide que de trouver un enregistrement pas sa clef.
--------------------------------------------------------------------------------------------
source de ces textes et explication de l'algo : http://www-lium.univ-lemans.fr/~carlier/recherche/soundex.html
Conclusion :
Pratiquement, si on associe un algorithme soundex avec un algorithme de levenstein (http://www.csharpfr.com/codes/LEVENSHTEIN-DISTANCE-ALGORITHME_39298.aspx) on arrive à avoir des résultats qui sont très pertinents. Je propose dans cette source le Soundex et le Soundex2 (une amélioration de celui-ci).
J'ai également ajouté un projet qui permet de tester les deux algos (Levenshtein et soudex). Je vous laisse le soin de faire quelques testes pour voir que ça marche assez bien ;-)
Commentaires constructifs et idées d'améliorations pour que ça soit plus performant sont les bienvenus !
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.