Hosszú mintákat illesztő algoritmusok vizsgálata és implementálása

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 dokumentumban mutatunk egy alternatív, tisztán hash táblára épülő megoldást, valamint összehasonlítjuk a hash táblás módszert a szuffix-fát illetve szuffix-tömböt használó megközelítésekkel. A méréseket különböző típusú szövegekre külön végezzük (például XML, DNS szekvencia, természetes nyelv), hogy az egyes módszerek jellegzetességére jobban rávilágítsunk.

A mérések eredménye azt mutatja, hogy több területen a hash táblát használó algoritmus nagyobb hatékonysággal képes nagy mennyiségű mintát illeszteni, mint a gyakorlatban széles körben elterjedt szuffix-tömb alapú megoldás.

szerző

• 
  Galkó Ferenc
  mérnökinformatikus
  nappali

konzulens

• 
  Dr. Juhász Sándor
  projektvezető, Mirango Kft. (külső)

helyezés