Como faço compare as frases a semelhança?

Question

Ao entrar em uma questão, stackoverflow apresenta uma lista de perguntas que ele considera susceptível de cobrir o mesmo tópico.Eu tenho visto características semelhantes em outros sites ou em outros programas, também (arquivo de Ajuda de sistemas, por exemplo), mas eu nunca programado algo como isso mesmo.Agora estou curioso para saber que tipo de algoritmo pode-se usar para isso.

A primeira abordagem que vem à mente é a de dividir a frase em palavras e procure frases que contenham essas palavras.Antes de você fazer isso, você provavelmente quer jogar fora insignificante palavras (como o 'o', 'a', 'não', etc.) e, em seguida, você vai querer para classificar os resultados.

Ei, espere - vamos fazer isso para páginas da web e, em seguida, podemos ter um ...watchamacallit ...- um "motor de busca" e, em seguida, podemos vender anúncios e, em seguida, ...

Não, a sério, quais são as formas comuns para resolver este problema?

Answer 1

Uma abordagem é o chamado saco-de-palavras de modelo.

Como você adivinhou, primeiro você contar quantas vezes as palavras aparecem no texto (normalmente chamado de documento em PNL-linguagem).Em seguida, você tem que jogar fora o chamado parar de palavras, tais como "o", "um", "ou" e assim por diante.

Você é deixado com palavras e contagem de palavras.Fazer isso por um tempo e você terá um abrangente conjunto de palavras que aparecem nos documentos.Em seguida, você pode criar um índice para estas palavras:"projetada" é 1, "apple" é 2, ..., "z-index" é 70092.

Agora você pode levar a sua palavra sacos e transformá-los em vetores.Por exemplo, se seu documento contém duas referências para aardvarks e nada mais, ele teria esta aparência:

[2 0 0 ... 70k zeroes ... 0].

Após isso, você pode contar o "ângulo entre dois vetores com um produto escalar.Quanto menor o ângulo, mais os documentos.

Esta é uma versão simples, e existem outras técnicas mais avançadas.Pode o Taxas de ser com você.

Answer 2

@Hanno você deve tentar o algoritmo de distância de Levenshtein.Dada uma seqüência de caracteres de entrada s e uma lista de cadeias de caracteres t o mesmo para cada seqüência de caracteres u no t e voltar a um com o mínimo de distância de Levenshtein.

http://en.wikipedia.org/wiki/Levenshtein_distance

Veja um exemplo de uma implementação de Java em http://www.javalobby.org/java/forums/t15908.html

Answer 3

Para aumentar o saco-de-palavras idéia:

Existem algumas maneiras que você pode, também, prestar atenção ao de n-gramas, seqüências de duas ou mais palavras mantidos em ordem.Você pode querer fazer isso porque uma pesquisa por "espaço complexidade" é muito mais do que uma pesquisa para as coisas com "espaço" E "complexidade", pois o significado dessa frase é mais do que a soma de suas partes;isto é, se você obter um resultado que fala sobre a complexidade do espaço exterior e o universo, provavelmente não é isso que a busca por "espaço complexidade" realmente significava.

A ideia chave de processamento de linguagem natural aqui é o de informação mútua, que permite a você (através de algoritmos) para julgar se é ou não é uma frase é realmente uma frase específica (tais como "espaço de complexidade") ou palavras, que são, coincidentemente adjacentes.Matematicamente, a idéia principal é perguntar, probabilistically, se essas palavras aparecem próximas umas das outras com mais frequência do que seria de adivinhar por suas freqüências sozinho.Se você ver uma frase com uma alta de informação mútua pontuação em sua consulta de pesquisa (ou enquanto indexação), você pode obter melhores resultados, tentando manter estas palavras em sequência.

Answer 4

A partir do meu (bem pequena) de experiência no desenvolvimento de pesquisa de texto completo motores:Eu olhava para cima questões que contenham algumas palavras da consulta (no seu caso, a consulta é a sua pergunta).Com certeza, palavras de ruído deve ser ignorado e nós pode querer verificar para consulta "forte", palavras como "ASP.Net" para restringir o escopo da pesquisa.http://en.wikipedia.org/wiki/Index_(search_engine)#Inverted_indices'>índices Invertidos são comumente usados para encontrar perguntas com palavras, estamos interessados.

Depois de encontrar perguntas com palavras da consulta, nós podemos calcular a distância entre palavras, estamos interessados em perguntas, de modo a questão com "frases de semelhança' texto postos mais altos do que questão com " discutir semelhança, ouve-se frases a seguir...' texto.