Encontrar conteúdo duplicado usando o MySQL e PHP

Question

Eu estou enfrentando um problema no desenvolvimento de meu aplicativo web, aqui está a descrição:

Esta webapp (ainda em alpha) é baseado em conteúdo gerado pelo usuário (artigos geralmente curtos, embora seu comprimento pode se tornar bastante grande, cerca de um quarto da tela), cada usuário envia pelo menos 10 desses artigos, de modo que o número deve crescer muito rápido. Por natureza, cerca de 10% dos artigos será duplicada, então eu preciso de um algoritmo para buscá-los.

Eu vim acima com os seguintes passos:

1. No envio buscar um comprimento de texto e armazená-lo em uma mesa separada (article_id, comprimento), o problema é que os artigos são codificados usando special_entities PHP () função e conteúdo usuários post com ligeira modificações (alguém vai perder a vírgula, sotaque ou mesmo pular algumas palavras)
2. Em seguida, recuperar todas as entradas do banco de dados com intervalo de comprimento = new_post_length +/- 5% (que eu deveria usar um outro limite, tendo em mente que o fator humano em artigos submissão?)
3. Obter os primeiros 3 palavras-chave e compará-los com os artigos obtidos na etapa 2
4. Ter um conjunto final com o maior número de partidas prováveis ??comparar a nova entrada usando a função Levenstein () do PHP

Este processo deve ser executado no artigo apresentação, não usando cron. No entanto, eu suspeito que irá criar cargas pesadas no servidor.

Você poderia fornecer alguma idéia por favor?

Obrigado! Mike

Answer 1

Texto semelhança / plagiat / duplicado é um grande tema. Há tantas algos e soluções.

Lenvenstein não irá funcionar no seu caso. Você só pode usá-lo em pequenos textos (devido à sua "complexidade" que iria matar o seu CPU).

Alguns projetos usam o "alinhamento local adaptativa de palavras-chave" (você vai encontrar informações sobre isso no google.)

Além disso, você pode verificar isso (Verifique as 3 ligações na resposta, muito instrutivo):

Cosine semelhança vs Hamming distância

Esperamos que isto ajude.

Answer 2

Eu gostaria de salientar que git, o sistema de controle de versão, tem excelentes algoritmos para detectar conteúdo duplicado ou quase duplicado. Quando você faz um commit, ele vai mostrar os arquivos modificados (independentemente da mudança de nome), e qual a percentagem alterado.

É open source, e em grande parte escrito em pequeno, focado programas C. Talvez haja algo que você poderia usar.

Answer 3

Você poderia projetar seu aplicativo para reduzir a carga por não ter que verificar cadeias de texto e palavras-chave contra todas as outras mensagens na mesma categoria. E se você tivesse os usuários enviar o conteúdo de terceiros que estão fazendo referência como urls? Veja Tumblr implementation-- basicamente há um campo de texto de forma livre de modo que cada usuário pode comentar e criar a sua própria parte narrativa do conteúdo do post, mas os campos, então não são formatados também dependendo do tipo de referência o usuário está adicionando (vídeo, imagem, link, citação, etc.) Uma melhoria no Tumblr seria deixar o add usuário como muitos / poucos tipos de conteúdo formatado como eles querem em um determinado posto.

Em seguida, você está apenas verificando contra os tipos conhecidos como uma URL ou código de vídeo de incorporação. Combine isso com a sugestão de rexem para forçar os usuários a classificar por categoria ou gênero de algum tipo, e você terá um alcance muito menor para procurar duplicatas.

Além disso, se você pode dar a cada usuário uma maneira de postar em seu próprio "fluxo", então não importa se muitas pessoas duplicar o mesmo conteúdo. Dar às pessoas alguma forma para votar a partir dos fluxos individuais para uma "página" fluxo de nível principal para que a comunidade pode regular quando vêem os itens duplicados. Em vez de um voto up / down como o Digg ou Reddit, você pode adicionar uma forma das pessoas para fundir / Anexar mensagens a mensagens relacionadas (deixá-los classificar e gerenciar o conteúdo como uma atividade em seu aplicativo ao invés de torná-lo uma questão de trás do cenas processamento).