Mintaillesztő algoritmusok vizsgálata

OData támogatás
Konzulens:
Dr. Dudás Ákos
Automatizálási és Alkalmazott Informatikai Tanszék

A szöveg alapú mintaillesztés feladata hosszú karaktersorozatokban meghatározott szövegrészek helyének megkeresése. A feladat, bár elsőre egyszerűnek hangzik, nagyméretű bemenetek esetén memóriában és futási időben is kihívást jelent. Ezeknek az algoritmusoknak sok felhasználási területe van nyelvfeldolgozás, a keresőmotorok, vagy akár a bioinformatika területén.

A mintaillesztés általános esetben kétféle módszerrel végezhető el. Az egyik ilyen, amikor a bemeneti szövegre illesztjük a mintánkat. A másik eset pedig az, amikor a szövegen ún. előfeldolgozást végzünk el, mivel többször is szeretnénk keresést végrehajtani. Az előfeldolgozás segítésével egy adatstruktúrát építünk a szövegből. A legismertebb adatstruktúrák a szuffix tömbök és a szuffix fák.

A párhuzamos programozással egy problémát felosztva több részre, elérhető, hogy több feldolgozási egység dolgozzon a saját részén egyszerre a többivel. Régebben a processzorok órajelének növelése volt az alapja annak, hogy egy program futásának az idejét csökkentsék, de ma már a teljesítmény növelésének érdekében a programok párhuzamosítása vette át a vezető szerepet.

Felmerül tehát a kérdés, hogy a mintaillesztéses algoritmusok mivel nagyméretű adatokkal dolgozhatnak, milyen mértékben és feltételek mellett párhuzamosíthatók

A dolgozatomban bemutatom mélyebben a szuffix tömbökre épülő mintaillesztéses algoritmusokat, illetve ezek párhuzamosítási lehetőségeit CPU-n illetve GPU-n is.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.