Thesis Details

Akcelerace algoritmů pro porovnání řetězců na základě podobnosti

Bachelor's Thesis Student: Voženílek Jan Academic Year: 2007/2008 Supervisor: Martínek Tomáš, doc. Ing., Ph.D.
English title
Acceleration of Algorithms for Approximate String Matching
Language
Czech
Abstract

The objective of this bachelor's thesis is to design and implement architecture for FPGA chips that accelerates matching of two strings and scoring them for similarity. Used processes come from bioinformatics algorithms, especially Needleman-Wunsch and Smith-Waterman. Due to general design and generic implementation in VHDL the unit is able to compare any sequences of characters, which is a task widely used in many branches of informatics from database searches (where approximate matching allows discovery of spelling errors) to spam detection. Depending on task specification the acceleration speed up against common software solution can reach orders of hundreds or even thousands.

Keywords

FPGA, VHDL, acceleration, approximate string matching

Department
Department of Computer Systems FIT BUT
Degree Programme
Information Technology
Files
Status
defended, grade A
Date
9 June 2008
Reviewer
Kořenek Jan, doc. Ing., Ph.D.
Committee
Kotásek Zdeněk, doc. Ing., CSc. (DCSY FIT BUT), předseda
Drábek Vladimír, doc. Ing., CSc. (DCSY FIT BUT), člen
Hrubý Martin, Ing., Ph.D. (DITS FIT BUT), člen
Malo Roman, Ing., Ph.D. (Mendelu), člen
Matoušek Petr, doc. Ing., Ph.D., M.A. (DIFS FIT BUT), člen
Strnadel Josef, Ing., Ph.D. (DCSY FIT BUT), člen
Citation
VOŽENÍLEK, Jan. Akcelerace algoritmů pro porovnání řetězců na základě podobnosti. Brno, 2008. Bachelor's Thesis. Brno University of Technology, Faculty of Information Technology. 2008-06-09. Supervised by Martínek Tomáš. Available from: https://www.fit.vut.cz/study/thesis/6600/
BibTeX 
@bachelorsthesis{FITBT6600,
    author = "Jan Vo\v{z}en\'{i}lek",
    type = "Bachelor's thesis",
    title = "Akcelerace algoritm\r{u} pro porovn\'{a}n\'{i} \v{r}et\v{e}zc\r{u} na z\'{a}klad\v{e} podobnosti",
    school = "Brno University of Technology, Faculty of Information Technology",
    year = 2008,
    location = "Brno, CZ",
    language = "czech",
    url = "https://www.fit.vut.cz/study/thesis/6600/"
}

Theses

Back to top