Detail práce

Beat Grep with Counters, Challenge

Diplomová práce Student: Horký Michal Akademický rok: 2020/2021 Vedoucí: Holík Lukáš, doc. Mgr., Ph.D.
Název česky
Rychlejší než grep pomocí čítačů
Jazyk práce
anglický
Abstrakt

Vyhledávání regulárních výrazů má ve vývoji softwaru nezastupitelné místo. Rychlost vyhledávání může ovlivnit použitelnost softwaru, a proto je na ni kladen velký důraz. Pro určité druhy regulárních výrazů mají standardní přístupy pro vyhledávání vysokou složitost. Kvůli tomu jsou náchylné k útokům založeným na vysoké náročnosti vyhledávání regulárních výrazů (takzvané ReDoS útoky). Regulární výrazy s omezeným opakováním, které se v praxi často vyskytují, jsou jedním z těchto druhů. Efektivní reprezentace a rychlé vyhledávání těchto regulárních výrazů je možné s použítím automatu s čítači. V této práci představujeme implementaci vyhledávání regulárních výrazů založeném na automatech s čítači v C++. Vyhledávání je implementováno v rámci RE2, rychlé moderní knihovny pro vyhledávání regulárních výrazů. V práci jsme provedli experimenty na v praxi používaných regulárních výrazech. Výsledky experimentů ukázaly, že implementace v rámci nástroje RE2 je rychleší než původní implementace v jazyce C#.

Klíčová slova

regulární výraz, vyhledávání regulárních výrazů, omezené opakování, automat s čítači, automat s čítacími množinami, RE2, C++, C#

Ústav
Studijní program
Informační technologie, obor Informační systémy
Soubory
Stav
obhájeno, hodnocení B
Obhajoba
21. června 2021
Oponent
Průběh obhajoby

Student nejprve prezentoval výsledky, kterých dosáhl v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Student následně odpověděl na otázky oponenta a na doplnění ze strany přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studenta na položené otázky rozhodla práci hodnotit stupněm "B".

Otázky u obhajoby
  1. Můžete charakterizovat třídu (a uvést konkrétní příklad) regulárních výrazů (a případně textů pro vyhledávání), na které Váš nástroj překonává existujíc nástroje (grep, RE2, CA)?
  2. Nástroje jako jsou grep a RE2 těží z pokročilé optimalizace. Domníváte se, že výkonnost Vašeho nástroje lze značně vylepšit dalšími optimalizacemi (případně jakými)?
  3. Komise, například: Zvažoval jste i jiné metoty převodu regulárních výrazů?
Komise
Hruška Tomáš, prof. Ing., CSc. (UIFS FIT VUT), předseda
Burget Radek, doc. Ing., Ph.D. (UIFS FIT VUT), člen
Grégr Matěj, Ing., Ph.D. (UIFS FIT VUT), člen
Kreslíková Jitka, doc. RNDr., CSc. (UIFS FIT VUT), člen
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT), člen
Očenášek Pavel, Mgr. Ing., Ph.D. (UIFS FIT VUT), člen
Citace
HORKÝ, Michal. Beat Grep with Counters, Challenge. Brno, 2021. Diplomová práce. Vysoké učení technické v Brně, Fakulta informačních technologií. 2021-06-21. Vedoucí práce Holík Lukáš. Dostupné z: https://www.fit.vut.cz/study/thesis/22461/
BibTeX
@mastersthesis{FITMT22461,
    author = "Michal Hork\'{y}",
    type = "Diplomov\'{a} pr\'{a}ce",
    title = "Beat Grep with Counters, Challenge",
    school = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}",
    year = 2021,
    location = "Brno, CZ",
    language = "english",
    url = "https://www.fit.vut.cz/study/thesis/22461/"
}
Nahoru