Algoritmo para encontrar artigos com texto semelhante

StackOverflow https://stackoverflow.com/questions/246961

Pergunta

Eu tenho muitos artigos em um banco de dados (com título, texto), eu estou procurando um algoritmo para encontrar o X artigos mais semelhantes, algo como "Questões relacionadas" de estouro de pilha quando você faz uma pergunta.

Eu tentei googling para isso, mas só encontrou páginas sobre outras questões "semelhantes texto", algo como comparar cada artigo com todos os outros e armazenar um lugar similaridade. SO faz isso em "tempo real" no texto que acabou de digitar.

Como?

Foi útil?

Solução

Editar distância não é um candidato provável, como seria de ortografia / palavra de ordem dependente, e muito mais computacionalmente caro do que Will está levando a crer, considerando o tamanho e número dos documentos que você realmente estar interessado em pesquisar.

Algo como Lucene é o caminho a percorrer. Você índice todos os seus documentos, e então quando você quer encontrar documentos semelhantes a um determinado documento, você transformar o seu documento dado em uma consulta, e procure o índice. Internamente Lucene estará usando tf-idf e um índice invertido para fazer todo o processo levar uma quantidade de tempo proporcional ao número de documentos que poderiam combinar, não o número total de documentos em a coleção.

Outras dicas

Ela depende de sua definição de similiar.

O algoritmo edit-distância é o algoritmo padrão para (latim) sugestões do dicionário, e pode trabalhar em textos inteiros. Dois textos são semelhantes se eles têm basicamente as mesmas palavras (eh letras) na mesma ordem. Assim, os dois seguintes comentários livro seria bastante semelhante:

1) "Este é um grande livro"

2) "Estes não são grandes livros"

(O número de cartas para remover, inserir, eliminar ou alterar a transformar (2) em (1) é denominado o 'distância de edição'.)

Para implementar isso, você gostaria de visitar cada revisão programática. Isto não é talvez tão caro quanto parece, e se é muito caro que você poderia fazer as comparações como uma tarefa de fundo e armazenar o n-mais-similiar em si um campo de banco de dados.

Outra abordagem é compreender algo da estrutura de línguas (latim). Se você tira curta palavras (não-capitialised ou cotados), e pesos atribuir a palavras (ou prefixos) que são comuns ou original, você pode fazer uma comparação Bayesianesque. Os dois seguintes revisões de livro pode ser simiplied e encontrado para ser semelhante:

3) "A Revolução Francesa foi blah blah Guerra e Paz, blá, blá França." -> França / Francês (2) Revolution (1) Guerra (1) Paz (1) (note que um dicionário foi usado para combinar França e francês)

4) "Este livro é blá blá uma revolução na cozinha francesa." -> França (1) Revolution (1)

Para implementar isso, você iria querer identificar as 'palavras-chave' em um comentário quando foi criado / atualizado, e para encontrar comentários similiar usar essas palavras-chave no onde cláusula de uma consulta (o ideal 'texto completo' busca se o banco de dados suporta TI), com talvez um pós-processamento do resultados-set por conseguir os candidatos encontrados.

Livros também têm categorias - são thrillers definidos na França similiar aos estudos históricos da França, e assim por diante? Meta-dados além título e texto pode ser útil para manter resultados relevantes.

O tutorial neste href="http://www.catalysoft.com/articles/StrikeAMatch.html" ligação soa como ele pode ser o que você precisa. É fácil de seguir e funciona muito bem.

Seu algoritmo premia ambos os substrings comuns e uma ordenação comum desses substrings e assim deve escolher títulos semelhantes bastante bem.

Eu sugiro índice seus artigos usando Apache Lucene , a alta desempenho, biblioteca motor de pesquisa de texto full-featured escrito inteiramente em Java. É uma tecnologia adequada para praticamente qualquer aplicação que requer pesquisa de texto completo, especialmente multi-plataforma . Uma vez posicionado, você pode facilmente encontrar artigos relacionados.

Um algoritmo comum usado é o Self-Organizing Map . É um tipo de rede neural que irá automaticamente categorizar seus artigos. Então você pode simplesmente encontrar o local que um artigo atual está no mapa e todos os artigos perto dele estão relacionados. A parte importante do algoritmo é como se fosse vector quantize sua entrada . Existem várias maneiras de fazer com com texto. Você pode botar seu documento / título, você pode contar palavras e usar isso como uma n vetor dimensional, etc. Espero que ajude, embora eu possa ter aberto uma caixa de Pandora para você de uma viagem sem fim no AI.

O mesmo acontece com a comparação apenas no título, não no corpo do texto da questão, portanto, apenas em cordas bastante curtos.

Você pode usar seu algoritmo (nenhuma idéia o que parece) no título do artigo e as palavras-chave. Se você tem mais tempo de CPU para queimar, também sobre os resumos de seus artigos.

Destacando a sugestão Lucene para full-text, mas nota que o Java não é um requisito; um .NET porta está disponível . veja também a principal página Lucene para links para outros projetos, incluindo Lucy, uma porta C.

Talvez o que você está procurando é algo que faz parafraseando . Eu só tenho conhecimento superficial desta, mas parafraseando é um linguagem natural de processamento conceito para determinar se dois passagens do texto, na verdade média a mesma coisa -. embora a podem usar palavras completamente diferentes

Infelizmente eu não sei de todas as ferramentas que lhe permitem fazer isso (embora eu estaria interessado em encontrar um)

Você pode usar SQL índice de texto completo do servidor para obter a comparação inteligente, acredito que isso é usando uma chamada ajax, que faz uma consulta para retornar as perguntas semelhantes.

Que tecnologias você está usando?

Se você estiver procurando por palavras que ferem tanto, você poderia converter para soundex e as palavras soundex para corresponder ... trabalhou para mim

Eu tentei alguns métodos, mas nenhum funciona well.One pode obter um resultado relativamente satified assim: Primeiro: obter um código Google SimHash para cada parágrafo de todo o texto e armazená-lo em databse. Segundo: Índice para o código SimHash. Terceiro: o processo de seu texto para ser comparado como acima, obter um código SimHash e pesquisar todo o texto pelo índice SimHash que além formar uma distância Hamming como 5-10. Em seguida, compare simility com vector prazo. Isso pode obras para big data.

A ligação em @ de alex77 pontos resposta a uma Sorensen -Dice Coeficiente que foi descoberto independentemente pelo autor desse artigo -. ler o artigo está muito bem escrito e bem a pena

Eu acabei usando esse coeficiente para minhas próprias necessidades. No entanto, o coeficiente original pode produzir resultados errados quando se lida com

  • pares de palavras de três letras que contêm um erro de ortografia, por exemplo, [and,amd] e
  • três pares palavra letra que são anagramas exemplo [and,dan]

No primeiro caso Dice relata erroneamente um coeficiente de zero, ao passo que no segundo caso, o coeficiente de transforma-se como 0,5, o que é erroneamente alta.

Uma melhoria tem sido sugerido que em sua essência consiste em tomar o primeiro e o último caractere da palavra e criar um bigram adicional.

No meu ponto de vista a melhoria só é realmente necessário para 3 palavras da letra - em palavras mais longas as outras bigramas ter um efeito tampão que encobre o problema. Meu código que implementa esta melhoria é dada abaixo. 

function wordPairCount(word)
{
 var i,rslt = [],len = word.length - 1;
 for(i=0;i < len;i++) rslt.push(word.substr(i,2));
 if (2 == len) rslt.push(word[0] + word[len]);
 return rslt;
}

function pairCount(arr)
{
 var i,rslt = [];
 arr = arr.toLowerCase().split(' ');
 for(i=0;i < arr.length;i++) rslt = rslt.concat(wordPairCount(arr[i]));
 return rslt;
}

function commonCount(a,b)
{
 var t;
 if (b.length > a.length) t = b, b = a, a = t; 
 t = a.filter(function (e){return b.indexOf(e) > -1;});
 return t.length;
}

function myDice(a,b)
{
 var bigrams = [],
 aPairs = pairCount(a),
 bPairs = pairCount(b);
 debugger;
 var isct = commonCount(aPairs,bPairs);
 return 2*commonCount(aPairs,bPairs)/(aPairs.length + bPairs.length); 
}

$('#rslt1').text(myDice('WEB Applications','PHP Web Application'));
$('#rslt2').text(myDice('And','Dan'));
$('#rslt3').text(myDice('and','aMd'));
$('#rslt4').text(myDice('abracadabra','abracabadra'));
*{font-family:arial;}
table
{
 width:80%;
 margin:auto;
 border:1px solid silver;
}

thead > tr > td
{
 font-weight:bold;
 text-align:center;
 background-color:aqua;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.0.0/jquery.min.js"></script>
<table>
<thead>
<tr>
<td>Phrase 1</td>
<td>Phrase 2</td>
<td>Dice</td>
</tr>
<thead>
<tbody>
<tr>
<td>WEB Applications</td>
<td>PHP Web Application</td>
<td id='rslt1'></td>
</tr>
<tr>
<td>And</td>
<td>Dan</td>
<td id='rslt2'></td>
</tr>
<tr>
<td>and</td>
<td>aMd</td>
<td id='rslt3'></td>
</tr>
<tr>
<td>abracadabra</td>
<td>abracabadra</td>
<td id='rslt4'></td>
</tr>
</tbody>
</table>

Observe o erro de ortografia deliberada no último exemplo: Abraça Dabra vs Abraça Badra . Mesmo que nenhuma correção bigram extra é aplicado o coeficiente relatado é 0.9. Com a correção seria de 0,91.

Felizmente, isso vai ajudar outras pessoas que se deparam com esta discussão.

Dado um texto de exemplo, este Listas programa os textos repositório ordenados por semelhança: implementação simples de saco de palavras em C ++ . O algoritmo é linear no comprimento total do texto da amostra e os textos do repositório. Além disso, o programa é multi-threaded para processar textos repositório em paralelo.

Aqui está o algoritmo core: 

class Statistics {
  std::unordered_map<std::string, int64_t> _counts;
  int64_t _totWords;

  void process(std::string& token);
public:
  explicit Statistics(const std::string& text);

  double Dist(const Statistics& fellow) const;

  bool IsEmpty() const { return _totWords == 0; }
};

namespace {
  const std::string gPunctStr = ".,;:!?";
  const std::unordered_set<char> gPunctSet(gPunctStr.begin(), gPunctStr.end());
}

Statistics::Statistics(const std::string& text) {
  std::string lastToken;
  for (size_t i = 0; i < text.size(); i++) {
    int ch = static_cast<uint8_t>(text[i]);
    if (!isspace(ch)) {
      lastToken.push_back(tolower(ch));
      continue;
    }
    process(lastToken);
  }
  process(lastToken);
}

void Statistics::process(std::string& token) {
  do {
    if (token.size() == 0) {
      break;
    }
    if (gPunctSet.find(token.back()) != gPunctSet.end()) {
      token.pop_back();
    }
  } while (false);
  if (token.size() != 0) {
    auto it = _counts.find(token);
    if (it == _counts.end()) {
      _counts.emplace(token, 1);
    }
    else {
      it->second++;
    }
    _totWords++;
    token.clear();
  }
}

double Statistics::Dist(const Statistics& fellow) const {
  double sum = 0;
  for (const auto& wordInfo : _counts) {
    const std::string wordText = wordInfo.first;
    const double freq = double(wordInfo.second) / _totWords;
    auto it = fellow._counts.find(wordText);
    double fellowFreq;
    if (it == fellow._counts.end()) {
      fellowFreq = 0;
    }
    else {
      fellowFreq = double(it->second) / fellow._totWords;
    }
    const double d = freq - fellowFreq;
    sum += d * d;
  }
  return std::sqrt(sum);
}

A maneira mais simples e rápida de similaridade comparar entre resumos é provavelmente utilizando o conceito set. Primeiro converter textos abstratos em conjunto de palavras. Em seguida, verificar o quanto cada conjunto se sobrepõe. conjunto de recursos do Python vem muito mão executar esta tarefa. Você ficaria surpreso ao ver o quão bem este método compara a esses "papéis semelhantes / relacionado" opções lá fora fornecido pelo GScholar, ADS, WOS ou Scopus.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top