Les soundex

Préambule
1. Le principe
2. Le premier Soundex
3. Soundex 2
4. Phonex
5. Le code
6. Tests
7. En complément
7.1. HAMMING et sa différence
7.2. Levenshtein et sa distance
8. Bibliographie

Préambule

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.

1. Le 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.

Certaines base de données utilisent nativement des Soundex pour la recherche. Il en est ainsi de Paradox et de son opérateur « Comme » valable dans les requêtes QBE, de Oracle, ou encore de Watcom SQL devenu SQL Anywhere.
Mais attention : dans tous ces cas, il est probable que votre « soundex » fonctionne sur la consonance anglo-saxonne du langage et non sur les sons spécifiques à la langue française.

2. Le premier Soundex

Voici l’algorithme original de Russel & O’Dell datant de 1918

On retranscrit le mot en majuscules
On conserve la première lettre du mot
On élimine ensuite toutes les voyelles, le H et le W
On transcode ensuite les lettres restantes à l’aide de la table suivante

Version Anglo-Saxonne

Lettre	Type de consonnance	code
B F P V	Bilabiales	1
C G J K Q S X Z	Labiodentales	2
D T	Dentales	3
L	Alvéolaires	4
M N	Vélaires	5
R	Laryngales	6

On élimine ensuite toutes les paires consécutives de chiffres dupliquées
On ne conserve que 4 caractères du Soundex ainsi obtenu, et on le complète par des zéros le cas échéant

Compte tenu que les tables de caractères modernes, permettent maintenant de saisir des lettres majuscules accentuées, il est nécessaire de transcrire ces lettres en lettres simples. En particulier, dans la langue française, le c majuscule avec cédille (Ç ) sera transformé en S. De même que le caractère Œ (dans le mot cœur par exemple) sera transformé en E.

De plus il est nécessaire de supprimer les espaces morts avant et après le mot ainsi que les blancs et le tiret.

Version Française

Lettre	Type de consonnance	code
B P	Bilabiales	1
C K Q	Labiodentales	2
D T	Dentales	3
L	Alvéolaires	4
M N	Vélaires	5
R	Laryngales	6
G J	Labiodentales	7
S X Z	Labiodentales	8
F V	Bilabiales	9

3. Soundex 2

Soundex 2 est un algorithme francisé , et dérivé de l’algorithme décrit dans le livre de Joe Celko – « SQL avancé », parue en 1995 chez Thomson International Publishing. Il repose sur l’algorithme de Gus Baird (Georgia Tech) énoncé en page 85.

Contrairement au précédent qui ne fait appel qu’à des chiffres à l’exception du premier caractère, cette nouvelle version conserve la plupart des lettres.

En comparant les trois versions, on trouve :
Pour Soundex Anglo-Saxons, le nombre de combinaisons possibles de 26x7x7x7 = 8 918
Pour Soundex Français, le nombre de combinaisons possibles de 26x10x10x10 = 26 000
Pour Soundex 2, le nombre de combinaisons différentes monte jusqu’aux environs de 20x20x20x20 = 160 000

Il se révèle donc plus performant dans de nombreux cas, c’est à dire qu’il permet de sélectionner moins d’occurrence lors des recherches avec le même encombrement de 4 caractères.

Voici cette nouvelle version francisée :

Éliminer les blancs à droite et à gauche du nom
Convertir le nom en majuscule
Convertir les lettres accentuées et le c cédille en lettres non accentuées
Eliminer les blancs et les tirets
Remplacer les groupes de lettres suivantes par leur correspondance (en conservant l’ordre du tableau) :

GUI	KI
GUE	KE
GA	KA
GO	KO
GU	K
CA	KA
CO	KO
CU	KU
Q	K
CC	K
CK	K

Remplacer toutes les voyelles sauf le Y par A exceptée s’il y a un A en tête
Remplacer les préfixes suivants par leur correspondance :

MAC	MCC
ASA	AZA	(ASAmian)
KN	NN	(KNight)
PF	FF	(PFeiffer)
SCH	SSS	(SCHindler)
PH	FF	(PHilippe)

Supprimer les H sauf s’ils sont précédés par C ou S
Supprimer les Y sauf s’il est précédé d’un A
Supprimer les terminaisons suivantes A, T, D et S
Enlever tous les A sauf le A de tête s’il y en a un
Enlever toutes les sous chaînes de lettre répétitives
Conserver les 4 premiers caractères du mot et si besoin le compléter avec des blancs pour obtenir 4 caractères

5. Phonex

Phonex est un algorithme de Soundex plus perfectionné encore que la version francisée de Soundex2. Sachez que Phonex est optimisée pour le langage français, sait reconnaître différents types de sons comme les sons ‘on’, ‘ai’, ‘ein’, etc... et place son résultat sous la forme d’un réel de type double précision (5.0 x 10-324 .. 1.7 x 10308 sur 15 à 16 chiffres significatifs). Son temps de calcul est double de Soundex et 30% supérieure seulement à Soundex2.

Algorithme Phonex
Copyright Frédéric BROUARD (31/3/99)

Merci à Florence MARQUIS, orthophoniste, pour son aide à la mise au point de cet algorithme

1 remplacer les y par des i
2 supprimer les h qui ne sont pas précédés de c ou de s ou de p
3 remplacement du ph par f
4 remplacer les groupes de lettres suivantes :

gan	kan
gam	kam
gain	kain
gaim	kaim

5 remplacer les occurrences suivantes, si elles sont suivies par une lettre a, e, i, o, ou u :

ain	yn
ein	yn
aim	yn
eim	yn

6 remplacement de groupes de 3 lettres (sons 'o', 'oua', 'ein') :

eau	o
oua	2
ein	4
ain	4
eim	4
aim	4

7 remplacement du son ‘é’ :

é	y
è	y
ê	y
ai	y
ei	y
er	yr
ess	yss
et	yt

8 remplacer les groupes de 2 lettres suivantes (son ‘an’ et ‘in’), sauf s’il sont suivi par une lettre a, e, i o, u ou un son 1 à 4 :

an	1
am	1
en	1
em	1
in	4

Prise en compte du son "on"

9 remplacer les s par des z s’ils sont suivi et précédés des lettres a, e, i, o,u ou d’un son 1 à 4
10 10 remplacer les groupes de 2 lettres suivants :

oe	e
eu	e
au	o
oi	2
oy	2
ou	3

11 remplacer les groupes de lettres suivants

ch	5
sch	5
sh	5
ss	s
sc	s

12 remplacer le c par un s s’il est suivi d’un e ou d’un i
13 remplacer les lettres ou groupe de lettres suivants :

c	k
q	k
qu	k
gu	k
ga	ka
go	ko
gy	ky

14 remplacer les lettres suivante :

a	o
d	t
p	t
j	g
b	f
v	f
m	n

15 Supprimer les lettres dupliquées
16 Supprimer les terminaisons suivantes : t, x
17 Affecter à chaque lettres le code numérique correspondant en partant de la dernière lettre

0	1
1	2
2	3
3	4
4	5
5	e
6	f
7	g
8	h
9	i
10	k
11	l
12	n
13	o
14	r
15	s
16	t
17	u
18	w
19	x
20	y
21	z

18 Convertissez les codes numériques ainsi obtenu en un nombre de base 22 exprimé en virgule flottante.

Exemple : nom « PHYLAURHEIMSMET »

1	PHILAURHEIMSMET
2	PHILAUREIMSMET
3	FILAUREIMSMET
4	FILAUREIMSMET
5	FILAUREIMSMET
6	FILAUR4SMET
7	FILAUR4SMY
8	FILAUR4SMY
9	FILAUR4SMY
10	FILOR4SMY
11	FILOR4SMY
12	FILOR4SMY
13	FILOR4SMY
14	FILOR4SNY
15	FILOR4SNY
16	FILOR4SNY
17	FILOR4SNY
18	6, 9, 11, 13, 14, 3, 15, 12, 20
19	622^(-1) + 922^(-2) + 1122(-3) + 1322(-4) + 1422(-5) + 322(-6) + 1522(-7) + 1222(-8) + 20*22(-9)
20	0.29241361598339205

5. Le code

Implémentation des fonctions SOUNDEX, SOUNDEX_FR, SOUNDEX2 et PHONEX en Python

Soundex.py : Ici

Contient soundex, soundex_fr, soundex2

Phonex.py : Ici

Contient phonex

6. Les tests

A Venir

7. En complément

Afin de savoir si deux SOUNDEX sont très différents ou très peu différents, on a développé toute une série de fonctions dont l'utilisation est à prendre "avec des pincettes".

7.1. HAMMING et sa différence

Différence de HAMMING est le nombre de caractères non identiques à la même position dans deux châines de caractères de même longueurs.
Par exemple les chaînes suivantes : "D823" et "M843" ont une différence de HAMMING de 2.
Ainsi deux soundex sont identiques si la différence de HAMMING vaut zéro. Il sont semblable si cette différence est 1. Ils sont totalement dissemblables si la distances de HAMMING est 4 (le maximum dans ce cas).
La différence de HAMMING est un algorithme simple et très performant car d'un coût linéaire.
On trouve cette fonction opérant notamment sur les soundex sur quelques SGBDR dont SQL Server (fonction DIFFERENCE qui, curieusement fonctionne "à l'envers")...

7.2. Levenshtein et sa distance

LDA (Levenshtein Distance Algorithme) calcule la distance de Levenshtein (nom de son inventeur) définie comme le nombre minimal de caractères qu'il faut remplacer, insérer ou modifier pour transformer une chaîne en une autre.

Quelques exemples :

PORTES PORTER	1 (transformation du S en R)
PORTE PORTER	1 (ajout d'une lettre R)
POTES PORTES	1 (ajout d'une lettre R)
POTE POSTER	2 : POTE étape 0 POSTE étape 1 POSTER étape 2
DEPORTEES POSTERS	4 : POSTERS D POSTERS étape 1 DEPOSTERS étape 2 DEPORTERS étape 3 DEPORTEES étape 4

A noter, la littérature anglaise parle de "edit distance".

En fait, cette "distance" est le nombre des opérations unitaires d'insertions, de remplacements et d'effacements conduisant la chaîne source a devenir la chaîne cible. Cette opération et l'algorithme qui en découle est considéré comme étant à l'origine des premières méthodes de programmation d'algorithmes génétiquement modifiables. En effet cet algorithme utilise la technique du "backtraking" et par conséquent la récursivité.

Ces algorithmes sont actuellement forts utilisés dans le cas de la recherche génétique car ils permettent de comparer les codes génétiques qui sont représentés en machine par de très grandes châines de caractères ne comprenant que les lettres a c g et t.

8. Bibliographie

2 Soundex :
Russel & O’Dell datant de 1918

3 Soundex 2 :
Algorithme décrit dans le livre de Joe Celko – « SQL avancé », parue en 1995 chez Thomson International Publishing.
Il repose sur l’algorithme de Gus Baird (Georgia Tech) énoncé en page 85.

4 Phonex :
Algorithme de Frédéric BROUARD
Original page : http://sqlpro.developpez.com/cours/soundex/

5 Code Python Soundex :
Adapté par Florent Carlier

5 Code Python Phonex :
Adapté par Christian Pennaforte (http://www.pennaforte.net) et Florent Carlier

7.1 Hamming :
http://merlin.mbcr.bcm.tmc.edu:8001/bcd/Curric/PrwAli/node2.html

7.2 Levenstein :
La communication originale : V. I. Levenshtein, "Binary Codes Capable of Correcting Deletions, Insertions and Reversals," in Soviet Physics Dokl. n°10, p707 à 710 (1966)
http://www.merriampark.com/ld.htm
http://www-igm.univ-mlv.fr/~lecroq/seqcomp/node2.html
http://www.cut-the-knot.com/do_you_know/Strings.html

7.2 Génétique :
http://www.csis.hku.hk/~nikos/courses/CSIS7101/strings.pdf