Surfistes a càmara lenta

Archive for the ‘Detector de duplicats’ Category

En el últim post sobre detecció de duplicats les coses no pintaven bé, s’havia fet una primera versió del detector, però no acabava de ser el que necessitem, ja que detectava duplicats exactes, això vol dir que un parell de documents amb l’ordre dels paràgrafs canviats el considerava diferents. El objectiu del projecte quedava modificat, no busquem duplicats, sinó near-duplicates, o sigui documents que son iguals en contingut, simple i obvi, no?

Per desenvolupar el nou algoritme ens hem començat per llegir una sèrie d’articles que parlen d’aquest tema, i a partir d’aquests articles hem desenvolupat el algoritme de Charikar’s simhash (és el mateix que utilitza google).
Detecting NearDuplicates for Web Crawling
Similarity estimation techniques frum rounding Algorithms
Finding NearDuplicate Web Pages: A LargeScale Evaluation of Algorithms
L’algoritme consisteix en:

Els documents que es volen avaluar es separen en ngrams (paraules agrupades de n en n), per cada una d’aquestes paraules, es diuen tokens normalment, generem un valor de hash de 64bits, nosaltres hem utilitzat el Ranbin hash perquè és molt ràpid.
És crea paral.lelament un Vector de ints de tantes posicions com bits té la funció de hash (64b), inicialitzat a 0.

Cada ith bit del valor hash modifica el valor vth del vector de la següet manera:
ith = 1 incrementem el bit vth del vector en 1
ith = 0 decrementem el bit vth del vector en 1.
per exemple:
Si hash(hola) = 0 1 1 1 0 1 1 0 0 0
v = 1 1 0 2 -3 6 -2 0 0 0
vfinal = 0 2 1 3 -4 7 -1 -1 -1 -1
al final ens quedarà un vector així:
V = [-123,-76,10,0,0,-12,1,3] aquest vector el transformem amb un fingerprint de la següent manera:
si ith valor > 0 vth bit del fingerprint 1
si ith < 1 vth bit del fingerprint 0
així doncs quedaria així F = [0,0,1,0,0,0,1,1]

I aquest és l'algoritme.
El pròxim post, analitzarem els test obtinguts d'aplicar aquest algoritme.

La primera versió del detector de duplicats ja està en marxa, i una vegada en marxa veiem les seves mancances.

En aquests moments detectem documents duplicats en el cas que un document sigui idèntic a un altres o un respecte l’altre només variïn paraules que no son paraules clau. Això està bé, però no es suficient, el que volem detectar son el que s’anomena near-duplicates, documents idèntics en contingut.

Dos documents poden ser idèntics en contingut però amb diferent estructura o poden contenir parts del text poc rellevants, títols o annexes.
Aquesta és la situació que hem detectat, tenim documents en diferents formats (PDF, web, xml,…), si extraiem el text d’aquests documents ens podem trobar que el PDF té idèntic contingut que el XML, però amb l’ordre dels elements canviats, per tant el sistema considera que son diferents. També podem trobar que del xml extraiem el contingut dels tags, però no el nom dels tags (introducció, objectius,…), en el PDF s’extreuen els nom dels tags perquè estan com a contingut, i elements extres com el Index del PDF, i els currículums i les fotos i els elements flash i els exercicis que es maqueten d’una manera especial i la bibliografia i el glossari i i i més més més,……………………………………………

Per tant s’ha de buscar un altre sistema hem de passar d’un detector de duplicats a un detector de near-duplicates.

Google porta treballant amb aquest tema des de com a mínim el 2005, ha tret un sistema de detecció de duplicats i la patentat, com sempre un pas endavant. Goole a montat el seu sistema de duplicats basant-se en el Charikar’s simhash fingerprint. Que és? Com funciona? ho deixem per la proxima.

Referencies:
http://dsrg.mff.cuni.cz/~holub/sw/shash/#a1.
Similarity Estimation Techniques from Rounding Algorithms
Detecting NearDuplicates for Web Crawling

Tenim un cercador i tenim un dimoni que va alimentant a les col•leccions del servidor, però que passa si ens arriba un fitxer duplicat, en el que només ha variat una paraula o una frase?
Utilitzem els primers 10 segons per lamentacions i queixes sobre l’ofici que hem triat, la resta per buscar solucions.
– Primera aproximació:
Creem una fitxa per cada document de la col.lecció, això s’anomena fingerprint, que ens diu:
Num de frases.
Num de tokens totals (paraules)
Num de tokens diferents
Tokens més característics del document, els TOP 10, els calculem amb la formula de idf normalitzada, amb valor <0.8.
Amb tot això ja tenim el fingerprint d’un document.
Ho comparem amb altres fingerprints d’altres documents. Que passara?
to be continued…