Surfistes a càmara lenta

Archive for the ‘Cercador’ Category

En Doraemon se’n va de vacances havent fet els següents deures:

– Mostra missatges dels fòrums d’una assignatura que poden contenir una possible resposta a la consulta d’un alumne

– Mostra contextos útils per a trobar una resposta que provenen dels materials didàctics

–  Llista referències externes sobre els temes consultats. Les referències, de moment, són articles de la Viquipèdia i els articles o llibres sobre el tema en qüestió referenciats al  Delicious

– Mostra contextos trobats via un cercador tipus Google que li poden ser útils al consultor per trobar una resposta.

Llegeix la resta d’aquesta entrada »

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…

Estem construint un cercador que ha de contestar les preguntes de l’alumne:

Quina va ser la primera ciutat fenicia?
Capital de França.
Que és la psicologia cognitiva?
Definició de estatut.

Desenvolupem petites releases per arrivar al objectiu esmentat anteriorment.
Per desenvolupar aquest projecte estem utilitzant Lucene, Lingpie i llegim papers i mes papers sobre aquesta temàtica.
Els materials estàn indexats ens fragment per mirar de donar una millor resposta.

Ha sortit la nova release del cercador de materials de la UOC, amb les següents novetats, obtingudes de les reunions amb els departament de lingüística computacional.
[1]- Indexació de paraules per 3-grams,4-grams Català i castellà per “Has volgut dir”.
[2]- Indexació dels corpus català, castellà i anglès per indexar i buscar.
[3]- Algoritme de stemer genèric que calculem a partir de la indexació 3-4 grams anterior.

Nou “Has volgut dir”:
Actualment per exemple si busquem: piromides egipocies
El sistema ens diu: piràmides egípcies. Evidentment hi ha altres casos que diu coses rares.
Algoritme que hem implementat:
Si no troba cap resultat o menys de deu, divideix les paraules de la cerca en 3-4 grams i llença un cerca sobre les col·leccions (corpus en funció del idioma) de 3-4 grams, donant més pes al n-grams inicials, amb els 10 millors resultats aplica l’algoritme de JaroWinkler Distance i tria la paraula que té un % més alt però com a minim 80%.
És podria millorar el sistema tenint en compte la funció que fa la paraula (Nom, verb, adjectiu,…)?
per exemple:
Si piràmides es un NCFP000 puc considerar egípcies AQ0FP0 (ja que pot funcionar de N ó A i com va enredera un N la considero un A) i donar més pes a piràmides?
Puc seguir algun tipus de regle com la que us he dit anteriorment?
El que m’agradaria és poder contestar les preguntes de l’usuari.
On puc trobar patrons de preguntes dels usuaris per aproximar mé la resposta?
Categoritzant, o sigui de que parla el document (historia,psicologia,…), milloraria les cerques?
Aquestes son algunes de les preguntes que ens plantegem per millorar el sistema.