Detail práce

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

Bakalářská práce Student: Voženílek Jan Akademický rok: 2007/2008 Vedoucí: Martínek Tomáš, doc. Ing., Ph.D.
Název anglicky
Acceleration of Algorithms for Approximate String Matching
Jazyk práce
český
Abstrakt

Cílem této bakalářské práce je návrh a implementace architektury pro FPGA čipy akcelerující porovnávání dvou řetězců a jejich ohodnocení na podobnost. Použité postupy vycházejí z bioinformatických algoritmů, především Needleman-Wunsch a Smith-Waterman. Jednotka může díky obecnému návrhu a generickému zpracování v jazyce VHDL porovnávat libovolné sekvence znaků, což je úloha prostupující mnoha oblastmi informatiky od prohledávání databází (kde porovnání na podobnost umožňuje odhalit překlepy) po detekci nevyžádané elektronické pošty - spamu. V závislosti na specifikaci úlohy se může zrychlení oproti běžnému softwarovému řešení pohybovat v řádu stovek až tisíců.

Klíčová slova

FPGA, VHDL, akcelerace, porovnání řetězců na základě podobnosti

Ústav
Ústav počítačových systémů FIT VUT v Brně
Studijní program
Informační technologie
Soubory
Stav
obhájeno, hodnocení A
Obhajoba
9. června 2008
Oponent
Kořenek Jan, doc. Ing., Ph.D.
Komise
Kotásek Zdeněk, doc. Ing., CSc. (UPSY FIT VUT), předseda
Drábek Vladimír, doc. Ing., CSc. (UPSY FIT VUT), člen
Hrubý Martin, Ing., Ph.D. (UITS FIT VUT), člen
Malo Roman, Ing., Ph.D. (Mendelu), člen
Matoušek Petr, doc. Ing., Ph.D., M.A. (UIFS FIT VUT), člen
Strnadel Josef, Ing., Ph.D. (UPSY FIT VUT), člen
Citace
VOŽENÍLEK, Jan. Akcelerace algoritmů pro porovnání řetězců na základě podobnosti. Brno, 2008. Bakalářská práce. Vysoké učení technické v Brně, Fakulta informačních technologií. 2008-06-09. Vedoucí práce Martínek Tomáš. Dostupné z: https://www.fit.vut.cz/study/thesis/6600/
BibTeX 
@bachelorsthesis{FITBT6600,
    author = "Jan Vo\v{z}en\'{i}lek",
    type = "Bakal\'{a}\v{r}sk\'{a} pr\'{a}ce",
    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 = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}",
    year = 2008,
    location = "Brno, CZ",
    language = "czech",
    url = "https://www.fit.vut.cz/study/thesis/6600/"
}

Závěrečné práce

Nahoru