Naslov
Pretraživanje podataka na temelju djelomičnog slaganja nizova
(Data searching based on approximate string matching)

Autori
Akšamović, Marin

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, preddiplomski

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
08.07

Godina
2008

Stranica
27

Mentor
Dalbelo Bašić, Bojana

Ključne riječi
približno pretraživanje tekstualnih nizova; Levenshteinova udaljenost; EDP algoritam; BITAP algoritam; dinamičko programiranje; bit paralelizam
(approximate string searching; Levenshtein distance; EDP algorithm; BITAP algorithm; dynamic programming; bit parallelism)

Sažetak
Približno pretraživanje tekstnih nizova je bitan sastavni dio mnogih problema, kao što su pretraživanje teksta, bioinformatika i obrada signala. Ta vrsta pretraživanja može biti pretraživanje tekstnog niza s k neslaganja i pretraživanje tekstnog niza s k razlika, ovisno o izabranoj funkciji udaljenosti (Hammingova ili Levenshteinova). Osnovni zadatak algoritma pretraživanja s k razlika je naći uzorak P unutar teksta T s najviše k dopuštenih pogrešaka, gdje pogreška može biti umetanje, brisanje ili zamjena znaka. Ovaj rad uspoređuje vremena trajanja dva algoritma pretraživanja s k razlika, EDP i BITAP. EDP je temeljen na dinamičkom programiranju, a BITAP na bit paralelizmu.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

POVEZANOST RADA