Parallel Pattern Matching Using Bit-vectors
Popis výsledku
Náš paralelní algoritmus pro vyhledávání vzorku v textu je proveden v case O(k log m) , kde k je pocet chyb a m je delka vzorku, na O(n/log m) procesorech, kde n je delka textu, na stroji CREW PRAM. Algoritmus pouziva bitově paralelní simulace konečnýchautomatů.
Klíčová slova
bit-parallel NFA simulationfinite automataparallel algorithmpattern matching
Identifikátory výsledku
Kód výsledku v IS VaVaI
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Parallel Pattern Matching Using Bit-vectors
Popis výsledku v původním jazyce
We present a fast parallel algorithm for approximate pattern matching. The algorithm is vased on bit-parallel ondeterministic finite automata simulation in contrary to existing algorithms based on dynamic programming. Our algorithm takes O(k log m) parallel time using O(n/log m) processors on CREW PRAM, where mn is the length of the text, m is the length of the pattern, and k is the number of edit operations.
Název v anglickém jazyce
Parallel Pattern Matching Using Bit-vectors
Popis výsledku anglicky
We present a fast parallel algorithm for approximate pattern matching. The algorithm is vased on bit-parallel ondeterministic finite automata simulation in contrary to existing algorithms based on dynamic programming. Our algorithm takes O(k log m) parallel time using O(n/log m) processors on CREW PRAM, where mn is the length of the text, m is the length of the pattern, and k is the number of edit operations.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2007
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
MEMICS proceedings 2007
ISBN
978-80-7355-077-6
ISSN
—
e-ISSN
—
Počet stran výsledku
8
Strana od-do
201-208
Název nakladatele
Masarykova univerzita
Místo vydání
Brno
Místo konání akce
Znojmo
Datum konání akce
26. 10. 2007
Typ akce podle státní příslušnosti
EUR - Evropská akce
Kód UT WoS článku
—
Druh výsledku
D - Stať ve sborníku
CEP
IN - Informatika
Rok uplatnění
2007