Fast Pattern-Matching on Indeterminate Strings

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F05%3A03110723" target="_blank" >RIV/68407700:21230/05:03110723 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Fast Pattern-Matching on Indeterminate Strings

Original language description

In a string x on an alphabet, a position i is said to be indeterminate iff x[i] may be any one of a specified subset of the aplhabet. A string x containing indeterminate positions is therefore also said to be indeterminate. Indeterminate strings can arise in DNA and amino acid sequences as well as in cryptological applications. In this paper we describe fast algorithms for finding all occurrences of a pattern p=p[1..m] in a given text x=x[1..n], where either or both of p and x can be indeterminate. Ouralgorithms are based on the Sunday variant of the Boyer-Moore pattern-matching algorithm, one of the fastest exact pattern-matching algorithms known. The methodology we describe applies more generally to all variants of Boyer-Moore (such as Horspool's, for example) that depend only on calculation of the "rightmost shift" array: our method therefore assumes that the alphabet is indexed (essentially, an integer alphabet), a requirement normally satisfied in practice.

Czech name

Rychlé vyhledávání v neurčitých řetězcích

Czech description

Pozice i v řetězci x nad vstupní abecedou je nazvána neurčitá právě tehdy pokud x[i] může být libovolnou z podmnožin vstupní abecedy. Řetězec x obsahující neurčité pozice se také nazývá neurčitý. V tomto článku popisujeme rychlý algoritmus pro vyhledávání v textu, kde vzorek nebo text nebo oba mohou být neurčitými řetězci. Náš algoritmus je založen na Sunday variantě Boyer-Mooreova algoritmu, jednoho z nejrychlejších vyhledávacích algoritmů.

Type

D - Article in proceedings

CEP classification

IN - Informatics

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2005

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the 16th Australasian Workshop on Combinatorial Algorithms

ISBN

0-646-45252-5

ISSN

—

e-ISSN

—

Number of pages

14

Pages from-to

415-428

Publisher name

University of Ballarat

Place of publication

Ballarat, Victoria

Event location

Ballarat, Victoria, Australia

Event date

Sep 18, 2005

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—