Algoritmo de comparação de palavras (não por ordem alfabética)

votos
5

Eu preciso para codificar uma solução para um determinado requisito, e eu queria saber se alguém é ou familiarizado com uma biblioteca off-the-shelf que pode alcançá-lo, ou pode dirigir-me ao melhor prática. Descrição:

O usuário insere uma palavra que é suposto ser uma das várias opções fixas (I manter as opções em uma lista). Eu sei que a entrada deve ser em um membro na lista, mas uma vez que é a entrada do usuário, ele / ela pode ter cometido um erro. Eu estou procurando um algoritmo que vai me dizer o que é a palavra mais provável que o usuário quis dizer. Eu não tenho qualquer contexto e eu não posso forçar o usuário a escolher de uma lista (ou seja, ele deve ser capaz de introduzir a palavra livre e manualmente).

Por exemplo, digamos que a lista contém as palavras água, “quarto”, cerveja, “beterraba”, “inferno”, “Olá” e aardvark.

A solução deve levar em conta os diferentes tipos de erros normais:

  • erros de velocidade (por exemplo, dobrando caracteres, soltando caracteres etc)
  • Teclado erros adjacente caracteres (por exemplo, qater para “água”)
  • erros não-nativos Inglês (por exemplo, quater para “quarter”)
  • E assim por diante...

A solução óbvia é comparar letra por letra e dar pesos penalidade a cada letra diferente, carta extra e letra que falta. Mas esta solução ignora milhares de erros padrão Tenho certeza que estão listados em algum lugar. Eu tenho certeza que existem heurísticas aí que lidar com todos os casos, tanto específicos e gerais, provavelmente usando um grande banco de dados de incompatibilidades padrão (estou aberto a soluções de dados-pesado).

Eu estou codificação em Python, mas eu considero essa questão da língua-agnóstico.

Quaisquer recomendações / pensamentos?

Publicado 19/05/2009 em 17:45
fonte usuário
Em outras línguas...                            


7 respostas

votos
10

Você quer ler como o Google faz isso: http://norvig.com/spell-correct.html

Edit: Algumas pessoas mencionaram algoritmos que definem uma métrica entre uma determinada palavra de utilizador e uma palavra candidato (levenshtein, soundex). Esta não é, contudo, uma solução completa para o problema, uma vez que seria igualmente necessário uma estrutura de dados para executar eficientemente uma busca vizinho mais próximo não-euclidiana. Isso pode ser feito, por exemplo, com a Árvore da capa: http://hunch.net/~jl/projects/cover_tree/cover_tree.html

Respondeu 19/05/2009 em 17:49
fonte usuário

votos
6

Uma solução comum é calcular a distância Levenshtein entre a entrada e seus textos fixos. A distância Levenshtein de duas cordas é apenas o número de operações simples - inserções, exclusões e substituições de um único personagem - necessário para transformar uma das cordas para o outro.

Respondeu 19/05/2009 em 17:51
fonte usuário

votos
2

Você já pensou em algoritmos que comparam por sons fonéticos, como soundex ? Não deve ser muito difícil de produzir representações soundex da sua lista de palavras, armazená-los e, em seguida, obter um soundex da entrada do usuário e encontrar a correspondência mais próxima lá.

Respondeu 19/05/2009 em 17:49
fonte usuário

votos
1

Se o conjunto de dados é muito pequeno, simplesmente comparando a distância Levenshtein em todos os itens de forma independente deve bastar. Se for maior, porém, você vai precisar usar um BK-Tree sistema de indexação semelhantes ou. O artigo I ligada a descreve como encontrar jogos dentro de uma determinada distância Levenshtein, mas é bastante simples de se adaptar a fazer buscas vizinho mais próximo (e deixado como um exercício para o leitor;).

Respondeu 20/05/2009 em 10:04
fonte usuário

votos
1

Olhe para o algoritmo Bitap. Ele qualifica bem para o que você quer fazer, e ainda vem com um exemplo de código fonte na Wikipédia.

Respondeu 19/05/2009 em 17:56
fonte usuário

votos
0

Tente pesquisar por "Levenshtein distância" ou "editar distância". Ele conta o número de operações de edição (apagar, inserir, alterar carta) que você precisa para transformar uma palavra em outra. É um algoritmo comum, mas, dependendo do problema que você pode precisar de algo especial com pesos diferentes para os diferentes tipos de erros de digitação.

Respondeu 19/05/2009 em 17:55
fonte usuário

votos
0

Embora não pode resolver todo o problema, você pode querer considerar usando o algoritmo soundex como parte da solução. Uma rápida pesquisa no google de "soundex" e "python" mostrou algumas implementações de python do algoritmo.

Respondeu 19/05/2009 em 17:54
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more