Regisztráció és bejelentkezés

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
    , Automatizálási és Alkalmazott Informatikai Tanszék