Comment nous avons créé une segmentation de mots instantanée avec Rust

Pour suggérer et générer de nouvelles idées de noms de domaine, nous devons pouvoir identifier les mots qui composent un nom de domaine. La segmentation de mots est une technique de traitement automatique du langage, généralement employée pour trouver les mots dans des chaînes écrites dans des langues sans séparation naturelle entre les mots, comme le chinois ou le japonais. Nous utilisons cette technique pour trouver les mots « Instant Domain Search » dans des domaines comme instantdomainsearch.com. La bibliothèque Python wordsegment résout ce problème, mais nous avons dû la porter en Rust pour la rendre suffisamment rapide pour Instant Domain Search.

Wordsegment se fonde sur l’exemple de segmentation de mots de Peter Norvig dans Beautiful Data. L’idée centrale consiste à parcourir toutes les segmentations possibles d’une chaîne et à les noter selon leur probabilité d’apparaître dans un texte réel. Cela demande deux éléments :

• Une manière d’estimer la probabilité qu’une phrase apparaisse dans le monde réel.
• Une manière efficace de noter toutes les segmentations possibles de la chaîne d’entrée.

Voyons le fonctionnement de chacun.

Noter une phrase

La méthode la plus simple consiste à noter les mots isolés selon leur probabilité d’apparaître dans des données anglaises du monde réel ; Norvig utilisait un jeu de données Google appelé Google Trillion Web Corpus (2006). La collection Web 1T est publiquement disponible uniquement à des fins de recherche et d’enseignement, et c’est celle que j’ai d’abord utilisée pour notre portage.

Pour obtenir le score d’apparition d’un mot isolé, divisez le nombre d’occurrences de ce mot dans le corpus par le nombre total d’occurrences de mots. Par exemple, le mot « instant » apparaît environ 28 millions de fois dans Web 1T. Le corpus utilisé contient environ 588 milliards de mots au total, puisqu’il ne contient pas la longue traîne des mots rares ; nous attribuons donc à « instant » une probabilité de 0.000049. Il faut aussi noter les mots absents du corpus ; consultez le chapitre de Norvig pour les détails.

L’étape suivante consiste à noter une suite de mots. Nous pourrions multiplier les probabilités de tous les mots de la phrase d’entrée. Pour éviter les erreurs arithmétiques dues à la multiplication d’une série de petits nombres, nous prenons plutôt le logarithme en base 10 de chaque valeur et additionnons les résultats. Pour « this is a test », cela donne -2.3 + -2.1 + -1.8 + -3.6 = -9.7. À l’inverse, appliquer la formule aux mots introuvables dans le corpus donne -22 pour « thisisatest ».

Pour affiner les résultats, nous considérons aussi, comme Norvig, les bigrammes : la probabilité conditionnelle que deux mots apparaissent côte à côte. Pour chaque mot qui n’est pas au début de la chaîne, au lieu de considérer sa simple probabilité d’apparition, nous considérons la probabilité qu’il apparaisse après le mot précédent. Avec le corpus original, nous attribuons à « is » après « this » le score -3.2 plutôt que -2.1, ce qui nous permet d’utiliser le contexte pour améliorer les scores.

Énumérer les segmentations

Pour les chaînes courtes, nous voulons énumérer toutes les segmentations possibles afin de trouver la séparation dont le score est optimal. Cependant, le nombre de segmentations augmente de façon exponentielle avec la longueur de la chaîne, ce qui rend cette approche impossible pour les chaînes longues. Les mots très longs sont aussi de moins en moins probables. Nous commençons donc par définir une longueur maximale de mot de 24 caractères. Nous séparons ensuite la chaîne d’entrée à chacune des 24 premières limites de caractères et ajoutons le score du premier mot à celui des mots restants.

Norvig utilisait la récursion, et nous avons suivi cette approche dans les premières versions du portage Rust. Nous avons récemment modifié l’implémentation d’après l’article de Wolf Garbe, Fast Word Segmentation of Noisy Text. Nous utilisons désormais une variante de l’algorithme de matrice triangulaire présenté dans cet article. Notre implémentation utilise un tableau de taille dynamique, le Vec de Rust, pour suivre le meilleur score à chaque position de segmentation. Par exemple, pour « thisisatest », le candidat de la position 6, après « is », aurait une longueur de 2 et le score de « this is ». Cette approche borne la taille de pile, et les boucles imbriquées me semblent plus faciles à comprendre que la récursion bornée. Nous avons adapté l’approche de matrice triangulaire pour utiliser les scores de bigrammes.

Optimisations de performance

Sur ma machine, la bibliothèque Python wordsegment peut segmenter « thisisatest » une fois toutes les 500 µs. La dernière version d’instant-segment effectue la même tâche en 4 µs, soit 95 fois plus vite, pour le même travail. Voici quelques techniques utilisées.

• Le portage initial n’était que 1,7 fois plus rapide que le code Python. Il employait l’approche récursive de wordsegment et du code de Norvig pour énumérer les segmentations, ainsi qu’une table de hachage pour mettre en cache les scores partiels. Il est par exemple plus rapide de calculer « thisis a test » et « this is a test » si vous réutilisez le score de « a test ».
• Éviter certaines allocations inutiles dans la boucle principale et passer à l’algorithme ahash pour le cache a porté la performance à 4,9 fois Python.
• La crate smartstring évite les allocations sur le tas pour les chaînes courtes, ce qui convient bien puisque les mots sont généralement courts. Cela a porté la performance à 9 fois Python.
• L’intégration en ligne de la boucle principale qui produit les positions de segmentation nous a amenés à 11 fois Python.
• Éviter les allocations répétées des résultats intermédiaires nous a permis d’atteindre 12 fois Python.
• Les chaînes Rust sont encodées en UTF-8 ; les tranches doivent donc valider les positions. instant-segment rejette les chaînes contenant des entrées non ASCII, et quelques utilisations de code unsafe pour contourner la validation Unicode ont amélioré la performance jusqu’à 15 fois.
• La mise à jour d’ahash vers une version plus récente a permis d’atteindre 18 fois.
• Remplacer f64::powf() par f64::powi() a permis d’atteindre 19 fois.
• La réutilisation d’allocations intermédiaires, lorsque plusieurs segmentations se suivent, a permis d’atteindre 25 fois la vitesse de Python.
• Enfin, l’adoption de l’approche de matrice triangulaire a permis d’atteindre 95 fois.

instant-segment

Nous avons publié ce travail en open source, et la dernière version d’instant-segment est disponible sur crates.io. Cette année, nous avons ajouté des liaisons Python grâce à l’excellent PyO3 et mis à jour le jeu de données de test distribué avec notre dépôt afin de nous appuyer sur des jeux de données plus récents et aux licences plus libres de Google et du projet SCOWL. Il est donc plus simple que jamais de commencer avec instant-segment. Nous aimerions avoir vos retours sur le projet et savoir comment vous l’utilisez !