Quais algoritmos posso usar para detectar se artigos ou postagens são duplicados?

17

Estou tentando detectar se uma postagem de artigo ou fórum é uma entrada duplicada no banco de dados. Pensei um pouco sobre isso, chegando à conclusão de que alguém que duplicou o conteúdo o faria usando um dos três (em descendente difícil de detectar):

  1. cópia simples cole o texto inteiro
  2. copiar e colar partes do texto, mesclando-o com seus próprios
  3. copie um artigo de um site externo e disfarce como seu

Preparando o texto para análise

Basicamente qualquer anomalia; o objetivo é tornar o texto o mais "puro" possível. Para resultados mais precisos, o texto é "padronizado" por:

  1. Retirar espaços em branco duplicados e aparar à esquerda e à direita.
  2. Novas linhas são padronizadas para \ n.
  3. Tags HTML são removidas.
  4. Usando um RegEx chamado Daring Fireball, os URLs são removidos.
  5. Eu uso o código BB no meu aplicativo para que vá para.
  6. (ä) cêntricos e estrangeiros (além do inglês) são convertidos para sua forma não estrangeira.

Eu armazeno informações sobre cada artigo na (1) tabela de estatísticas e na (2) tabela de palavras-chave.

(1) Tabela de estatísticas As estatísticas a seguir são armazenadas sobre o conteúdo textual (muito parecido com este post)

  1. comprimento do texto
  2. contagem de letras
  3. contagem de palavras
  4. contagem de sentenças
  5. média de palavras por frase
  6. índice de legibilidade automatizado
  7. pontuação de nevoeiro

Para os idiomas europeus, Coleman-Liau e o Índice de Legibilidade Automatizada devem ser usados, pois não usam contagem de sílabas; portanto, devem produzir uma pontuação razoavelmente precisa.

(2) Tabela de palavras-chave

As palavras-chave são geradas pela exclusão de uma lista enorme de palavras de parada (palavras comuns), por exemplo, 'the', 'a', 'of', 'to', etc., etc.

Dados de amostra

  • text_length, 3963
  • letter_count, 3052
  • word_count, 684
  • frase_contagem, 33
  • word_per_sentence, 21
  • gunning_fog, 11.5
  • auto_read_index, 9.9
  • palavra-chave 1, morta
  • palavra-chave 2, oficiais
  • palavra chave 3, polícia

Deve-se observar que, depois que um artigo é atualizado, todas as estatísticas acima são regeneradas e podem ter valores completamente diferentes.

Como eu poderia usar as informações acima para detectar se um artigo publicado pela primeira vez já existe no banco de dados?

Sei que tudo o que projetar não será perfeito, o maior risco é (1) O conteúdo que não é duplicado será sinalizado como duplicado (2) O sistema permite a passagem do conteúdo duplicado.

Portanto, o algoritmo deve gerar um número de avaliação de risco de 0, sem risco duplicado 5, sendo possível duplicado e 10 sendo duplicado. Qualquer coisa acima de 5, há uma boa possibilidade de o conteúdo ser duplicado. Nesse caso, o conteúdo pode ser sinalizado e vinculado às possíveis duplicatas do artigo, e um humano pode decidir se deseja excluir ou permitir.

Como eu disse antes, estou armazenando palavras-chave para todo o artigo, mas gostaria de saber se poderia fazer o mesmo com base em parágrafos; isso também significaria separar ainda mais meus dados no banco de dados, mas também facilitaria a detecção (2) no meu post inicial.

Estou pensando em média ponderada entre as estatísticas, mas em que ordem e quais seriam as consequências ...

algorithms Michael
fonte
Se for uma correspondência exata, você pode simplesmente definir um campo como único. Caso contrário, você precisará decidir em que momento um texto pode ser considerado uma cópia ou um trabalho derivado de perto.
James P.
2
Há muitas direções nas quais esse tipo de análise pode ser adotado. As pessoas escrevem livros inteiros sobre esse tipo de tópico. Se seu objetivo é determinar a "proximidade relativa", você realmente tem poucas opções a não ser se aprofundar no que se chama Processamento de Linguagem Natural e Aprendizado de Máquina . É assim que os cientistas da computação chamam, mas na verdade são apenas análises estatísticas avançadas. Um bom ponto de partida pode ser observar as distâncias de Levenshtein, mas estatísticas "burras", como contagem de palavras / frases, provavelmente farão muito pouco por você.
Rdlowrey 8/08/12
1
Além disso, antes de ser migrado do SO esta foi marcado [php], de modo que você pode verificar nativo do php levenshtein função
rdlowrey
Ótima idéia de ter um teste humano provavelmente duplicado! Você pode decidir automaticamente que> 7 é uma duplicata e <6 é diferente e só faz com que os humanos verifiquem pontuações de 6 ou 7. Sei que, com a identificação de spam, existe uma máquina que não sabe E-humana- categoria não sabe; uma área cinza entre uma cópia quase duplicada e uma obra original, onde o melhor que você pode fazer é fazer uma decisão arbitrária.
precisa saber é o seguinte
@rdlowrey - Os algoritmos de Levenshtein são o que eu usei em um projeto semelhante que fiz em C #. Eu concordo, é um bom lugar para começar e pode ser suficiente.
jfrankcarr

Respostas:

4

Existem muitos algoritmos que lidam com a similaridade de documentos na PNL. Aqui está um artigo seminal descrevendo vários algoritmos. A wikipedia também possui uma coleção maior. Sou a favor da medida de Jaro Winkler e a usei para projetos de pós-graduação em métodos aglomerativos de agrupamento.

Candide
fonte
6

Dê uma olhada no algboritmo de Rabin-Karp . Ele usa um hash rotativo, como o rsync usa para minimizar os bytes transmitidos durante uma sincronização. Ao ajustar o tamanho da janela que você usa para o hash, você pode torná-lo mais ou menos sensível. O RK é usado para, entre outras coisas, a detecção de plágio, que está basicamente procurando uma espécie de fraude.

Peter Rowell
fonte
4
O problema que o OP descreve parece exatamente como a detecção de plágio , e eu sugiro isso como o primeiro lugar para procurar ajuda. (Apenas certifique-se de identificar suas fontes!)
Caleb
4

Um primeiro passo para isso pode ser detectar sentenças (ou algum outro bloco de dados razoável. Pegue esses blocos e retire quaisquer dados mete, espaço em branco aleatório em html, retornos etc. Pegue um MD5 de resultado e armazene-o em uma tabela. então combine contra esses blocos para tentar encontrar combinações.

Se isso não funcionar, você pode tentar n-gramas. Aqui você precisa de uma entrada de cada palavra na página, mas ela deve oferecer boas correspondências.

http://en.wikipedia.org/wiki/N-gram

gam3
fonte
As medidas baseadas em n gramas são muito melhores que os hashes MD5, especialmente para dados semiestruturados, como html.
Candide
1

Para uma matemática matemática exata, eu armazenaria um hash e depois o compararia.

Penso que os sistemas utilizados nos exames medem grupos de palavras e depois a frequência de grupos de cada tamanho. Por exemplo, uma cadeia de 30 palavras copiadas terá 5 pontos de risco e 5 ocorrências de 10 cadeias de palavras terão 5 pontos. Em seguida, você terá uma limitação de 30 pontos por 500 palavras.

Você realmente precisa de um algoritmo semântico para que palavras como 'also' e 'e' sejam analisadas da mesma forma.

Lhama invertida
fonte