Hatékony mintakeresés hosszú szövegekben

OData támogatás
Konzulens:
Dr. Juhász Sándor
Automatizálási és Alkalmazott Informatikai Tanszék

A szuffix-fák és szuffix-tömbök jól ismertek arról, hogy effektíven képesek rengeteg szövegfeldolgozással kapcsolatos problémát megoldani, mint például a pontos mintaillesztést, aminek rengeteg felhasználási területe van például a keresőmotorok vagy a természetes nyelvfeldolgozás területén. Ebben a szakdolgozatban mutatok egy alternatív, tisztán hash táblára épülő megoldást, valamint összehasonlítom a hash táblás módszert a szuffix-fát illetve szuffix-tömböt használó megközelítésekkel. A hash tábla alapú megoldás hatékonyságának növelésére különböző ötleteket ismertetek a szakdolgozatban, melyekkel jelentősen csökkenthető a módszer memóriaigénye és futási ideje. Különböző típusú bemenetekkel tesztelem a létező megoldásokat, hogy az egyes módszerek jellegzetességeire jobban rávilágítsak. A mérések eredménye azt mutatja, hogy több területen a hash táblát használó algoritmus hatékonyabban képes nagy mennyiségű mintát illeszteni, mint a gyakorlatban széles körben elterjedt szuffix-tömb alapú megoldások.

Letölthető fájlok

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