investigation ECHELON images/petit_logo_jcd.gif

 

US Patent 5,418,951: Method of retrieving documents that concern the same topic retour

 

la promesse des inventeurs

Le brevet 5,418,951 a été déposé par la NSA au bureau américain des brevets en septembre 1994. Il décrit une "méthode pour retrouver des documents qui concernent le même sujet". Pour cela, il propose la méthode des n-grams.

Il s'agit d'une méthode de recherche de textes sans utilisation de mot clé. Elle peut être employée pour la recherche de documents par langue ou par sujet. Elle peut servir également pour d'autres type de documents informatisés comme des enregistrements sonores (de la parole) ou des images.

 

génèse de l'invention

La recherche par mot clé trouve ses limites. Elle se heurte aux problème de reconnaissance des synomymes (par exemple "voiture" et "automobile") ainsi qu'aux formes dérivées des mots (recherche, rechercher). Elle est aussi très sensible aux erreurs de transmission ou aux fautes d'orthographe.

Les méthodes de recherche par mot clé peuvent être améliorées en utilisant des tables de synomymes mais on s'aperçoit rapidement que le sens d'un mot ne peut pas être extrait complétement d'un dictionnaire. Il dépend du contexte. Différentes méthodes ont été décrites pour prendre en compte des informations décrivant le contexte (vecteurs de contexte, graphes conceptuels, réseaux sémantiques, réseaux d'inférence).

La méthode n-gram se veut en rupture avec ces différentes approches.

Dans cette méthode, on ne compare pas des mots, mais des chaînes de caractères. Il n'y a pas de dictionnaire. Elle est facile à programmer dans n'importe quel langage informatique ou même dans du hardware. Elle ne nécessite pas de grandes quantités de mémoire.

Elle peut fonctionner avec n'importe qu'elle langue, y compris des idéogrammes Japonais. Elle permet :

 

les performances de la méthode

Les documents ne sont pas traités comme des listes de mots mais découpés en groupes de caractères consécutifs (2, 3, 5, ..) appelés n-grams qui seront comparés aux n-grams des documents la base de données de référence.

L'hypothèse est que si deux documents traitent du même sujet, ils se ressemblent, et donc contiennent des n-grams semblables.

Cette analyse peut se faire sur des textes comportant un grand nombre d'erreurs. Ainsi pour la recherche des langues, la différence entre le Swaïili et le Suédois peut être déterminée même avec 25% d'erreurs. Lorsque les langues sont plus proches, comme entre le Russe et le Tchèque, le taux d'erreur ne doit pas excéder 15%.

Le texte peut être préparé en ne conservant que les lettres et les espaces, en supprimant les espaces multiples, ou en convertissant les minuscules en majuscules.

La suppression de la ponctuation permet d'augmenter les performances en diminuant le nombre de n-grams différents.

Pour que la méthode soit efficace, il faut que le nombre de documents de référence soit significatif. Expérimentalement, on a déterminé que dix documents de référence sont nécessaires pour une recherche de langue tandis que pour une recherche de sujet dans une langue particulière, il en faut 50, de mille caractères chacun environ.

 

comment ça marche ?

Chaque document de la base de données est découpé en n-grams. Un poids est donné à chaque n-gram. Ce poids est égal à son nombre d'occurences (nombre d'apparitions dans le texte) divisé par le nombre de n-grams du texte.

Pour soumettre un nouveau document à la base de données, on le découpe également en n-grams et on calcule le poids de chacun de ses n-grams.

Ensuite pour chaque document de la base de donnée, on effectue les opérations suivantes :

En résumé, le score "n" de chaque texte vaut donc :

equation

 

l'étude

La lecture de ce brevet m'a laissé perplexe. C'est le moins que je puisse dire. J'ai dû relire l'explication des formules utilisées à plusieurs reprises avant de pouvoir les réécrire en français. Finalement, ça ressemble à quelque chose de connu (il suffirait de rechercher dans un cours d'analyse statistique) mais il faudrait surtout expérimenter pour vérifier si ça marche. La mise en oeuvre du test n'est pas triviale. Ce n'est pas très compliqué, mais pas simple non plus, juste entre les deux, et si c'était exprès, on ne ferait pas autrement (d'où l'idée que c'est peut-être un leurre). D'abord il faudrait commencer par constituer une base de test avec de nombreux documents traitant de sujets différents mais bien identifiés ou écrits dans des langues différentes (on peut en trouver plein sur le web).

Je me suis contenté ici d'un test élémentaire pour voir ce que ça peut donner.

Le texte traité est le même que celui utilisé pour la recherche de mots clés.

J'ai dû encore écrire un petit bout de programme pour découper le texte en n-grams, du QBasic cette fois. Il convenait mieux pour lire le fichier caractère par caractère. Ce langage faisait partie des anciennes versions de MSDOS, il n'est plus dans Windows mais je le garde précieusement. Le programme est un "prototype". Il permet de créer des n-grams de 1, 2 ou 10 caractères, mais il faut modifier le programme à chaque fois (variable nbc).

Ici, il est paramétré pour des n-grams de 10 caractères (des 10-grams donc).

Sans rentrer dans le détail de programmation, on peut remarquer que les accents sont supprimés. J'ai été obligé de le faire à cause d'une incompatibilité entre le programme de tri de DOS (sort) qui tient compte des accents et le programme uniq que j'utilise ensuite, qui lui, les ignore... Le comptage ne pouvait pas fonctionner sans ce transcodage.

Les caractères spéciaux (retour à la ligne, tabulation, etc...) qui se trouvent dans le fichier sont remplacés par "_", ceux qui ont un code ASCII supérieur à 127 sont remplacés par "?". C'est le choix que j'ai fait mais il vaudrait peut-être mieux tout simplement les éliminer .

Enfin, je n'ai pas traité correctement la fin de fichier... les n derniers n-gram produits n'ont pas "n" caractères. Il faudrait normalement ajouter des caractères de remplissage.

' leccar2.bas - jc devaux - 02/11/2001
' lecture d'un fichier en mode caractère
' avec traduction des caracteres 0-16 (_), filtre des accents
' les entrees sont supposees dans 0-127 (remplacement par ? apres 127)
' traduction en majuscule
' version 2 cree toutes les chaines de n car.

ON ERROR GOTO 100
nbc = 10
OPEN "file.txt" FOR INPUT AS #1
OPEN "file-10.txt" FOR OUTPUT AS #2
'
DIM b$(nbc), c$(nbc), retard(nbc)
FOR i = 1 TO nbc
b$(i) = "": c$(i) = "": retard(i) = i - 1
NEXT

WHILE NOT EOF(1)
a$ = INPUT$(1, 1): a0$ = a$ ' lecture du fichier en mode caractere
FOR i = 1 TO nbc
IF retard(i) = 0 THEN
b$(i) = b$(i) + a$
IF (a$ = "à" OR a$ = "â" OR a$ = "ä") THEN a$ = "a"
IF (a$ = "é" OR a$ = "è" OR a$ = "ê" OR a$ = "ë") THEN a$ = "e"
IF (a$ = "ï" OR a$ = "Î") THEN a$ = "i"
IF (a$ = "ü" OR a$ = "û") THEN a$ = "u"
j = ASC(a$)
IF j > 127 THEN j = ASC("?") ' filtre accents (un peu brutal)
IF j > 96 AND j < 123 THEN j = j - 32 ' MAJ
IF j < 16 THEN j = ASC("_") 'transcode car speciauc (CR,LF, ...)
c$(i) = c$(i) + CHR$(j)
ELSE
retard(i) = retard(i) - 1
END IF
' on a obtenu les nbc caracteres
IF LEN(c$(i)) = nbc THEN
PRINT "<"; b$(i); "> <"; c$(i); ">"; a0$; ">", i, LEN(b$(i))
PRINT #2, c$(i)
b$(i) = "": c$(i) = ""
END IF
NEXT i
WEND

100 ' fin du fichier, on vide le tableau c$
FOR i = 1 TO nbc
IF c$(i) <> "" THEN
PRINT "<"; b$(i); "> <"; c$(i); "< ..."; a0$; ">", i, LEN(b$(i))
PRINT #2, c$(i)
END IF
NEXT i
CLOSE #2
CLOSE #1
END

 

Ensuite le traitement reprend les mêmes principes que pour l'étude sur les mots clés : tri, regroupement des doublons avec comptage et nouveau tri. Toutes ces opérations sont réalisées par les deux fichiers suivants (renommés txt pour s'afficher dans le navigateur).

LECCAR2.BAS cptCar_file.bat

note : si vous afficher le fichier leccar2.bas dans le navigateur, vous remarquerez peut être quelques différences avec celui affiché dans le cadre précédent. Les à, â, .. ne sortent pas correctement car le codage des accents n'est pas le même que sous DOS. Une difficulté supplémentaire pour traiter des fichiers d'origines diverses comportant des lettres accentuées.

 

Voici donc à quoi ressemblent les fichiers de n-gram :

1-grams 2-grams 3-grams 5-grams 10-grams
J
E

N
'
A
I

M
A
L
H
E
U
R
E
U
S
E
M
E
N
T
JE
E
N
N'
'A
AI
I
M
MA
AL
LH
HE
EU
UR
RE
EU
US
SE
EM
ME
EN
NT
T
JE
E N
N'
N'A
'AI
AI
I M
MA
MAL
ALH
LHE
HEU
EUR
URE
REU
EUS
USE
SEM
EME
MEN
ENT
NT
T A
JE N'
E N'A
N'AI
N'AI
'AI M
AI MA
I MAL
MALH
MALHE
ALHEU
LHEUR
HEURE
EUREU
UREUS
REUSE
EUSEM
USEME
SEMEN
EMENT
MENT
ENT A
NT AU
T AUC
JE N'AI MA
E N'AI MAL
N'AI MALH
N'AI MALHE
'AI MALHEU
AI MALHEUR
I MALHEURE
MALHEUREU
MALHEUREUS
ALHEUREUSE
LHEUREUSEM
HEUREUSEME
EUREUSEMEN
UREUSEMENT
REUSEMENT
EUSEMENT A
USEMENT AU
SEMENT AUC
EMENT AUCU
MENT AUCUN
ENT AUCUN
NT AUCUN S
T AUCUN SO

 

puis après regroupement des n-grams identiques :

1-grams 2-grams 3-grams 5-grams 10-grams
2347
12 !
34 "
197 '
7 (
7 )
3 *
111 ,
19 -
152 .
2 1
4 :
2 ;
343 ?
714 A
63 B
419 C
322 D
1601 E
85 F
61 G
70 H
740 I
122 J
3 K
502 L
324 M
715 N
524 O
356 P
174 Q
661 R
882 S
721 T
713 U
132 V
2 W
63 X
40 Y
4 Z
1 [

1 ]
142 _
18
12 !
19 "
7 (
9 -
3 .
1 1
3 :
99 ?
115 A
19 B
219 C
228 D
124 E
50 F
14 G
6 H
41 I
99 J
1 K
210 L
136 M
83 N
33 O
226 P
124 Q
42 R
153 S
124 T
55 U
41 V
2 W
11 Y
1 ]
19 _
10 !
2 !_
11 "
1 ")
2 ",
3 ".

...

3
1 A
2 C
1 D
1 F
4 J
1 L
2 Q
1 R
2 _
10 !
2 !_
1 ",
1 ".
1 "?
1 "A
1 "B
2 "C
1 "D
2 "E
2 "I
1 "K
3 "L
1 "S
2 "V
1 (A
1 (C
1 (D
1 (E
1 (J
1 (L
1 (Q
9 -
3 ..
1 11
3 :
61 ?
7 ?A
11 ?C
1 ?D
1 ?L

...
1
1 _
1 __
1 AU
1 C'E
1 CEL
1 DOM
1 FLI
1 JAM
3 JE
1 L'E
1 QU'
1 QUE
1 REM
2 ___
1 ! J
1 ! !
1 ! ..
1 ! D?
1 ! J'
1 ! LE
1 ! NO
1 ! QU
1 ! S'
1 ! TU
2 !___
1 ", C
1 ". C
1 "?CR
1 "ALL
1 "BON
2 "CON
1 "D?C
1 "EXE
1 "EXP
1 "IL
1 "INT
1 "KIL
1 "L'?
1 "L'E
1 "LA

...
1 ____S
1 ____SI
1 ____SI
1 AU FOND,
1 C'EST PE
1 CELUI DE
1 DOMINIQU
1 FLICS DE
1 JAMAIS.
1 JE NE LE
1 JE NE SA
1 JE PR?F?
1 L'EXPRES
1 QU'ON CO
1 QUE TU N
1 REMISE E
1 ____POUR
1 ____SI T
1 ! JE PR?
1 ! ! JE P
1 ! ... ENF
1 ! D?S QU'
1 ! J'AI "D
1 ! LE MEIL
1 ! NON S?R
1 ! QUANT ?
1 ! S'IL Y
1 ! TU DIS
1 !____JE N
1 !________
1 ", C'?TAI
1 ". C'EST
1 "?CRIVAIN
1 "ALLI?S"
1 "BONS LIE
1 "CONFIDEN
1 "CONS?QUE
1 "D?CID?"
1 "EXERCICE
1 "EXP?RIEN
1 "IL N'Y A

...

Le comtage de 1-grams revient à compter le nombre de caractères.
Comme on s'y attendait, le E est la lettre la plus fréquente dans un texte en Français (1601 fois) tandis qu'on observe 2347 espaces, 111 virgules, et 152 points... Le nombre de "?" ou de "_" n'est pas significatif car résultat du transcodage de certains caractères (voir programme leccar2.bas plus haut).

Pour les autres types de n-grams, ce ne sont ici que les débuts des fichiers... Noter que le programme ignore les espaces de début et de fin de chaîne. Il ne fait pas la différence entre " !" et "! ", ce qui fausse certains comptages.

Pour obtenir le poids de chaque n-gram, il faudrait diviser les valeurs de comptage obtenues par le nombre de n-gram du fichier (c'est à dire le nombre de caractères) soit, ici par 13 397.

Les nombres de n-grams obtenus sont :

1-grams 2-grams 3-grams 5-grams 10-grams
43 487 2209 7507 12 671

 

Le tableau suivant donne les n-grams les plus fréquents :

1-grams 2-grams 3-grams 5-grams 10-grams
2347
1601 E
882 S
740 I
721 T
715 N
714 A
713 U
661 R
524 O
502 L
419 C
356 P
343 ?
324 M
322 D
197 '
174 Q
152 .
142 _
132 V
122 J
111 ,
85 F
70 H
63 X
63 B
61 G
40 Y
34 "
19 -
12 !
7 )
7 (
4 Z
4 :
3 K
3 *
2 W
2 ;
2 1
1 ]
1 [
657 E
395 S
242 T
228 D
226 P
219 C
216 ES
210 L
189 EN
173 QU
166 RE
165 LE
155 ON
153 N
153 S
152 NT
148 AI
136 M
125 TE
124 T
124 Q
124 E
123 R
121 DE
120 UE
120 IS
115 A
114 OU
114 ER
111 ME
110 ,
109 __
109 CE
105 UR
104 ?
103 A
102 .
100 I
99 J
99 ?
97 AN

...
127 ES
124 QU
105 QUE
97 DE
93 RE
92 LE
82 UE
81 IS
78 NT
76 ___
76 LE
75 ENT
75 PA
75 CE
74 E P
74 DE
72 E D
68 JE
67 NE
67 E C
65 JE
62 CO
61 ?
60 ON
59 LA
55 E S
52 UN
51 ET
51 EST
50 UR
50 ER
50 MA
49 E Q
49 E L
49 CE
49 AIS
48 NS
48 PE
47 LES
47 LA
47 ET

...
58 QUE
39 LES
37 PAS
33 E QUE
33 'EST
31 MENT
31 C'EST
31 QUI
31 C'ES
26 PLUS
25 EMENT
25 DES
23 JE N
22 E NE
21 PLUS
21 DANS
21 CE QU
21 SUR
20 _____
20 MAIS
20 JE NE
20 E DE
19 S PAS
19 QUE J
19 POUR
19 DANS
18 E JE
18 POUR
18 MAIS
18 CELA
17 CELA
17 COMP
17 CE Q
16 UE JE
16 QUE T
16 , JE
16 UNE
15 S DE
15 '?CRI
15 ____
15 M?ME

...
7 L'?CRITURE
7 '?CRITURE
7 INTERNET
6 JE NE SAIS
6 E NE SAIS
6 L'?CRITUR
6 JE NE SAI
5 UJOURD'HUI
5 NE SAIS PA
5 JOURD'HUI
5 E SAIS PAS
5 E L'?CRITU
5 E COMPREND
5 CE QUE JE
5 AUJOURD'HU
5 SAIS PAS
5 PROBL?ME
5 NE SAIS P
5 CE QUE JE
4 __________
4 US SOMMES
4 UR INTERNE
4 SUR INTERN
4 R INTERNET
4 QUE C'EST
4 OUS SOMMES
4 OMPRENDRE
4 OMPL?TEMEN
4 NOUS SOMME
4 MPL?TEMENT
4 LA MANI?RE
4 ES CHOSES
4 E QUI EST
4 E QUE C'ES
4 COMPRENDRE
4 COMPL?TEME
4 CE QUE TU
4 A MANI?RE
4 TOUJOURS
4 SUR INTER
4 QUE C'EST

...

On reconnaît facilement du français dans la colonne 5-grams et dans une moindre mesure dans la colonne 3-grams.

Les séquences de "___" correspondent, je pense, à des séquences de CR-LF, c'est à dire à des sauts de lignes. Le document devait comporter 109 lignes. Je remarque aussi une anomalie dans la traduction du "é" dans "écriture" qui devient "?criture" que je n'explique pas.

 

Le tableau suivant donne accès à l'ensemble des fichiers résultats de cette "étude" :

1-grams 2-grams 3-grams 5-grams 10-grams
file-1u.txt file-2u.txt file-3u.txt file-5u.txt file-10u.txt
file-1uo.txt file-2uo.txt file-3uo.txt file-5uo.txt file-10uo.txt

 

Ces données peuvent aussi être présentées sous forme graphique, ce qui leur donne un aspect très scientifique (de quoi négocier un gros budget de recherche) :

 

 

ma conclusion

Je n'avais jamais jusqu'ici eu l'occasion d'avoir un brevet d'invention entre les mains. Celui-ci, me semble plutôt léger. Il n'y a presque rien dedans et je me demande même s'il serait accepté en France vu qu'il n'invente rien, pratiquement . La méthode n-gram avait déjà été décrite auparavant, dans des articles de revues scientifiques, comme le précise d'ailleurs lui même, le texte du brevet.

Quant à savoir si cette technique est efficace, mon étude est trop superficielle pour le dire. C'est d'abord une méthode statistique. La langue peut elle être enfermée dans une analyse statistique ? C'est une vraie question à laquelle je me garderai de répondre ! Tant de choses, de comportements, se laissent enfermer dans une analyse statistique.

Si je devais pousser plus loin cette étude, je serais tenté de soumettre les derniers romans sortis cette année à un traitement n-gram. Ce serait un autre angle d'approche, une "rupture" dont nous aurions parfois besoin !

J'observe aussi dans cette méthode qu'elle ne peut être pratiquée autrement qu'avec des ordinateurs car elle nécessite de manipuler beaucoup de données. Depuis que ces machines se sont généralisées, une nouvelle manière d'aborder les problèmes techniques est apparue qui consiste à "essayer des trucs". On peut facilement se laisser prendre, une question en entraîne une autre, et c'est sans fin.

 

 

retour ; page echelon ; début de page


me contacter par e-mail jean-claude.devaux (site officiel)

mise à jour le 17/06/2002