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

master's thesis

• Title (english): Efficient Detection of Near-duplicate Documents Using Minhash Algorithm
• Author: Andrea Soldo
• Mentor: Siniša Srbljić (mentor)
• Committee member: Siniša Srbljić (predsjednik povjerenstva)
• Committee member: Dejan Škvorc (član povjerenstva)
• Committee member: Ante Đerek (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2016-07-06, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: usporedba datoteka; usporedba teksta; slične datoteke; minhash; sažimanje; Jaccardov indeks; lokalno osjetljivo
• Keywords (english): minhash; similarity preserving; hashing; similar files; similar text; Jaccard distance; LSH
• Language: croatian
• URN:NBN: urn:nbn:hr:168:831104
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2018-02-06 11:52:02