Primjena algoritma Minhash za učinkovito otkrivanje sličnih dokumenata

diplomski rad

• Naslov (engleski): Efficient Detection of Near-duplicate Documents Using Minhash Algorithm
• Autor: Andrea Soldo
• Mentor: Siniša Srbljić (mentor)
• Član povjerenstva: Siniša Srbljić (predsjednik povjerenstva)
• Član povjerenstva: Dejan Škvorc (član povjerenstva)
• Član povjerenstva: Ante Đerek (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2016-07-06, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Ovaj rad ima detaljan osvrt na upotrebu minhash algoritma kao metode za pronalazak sličnih tekstualnih datoteka. Algoritam je primijenjen na dvije vrste datoteka. Jedna vrsta su digitalne knjige u kojima su simulirane pogreške slične onima koje nastaju prilikom skeniranja, odnosno optičkog prepoznavanja teksta, a druga vrsta su datoteke elektroničke pošte koje se razlikuju u cijelim segmentima. Mjerena je preciznost i odziv algoritma ovisno o ulaznim parametrima kao što su veličina sažetka i veličina podnizova na koje je ulazni tekst podijeljen. Analizirana je i komponenta lokalno osjetljivog sažimanja u minhash algoritmu. Za sva mjerenja korištena je vlastita implementacija algoritma u Pythonu.

Sažetak (engleski)

This paper describes minhash algorithm and it's use in finding similar text content. Two different types of data were observed. One were digital books which contained simulated scanning errors or OCR errors and the other were e-mails that differ in whole segments of text. Depending on input parameters, such as the size of minhash or the shingle length, algorithm had different outcomes and the success of that outcome was presented with precision and recall measurements. Furthermore the locality sensitive hashing (LSH) part of algoritm was analysed. Implementation of algorithm was done in Python and was used for all tests and measurements done in this paper.

• Ključne riječi: usporedba datoteka; usporedba teksta; slične datoteke; minhash; sažimanje; Jaccardov indeks; lokalno osjetljivo
• Ključne riječi (engleski): minhash; similarity preserving; hashing; similar files; similar text; Jaccard distance; LSH
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:831104
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2018-02-06 11:52:02