Prólogo

Boa tarde, queridos leitores. Neste artigo, falarei sobre como analisar um número escrito em palavras em russo.

Inteligente, esse analisador permite extrair números do texto com erros cometidos como resultado de entrada incorreta ou como resultado do reconhecimento óptico de texto de uma imagem (OCR).

Para os preguiçosos:
Link para o projeto github: link .

Do algoritmo ao resultado

Esta seção irá descrever os algoritmos usados. Cuidado, muitas cartas!

Declaração do problema

No trabalho, preciso reconhecer o texto de um documento impresso fotografado com uma câmera de smartphone / tablet. Devido ao contrato de não divulgação, não posso dar um exemplo de fotografia, mas o ponto é que o documento possui uma tabela na qual determinados indicadores são escritos em números e em palavras, e esses dados devem ser lidos. A análise de texto em palavras é necessária como uma ferramenta de validação adicional para garantir que o número seja reconhecido corretamente. Mas, como você sabe, o OCR não garante reconhecimento preciso de texto. Por exemplo, o número vinte, escrito em palavras, pode ser reconhecido como "dvupat" ou mesmo como "dvupat". É necessário levar isso em conta e extrair a quantidade máxima de informações, avaliando a magnitude do possível erro.

Nota Para reconhecimento de texto, eu uso o tesseract 4. Para o .NET, não existe um pacote NuGet pronto para a quarta versão, então criei um do ramo principal do projeto, que pode ser útil: Genesis.Tesseract4 .

Algoritmo básico de análise de números

Vamos começar com um simples, ou seja, com um algoritmo de reconhecimento de texto escrito em palavras, até o momento sem erros. Se você estiver interessado em análise inteligente, pule esta seção.

Eu não sou particularmente bom em pesquisar no Google, por isso não encontrei imediatamente um algoritmo pronto para resolver esse problema. No entanto, isso é ainda melhor, porque um algoritmo inventado por nós mesmos oferece mais espaço para codificação. E a tarefa em si acabou sendo interessante.

Então, vamos pegar um número pequeno, por exemplo, "cento e vinte e três". Consiste em três palavras ( tokens ), cada uma das quais corresponde a um número, todos esses números são resumidos:

Até agora, tudo é simples, mas aprofundamos, por exemplo, o número "duzentos e doze mil cento e cinco".

Como você pode ver, quando existem milhares no número (além de milhões e outros graus de mil), o número é dividido em partes que consistem em um pequeno número local, no exemplo acima - 212, e um fator (1000). Pode haver vários desses fragmentos, mas todos eles vão na ordem decrescente do multiplicador, por exemplo, mil ou mil não podem seguir mil. Isso também se aplica a partes de um número pequeno, uma vez que centenas não podem seguir centenas e dezenas de dezenas, portanto a entrada "cento e quinhentos" está incorreta. Chamaremos uma característica que relaciona dois tokens do mesmo tipo de nível , por exemplo, os "cem" e "trezentos" tokens têm um nível, e é maior que o "cinquenta" token.

A partir dessas considerações, nasce a idéia de um algoritmo. Vamos escrever todos os tokens possíveis ( amostras ), cada um dos quais atribuiremos um número, bem como dois parâmetros - o nível e o sinal do multiplicador.

De fato, você pode adicionar outros tokens a esta tabela, inclusive para idiomas estrangeiros, mas não se esqueça de que em alguns países é usado um sistema de nomeação longo, e não curto.

Agora vamos para a análise. Obteremos quatro quantidades:

1. Nível global (globalLevel). Indica o nível do último multiplicador. Inicialmente indefinido e necessário para o controle. Se encontrarmos um token multiplicador cujo nível é maior ou igual ao global, isso é um erro.
2. Valor global (globalValue). O somador total, em que o resultado é o resultado da multiplicação do número e fator local.
3. Nível local (localLevel). Indica qual o nível do último token. Inicialmente indefinido, funciona de maneira semelhante ao nível global, mas é redefinido após a descoberta do multiplicador.
4. Valor local (localValue) Um somador de tokens não multiplicador, ou seja, números até 999.

O algoritmo é o seguinte:

1. Divida a string em tokens usando o "\ s +" regular.
2. Tomamos o próximo token, obtemos informações sobre ele a partir da amostra.
3. Se for um multiplicador:
   
   • Se o nível global estiver definido, garantiremos que seja maior ou igual ao nível do token. Caso contrário, isso é um erro; o número está incorreto.
   • Defina o nível global para o nível do token atual.
   • Multiplique o valor do token pelo valor local e adicione o resultado ao valor global.
   • Limpamos o valor e o nível local.
4. Se este não for um multiplicador:
   
   • Se o nível local estiver definido, garantiremos que seja maior ou igual ao nível do token. Caso contrário, isso é um erro; o número está incorreto.
   • Defina o nível local para o nível do token atual.
   • Adicione o valor do token ao valor local.
5. Retornamos o resultado como a soma dos valores globais e locais.

Um exemplo de trabalho para o número "dois milhões duzentos e doze mil cento e oitenta e cinco".

O resultado será 2.212.185.

Análise inteligente

Esse algoritmo pode ser usado para implementar outras comparações, e não apenas para analisar números, por esse motivo, tentarei descrevê-lo com mais detalhes.

Com a análise do número escrito corretamente, descobri. Agora, vamos pensar em quais erros podem ocorrer se o número obtido como resultado do OCR for gravado incorretamente. Não considero outras opções, mas você pode modificar o algoritmo para uma tarefa específica.

Eu identifiquei três tipos de erros que encontrei no processo de trabalho:

1. Substitua os caracteres por outros com um estilo semelhante. Por exemplo, a letra "c" é por algum motivo substituída por "p" e "n" por "e" e vice-versa. Ao usar a terceira versão do tesseract, é possível substituir a letra “o” por zero. Esses erros, de imediato, são os mais comuns e requerem ajuste para uma biblioteca de reconhecimento específica. Portanto, os princípios de trabalho das versões 3 e 4 do tesseract têm diferenças importantes, portanto os erros serão diferentes.
   
2. Mesclagem de token. As palavras podem se fundir (ainda não encontraram o oposto). Em combinação com o primeiro erro, gera frases demoníacas como "duplo". Vamos tentar demonizar esses monstros também.
   
3. Ruído - caracteres e frases deixados no texto. Infelizmente, há pouco que pode ser feito no momento, mas há uma perspectiva ao coletar estatísticas suficientemente significativas.
   

Ao mesmo tempo, o algoritmo de análise descrito acima quase não muda, a principal diferença está na quebra da string em tokens.

Mas vamos começar coletando algumas estatísticas sobre o uso de letras em tokens. Das 33 letras do idioma russo, apenas 20 são usadas ao escrever números inteiros não negativos, vamos chamá-los de boas letras :

Os 13 restantes, respectivamente, serão chamados de letras ruins . O tamanho máximo do token é de 12 caracteres (13 ao contar até quatrilhões). Substrings maiores que esse valor devem ser divididos.

Para comparar strings e tokens, decidi usar o algoritmo Wagner-Fisher , embora o chamasse de nome de Levenshtein no código. Como não preciso de uma instrução editorial, implementei uma versão do algoritmo compatível com a memória. Devo admitir que a implementação desse algoritmo acabou sendo uma tarefa mais difícil do que o próprio analisador.

Um pequeno programa educacional: a distância de Levenshtein é um caso especial do algoritmo Wagner-Fisher, quando o custo de inserção, exclusão e substituição de caracteres é estático. Isso não é assim em nossa tarefa. Obviamente, se encontrarmos uma letra ruim em uma substring, ela precisará ser substituída por uma boa letra, mas substituir uma boa por uma ruim é extremamente indesejável. De um modo geral, é impossível, mas a situação depende da tarefa específica.

Para descrever o custo de inserção, exclusão e substituição de caracteres, criei uma tabela como esta: um link para uma tabela com pesos . Embora seja preenchido com o método dos três P (sexo, dedo, teto), mas se você o preencher com dados baseados em estatísticas de OCR, poderá melhorar significativamente a qualidade do reconhecimento de números. O código da biblioteca contém o arquivo de recurso NumeralLevenshteinData.txt, no qual você pode inserir dados de uma tabela semelhante usando Ctrl + A, Ctrl + C e Ctrl + V.

Se um caractere que não seja de tabela for encontrado no texto, por exemplo, zero, o custo de inseri-lo será igual ao valor máximo da tabela e o custo de exclusão e substituição será igual ao mínimo, portanto, o algoritmo substituirá zero pela letra "o" e, se você usar a terceira versão do tesseract , faça sentido adicionar zero à tabela e escrever o preço mínimo para substituí-lo pela letra "o".

Então, preparamos os dados para o algoritmo Wagner-Fisher, vamos fazer alterações no algoritmo para dividir a string em tokens. Para fazer isso, passaremos por uma análise adicional de cada token, mas antes disso expandiremos as informações sobre o token com as seguintes características:

• Nível de erro . Um número real de 0 (sem erro) a 1 (o token está incorreto), o que significa quão bem o token foi comparado com a amostra.
  
• Um sinal de uso de um token . Ao analisar uma sequência com detritos intercalados, parte dos tokens será descartada, pois esse atributo não será definido. Nesse caso, o valor total do erro será considerado como a média aritmética dos erros dos tokens usados.
  

Algoritmo de análise de token:

1. Estamos tentando encontrar o token na tabela como está. Se encontrarmos - tudo está bem, devolva-o.
2. Caso contrário, faça uma lista de opções possíveis:

3. Estamos tentando combinar o token com a amostra usando o algoritmo Wagner-Fisher. Esta opção consiste em um token (amostra mapeada) e seu erro é igual à melhor distância dividida pelo comprimento da amostra.

   
   Exemplo: o token "zero" é comparado com a amostra "zero", enquanto a distância é 0,5, porque o custo de substituir a letra incorreta “y” por um bom “o” é 0,5. O erro total para este token será 0,5 / 4 = 0,125.
   

4. Se a substring for grande o suficiente (eu tenho 6 caracteres), tentaremos dividi-lo em duas partes de pelo menos 3 caracteres em cada. Para uma sequência de 6 caracteres, haverá uma única divisão: 3 + 3 caracteres. Para uma sequência de 7 caracteres - já existem duas opções, 3 + 4 e 4 + 3, etc. Para cada uma das opções, chamamos a mesma função de análise de token recursivamente, inserimos as opções recebidas na lista.

   
   

   Para não morrer em recursão, determinamos o nível máximo de falha. Além disso, as opções obtidas como resultado da divisão são artificialmente degradadas por uma certa quantidade (opção, por padrão 0,1), para que a opção de comparação direta seja mais valiosa. Eu tive que adicionar essa operação, porque subetapas do tipo "duplo" foram divididas com sucesso em tokens "dois" e "cinco" e não foram reduzidas a "vinte". Infelizmente, esses são os recursos do idioma russo.

   
   

   Exemplo: o token "duplo" tem uma comparação direta com a amostra "vinte", erro 0,25. Além disso, a melhor opção para dividir é "dois" + "cinco" com um custo de 0,25 (substituindo "a" por "i"), artificialmente piorado para 0,35, como resultado do qual o token "vinte" é preferido.

   
   
5. Após compilar todas as opções, selecionamos a melhor pela quantidade mínima de erros dos tokens participantes. O resultado é retornado.

Além disso, a verificação do token é introduzida no algoritmo principal de geração de número, para que o erro não exceda um determinado valor (opção, padrão 0,67). Com isso, filtramos o lixo em potencial, embora não com muito sucesso.

O algoritmo em poucas palavras para aqueles que estavam com preguiça de ler o texto acima

Dividimos a sequência de entrada que representa o número em palavras em substrings usando a regularidade \ s +, depois tentamos combinar cada substring com tokens de amostra ou dividi-lo em substrings menores, escolhendo os melhores resultados. Como resultado, obtemos um conjunto de tokens pelos quais geramos um número e o valor do erro é considerado a média aritmética dos erros entre os tokens usados ​​na geração.

Aprimorando um algoritmo para uma tarefa específica

Na minha tarefa, os números não são negativos e são relativamente pequenos, portanto, excluirei tokens desnecessários do "milhão" e superior. Para o teste, queridos leitores, ao contrário, adicionei tokens de jargão adicionais, que permitiam analisar seqüências de caracteres como “cinco peças”, “cortar duzentas” e até “três stolniks e duas peças de ouro”. É engraçado, mas nem sequer exigiu alterações no algoritmo.

Melhoria adicional

O algoritmo existente possui falhas:

1. Controle de caso. As cadeias "dois mil" e "dois mil" serão reconhecidas com erro zero como 2000. Na minha tarefa, o controle de caso não é necessário, é até prejudicial, mas se você precisar dessa função, isso será resolvido com a introdução de um sinalizador adicional no token, responsável pelo caso do próximo token .
   
2. Números negativos. Um token negativo adicional é introduzido com processamento especial. Nada complicado, mas não esqueça que a letra “y” é ruim e não ocorre nos números; você precisará alterar suas características de peso ou torcer para que não mude durante o processo de OCR.
   
3. Números fracionários. Isso é resolvido substituindo o tipo longo por um duplo e introduzindo símbolos de "décimos", "centésimos", etc. ... Não se esqueça de revisar a escala das letras.
   
4. Reconhecimento de números inseridos pelos usuários. Porque Ao digitar texto manualmente, geralmente cometemos erros relacionados à reedição do siVMolov, você deve adicionar esta operação ao algoritmo Wagner-Fisher.
   
5. Suporte para outros idiomas. Introduzimos novos tokens, expandimos a tabela de pesos.
   
6. Manuseio de lixo. Em alguns documentos, os dados são impressos, a qualidade da imagem pode ser ruim, a célula pode estar muito vazia. Nesse caso, o lixo que precisa ser limpo de alguma forma entra na linha. O melhor que posso oferecer no momento é pré-processar o documento antes do OCR. Remover as linhas da tabela e preenchê-las com uma cor próxima à cor do espaço livre da célula me ajudou muito. Isso não resolveu todos os problemas, mas melhorou a qualidade do reconhecimento de texto de documentos em que a tabela apresentava curvaturas devido a ferimentos no documento ou a um fotógrafo distorcido. Idealmente, você deve girar a própria célula e reconhecê-la separadamente, se você, é claro, tem uma mesa.
   

Então, qual é o resultado final?

O projeto possui um exemplo de aplicativo de console em execução no arquivo samples.txt com exemplos para o analisador. Aqui está uma captura de tela dos resultados:

Encarrego-o de avaliar o resultado, mas quanto a mim, não é ruim. O erro para exemplos de reconhecimento real não excede 0,25, embora eu ainda não tenha executado todo o conjunto de documentos disponíveis, provavelmente nem tudo será tão fácil lá.

Quanto à última seção, eu sempre me perguntava o quanto isso é "dofiga". Além disso, o programa deu uma resposta adequada ao quanto é preciso levar (não uso, mas ainda assim) e até mesmo determinou com precisão o significado da antiga palavra russa "escuridão". E sim, a conclusão não incluiu mais uma medida que a educação não permitiu acrescentar, mas o programa acredita que é igual a mil =)

Algumas palavras sobre a biblioteca

Inicialmente, meus planos não incluíam a criação de uma biblioteca, decidi projetá-la exclusivamente para um Habr. Tentei colocar o código em ordem, mas se você o usar, faça um garfo ou uma cópia, como provavelmente você não precisará de jargões e outros tokens incluídos nos exemplos.

A própria biblioteca é escrita no .NET Standart 2.0 e C # 7.x, e os algoritmos são facilmente traduzidos para outros idiomas.

No caso de uma possível expansão da biblioteca, adicionarei a composição dos componentes importantes do analisador de números em palavras (espaço de nome Genesis.CV.NumberUtils):

• RussianNumber.cs - analisador diretamente
• RussianNumber.Data.cs - arquivo com descrição de tokens
• RussianNumber.ToString.cs - número para conversor de texto em palavras
• RussianNumberParserOptions.cs - opções de analisador
• NumeralLevenshtein.cs - implementação do algoritmo Wagner-Fisher
• NumeralLevenshteinData.txt - recurso, dados de ponderação de letras

Uso:

• RussianNumber.ToString (valor) - converte um número em texto
• RussianNumber.Parse (valor, [opções]) - converte texto em número

Conclusão

Eu realmente espero que o artigo não pareça chato para você, apesar da abundância de texto. Recentemente, criei vários tópicos relacionados à visão computacional, sobre os quais há algo a dizer, então gostaria de saber uma opinião sobre esse formato de artigo. O que vale a pena adicionar ou, inversamente, remover? O que é mais interessante para você, leitores, os próprios algoritmos ou os fragmentos de código?

Você gosta do artigo? Confira os outros:

• Classe JavaScript Suporte à serialização de JavaScript
  
• Preenchendo modelos de texto com dados baseados em modelo. Implementação .NET usando funções dinâmicas de bytecode (IL)