Idée et objectifs

Mon idée est d'exploiter la catégorie générale des caractère telles que définies dans la norme Unicode pour détecter les frontières des mots. Une rupture dans la catégorie des caractères indiquant vraisemblablement un changement de mot.

Je souhaite que mon composant soit en mesure d'identifier correctement tous les mots détectés par le WhitespaceTokenizer (c'est un minimum), ainsi que les cas problématiques tels que :

  • les articles et pronoms contractés (l', d', j', m', ...)
  • les composés lexicaux à apostrophe (aujourd'hui, ...)
  • les composés lexicaux à traits d'union (arc-en-ciel, peut-être, sauve-qui-peut, ...)
  • les valeurs numériques (14 000, 14,18, 30 %, ...)
  • les acronymes (ASSEDIC, ASCII, ...) et les sigles (C-4, c-à-d, i.e., ...)
  • les unités de mesure (A/m, km/h, ...)

Mise en œuvre

Catégories générales des caractères unicodes

La norme unicode offre sept catégories générales de caractère :

UnicodeJava (getType)
les lettres (L)
Ll LOWERCASE_LETTER
LuUPPERCASE_LETTER
LmMODIFIER_LETTER
LoOTHER_LETTER
LtTITLECASE_LETTER
les marques (M)
McCOMBINING_SPACING_MARK
MeENCLOSING_MARK
MnNON_SPACING_MARK
les nombres (N)
NdDECIMAL_DIGIT_NUMBER
NlLETTER_NUMBER
NoOTHER_NUMBER
les ponctuations (P)
PcCONNECTOR_PUNCTUATION
PdDASH_PUNCTUATION
PeEND_PUNCTUATION
PiINITIAL_QUOTE_PUNCTUATION
PfFINAL_QUOTE_PUNCTUATION
PoOTHER_PUNCTUATION
PsSTART_PUNCTUATION
les symboles (S)
ScCURRENCY_SYMBOL
SmMATH_SYMBOL
SkMODIFIER_SYMBOL
SoOTHER_SYMBOL
les séparateurs (Z)
ZlLINE_SEPARATOR
ZpPARAGRAPH_SEPARATOR
ZsSPACE_SEPARATOR
divers (C)
CcCONTROL
CfFORMAT
CoPRIVATE_USE
CsSURROGATE
CnUNASSIGNED

Le site Fileformat fournit une liste et une description exhaustive des caractères contenus dans ces différentes catégories.

Description des mots

Mots pleins

Les mots pleins sont ceux qui se composent uniquement d'une suite de caractères alphanumériques, on peut les reconnaître à l'aide de l'automate suivant :

fsm-motsimple.png

Le cas de l'apostrophe

Les articles et pronoms contractés précédent un autre mot, ils se composent d'une seule lettre et d'un apostrophe. Les apostrophes appartiennent à la catégorie Po qui contient également le point d'exclamation, le dièse, ... ou bien à Lm. Il est préférable d'établir une liste des caractères correspondant. L'apostrophe (U+0027) et le modifieur apostrophe (U+02BC) sont les deux caractères qui semblent correspondre pour le français.

Les composés lexicaux à apostrophe sont quant à eux formés de deux séquences alphabétiques connectées par un apostrophe (aujourd'hui, ...).

L'automate permettant de reconnaître ces deux formes de mots :

fsm-apostrophe.png

Le cas du trait d'union

Le trait d'union est utilisé dans plusieurs configurations : pour les composés lexicaux (arc-en-ciel, peut-être, sauve-qui-peut, ...) et certains sigles sigles (C-4, c-à-d, ...). D'une manière générale certaines ponctuations sont employées au sein des mots : le point pour les abréviations (i.e., M., ...), ou le slash pour les unités de mesure (A/m, km/h, ...).

Les traits d'union sont regroupés dans la catégorie ''Punctuation, dash'' (''Pd''), les autres ponctuations (slash et point) sont placées dans ''Punctuation, other'' (''Po''). L'important c'est que ladite ponctuation soit placée entre deux séquences de lettres :

fsm-union.png

Les valeurs numériques particulières

Finalement le dernier cas particulier concerne les valeurs numériques complexes (14 000, 14,18, 30 %, -3, ...). La catégorie ''Symbol, Currency'' (''Sc'') nous intéresse particulièrement. Le symbole ''%'' se trouve dans la catégorie ''Punctuation, other' (''Po''), tandis que le point et la virgule décimale correspondent respectivement à U+002E et U+002C.

fsm-decimal.png

Algorithmie

La tokenisation s'effectue sur un flux continue de caractères. L'utilisation d'automates classiques tels que présentés précédemment n'est pas forcément possible car l'utilisation commune ne correspond pas forcément à une grammaire régulière et ils sont non déterministes. En gros nous pouvons nous retrouver dans ces cas de figure :

  • Parfois l'espace sépare un mot, parfois il est contenu au sein d'un mot (entre le nombre et la monnaie par exemple) ;
  • Parfois le passage d'un mot à un autre se fait en consommant un ou plusieurs caractères (espace), parfois le caractère de séparation appartient à l'un des deux mots (apostrophe) ;
  • La consommation d'un caractère inattendu ne doit pas interrompre le fonctionnement : une décision doit être prise (couper le mot ou pas).

Ma proposition consiste à mettre en œuvre une sorte de transducteur à pile. La pile permet uniquement de conserver un historique des derniers caractères consommés afin de découper les mots à une position antérieure si nécessaire (symbole de monnaie non trouvé mais espace consommé par exemple). L'utilisation d'un transducteur permet d'enovyer des signaux indiquant si une coupure de mot doit avoir lieu ou non.

Les signaux envoyés par le système peuvent être les suivants :

  • start_word un nouveau mot commence ;
  • end_word le mot courant se termine, le caractère juste consommé n'en faisant pas parti ;
  • end_words_prev le mot courant se termine au caractère anté-précédent ;
  • switch_word le mot courant se termine sur le caractère consommé, le caractère courant appartient à un nouveau mot ;
  • switch_word_prev le mot courant se termine au caractère anté-précédent, le caractère courant appartient à un nouveau mot ;
  • nop aucune opération

L'automate ci-dessous correspond à ce transducteur :

  • les états en N (orange) correspondent à l'automate de reconnaissance des valeurs numériques ;
  • les états en L (bleu) correspondent à une combinaison des automates de reconnaissance des mots alphabétiques ;
  • les transitions en rouge correspondent aux cas d'erreur où il faut prendre une décision ;
  • les transitions en vert correspondent aux cas attendus de changement de mot.

fsm-complete.png

Implémentation

J'ai recherché une bibliothèque Java pour manipuler des transducteurs... mais je n'ai rien trouvé. J'ai donc tout implémenté manuellement ce qui n'est pas formidable pour le maintient du code. J'ai donc implémenté également plusieurs tests unitaires.

Au final, les cas où les symboles monnétaires sont espacés des nombres par un espace pose problème, mais j'ai choisi de laisser tel quel car je ne vois pas de solution pratique (je ne vois plus grand chose en fait).

Chose intéressante, mon implémentation à base de transducteur est plus rapide de près de 40% que le composant WhitespaceTokenizer sur un petit corpus de test, mais d'autres tests donnent les deux annotateurs ex-aequo. La qualité du résultat est sans comparaison, comme l'illustre l'exemple ci-dessous :

 "Le Roi a reçu en audience en début d’après-midi au Château

Résultat du WhitespaceTokenizer : {", Le, Roi, a, reçu, en, audience, en, début, d, ’, après, -, midi, au, Château}

Résultat de notre composant : {", Le, Roi, a, reçu, en, audience, en, début, d’, après-midi, au, Château}

Distribution

Les jar avec les sources et le descripteur sont disponibles ici.

J'ai également ouvert un dépôt sur github pour ceux qui voudraient contribuer.