Prologue

Bonjour, chers lecteurs. Dans cet article, je vais vous expliquer comment analyser un nombre écrit en russe.

Intelligent, cet analyseur permet d'extraire des nombres du texte avec des erreurs commises à la suite d'une saisie incorrecte ou à la suite de la reconnaissance optique du texte d'une image (OCR).

Pour les paresseux:
Lien vers le projet github: lien .

De l'algorithme au résultat

Cette section décrira les algorithmes utilisés. Attention, beaucoup de lettres!

Énoncé du problème

Au travail, je dois reconnaître le texte d'un document imprimé photographié avec un appareil photo pour smartphone / tablette. En raison de l'accord de non-divulgation, je ne peux pas donner d'exemple de photographie, mais le fait est que le document a un tableau dans lequel certains indicateurs sont écrits en chiffres et en mots, et ces données doivent être lues. L'analyse du texte dans les mots est nécessaire comme outil de validation supplémentaire pour garantir que le numéro est correctement reconnu. Mais, comme vous le savez, l'OCR ne garantit pas une reconnaissance de texte précise. Par exemple, le nombre vingt, écrit en mots, peut être reconnu comme «dvupat» ou même comme «dvupat». Il est nécessaire d'en tenir compte et d'extraire le maximum d'informations, en évaluant l'ampleur de l'erreur possible.

Remarque Pour la reconnaissance de texte, j'utilise tesseract 4. Pour .NET, il n'y a pas de package NuGet prêt à l'emploi de la quatrième version, donc j'en ai créé un à partir de la branche principale du projet, qui peut être utile: Genesis.Tesseract4 .

Algorithme de base d'analyse des nombres

Commençons par un simple, à savoir avec un algorithme de reconnaissance de texte écrit en mots, jusqu'à présent sans erreurs. Si vous êtes intéressé par l'analyse intelligente, ignorez cette section.

Je ne suis pas particulièrement doué pour la recherche sur Google, donc je n'ai pas immédiatement trouvé d'algorithme prêt à l'emploi pour résoudre ce problème. Cependant, c'est encore mieux, car un algorithme inventé par nous-mêmes donne plus de place au codage. Et la tâche elle-même s'est avérée intéressante.

Prenons donc un petit nombre, par exemple, «cent vingt-trois». Il se compose de trois mots ( jetons ), chacun correspondant à un nombre, tous ces nombres se résument:

Jusqu'à présent, tout est simple, mais nous creusons plus profondément, par exemple, considérons le nombre «deux cent douze mille cent cinq».

Comme vous pouvez le voir, lorsqu'il y a des milliers dans le nombre (ainsi que des millions et d'autres degrés de mille), le nombre est divisé en parties constituées d'un petit nombre local, dans l'exemple ci-dessus - 212, et d'un facteur (1000). Il peut y avoir plusieurs de ces fragments, mais ils vont tous dans l'ordre décroissant du facteur, par exemple, mille ou mille ne peuvent pas suivre mille. Cela est également vrai pour des parties d'un petit nombre, car des centaines ne peuvent pas suivre des centaines et des dizaines de dizaines, donc l'entrée «cent cinq cents» est incorrecte. Nous appellerons une caractéristique qui relie deux jetons du même type un niveau , par exemple, les jetons «cent» et «trois cents» ont un niveau, et il est supérieur au jeton «cinquante».

De ces considérations naît l'idée d'un algorithme. Écrivons tous les jetons ( échantillons ) possibles, chacun d'eux assignera un numéro, ainsi que deux paramètres - le niveau et le signe du multiplicateur.

En fait, vous pouvez ajouter d'autres jetons à ce tableau, y compris pour les langues étrangères, mais n'oubliez pas que dans certains pays, un système de nommage long plutôt qu'un court est utilisé .

Passons maintenant à l'analyse. Nous obtiendrons quatre quantités:

1. Niveau global (globalLevel). Indique le niveau du dernier multiplicateur. Initialement indéfini et nécessaire pour le contrôle. Si nous rencontrons un jeton multiplicateur dont le niveau est supérieur ou égal au global, alors c'est une erreur.
2. Valeur globale (globalValue). Additionneur total, où le résultat est le résultat de la multiplication du nombre et du facteur locaux.
3. Niveau local (localLevel). Indique le niveau du dernier jeton. Initialement indéfini, fonctionne de manière similaire au niveau global, mais est réinitialisé après la découverte du multiplicateur.
4. Valeur locale (localValue) Un additionneur de jeton non multiplicateur, c'est-à-dire numéros jusqu'à 999.

L'algorithme est le suivant:

1. Divisez la chaîne en jetons en utilisant le régulier "\ s +".
2. Nous prenons le jeton suivant, nous obtenons des informations à ce sujet à partir de l'échantillon.
3. S'il s'agit d'un multiplicateur:
   
   • Si le niveau global est défini, nous nous assurons qu'il est supérieur ou égal au niveau du jeton. Sinon, il s'agit d'une erreur; le numéro est incorrect.
   • Définissez le niveau global au niveau du jeton actuel.
   • Multipliez la valeur du jeton par la valeur locale et ajoutez le résultat à la valeur globale.
   • Nous effaçons la valeur et le niveau locaux.
4. Si ce n'est pas un multiplicateur:
   
   • Si le niveau local est défini, nous nous assurons qu'il est supérieur ou égal au niveau du jeton. Sinon, il s'agit d'une erreur; le numéro est incorrect.
   • Définissez le niveau local au niveau du jeton actuel.
   • Ajoutez la valeur du jeton à la valeur locale.
5. Nous renvoyons le résultat comme la somme des valeurs globales et locales.

Un exemple de travail pour le nombre «deux millions deux cent douze mille cent quatre-vingt-cinq».

Le résultat sera le 2.212.185.

Analyse intelligente

Cet algorithme peut être utilisé pour implémenter d'autres comparaisons, et pas seulement pour l'analyse des nombres, c'est pourquoi je vais essayer de le décrire plus en détail.

Avec l'analyse du nombre correctement écrit compris. Réfléchissons maintenant aux erreurs qui peuvent se produire si le nombre obtenu à la suite de l'OCR est mal écrit. Je ne considère pas d'autres options, mais vous pouvez modifier l'algorithme pour une tâche spécifique.

J'ai identifié trois types d'erreurs que j'ai rencontrées au cours du travail:

1. Remplacez les caractères par d'autres avec un style similaire. Par exemple, la lettre «c» est pour une raison quelconque remplacée par «p», et «n» par «et» et vice versa. Lorsque vous utilisez la troisième version de tesseract, il est possible de remplacer la lettre «o» par zéro. Ces erreurs sont les plus courantes et nécessitent un réglage pour une bibliothèque de reconnaissance spécifique. Ainsi, les principes de fonctionnement des versions 3 et 4 de tesseract ont des différences cardinales, donc les erreurs y seront différentes.
   
2. Fusion de jetons. Les mots peuvent fusionner (n'ont pas encore rencontré le contraire). En combinaison avec la première erreur, il génère des phrases démoniaques telles que "double one". Essayons également de diaboliser ces monstres.
   
3. Bruit - caractères et phrases laissés dans le texte. Malheureusement, il n'y a pas grand-chose à faire pour le moment, mais il existe une perspective pour la collecte de statistiques suffisamment importantes.
   

Dans le même temps, l'algorithme d'analyse décrit ci-dessus ne change presque pas, la principale différence est de diviser la chaîne en jetons.

Mais commençons par collecter des statistiques sur l'utilisation des lettres dans les jetons. Sur les 33 lettres de la langue russe, seulement 20 sont utilisées lors de l'écriture d'entiers non négatifs, appelons-les de bonnes lettres :

Les 13 autres, respectivement, seront appelés mauvaises lettres . La taille maximale du jeton est de 12 caractères (13 en comptant pour le quadrillion). Les sous-chaînes plus longues que cette valeur doivent être divisées.

Pour comparer les chaînes et les jetons, j'ai décidé d'utiliser l'algorithme de Wagner-Fisher , bien que je l'appelle le nom de Levenshtein dans le code. Je n'ai pas besoin d'instructions éditoriales, j'ai donc implémenté une version mémoire de l'algorithme. Je dois admettre que la mise en œuvre de cet algorithme s'est avérée être une tâche plus difficile que l'analyseur lui-même.

Un petit programme éducatif: la distance Levenshtein est un cas particulier de l'algorithme de Wagner-Fisher, lorsque le coût d'insertion, de suppression et de remplacement de caractères est statique. Ce n'est pas le cas dans notre tâche. Évidemment, si nous trouvons une mauvaise lettre dans une sous-chaîne, alors elle doit être remplacée par une bonne lettre, mais remplacer un bon par une mauvaise est extrêmement indésirable. D'une manière générale, c'est impossible, mais la situation dépend de la tâche spécifique.

Pour décrire le coût d'insertion, de suppression et de remplacement de caractères, j'ai créé un tableau comme celui-ci: un lien vers un tableau avec des poids . Bien qu'il soit rempli avec la méthode des trois P (sexe, doigt, plafond), mais si vous le remplissez avec des données basées sur les statistiques OCR, vous pouvez améliorer considérablement la qualité de la reconnaissance des nombres. Le code de bibliothèque contient le fichier de ressources NumeralLevenshteinData.txt, dans lequel vous pouvez insérer des données d'une table similaire à l'aide de Ctrl + A, Ctrl + C et Ctrl + V.

Si un caractère non-table est trouvé dans le texte, par exemple zéro, le coût de son insertion est égal à la valeur maximale de la table, et le coût de la suppression et du remplacement est égal au minimum, donc l'algorithme est plus susceptible de remplacer zéro par la lettre «o», et si vous utilisez la troisième version de tesseract , il est alors logique d'ajouter zéro au tableau et d'écrire le prix minimum pour le remplacer par la lettre «o».

Nous avons donc préparé les données pour l'algorithme de Wagner-Fisher, apportons des modifications à l'algorithme pour diviser la chaîne en jetons. Pour ce faire, nous effectuerons une analyse supplémentaire de chaque jeton, mais avant cela, nous développerons les informations sur le jeton avec les caractéristiques suivantes:

• Niveau d'erreur . Un nombre réel de 0 (pas d'erreur) à 1 (le jeton est incorrect), ce qui signifie à quel point le jeton a été comparé à l'échantillon.
  
• Un signe d'utilisation d'un jeton . Lors de l'analyse d'une chaîne avec des débris entrecoupés, une partie des jetons sera rejetée, car cet attribut ne sera pas défini. Dans ce cas, la valeur d'erreur totale sera considérée comme la moyenne arithmétique des erreurs des jetons utilisés.
  

Algorithme d'analyse de jeton:

1. Nous essayons de trouver le jeton dans le tableau tel quel. Si nous trouvons - tout va bien, retournez-le.
2. Sinon, faites une liste des options possibles:

3. Nous essayons de faire correspondre le jeton avec l'échantillon en utilisant l'algorithme de Wagner-Fisher. Cette option se compose d'un jeton (échantillon mappé) et son erreur est égale à la meilleure distance divisée par la longueur de l'échantillon.

   
   Exemple: le jeton «zéro» est comparé à l'échantillon «zéro», tandis que la distance est de 0,5, car le coût de remplacement de la mauvaise lettre «y» par un bon «o» est de 0,5. L'erreur totale pour ce jeton sera de 0,5 / 4 = 0,125.
   

4. Si la sous-chaîne est suffisamment grande (j'ai 6 caractères), nous essayons de la diviser en deux parties d'au moins 3 caractères chacune. Pour une chaîne de 6 caractères, il y aura une seule division: 3 + 3 caractères. Pour une chaîne de 7 caractères - il y a déjà deux options, 3 + 4 et 4 + 3, etc. Pour chacune des options, nous appelons récursivement la même fonction d'analyse de jeton, nous entrons les options reçues dans la liste.

   
   

   Afin de ne pas mourir en récurrence, nous déterminons le niveau maximum d'échec. En outre, les options obtenues à la suite de la division sont artificiellement dégradées d'un certain montant (option, par défaut 0,1), de sorte que l'option de comparaison directe a plus de valeur. J'ai dû ajouter cette opération, car les sous-étapes du type "double" ont été divisées avec succès en jetons "deux" et "cinq", et n'ont pas été réduites à "vingt". Hélas, ce sont les caractéristiques de la langue russe.

   
   

   Exemple: le jeton «double» a une comparaison directe avec l'échantillon «vingt», erreur 0,25. De plus, la meilleure option pour diviser est «deux» + «cinq» avec un coût de 0,25 (en remplaçant «a» par «i»), aggravé artificiellement à 0,35, ce qui fait que le jeton «vingt» est préféré.

   
   
5. Après avoir compilé toutes les options, nous sélectionnons la meilleure par le minimum d'erreurs des jetons qui y participent. Le résultat est renvoyé.

De plus, la vérification des jetons est introduite dans l'algorithme de génération de nombres principal afin que leur erreur ne dépasse pas une certaine valeur (option, par défaut 0,67). Avec cela, nous éliminons les déchets potentiels, mais pas avec beaucoup de succès.

L'algorithme en bref pour ceux qui étaient trop paresseux pour lire le texte ci-dessus

Nous divisons la chaîne d'entrée représentant le nombre de mots en sous-chaînes en utilisant le \ s + régulier, puis nous essayons de faire correspondre chaque sous-chaîne avec des exemples de jetons ou de la diviser en sous-chaînes plus petites, en choisissant les meilleurs résultats. En conséquence, nous obtenons un ensemble de jetons par lequel nous générons un nombre, et la valeur d'erreur est prise comme la moyenne arithmétique des erreurs parmi les jetons utilisés dans la génération.

Affiner un algorithme pour une tâche spécifique

Dans ma tâche, les nombres sont non négatifs et relativement petits, donc j'exclurai les jetons inutiles du "million" et plus. Pour le test, chers lecteurs, au contraire, j'ai ajouté des jetons de jargon supplémentaires, qui permettaient d'analyser des chaînes telles que "cinq pièces", "tondre deux cents" et même "trois stolniks et deux pièces d'or". C'est drôle, mais cela n'a même pas nécessité de modifications de l'algorithme.

Nouvelle amélioration

L'algorithme existant a des défauts:

1. Contrôle de cas. Les chaînes "deux mille" et "deux mille" seront reconnues avec une erreur nulle comme 2000. Dans ma tâche, le contrôle de cas n'est pas requis, il est même dangereux, mais si vous avez besoin d'une telle fonction, cela est résolu en introduisant un drapeau supplémentaire dans le jeton qui est responsable du cas du prochain jeton .
   
2. Nombres négatifs. Un jeton négatif supplémentaire est introduit avec un traitement spécial. Rien de compliqué, mais n'oubliez pas que la lettre «y» est mauvaise et n'apparaît pas dans les chiffres, vous devrez changer ses caractéristiques de poids ou espérer qu'elle ne change pas pendant le processus OCR.
   
3. Nombres fractionnaires. Il est résolu en remplaçant le type long par un double et en introduisant des jetons "dixièmes", "centièmes", etc ... N'oubliez pas de réviser l'échelle des lettres.
   
4. Reconnaissance des numéros saisis par les utilisateurs. Parce que lors de la saisie manuelle de texte, nous faisons le plus souvent des erreurs liées à la réédition de siVMolov, vous devez ajouter cette opération à l'algorithme de Wagner-Fisher.
   
5. Prise en charge d'autres langues. Nous introduisons de nouveaux jetons, élargissons le tableau des poids.
   
6. Manipulation des ordures. Dans certains documents, les données sont imprimées, la qualité de l'image peut être médiocre, la cellule peut être vide et banale. Dans ce cas, les ordures qui doivent être nettoyées entrent d'une manière ou d'une autre dans la ligne. Le mieux que je puisse offrir pour le moment est de prétraiter le document avant l'OCR. Supprimer les lignes du tableau et les remplir avec une couleur proche de la couleur de l'espace libre de la cellule m'a beaucoup aidé. Cela n'a pas résolu tous les problèmes, mais a amélioré la qualité de la reconnaissance du texte des documents où le tableau avait des courbures en raison des ecchymoses du document ou d'un photographe tordu. Idéalement, vous devez faire pivoter la cellule elle-même et la reconnaître séparément, si vous avez bien sûr une table.
   

Alors, quel est le résultat net?

Le projet contient un exemple d'application console exécutée dans le fichier samples.txt avec des exemples pour l'analyseur. Voici une capture d'écran des résultats:

Je vous charge d'évaluer le résultat, mais moi, ce n'est pas mal. L'erreur pour les exemples de reconnaissance réels ne dépasse pas 0,25, bien que je n'aie pas encore exécuté l'ensemble des documents disponibles, tout ne sera probablement pas si fluide là-bas.

Quant à la dernière section, je me demandais toujours à quel point c'est «dofiga». En outre, le programme s'est donné une réponse adéquate, combien devrait être pris sur un personnel (je n'utilise pas, mais quand même) et a même déterminé avec précision la signification du vieux mot russe "obscurité". Et oui, la conclusion ne comprenait pas encore une autre mesure que l'éducation ne permettait pas d'ajouter, mais le programme estime qu'elle est égale à mille =)

Quelques mots sur la bibliothèque

Au départ, mes projets ne prévoyaient pas la création d'une bibliothèque, j'ai décidé de la concevoir exclusivement pour un Habr. J'ai essayé de mettre le code dans l'ordre, mais si vous l'utilisez, faites un fork ou une copie, comme vous n'aurez probablement pas besoin de jargon et d'autres jetons inclus dans les exemples.

La bibliothèque elle-même est écrite sous .NET Standart 2.0 et C # 7.x, et les algorithmes sont facilement traduits dans d'autres langues.

En cas d'expansion possible de la bibliothèque, j'ajouterai la composition des composants importants de l'analyseur numérique en mots (espace de noms Genesis.CV.NumberUtils):

• RussianNumber.cs - analyseur directement
• RussianNumber.Data.cs - fichier avec description des jetons
• RussianNumber.ToString.cs - convertisseur de nombre en texte en mots
• RussianNumberParserOptions.cs - options de l'analyseur
• NumeralLevenshtein.cs - implémentation de l'algorithme de Wagner-Fisher
• NumeralLevenshteinData.txt - ressource, données de pondération des lettres

Utilisation:

• RussianNumber.ToString (valeur) - convertir un nombre en texte
• RussianNumber.Parse (valeur, [options]) - convertit le texte en nombre

Conclusion

J'espère vraiment que l'article ne vous a pas semblé ennuyeux malgré l'abondance de texte. Récemment, j'ai trouvé beaucoup de sujets liés à la vision par ordinateur, sur lesquels il y a quelque chose à dire, donc je voudrais avoir une opinion sur ce format d'articles. Que vaut-il la peine d'ajouter ou, inversement, de supprimer? Qu'est-ce qui vous intéresse le plus, lecteurs, les algorithmes eux-mêmes ou les fragments de code?

Aimez-vous l'article? Découvrez les autres:

• Prise en charge de la sérialisation JavaScript de classe JavaScript
  
• Remplir des modèles de texte avec des données basées sur un modèle. Implémentation .NET à l'aide de fonctions de bytecode dynamique (IL)