Detail práce
Beat Grep with Counters, Challenge
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#.
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#
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".
- 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)?
- 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)?
- Komise, například: Zvažoval jste i jiné metoty převodu regulárních výrazů?
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
@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/" }