Prolog

Guten Tag, liebe Leser. In diesem Artikel werde ich darüber sprechen, wie man eine Zahl analysiert, die in russischen Wörtern geschrieben ist.

Smart Dieser Parser ermöglicht das Extrahieren von Zahlen aus Text mit Fehlern, die durch falsche Eingabe oder durch optische Erkennung von Text aus einem Bild (OCR) verursacht wurden.

Für die Faulen:
Link zum Github-Projekt: Link .

Vom Algorithmus zum Ergebnis

In diesem Abschnitt werden die verwendeten Algorithmen beschrieben. Achtung, viele Briefe!

Erklärung des Problems

Bei der Arbeit muss ich Text aus einem gedruckten Dokument erkennen, das mit einer Smartphone- / Tablet-Kamera fotografiert wurde. Aufgrund der Geheimhaltungsvereinbarung kann ich kein Beispiel für ein Foto geben, aber der Punkt ist, dass das Dokument eine Tabelle enthält, in der bestimmte Indikatoren in Zahlen und Worten geschrieben sind und diese Daten gelesen werden müssen. Das Parsen von Text in Wörtern ist als zusätzliches Validierungswerkzeug erforderlich, um sicherzustellen, dass die Nummer korrekt erkannt wird. Wie Sie wissen, garantiert OCR jedoch keine genaue Texterkennung. Zum Beispiel kann die in Worten geschriebene Zahl zwanzig als "dvupat" oder sogar als "dvupat" erkannt werden. Es ist notwendig, dies zu berücksichtigen und die maximale Informationsmenge zu extrahieren, um die Größe des möglichen Fehlers zu bewerten.

Hinweis Für die Texterkennung verwende ich tesseract 4. Für .NET gibt es kein fertiges NuGet-Paket der vierten Version, daher habe ich eines aus dem Hauptprojektzweig erstellt, das nützlich sein kann: Genesis.Tesseract4 .

Grundlegender Algorithmus zum Parsen von Zahlen

Beginnen wir mit einem einfachen, nämlich mit einem in Worten geschriebenen Texterkennungsalgorithmus, der bisher fehlerfrei war. Wenn Sie an Smart Parsing interessiert sind, überspringen Sie diesen Abschnitt.

Ich kann nicht besonders gut googeln, daher habe ich nicht sofort einen vorgefertigten Algorithmus zur Lösung dieses Problems gefunden. Dies ist jedoch sogar zum Besseren, weil Ein von uns erfundener Algorithmus bietet mehr Raum für die Codierung. Und die Aufgabe selbst erwies sich als interessant.

Nehmen wir also eine kleine Zahl, zum Beispiel "einhundertdreiundzwanzig". Es besteht aus drei Wörtern ( Token ), von denen jedes einer Zahl entspricht. Alle diese Zahlen werden zusammengefasst:

Bisher ist alles einfach, aber wir graben tiefer, zum Beispiel betrachten wir die Zahl "zweihundert, zwölftausend, einhundertfünf".

Wie Sie sehen können, wird die Zahl bei Tausenden in der Zahl (sowie Millionen und anderen Graden von Tausend) in Teile unterteilt, die aus einer lokalen kleinen Zahl im obigen Beispiel - 212 und einem Faktor (1000) bestehen. Es kann mehrere solcher Fragmente geben, aber alle gehen in absteigender Reihenfolge des Multiplikators vor, zum Beispiel können tausend oder eintausend nicht tausend folgen. Dies gilt auch für Teile einer kleinen Anzahl, da Hunderte nicht Hunderten und Zehntausenden folgen können, sodass der Eintrag „einhundertfünfhundert“ falsch ist. Wir werden ein Merkmal, das zwei Token desselben Typs in Beziehung setzt, als Stufe bezeichnen . Beispielsweise haben die Token „einhundert“ und „dreihundert“ eine Stufe und sind größer als die Marke „fünfzig“.

Aus diesen Überlegungen entsteht die Idee eines Algorithmus. Schreiben wir alle möglichen Token ( Samples ) auf, denen wir jeweils eine Zahl zuweisen, sowie zwei Parameter - den Pegel und das Vorzeichen des Multiplikators.

Sie können dieser Tabelle auch andere Token hinzufügen, auch für Fremdsprachen. Vergessen Sie jedoch nicht, dass in einigen Ländern eher ein langes als ein kurzes Benennungssystem verwendet wird .

Fahren wir nun mit dem Parsen fort. Wir erhalten vier Mengen:

1. Globale Ebene (globalLevel). Zeigt den Pegel des letzten Multiplikators an. Anfangs undefiniert und zur Kontrolle notwendig. Wenn wir auf ein Multiplikator-Token stoßen, dessen Pegel größer oder gleich dem globalen ist, ist dies ein Fehler.
2. Globaler Wert (globalValue). Der Gesamtaddierer, wobei das Ergebnis das Ergebnis der Multiplikation der lokalen Zahl und des Faktors ist.
3. Lokale Ebene (localLevel). Gibt an, welche Stufe der letzte Token hatte. Anfänglich undefiniert, funktioniert ähnlich wie auf globaler Ebene, wird jedoch nach der Ermittlung des Multiplikators zurückgesetzt.
4. Lokaler Wert (localValue) Ein Nicht-Multiplikator-Token-Addierer, d.h. Zahlen bis zu 999.

Der Algorithmus ist wie folgt:

1. Teilen Sie die Zeichenfolge mit dem regulären "\ s +" in Token auf.
2. Wir nehmen das nächste Token und erhalten Informationen darüber aus dem Beispiel.
3. Wenn es ein Multiplikator ist:
   
   • Wenn die globale Ebene festgelegt ist, stellen wir sicher, dass sie größer oder gleich der Ebene des Tokens ist. Wenn nicht, ist dies ein Fehler, die Nummer ist falsch.
   • Stellen Sie die globale Ebene auf die Ebene des aktuellen Tokens ein.
   • Multiplizieren Sie den Wert des Tokens mit dem lokalen Wert und addieren Sie das Ergebnis zum globalen Wert.
   • Wir löschen den lokalen Wert und das Niveau.
4. Wenn dies kein Multiplikator ist:
   
   • Wenn die lokale Ebene festgelegt ist, stellen wir sicher, dass sie größer oder gleich der Ebene des Tokens ist. Wenn nicht, ist dies ein Fehler, die Nummer ist falsch.
   • Stellen Sie die lokale Ebene auf die Ebene des aktuellen Tokens ein.
   • Fügen Sie den Token-Wert zum lokalen Wert hinzu.
5. Wir geben das Ergebnis als Summe der globalen und lokalen Werte zurück.

Ein Arbeitsbeispiel für die Zahl "zwei Millionen zweihundertzwölftausendeinhundertfünfundachtzig".

Das Ergebnis ist 2.212.185.

Intelligentes Parsen

Dieser Algorithmus kann verwendet werden, um andere Vergleiche zu implementieren, und nicht nur zum Parsen von Zahlen. Aus diesem Grund werde ich versuchen, ihn genauer zu beschreiben.

Mit dem Parsen der korrekt geschriebenen Nummer herausgefunden. Lassen Sie uns nun darüber nachdenken, welche Fehler auftreten können, wenn die durch OCR erhaltene Nummer falsch geschrieben wird. Ich erwäge keine anderen Optionen, aber Sie können den Algorithmus für eine bestimmte Aufgabe ändern.

Ich habe drei Arten von Fehlern identifiziert, auf die ich bei der Arbeit gestoßen bin:

1. Ersetzen Sie Zeichen durch andere mit einem ähnlichen Stil. Zum Beispiel wird der Buchstabe "c" aus irgendeinem Grund durch "p" und "n" durch "und" ersetzt und umgekehrt. Bei Verwendung der dritten Version von tesseract ist es möglich, den Buchstaben „o“ durch Null zu ersetzen. Diese Fehler sind spontan am häufigsten und erfordern die Optimierung für eine bestimmte Erkennungsbibliothek. Die Arbeitsprinzipien der Tesseract-Versionen 3 und 4 weisen also grundlegende Unterschiede auf, daher sind die Fehler dort unterschiedlich.
   
2. Token zusammenführen. Wörter können zusammengeführt werden (haben das Gegenteil noch nicht getroffen). In Kombination mit dem ersten Fehler werden dämonische Phrasen wie "doppelte Eins" generiert. Versuchen wir auch solche Monster zu dämonisieren.
   
3. Rauschen - linke Zeichen und Phrasen im Text. Leider kann im Moment wenig getan werden, aber es gibt eine Perspektive, wenn ausreichend signifikante Statistiken gesammelt werden.
   

Gleichzeitig ändert sich der oben beschriebene Parsing-Algorithmus fast nicht. Der Hauptunterschied besteht darin, die Zeichenfolge in Token zu zerlegen.

Beginnen wir jedoch mit der Erfassung einiger Statistiken zur Verwendung von Buchstaben in Token. Von den 33 Buchstaben der russischen Sprache werden nur 20 beim Schreiben nicht negativer Ganzzahlen verwendet. Nennen wir sie gute Buchstaben :

Die restlichen 13 werden als schlechte Buchstaben bezeichnet . Die maximale Größe des Tokens beträgt 12 Zeichen (13 bei Zählung bis Billiarde). Teilzeichenfolgen, die länger als dieser Wert sind, müssen aufgeteilt werden.

Um Zeichenfolgen und Token zu vergleichen, entschied ich mich für den Wagner-Fisher-Algorithmus , obwohl ich ihn im Code den Namen Levenshtein nannte. Ich benötige keine redaktionelle Anleitung, daher habe ich eine speicherfreundliche Version des Algorithmus implementiert. Ich muss zugeben, dass sich die Implementierung dieses Algorithmus als schwieriger herausstellte als der Parser selbst.

Ein kleines Bildungsprogramm: Die Levenshtein-Distanz ist ein Sonderfall des Wagner-Fisher-Algorithmus, wenn die Kosten für das Einfügen, Löschen und Ersetzen von Zeichen statisch sind. Dies ist bei unserer Aufgabe nicht der Fall. Wenn wir einen schlechten Buchstaben in einem Teilstring finden, muss dieser natürlich durch einen guten Buchstaben ersetzt werden, aber das Ersetzen eines guten durch einen schlechten ist äußerst unerwünscht. Im Allgemeinen ist es unmöglich, aber die Situation hängt von der spezifischen Aufgabe ab.

Um die Kosten für das Einfügen, Löschen und Ersetzen von Zeichen zu beschreiben, habe ich eine Tabelle wie diese erstellt: einen Link zu einer Tabelle mit Gewichten . Es ist zwar mit der Drei-P-Methode (Geschlecht, Finger, Decke) gefüllt, aber wenn Sie es mit Daten füllen, die auf OCR-Statistiken basieren, können Sie die Qualität der Nummernerkennung erheblich verbessern. Der Bibliothekscode enthält die Ressourcendatei NumeralLevenshteinData.txt, in die Sie mit Strg + A, Strg + C und Strg + V Daten aus einer ähnlichen Tabelle einfügen können.

Wenn im Text ein Nicht-Tabellenzeichen gefunden wird, z. B. Null, entsprechen die Kosten für das Einfügen dem Maximalwert aus der Tabelle, und die Kosten für das Löschen und Ersetzen entsprechen dem Minimum. Daher ersetzt der Algorithmus mit größerer Wahrscheinlichkeit Null durch den Buchstaben „o“, und wenn Sie die dritte Version von tesseract verwenden Dann ist es sinnvoll, der Tabelle Null hinzuzufügen und den Mindestpreis zu schreiben, um sie durch den Buchstaben „o“ zu ersetzen.

Also haben wir die Daten für den Wagner-Fisher-Algorithmus vorbereitet. Nehmen wir Änderungen am Algorithmus zum Aufteilen der Zeichenfolge in Token vor. Zu diesem Zweck werden wir eine zusätzliche Analyse jedes Tokens durchführen. Zuvor werden wir jedoch die Informationen über das Token mit den folgenden Merkmalen erweitern:

• Fehlerstufe . Eine reelle Zahl von 0 (kein Fehler) bis 1 (das Token ist falsch), was bedeutet, wie gut das Token mit der Stichprobe verglichen wurde.
  
• Ein Zeichen für die Verwendung eines Tokens . Beim Parsen einer Zeichenfolge mit eingestreuten Trümmern wird ein Teil der Token verworfen, da dieses Attribut nicht festgelegt wird. In diesem Fall wird der Gesamtfehlerwert als arithmetischer Durchschnitt der Fehler der verwendeten Token betrachtet.
  

Token-Analyse-Algorithmus:

1. Wir versuchen, das Token so wie es ist in der Tabelle zu finden. Wenn wir finden - alles ist gut, geben Sie es zurück.
2. Wenn nicht, erstellen Sie eine Liste möglicher Optionen:

3. Wir versuchen, das Token mit dem Wagner-Fisher-Algorithmus mit dem Sample abzugleichen. Diese Option besteht aus einem Token (zugeordnetes Sample) und sein Fehler entspricht dem besten Abstand geteilt durch die Länge des Samples.

   
   Beispiel: Das "Null" -Token wird mit dem "Null" -Sample verglichen, während der Abstand 0,5 beträgt, weil Die Kosten für das Ersetzen des schlechten Buchstabens "y" durch ein gutes "o" betragen 0,5. Der Gesamtfehler für dieses Token beträgt 0,5 / 4 = 0,125.
   

4. Wenn der Teilstring groß genug ist (ich habe 6 Zeichen), versuchen wir, ihn in zwei Teile mit jeweils mindestens 3 Zeichen zu unterteilen. Für eine Zeichenfolge mit 6 Zeichen gibt es eine einzelne Unterteilung: 3 + 3 Zeichen. Für eine Zeichenfolge mit 7 Zeichen gibt es bereits zwei Optionen: 3 + 4 und 4 + 3 usw. Für jede der Optionen rufen wir dieselbe Tokenanalysefunktion rekursiv auf und geben die empfangenen Optionen in die Liste ein.

   
   

   Um nicht in Rekursion zu sterben, bestimmen wir die maximale Fehlerquote. Darüber hinaus werden die durch die Teilung erhaltenen Optionen um einen bestimmten Betrag künstlich verschlechtert (Option, standardmäßig 0,1), so dass die direkte Vergleichsoption wertvoller ist. Ich musste diese Operation hinzufügen, weil Teilschritte vom Typ "doppelt" wurden erfolgreich in die Token "zwei" und "fünf" unterteilt und nicht auf "zwanzig" reduziert. Leider sind dies die Merkmale der russischen Sprache.

   
   

   Beispiel: Das "doppelte" Token hat einen direkten Vergleich mit der "zwanzig" Stichprobe, Fehler 0,25. Darüber hinaus ist die beste Option zum Teilen „zwei“ + „fünf“ mit Kosten von 0,25 (Ersetzen von „a“ durch „i“), die künstlich auf 0,35 verschlechtert wurden, wodurch der Token „zwanzig“ bevorzugt wird.

   
   
5. Nachdem wir alle Optionen zusammengestellt haben, wählen wir die beste aus der minimalen Fehleranzahl der daran teilnehmenden Token aus. Das Ergebnis wird zurückgegeben.

Darüber hinaus wird die Token-Überprüfung in den Algorithmus zur Generierung von Hauptnummern eingeführt, sodass deren Fehler einen bestimmten Wert nicht überschreitet (Option, Standardwert 0,67). Damit filtern wir potenziellen Müll aus, wenn auch nicht sehr erfolgreich.

Der Algorithmus auf den Punkt gebracht für diejenigen, die zu faul waren, um den obigen Text zu lesen

Wir teilen die Eingabezeichenfolge, bei der es sich um die Zahl in Worten handelt, unter Verwendung der Regelmäßigkeit \ s + in Teilzeichenfolgen auf. Anschließend versuchen wir, jede Teilzeichenfolge mit Beispieltoken abzugleichen oder sie in kleinere Teilzeichenfolgen aufzuteilen, um die besten Ergebnisse zu erzielen. Als Ergebnis erhalten wir eine Reihe von Token, mit denen wir eine Zahl generieren, und der Fehlerwert wird als arithmetisches Mittel der Fehler unter den in der Generierung verwendeten Token verwendet.

Schärfen eines Algorithmus für eine bestimmte Aufgabe

In meiner Aufgabe sind die Zahlen nicht negativ und relativ klein, daher werde ich unnötige Token von der "Million" und höher ausschließen. Für den Test, liebe Leser, habe ich im Gegenteil zusätzliche Jargon-Token hinzugefügt, mit denen Zeichenfolgen wie „fünf Teile“, „zweihundert mähen“ und sogar „drei Stolniks und zwei Goldstücke“ analysiert werden konnten. Es ist lustig, aber es waren nicht einmal Änderungen am Algorithmus erforderlich.

Weitere Verbesserung

Der vorhandene Algorithmus weist folgende Mängel auf:

1. Fallkontrolle. Die Zeichenfolgen "zweitausend" und "zweitausend" werden mit einem Fehler von Null als 2000 erkannt. In meiner Aufgabe ist keine Fallkontrolle erforderlich, sie ist sogar schädlich. Wenn Sie jedoch eine solche Funktion benötigen, wird dies durch Einfügen eines zusätzlichen Flags in das Token gelöst, das für den Fall des nächsten Tokens verantwortlich ist .
   
2. Negative Zahlen. Ein zusätzliches Minus-Token wird mit spezieller Verarbeitung eingeführt. Nichts kompliziertes, aber vergessen Sie nicht, dass der Buchstabe „y“ schlecht ist und nicht in den Ziffern vorkommt. Sie müssen seine Gewichtseigenschaften ändern oder hoffen, dass er sich während des OCR-Prozesses nicht ändert.
   
3. Bruchzahlen. Es wird gelöst, indem der lange Typ durch einen doppelten Typ ersetzt und Token von "Zehntel", "Hundertstel" usw. eingeführt werden. Vergessen Sie nicht, die Buchstabenskala zu überarbeiten.
   
4. Erkennung von von Benutzern eingegebenen Nummern. Weil Bei der manuellen Eingabe von Text machen wir meistens Fehler im Zusammenhang mit der erneuten Bearbeitung von siVMolov. Sie sollten diese Operation zum Wagner-Fisher-Algorithmus hinzufügen.
   
5. Unterstützung für andere Sprachen. Wir führen neue Token ein und erweitern die Gewichtstabelle.
   
6. Müllabfuhr. In einigen Dokumenten werden Daten gedruckt, die Bildqualität ist möglicherweise schlecht, die Zelle ist möglicherweise leer. In diesem Fall gelangt Müll, der gereinigt werden muss, irgendwie in die Leitung. Das Beste, was ich im Moment anbieten kann, ist, das Dokument vor der OCR vorzuverarbeiten. Das Entfernen der Tabellenzeilen und das Füllen mit einer Farbe, die der Farbe des freien Raums der Zelle nahe kommt, hat mir sehr geholfen. Dies löste nicht alle Probleme, verbesserte jedoch die Qualität der Erkennung von Text aus Dokumenten, bei denen die Tabelle aufgrund von Blutergüssen des Dokuments oder eines krummen Fotografen Krümmungen aufwies. Idealerweise sollten Sie die Zelle selbst drehen und separat erkennen, wenn Sie natürlich überhaupt einen Tisch haben.
   

Was ist das Endergebnis?

Das Projekt enthält ein Beispiel für eine Konsolenanwendung, die in der Datei samples.txt ausgeführt wird, mit Beispielen für den Parser. Hier ist ein Screenshot der Ergebnisse:

Ich fordere Sie auf, das Ergebnis zu bewerten, aber für mich ist es nicht schlecht. Der Fehler für echte Erkennungsbeispiele überschreitet nicht 0,25, obwohl ich noch nicht den gesamten Satz verfügbarer Dokumente ausgeführt habe, wird dort wahrscheinlich nicht alles so reibungslos sein.

Was den letzten Abschnitt betrifft, habe ich mich immer gefragt, wie sehr dies „Dofiga“ ist. Außerdem gab sich das Programm eine angemessene Antwort darauf, wie viel es braucht (ich benutze es nicht, aber immer noch) und bestimmte sogar genau die Bedeutung des alten russischen Wortes "Dunkelheit". Und ja, die Schlussfolgerung enthielt keine weitere Maßnahme, die die Bildung nicht hinzufügen durfte, aber das Programm geht davon aus, dass sie tausend entspricht =)

Ein paar Worte zur Bibliothek

Ursprünglich war nicht geplant, eine Bibliothek zu erstellen. Ich beschloss, sie exklusiv für einen Habr zu entwerfen. Ich habe versucht, den Code in Ordnung zu bringen, aber wenn Sie ihn verwenden, machen Sie eine Gabel oder eine Kopie, als Höchstwahrscheinlich benötigen Sie keinen Jargon und keine anderen in den Beispielen enthaltenen Token.

Die Bibliothek selbst ist unter .NET Standart 2.0 und C # 7.x geschrieben, und die Algorithmen können problemlos in andere Sprachen übersetzt werden.

Im Falle einer möglichen Erweiterung der Bibliothek werde ich die Zusammensetzung der wichtigen Komponenten des Zahlenparsers in Worten hinzufügen (Genesis.CV.NumberUtils-Namespace):

• RussianNumber.cs - direkter Parser
• RussianNumber.Data.cs - Datei mit Beschreibung der Token
• RussianNumber.ToString.cs - Konverter von Zahl zu Text in Worten
• RussianNumberParserOptions.cs - Parser-Optionen
• NumeralLevenshtein.cs - Implementierung des Wagner-Fisher-Algorithmus
• NumeralLevenshteinData.txt - Ressource, Daten zur Buchstabengewichtung

Verwendung:

• RussianNumber.ToString (Wert) - Konvertiert eine Zahl in Text
• RussianNumber.Parse (Wert, [Optionen]) - Konvertiert Text in Zahl

Fazit

Ich hoffe wirklich, dass Ihnen der Artikel trotz der Fülle an Texten nicht langweilig erschien. In letzter Zeit habe ich viele Themen im Zusammenhang mit Computer Vision entwickelt, über die es etwas zu erzählen gibt. Daher würde ich gerne eine Meinung zu diesem Artikelformat erfahren. Was ist es wert, hinzugefügt oder umgekehrt entfernt zu werden? Was ist für Sie, die Leser, die Algorithmen selbst oder die Codefragmente interessanter?

Gefällt dir der Artikel? Schauen Sie sich die anderen an:

• Klasse JavaScript Unterstützung der JavaScript-Serialisierung
  
• Füllen von Textvorlagen mit modellbasierten Daten. .NET-Implementierung mit IL-Funktionen (Dynamic Bytecode)