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.