A Simple Streaming Bit-parallel Algorithm for Swap Pattern Matching

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F17%3A00315777" target="_blank" >RIV/68407700:21240/17:00315777 - isvavai.cz</a>

Výsledek na webu

<a href="https://link.springer.com/chapter/10.1007%2F978-3-319-72453-9_28" target="_blank" >https://link.springer.com/chapter/10.1007%2F978-3-319-72453-9_28</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-72453-9_28" target="_blank" >10.1007/978-3-319-72453-9_28</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A Simple Streaming Bit-parallel Algorithm for Swap Pattern Matching

Popis výsledku v původním jazyce

The pattern matching problem with swaps is to find all occurrences of a pattern in a text while allowing the pattern to swap adjacent symbols. The goal is to design fast matching algorithm that takes advantage of the bit parallelism of bitwise machine instructions and has only streaming access to the input. We introduce a new approach to solve this problem based on the graph theoretic model and compare its performance to previously known algorithms. We also show that an approach using deterministic finite automata cannot achieve similarly efficient algorithms. Furthermore, we describe a fatal flaw in some of the previously published algorithms based on the same model. Finally, we provide experimental evaluation of our algorithm on real-world data.

Název v anglickém jazyce

A Simple Streaming Bit-parallel Algorithm for Swap Pattern Matching

Popis výsledku anglicky

The pattern matching problem with swaps is to find all occurrences of a pattern in a text while allowing the pattern to swap adjacent symbols. The goal is to design fast matching algorithm that takes advantage of the bit parallelism of bitwise machine instructions and has only streaming access to the input. We introduce a new approach to solve this problem based on the graph theoretic model and compare its performance to previously known algorithms. We also show that an approach using deterministic finite automata cannot achieve similarly efficient algorithms. Furthermore, we describe a fatal flaw in some of the previously published algorithms based on the same model. Finally, we provide experimental evaluation of our algorithm on real-world data.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA17-20065S" target="_blank" >GA17-20065S: Těsné parametrizované výsledky pro problémy orientované souvislosti</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

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ů

Název statě ve sborníku

Mathematical Aspects of Computer and Information Sciences

ISBN

978-3-319-72452-2

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

16

Strana od-do

333-348

Název nakladatele

Springer International Publishing

Místo vydání

Cham

Místo konání akce

Vídeň

Datum konání akce

15. 11. 2017

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—