POSIX reguláris kifejezések heurisztikus mintaillesztése
A POSIX reguláris kifejezések implementációi hagyományos esetben DFA vagy NFA automatát valósítanak meg. Az előbbi a nagy állapottér miatt bizonyos esetekben nagyon sok memóriát használhat fel, megvalósítása bonyolultabb, nagyobb terjedelmű. Az NFA megvalósítás egyszerűbb, memóriafelhasználása optimális, de teljesítményben elmarad a DFA implementációktól.
A reguláris kifejezések illesztése kiemelkedően fontos feladat, mert sok alkalmazás igényli azt. A FreeBSD saját grep programján történt fejlesztések világossá tették, hogy a gyenge teljesítmény bizonyos esetekben felhalmozódhat, és kritikussá válhat, ugyanakkor az extrém memóriahasználat sem megengedhető, főleg a beágyazott rendszerekben történő felhasználás miatt.
A GNU grep a C könyvtár implementációját megkerüli és heurisztikákat használva jobb teljesítményt ér el. Ezt az elvet érdemes lenne a reguláris kifejezések implementációjában megvalósítani. A GNU grep azonban egy független szoftverkomponens, és nincs befolyása a C könyvtár felett, csak így tudja elérni, hogy minden környezetben gyors legyen.
A dolgozat szerzője úgy döntött, hogy a FreeBSD operációs rendszer C könyvtárában létrehoz egy hatékony reguláris kifejezés implementációt, így minden ráépülő program profitál a hatékonyságából. Habár az ötlet részben már létezett a GNU grepben, a vizsgálatok alapján ez az első általános célú reguláris kifejezés implementáció, amely így működik. A dolgozat bemutatja, hogyan lehet heurisztikusan közelíteni a reguláris kifejezéseket, és ezáltal jobb teljesítményt elérni.
szerző
-
Kövesdán Gábor
mérnök informatikus
nappali
konzulens
-
Bányász Gábor
tanársegéd, Automatizálási és Alkalmazott Informatikai Tanszék
