Detecció de Near-duplicates

Projecte encarregat per la UOC.
Objectiu: Construir una eina que ens permetès detectar si dos documents estàn parlant del mateix, quan passa això els documents son near-duplicates.
Tecnologia: Java
Algoritme: Charikar's Algorithm

Que son documents Near-duplicates?

Documents amb identic contingut, però que varien en petites parts del document, per exemple, odre dels paràgrafs, links, canvis de puntuació, paraules o frases redactades d'un altre manera,etc ...

Perquè necessitem Near-duplicates?

- Estalviar espai al disc
- Evitar incloure documents amb diferents versions.
- Detectar plagis a nivell de text.

Com es poden detectar Near-duplicates?

Per detectar Near-duplicates utilitzarem la tècnica dels fingerprints, això significa caracteritzar cada document amb un vector de 64 bits únic, com si fos una emprempta digital.
Per saber si dos documents son Near duplicates, compararem les seves empremtes digitals.

Per poder realitzar això utilitzarem dos algoritmes, un algoritme desenvolupat per Moses Charikar, que genera a partir d'un document un vector de 64 bits que el caracteritza, i l'algorithme de Hamming distance, que permet medir la similitut entre dos vectors de n bits.

L'algoritme de M.Charikars no es pot utlitzar a USA ja que el té patentat Google.

En que consisteix el Charikar’s algorithm?

Caracterització del document
Aplicar funcions de hash a les característiques
Obtenim fingerprint
Apliquem funcions de comparació de vectors:
    (Doc1,Doc2) son near-duplicate ?
    hamming-distance(fingerprint(Doc1), fingerprint(Doc2)) = k

Que vol dir caracteritzar documents?

Caracteritzar documents vol dir buscar quines coses té un document que el diferencien dels altres, per exemple número de paraules, número de paràgrafs, signes de puntuació, frases, etc...

Es cosa nostra definir quina característica serà la mes apropiada per generar el fingerprint.
Per la nostre experiència una caracterització que ens funciona és la de dividir els documents en Shingles, o sigui conjunt de paraules agrupades de n en n, també s’anomena agrupació per n-grams.

Per exemple la frase següent agrupada en 3-grams seria:
    Frase:detecció de documents near duplicates
    3-grams: detecció de documents, de documents near,documents near duplicates.

Per acabar de caracteritzar el document apliquem l’eliminació de stop-words (paraules sense significat) i fem stemming sobre cada paraula (extraiem l’arrel de la paraula).

De manera que l’exemple anterior quedaria:
    Frase: detecció de documents near duplicates
    Stop-words: detecció documents near duplicates
    Stemming: detectar document near duplicate
    3-grams: detectar document near, document near duplicate

Una vagada extretes les característiques aplicarem una funció de hash a cada una d’elles.

Rabin-Hash

Hi ha moltes funció de hash que podem utilitzar.
Hem decidit utilitzar la funció Hash-Rabin, perquè es molt ràpida.

Per la frase "detecting near duplicates" obtindriem els següents hash de 64 bits.
Detecting -   0000000000000000000000000000000000000000000110100111110100001011
Near -            0000000000000000000000000000000000000000000011110000000000010111
Duplicates -  0000000000000000000000000000000001111101100000110110100101111111

Com es calcula un fingerprint?

Partim d'un vector de 64 bits amb tot 0, per cada hash que hem obtingut de la caracterització del document apliquem el següent:
Si vector de bits de la paraula es 1 incrementa el vector resultant en 1, sinó (<=1)el decrementem en 1.
Exemple:

Vector inicial   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
Detecting -   0   1   1   0   1   0   0   1   1   1   1   1   0   1   0   0   0   0   1   0   1   1

Vector res. -1   1  1  -1  1  -1  -1   1   1   1   1   1  -1   1  -1  -1  -1  -1  1 -1   1   1
Near -            0   0  1   1   1   1   0   0   0   0   0   0   0    0   0   0   0    1  0  1   1   1

Vector res.  -2  1   2   0   2   0  -2  0   0   0   0   0   -2  0   -2  -2  -2   0 -1  0   2   2  
Duplicates -   1  1  0  0   0    0    0  1  1   0   1   1    0   1    0   0    1   0  1  1   1   1

Vector res.  -1   2  1  -1  1  -1  -3   1  1  -1   1  1   -3   1   -3   -3  -1  -1  0 1   3   3  

Una vegada hem aplicat totes les caracteritzacions en format hash, generem el fingerprint de la següent manera:
Si el vector resultant és negatiu o 0,  el fingerprint d’aquella posició val 0, en cas contrari val 1. Per tant el fingerprint quedaria de la següent manera:

Fingerprint   0    1  1   0  1   0   0   1  1   0   1   1    0    1   0    0   0    0  1  1  1   1

Hamming distance.

Algoritme per calcular la semblança entre dos documents, n’hi ha més, però nosaltres utilitzarem aquest.
Bàsicament el que fa aquest algoritme és mirar, donat dos vectors de n bits, quantes modificacions s'ha de fer a un d’ells perquè sigui igual a l’altre, aquest número l’anomenarem K.

Son Near-duplicates dos document?

Considerem que dos documents son near-duplicates quan la K resultant d’aplicar Hamming-distance als fingerprint és <= 3.