序言

下午好，亲爱的读者们。 在本文中，我将讨论如何解析用俄语单词书写的数字。

聪明地使用此解析器，可以从文本中提取数字，而由于输入错误或从图像（OCR）对文本进行光学识别而导致错误。

对于懒惰的人：
链接到github项目： link 。

从算法到结果

本节将描述所使用的算法。 注意，很多字母！

问题陈述

在工作中，我需要从使用智能手机/平板电脑相机拍摄的打印文档中识别文本。 根据保密协议，我无法举例说明照片，但重点是文档中有一个表格，其中某些指标用数字和文字表示，必须读取这些数据。 作为额外的验证工具，有必要将文字解析为文本，以确保正确识别数字。 但是，您知道，OCR无法保证准确的文本识别。 例如，用文字写的数字20可以识别为“ dvupat”，甚至可以识别为“ dvupat”。 有必要考虑到这一点，并提取最大的信息量，评估可能的错误值。

注意事项 对于文本识别，我使用tesseract4。对于.NET，没有现成的第四版NuGet软件包，因此我从主项目分支创建了一个可以方便使用的软件包 ： Genesis.Tesseract4 。

基本号码解析算法

让我们从一个简单的例子开始，即以文字编写的文本识别算法，到目前为止没有错误。 如果您对智能分析感兴趣，请跳过此部分。

我不是特别擅长使用Google搜索，因此我没有立即找到解决该问题的现成算法。 但是，这甚至变得更好，因为 我们自己发明的算法为编码提供了更多空间。 任务本身变得很有趣。

因此，让我们以一小部分为例，例如“ 123”。 它由三个词（ 令牌 ）组成，每个词对应一个数字，所有这些数字加起来为：

到目前为止，一切都很简单，但是我们进行了更深入的研究，例如，考虑数字“ 212.125万”。

如您所见，当数字中有成千上万（以及数百万和其他千分之一度）时，该数字被分成多个部分，其中包括一个局部小数（在上面的示例中为212）和一个因数（1000）。 可能有几个这样的碎片，但是它们都以乘数的降序排列，例如，一千或一千不能跟随一千。 对于少数零件也是如此，因为数百个零件不能跟随数百个零件，因此条目“一百五百个”是不正确的。 我们将把与两个相同类型的令牌相关联的特性称为一个级别 ，例如，“一百”和“三百”令牌具有一个级别，并且大于“五十”令牌。

基于这些考虑，算法的思想诞生了。 让我们写出所有可能的标记（ 样本 ），为每个标记分配一个数字，以及两个参数-乘数的水平和符号。

实际上，您可以在该表中添加任何其他标记，包括用于外语的标记，只是不要忘记在某些国家/地区使用长而不是短的命名系统 。

现在让我们继续分析。 我们将得到四个数量：

1. 全局级别 （globalLevel）。 指示最后一个乘数的级别。 最初未定义，是控制所必需的。 如果我们遇到一个级别大于或等于全局的乘法器令牌，那么这是一个错误。
2. 全局值 （globalValue）。 总加法器，其结果是本地数字和因子相乘的结果。
3. 本地级别 （localLevel）。 指示最后一个令牌的级别。 最初是未定义的，其工作方式类似于全局级别，但在发现乘数后会重置。
4. 本地值 （localValue） 非乘法器令牌加法器，即 最多999。

算法如下：

1. 使用“ \ s +”常规将字符串拆分为标记。
2. 我们获取下一个令牌，我们从样本中获取有关它的信息。
3. 如果是乘数：
   
   • 如果设置了全局级别，那么我们确保它大于或等于令牌的级别。 如果不是，则错误；该数字不正确。
   • 将全局级别设置为当前令牌的级别。
   • 将令牌的值乘以本地值，然后将结果添加到全局值。
   • 我们清除当地的价值和水平。
4. 如果这不是乘数：
   
   • 如果设置了本地级别，那么我们确保它大于或等于令牌的级别。 如果不是，则错误；该数字不正确。
   • 将本地级别设置为当前令牌的级别。
   • 将令牌值添加到本地值。
5. 我们以全局值和局部值之和返回结果。

数字“ 212.121万.185”的工作示例。

结果将是2.212.185。

智能解析

该算法不仅可以用于解析数字，还可以用于执行其他比较，因此，我将尝试更详细地描述它。

随着解析正确的数字找出来。 现在让我们考虑一下，如果错误地写入了由于OCR而获得的数字，会发生什么错误。 我不考虑其他选项，但是您可以针对特定任务修改算法。

我确定了在工作过程中遇到的三种错误：

1. 用具有相似样式的其他字符替换字符。 例如，由于某种原因，字母“ c”被“ p”替换，“ n”被“ and”替换，反之亦然。 使用第三版tesseract时，可以将字母“ o”替换为零。 这些错误是最常见的，需要针对特定​​的识别库进行调整。 因此，tesseract版本3和版本4的工作原理存在根本差异，因此错误会有所不同。
   
2. 令牌合并。 单词可以合并在一起（尚未遇到相反的情况）。 结合第一个错误，它会生成恶魔短语，例如“双一个”。 让我们尝试妖魔化这些怪物。
   
3. 杂讯-文字中的左字符和词组。 不幸的是，目前尚无能为力，但收集足够重要的统计数据是有希望的。
   

同时，上述解析算法几乎不变，主要区别在于将字符串分成令牌。

但是，让我们从收集有关令牌中字母使用情况的一些统计信息开始。 在俄语的33个字母中，编写非负整数时仅使用20个字母，我们称它们为好字母 ：

其余的13个分别称为坏字母 。 令牌的最大大小为12个字符（计数为四千万时为13个字符）。 长度大于此值的子字符串必须拆分。

为了比较字符串和标记，我决定使用Wagner-Fisher算法 ，尽管我在代码中将其称为Levenshtein。 我不需要编辑说明，因此实现了该算法的内存友好版本。 我必须承认，与解析器本身相比，实现该算法是一项更加困难的任务。

一个很小的教育程序：当插入，删除和替换字符的成本是固定的时，Levenshtein距离是Wagner-Fisher算法的特例。 在我们的任务中并非如此。 显然，如果我们在子字符串中找到了一个坏字母，则需要用一个好字母替换它，但是用一个坏字母替换一个好字母是非常不可取的。 一般来说，这是不可能的，但具体情况取决于具体任务。

为了描述插入，删除和替换字符的成本，我创建了一个像这样的表： 链接到具有weights的表 。 虽然它用三种P方法（性别，手指，天花板）填充，但是如果用基于OCR统计的数据填充它，则可以显着提高数字识别的质量。 库代码包含NumeralLevenshteinData.txt资源文件，您可以使用Ctrl + A，Ctrl + C和Ctrl + V从类似的表中插入数据。

如果在文本中找到一个非表字符，例如零，则插入它的开销等于表中的最大值，而删除和替换的开销等于最小值，因此该算法更有可能用字母“ o”替换零，并且如果您使用的是第三版tesseract ，则可以在表格中加上零，并写出最低价格，以字母“ o”代替，这很有意义。

因此，我们为Wagner-Fisher算法准备了数据，让我们对将字符串分成令牌的算法进行更改。 为此，我们将对每个令牌进行额外的分析，但是在此之前，我们将使用以下特征扩展有关令牌的信息：

• 错误级别 。 从0（无错误）到1（令牌不正确）的实数，这表示令牌与样本的比较程度。
  
• 使用令牌的标志 。 当解析带有散布的碎片的字符串时，部分标记将被丢弃，因为不会设置此属性。 在这种情况下，总错误值将被视为所使用令牌的错误的算术平均值。
  

令牌分析算法：

1. 我们正在尝试按原样在表中查找令牌。 如果发现-一切都很好，请将其退回。
2. 如果不是，则列出可能的选项：

3. 我们正在尝试使用Wagner-Fisher算法将令牌与样本匹配。 此选项由一个标记（映射的样本）组成，其误差等于最佳距离除以样本的长度。

   
   示例：将 “零”令牌与“零”样本进行比较，而距离为0.5，因为 用好“ o”替换坏字母“ y”的成本为0.5。 此令牌的总错误将是0.5 / 4 = 0.125。
   

4. 如果子字符串足够大（我有6个字符），我们尝试将其分为两部分，每部分至少3个字符。 对于6个字符的字符串，将进行一个除法运算：3 + 3个字符。 对于7个字符的字符串-已经有两个选项，3 + 4和4 + 3，等等。 对于每个选项，我们递归调用相同的令牌分析函数，然后将接收到的选项输入列表。

   
   

   为了避免死于递归，我们确定了最大的故障级别。 另外，由于除法而获得的期权会被人为地降低一定数量（期权，默认为0.1），因此直接比较期权更有价值。 我必须添加此操作，因为 “ double”类型的子步骤成功地划分为标记“两个”和“五个”，而没有减少为“二十”。 las，这些是俄语的功能。

   
   

   示例： “双”标记与“二十”样本具有直接比较，错误0.25。 此外，最好的除法选择是“二” +“五”，成本为0.25（用“ i”代替“ a”），人为地恶化为0.35，因此，首选令牌“二十”。

   
   
5. 编译完所有选项后，我们通过参与其中的令牌的最小错误量来选择最佳选项。 返回结果。

另外，将令牌验证引入主号码生成算法中，以使它们的错误不超过某个值（选项，默认值为0.67）。 这样一来，尽管不是很成功，我们还是筛选出了潜在的垃圾。

简而言之，对于那些懒于阅读上面文本的人来说，该算法

我们使用\ s +规律性将输入字符串（即单词中的数字）拆分为子字符串，然后尝试将每个子字符串与样本标记匹配，或将其拆分为较小的子字符串，以选择最佳结果。 结果，我们获得了一组令牌，通过它们我们生成了一个数字，并且将错误值用作生成中使用的令牌之间的错误的算术平均值。

优化特定任务的算法

在我的任务中，数字是非负的并且相对较小，因此我将从“百万”及更高级别中排除不必要的令牌。 相反，对于测试，亲爱的读者，我添加了附加的行话令牌，这些行话允许解析字符串，例如“五件”，“割两百件”甚至“三只斯托尼克和两块金”。 这很有趣，但是甚至不需要更改算法。

进一步改善

现有算法存在缺陷：

1. 案例控制。 字符串“ 2000”和“ 2000”将以零错误识别为2000。在我的任务中，不需要大小写控制，这甚至是有害的，但是如果需要这种功能，可以通过在令牌中引入一个负责下一个令牌情况的附加标志来解决。 。
   
2. 负数。 额外的负令牌通过特殊处理引入。 没什么复杂的，但是请不要忘记字母“ y”是不好的并且不会出现在数字中，您需要更改其重量特征，或者希望它在OCR过程中不会改变。
   
3. 小数。 通过将长型替换为双精度型并引入“十分之几”，“十分之几”等标记，可以解决此问题。...不要忘记修改字母的小数位数。
   
4. 识别用户输入的数字。 因为 手动输入文本时，我们经常会犯与重新编辑siVMolov有关的错误，您应该将此操作添加到Wagner-Fisher算法中。
   
5. 支持其他语言。 我们引入了新的代币，扩展了权重表。
   
6. 垃圾处理。 在某些文档中，打印了数据，图像质量可能很差，单元格可能是空的。 在这种情况下，需要清理的垃圾进入了生产线。 目前，我能提供的最好的方法是在OCR之前对文档进行预处理。 删除表格行并用接近单元格自由空间颜色的颜色填充它们对我有很大帮助。 这并不能解决所有问题，但是提高了由于文件的淤青或弯曲的摄影师而使桌子弯曲的情况下，从文件中识别文本的质量。 理想情况下，如果您完全有一张桌子，则应该旋转单元格本身并分别识别它。
   

那么底线是什么？

该项目有一个示例程序，该示例程序运行在samples.txt文件中，并带有解析器的示例。 这是结果的屏幕截图：

我要求您评估结果，但就我而言，这还不错。 实际识别示例的错误不超过0.25，尽管我还没有运行整个可用文档集，但可能不是那里的所有事情都会如此顺利。

至于最后一部分，我一直想知道这是多少“ dofiga”。 此外，该程序还为需要花多少钱（我不使用，但仍然使用）提供了适当的答案，甚至可以准确地确定旧俄语单词“黑暗”的含义。 是的，结论并未包括教育不允许增加的另一项措施，但该计划认为这等于一千=）

关于图书馆的几句话

最初，我的计划不包括创建库，我决定专门为Habr设计库。 我试图按顺序排列代码，但是如果使用它，请制作一个fork或副本，例如 您很有可能不需要示例中包含的行话和其他标记。

该库本身是用.NET Standart 2.0和C＃7.x编写的，并且这些算法很容易转换为其他语言。

在可能扩展库的情况下，我将用字（Genesis.CV.NumberUtils命名空间）添加数字解析器重要组件的组成：

• RussianNumber.cs-直接解析器
• RussianNumber.Data.cs-带有令牌描述的文件
• RussianNumber.ToString.cs-数字到文本转换器的单词
• RussianNumberParserOptions.cs-解析器选项
• NumeralLevenshtein.cs-Wagner-Fisher算法的实现
• NumeralLevenshteinData.txt-资源，字母权重数据

用法：

• RussianNumber.ToString（值）-将数字转换为文本
• RussianNumber.Parse（值，[选项]）-将文本转换为数字

结论

我确实希望，即使文本很多，这篇文章对您也不会感到无聊。 最近，我提出了许多与计算机视觉有关的主题，关于这些主题有话要说，因此，我想对这种格式的文章发表看法。 什么值得添加或反之删除？ 您，读者，算法本身或代码片段对您来说更有趣？

你喜欢这篇文章吗？ 查看其他：

• 类JavaScript JavaScript序列化支持
  
• 用基于模型的数据填充文本模板。 .NET使用动态字节码（IL）函数的实现