Reguláris kifejezések mintaillesztésének algoritmikus optimalizása

Félév: 2021-2022 tavasz

Kategória: Szoftver

Téma leírása

Adott egy meglévő implementáció reguláris kifejezések optimalizálására. Az elv lényege, hogy heurisztikákat alkalmazva leszűkíthető az a környezet, amelyen a reguláris kifejezéseket illesztő véges automatát futtatni kell, és így az idő többségében egy annál gyorsabb szövegkereső algoritmus (Quick-Search, Boyer-Moore és variánsai) fut. Ezzel a futási idő lényegesen javítható. A meglévő implementáció C nyelven íródott, mivel a teljesítmény így optimizálható ki a legjobban.

A hallgató feladata bekapcsolódni ennek a meglévő implementációnak a fejlesztésébe. Ez a következőket foglalja magában:

• A téma megismerése, a meglévő implementáció megértése. A téma bonyolultsága miatt ez is némileg több időt tesz ki, mint egy átlagosabb témánál.
• Funkcionális és teljesítménytesztek készítése, debuggolás. Meg kell mutatni, hogy az implementáció helyesen működik, és szeretnénk mérésekkel is alátámasztani, hogy bizonyos minták esetén jelentősen jobb teljesítményt ad.
• Ötletelés, további optimalizációs ötletek kihasználása.

 

A téma kutatási jellegű feladat, aki elmélyed benne akár TDK-ig vagy publikációig is viheti. Ideális olyan hallgatóknak, akik nem mindennapi témát (pl. hétköznapi webalkalmazás) szeretnének választani, hanem valami mélyebbet, rendkívülibbet készítenének az önlab során. Az itt szerzett tapasztalatok, publikációk egy későbbi PhD képzéshez is igen hasznosak.

Feltételek

• Linux build eszközök ismerete (make, gcc stb.)
• C nyelv
• angol
• érdeklődés kutatási irányba és elszántság

Maximális létszám: 2 fő