MinHsh

MIN – HASH

INTRODUÇÃO
Detecção de documentos duplicados, tem se tornado cada vez mais importânte para as empresas que possuem coleções de e-mails armazenados, páginas web e documentos com várias cópias que podem ou não serem mantidos atualizados.
Porém antes de explicar o algorítmo Min-Hash, devemos nos perguntar: O que é similaridade de documento? O objetivo principal do MinHash é responder de forma eficiênte o quanto semelhante um documento é do outro. Podemos visualizar este exemplo abaixo:
Vamos supor que temos dois conjuntos:
Conjunto A = ["cadeira" , "mesa", "tapete", "teclado", "mouse"]
Conjunto B = ["cadeira", "tapete", "teclado"]
Para medir o quanto estes conjuntos são similares, existe um método chamado Coeficiente de
Jaccard. Onde é calculado: A quantidade de elementos comuns dividido pelo resultado da subtração do número total de elementos pela quantidade de elementos comuns. Complicado? Não! Veremos como é simples no exemplo abaixo:
Coef. Jaccard: Definido como o tamanho da intersecção dividida pelo tamanho da união dos conjuntos. Mas para facilitar, podemos entender da seguinte forma:

Quantidade Elementos comuns -> QEC
Total de elementos -> TE
QEC / (TE – QEC)
Neste caso, temos 3 elementos comuns (QEC): "cadeira", "tapete" e "teclado" e um total de 8 elementos somando todos os conjuntos. Desta forma, o coeficiente de Jaccard será:
3 / ( 8 – 3 ) = 3 / (5) = 0,6 ou 60%
SIMILARIDADES EM DOCUMENTOS
Um documento de texto pode ser considerado um conjunto enorme de palavras. Para verificar a similaridade deste documento, é seguido a mesma ídeia do exemplo anteriormente visto com conjunto de 8 palavras. Porém, se o documento for dividido em palavras, na hora da execução do cáculo de similaridade, seria considerado sempre quase 100% de semelhança, mesmo que ambos documentos tivessem significados completamentes diferentes. No caso do cáclulo de similaridade em documentos, o objetivo é buscar a similaridade do texto escrito,