Cada usuário já teve erros de digitação ao escrever consultas de pesquisa. A ausência de mecanismos que corrijam erros de digitação leva à emissão de resultados irrelevantes ou mesmo à sua ausência. Portanto, para tornar o mecanismo de pesquisa mais orientado ao usuário, são incorporados mecanismos de correção de erros.

A tarefa de corrigir erros de digitação, à primeira vista, parece bastante complicada. Mas se você começar com uma variedade de erros, a implementação de uma solução pode ser difícil. Em geral, a correção de erros de digitação é dividida em independente e sensível ao contexto (onde o ambiente do dicionário é levado em consideração) . No primeiro caso, os erros são corrigidos para cada palavra separadamente, no segundo - levando em consideração o contexto (por exemplo, para a frase "ela foi para casa" no caso independente de contexto, a correção ocorre para cada palavra separadamente, onde podemos obter "ela foi para casa", e no segundo caso, a correção correta dará "ela foi para casa").

Nas consultas de pesquisa do usuário que fala russo, quatro grupos principais de erros podem ser distinguidos apenas para correção independente do contexto [ 1 ]:
1) erros nas próprias palavras (digamos mr → oi), esta categoria inclui todos os tipos de omissões, inserções e permutações de letras - 63,7%,
2) ortografia contínua das palavras - 16,9%,
3) layout distorcido (ghbdtn → oi) - 9,7%,
4) transliteração (alfeneiro → oi) - 1,3%,
5) erros mistos - 8,3%.

Os usuários fazem erros de digitação em aproximadamente 10 a 15% dos casos. Ao mesmo tempo, 83,6% dos pedidos têm um erro, 11,7% - dois, 4,8% - mais de três. O contexto é importante em 26% dos casos.

Essas estatísticas foram compiladas com base em uma amostra aleatória do log diário do Yandex em 2013, com base em 10.000 consultas. No domínio público, há uma apresentação muito anterior do Yandex para 2008, que mostra uma distribuição semelhante de estatísticas [ 2 ]. A partir disso, podemos concluir que a distribuição de variedades de erros para consultas de pesquisa, em média, não muda ao longo do tempo.

Em geral, o mecanismo de correção de erros de digitação é baseado em dois modelos: o modelo de erro e o modelo de linguagem. Além disso, para uma correção independente do contexto, apenas o modelo de erro é usado e, em uma correção dependente do contexto, dois são usados ao mesmo tempo. O modelo de erro geralmente é a distância editorial ( distância de Levenshtein, Damerau-Levenshtein, vários fatores de ponderação, métodos semelhantes ao Soundex etc.) também podem ser adicionados aqui - nesse caso, a distância é chamada ponderada) ou o modelo de Bril-Moore, que trabalha nas probabilidades de transições de uma linha para outra. Bril e Moore posicionam seu modelo como mais perfeito, no entanto, em uma das competições mais recentes do SpellRuEval, a abordagem Damerau-Levenshtein mostrou um resultado melhor [ 3 ], apesar do fato de a distância Damerau-Levenshtein (o esclarecimento não ter peso) não usar informações a priori sobre as estatísticas de guarda baixa . Essa observação é especialmente indicativa se os mesmos textos de treinamento foram usados para diferentes implementações de corretores automáticos na biblioteca DeepPavlov.

Obviamente, a possibilidade de uma correção sensível ao contexto complica a construção do auto-corretor, pois além do modelo de erro, é adicionada a necessidade de um modelo de linguagem. Mas se você prestar atenção às estatísticas dos erros de digitação, todas as consultas de pesquisa escritas incorretamente poderão ser corrigidas sem contexto. Isso sugere que o benefício de pelo menos um auto-corretor independente do contexto pode ser muito significativo.

Além disso, uma correção sensível ao contexto para corrigir erros de digitação em solicitações consome muito recurso. Por exemplo, em um dos discursos de Yandex, a lista de pares para corrigir erros de digitação (bigrams) de palavras diferia 10 vezes em comparação com o número de palavras (unigramas) , o que dizer dos trigramas? Obviamente, isso depende substancialmente da variabilidade das consultas. Parece um pouco estranho quando o corretor automático ocupa metade da memória do produto proposto da empresa, cujo objetivo não é o de resolver o problema de ortografia. Portanto, a questão da implementação de correções sensíveis ao contexto nos mecanismos de pesquisa de produtos de software pode ser muito controversa.

À primeira vista, temos a impressão de que existem muitas soluções prontas para qualquer linguagem de programação que podem ser usadas sem muita imersão nos detalhes da operação de algoritmos, inclusive em sistemas comerciais. Mas, na prática, o desenvolvimento de suas soluções continua. Por exemplo, recentemente, o Joom tomou sua própria decisão de corrigir erros de digitação usando modelos de linguagem para consultas de pesquisa [ 4 ]. A situação é realmente difícil com a disponibilidade de soluções chave na mão? Para esse fim, na medida do possível, foi feita uma ampla visão geral das soluções existentes. Antes de iniciar a revisão, decidiremos como a qualidade do corretor automático é verificada.

Controle de qualidade

A questão de verificar a qualidade do corretor automático é muito controversa. Uma abordagem simples para validação é através do Precision and Recall. De acordo com o padrão ISO, a precisão e a integridade são complementadas pela correção (em inglês “correção”).

A completude (Rechamada) é calculada da seguinte forma: uma lista de palavras corretas é enviada ao auto-corretor (Total_list_true) e o número de palavras que o auto-corretor considera corretas (Spellchecker_true) dividido pelo número total de palavras corretas (Total_list_true) será considerado completo.

R e c h a m a d a = V e r i f i c a d o r O r t o g r á f i c o_{t} r u e o v e r T o t a l_{l} i s t_{t} r u e

$Rechamada = {Verificador Ortográfico \ _true \ over Total \ _list \ _true}$

Para determinar a precisão (Precisão), uma lista de palavras incorretas (Total_list_false) é fornecida à entrada do corretor automático e o número de palavras que o corretor automático considera incorretas (Spell_checker_false), dividido pelo número total de palavras incorretas (Total_list_false), é definido como precisão.

P r e c i s ã o = V e r i f i c a d o r O r t o g r á f i c o_{f} a l s e s o b r e o T o t a l_{l} i s t_{f} a l s e

$Precisão = {Verificador Ortográfico \ _false \ sobre o Total \ _list \ _false}$

Como geralmente essas métricas são informativas e como podem ser úteis, cada uma determina de forma independente. Afinal, a essência desse teste é que a palavra é verificada no dicionário de treinamento. A correção pode ser considerada uma métrica mais visual, segundo a qual o auto- corretor de cada palavra do conjunto de palavras incorretas forma uma lista de candidatos substitutos para os quais essa palavra incorreta pode ser corrigida (lembre-se de que pode haver palavras que não estão contidas no dicionário de treinamento) . Suponha que o tamanho de uma lista de candidatos a substituição seja 5. Com base no fato de que a lista é de 5, 6 grupos serão formados, em um dos quais colocaremos cada palavra errada original de acordo com o seguinte princípio: no 1º grupo - se houver na lista de candidatos a substitutos, a palavra correta em que devemos estar é 1º, no 2º se for o 2º etc. etc. e no último grupo, se a suposta palavra correta não estiver na lista de candidatos a substitutos. Obviamente, quanto mais palavras caírem no 1º grupo e menos no 6º, melhor o corretor automático funciona.

Os autores consideraram a abordagem considerada no artigo [ 5 ], na qual foram comparados os auto-corretores independentes do contexto, com viés para o padrão ISO. Ele também fornece links para outros métodos de avaliação da qualidade.

Por um lado, essa abordagem não se baseia em estatísticas brutas, que podem ser baseadas no modelo de erro de Brill - Moore [ 6 ] ou no modelo de erro de distância ponderada Damerau - Levenshtein.

Para verificar a qualidade do trabalho de um auto-corretor independente do contexto, criamos nosso próprio gerador de erros de digitação, que gerava erros de digitação com layout incorreto e erros de ortografia com base nas estatísticas de erros de digitação enviadas pelo Yandex. Para erros ortográficos, inserções aleatórias, substituições, exclusões, rearranjos foram gerados e o número de erros também variou de acordo com essas estatísticas. Para erros no layout distorcido, a palavra correta foi alterada caractere por caractere inteiramente de acordo com a tabela de conversão de caracteres.

Em seguida, uma série de experimentos foi realizada para toda a lista de palavras no dicionário de treinamento (as palavras do dicionário de treinamento foram corrigidas por incorretas, de acordo com a probabilidade de um erro de digitação específico) . Em média, o auto-corretor corrige as palavras corretamente em 75% dos casos. Sem dúvida, esse número será reduzido quando o dicionário de aprendizado for reabastecido com palavras próximas à distância editorial, uma grande variedade de formas de palavras. Esse problema pode ser resolvido complementando-se com os modelos de linguagem, mas deve-se ter em mente que a quantidade de recursos necessários aumentará significativamente.

Soluções prontas

A consideração de soluções prontas foi realizada com foco no uso próprio e a prioridade foi dada aos corretores automáticos que satisfazem três critérios:
1) linguagem de implementação,
2) tipo de licença,
3) capacidade de atualização.

No desenvolvimento de produtos, o Java é considerado um dos mais populares; portanto, foi dada prioridade ao procurar bibliotecas. Das licenças relevantes: MIT, Public, Apache, BSD. Capacidade de atualização - não mais de 2 anos a partir da última atualização. Durante a pesquisa, foram registradas informações adicionais, por exemplo, sobre a plataforma suportada, os programas adicionais necessários, os recursos do aplicativo, as possíveis dificuldades para o primeiro uso etc. Os links com recursos básicos e úteis para as fontes são fornecidos no final do artigo. Em geral, se não limitado aos critérios acima, o número de soluções existentes é grande. Vamos dar uma breve olhada nos principais e dar mais atenção a apenas alguns.

Historicamente, um dos auto- corretores mais antigos é o Ispell (International Spell), escrito em montador em 1971, posteriormente transferido para C e usa a distância editorial de Damerau-Levenshtein como modelo de erros. Para ele, existe até um dicionário em russo. Posteriormente, ele foi substituído por dois auto- corretores HunSpell (anteriormente MySpell ) e Aspell . Ambos são implementados em C ++ e são distribuídos sob licenças GPL. O HunSpell também é coberto pela GPL / MPL e é usado para corrigir erros de digitação no OpenOffice, LibreOffice, Google Chrome e outras ferramentas.

Existem muitas soluções JS para a Internet e navegadores (incluindo: nodehun-sentenças , nspell , node-markdown-spellcheck , Proofreader , Spellcheck-API - um grupo de soluções baseadas no auto- corretor Hunspell ; grunt-spell - para NodeJS; yaspeller- ci - invólucro para o auto- corretor Yandex.Speller , distribuído no MIT; rousseau - revisor leve em JS - usado para ortografia).

A categoria de soluções pagas inclui: Spellex ; Verificador ortográfico do código fonte - como um aplicativo de desktop; para JS: nanospell ; para Java: Keyoti RapidSpell Spellchecker , JSpell SDK , WinterTree (WinterTree pode até comprar código-fonte por US $ 5.000).

O auto-corretor de Peter Norwig é amplamente utilizado, cujo código Python está disponível publicamente no artigo " Como escrever um corretor ortográfico " [ 7 ]. Com base nessa solução simples, os auto- corretores foram criados em outros idiomas, por exemplo: verificação ortográfica Norvig , verificação ortográfica scala-norvig (no Scala), correção ortográfica de brinquedos - Golang Spellcheck (no GO), pyspellchecker (no Python) . Obviamente, aqui não estamos falando de modelos de linguagem e correção sensível ao contexto.

Para editores de texto, especialmente para o VIM, o vim-dialect , vim-ditto - é distribuído sob uma licença pública; para o Notepad ++ desenvolvido por DspellCheck em C ++, licença GPL; O Emacs possui uma ferramenta para detectar idiomas automaticamente ao imprimir, chamado de palpite , distribuído sob uma licença pública.

Existem serviços separados dos gigantes da pesquisa: Yandex.Speller - da Yandex, sobre o wrapper mencionado acima, google-api-spelling-java (respectivamente, do Google).

Bibliotecas gratuitas para Java: languagetool (licenciado sob LGPL), integra-se à biblioteca de pesquisa de texto Lucene e permite o uso de modelos de linguagem; é necessária a versão 8 do Java; Jazzy (um análogo da Aspell ) é licenciado sob LGPLv2 e não é atualizado desde 2005, e em 2013 foi portado para o GitHub. À semelhança deste auto-corretor, uma solução separada foi feita [ 8 ]; O Jortho (Java Orthography) é distribuído sob a GPL e permite o uso gratuito exclusivamente para fins não comerciais, para fins comerciais - por uma taxa adicional; Jaspell (licenciado sob BSD e não é atualizado desde 2005); Open Source Java Suggester - não é atualizado desde 2013, distribuído pela SoftCorporation LLC e permite uso comercial; LuceneSpellChecker é um autocorrector Lucene escrito em Java e distribuído sob a licença Apache.

Por muito tempo, Wolf Garbe lidou com erros de digitação, propôs os algoritmos SymSpell (sob a licença MIT) e LinSpell (sob a LGPL) com implementações em C # [ 9 ] que usam a distância Damerau-Levenshtein para o modelo de erro. A peculiaridade de sua implementação é que, na fase de geração de possíveis erros para a palavra de entrada, apenas exclusões são usadas, em vez de todos os tipos de exclusões, inserções, substituições e permutações. Em comparação com a implementação do auto-corretor de Peter Norwig, ambos os algoritmos funcionam mais rapidamente devido a isso, enquanto o aumento na velocidade aumenta significativamente se a distância Damerau-Levenshtein se tornar maior que dois. Além disso, devido ao fato de apenas exclusões serem usadas, o tempo de formação do dicionário é reduzido. A diferença entre os dois algoritmos é que o LinSpell é mais econômico na memória e mais lento na velocidade de pesquisa, SymSpell - vice-versa. Em uma versão posterior, o SymSpell corrige erros de ortografia dividida. Modelos de idioma não são usados.

Os corretores automáticos mais recentes e promissores para uso com modelos de linguagem e correção de erros sensíveis ao contexto incluem Yandex.Speller , JamSpell [ 10 ], DeepPavlov [ 11 ]. Os dois últimos são distribuídos livremente: JamSpell (MIT), DeepPavlov (sob Apache).

O Yandex.Speller usa o algoritmo CatBoost, trabalha com várias linguagens e corrige todos os tipos de erros, mesmo levando em consideração o contexto. A única solução encontrada que corrige erros de layout e transliteração incorretos. A solução possui versatilidade, o que a torna popular. Sua desvantagem é que é um serviço remoto, e sobre restrições e condições de uso podem ser encontradas aqui [ 12 ]. O serviço funciona com um número limitado de idiomas; você não pode adicionar palavras e gerenciar o processo de correção. De acordo com o recurso [ 3 ], de acordo com os resultados da competição RuSpellEval, este auto-corretor apresentou a mais alta qualidade de correções. O JamSpell é o corretor automático mais rápido conhecido (implementação em C ++); existem pastas prontas para outros idiomas. Corrige erros apenas nas próprias palavras e trabalha com um idioma específico. Você não pode usar a solução no nível de unigramas e bigrams. Para obter uma qualidade aceitável, é necessário um grande texto de treinamento.
O DeepPavlov possui algumas boas práticas, no entanto, a integração dessas soluções e o suporte subsequente em seu próprio produto pode causar dificuldades, pois trabalhar com elas exige a conexão de um ambiente virtual e o uso de uma versão anterior do Python 3.6. O DeepPavlov oferece uma escolha de três implementações prontas de auto- corretores , em duas das quais os modelos de erro Bril-Moore são usados e em dois modelos de linguagem. Ele só corrige erros de ortografia e a opção com um modelo de erros baseado na distância Damerau-Levenshtein pode corrigir erros de gravação contínua.

Mencionarei outra das abordagens modernas para corrigir erros de digitação, que se baseia no uso de representações vetoriais de palavras (Word Embeddings). Sua vantagem é que ele pode ser usado para criar um auto-corretor para corrigir palavras com base no contexto. Mais detalhes sobre essa abordagem podem ser encontrados aqui [ 13 ]. Mas, para usá-lo para corrigir erros de digitação de consultas de pesquisa, você precisará acumular um grande log de consultas. Além disso, o modelo em si pode ser bastante amplo em termos de consumo de memória, o que afetará a complexidade da integração ao produto.

Escolha de Naumen

Das soluções prontas para Java, um auto-corretor da Lucene foi selecionado (distribuído sob uma licença da Apache). Permite corrigir erros de digitação em palavras. O processo de aprendizado é rápido: por exemplo, a formação de uma estrutura de dados de dicionário especial - um índice para 3 milhões de linhas - foi de 30 segundos em um processador Intel Core i5-8500 de 3,00 GHz, 32 Gb de RAM, Lucene 8.0.0. Nas versões anteriores, o tempo pode ser 2 vezes maior. O tamanho do dicionário de treinamento é de 3 milhões de linhas (~ 73 Mb de arquivo txt), a estrutura do índice é de ~ 235 Mb. Para o modelo de erro, você pode escolher a distância entre Jaro-Winkler, Levenshtein, Damerau-Levenshtein, N-Gram, se necessário, pode adicionar a sua própria. Se necessário, é possível conectar um modelo de linguagem [ 14 ]. Os modelos são conhecidos desde 2001, mas sua comparação com soluções modernas conhecidas no domínio público não foi encontrada. O próximo passo é verificar o trabalho deles.

A solução baseada em Lucene resultante apenas corrige erros nas próprias palavras. Não é difícil adicionar uma correção de um layout distorcido do teclado a qualquer solução por meio de uma tabela de conversão apropriada, reduzindo assim a possibilidade de saída irrelevante para 10% (de acordo com as estatísticas de erros de digitação). Além disso, é fácil adicionar escrita separada de 2 palavras fundidas e transliteração.

As principais desvantagens da solução são a necessidade de conhecimento de Java, a falta de casos de uso detalhados e a documentação detalhada, o que se reflete em uma diminuição na velocidade de desenvolvimento de soluções para especialistas em Data Science. Além disso, erros de digitação com uma distância Damerau-Levenshtein superior a 2 não são corrigidos. Novamente, se prosseguirmos nas estatísticas de deturpação, mais de 2 erros em uma palavra ocorrerão com menos frequência do que em 5% dos casos. A necessidade de complicar o algoritmo, em particular, justifica um aumento no consumo de memória? Já depende do caso do cliente. Se houver recursos adicionais, por que não usá-los?

Principais recursos para corretores automáticos acessíveis :

Referências

Visão geral das soluções Open Typo Correction

Controle de qualidade

Soluções prontas

Escolha de Naumen

More articles: