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

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Fast Pattern-Matching on Indeterminate Strings

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Fast Pattern-Matching on Indeterminate Strings

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2005

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

Proceedings of the 16th Australasian Workshop on Combinatorial Algorithms

ISBN

0-646-45252-5

ISSN

—

e-ISSN

—

Počet stran výsledku

14

Strana od-do

415-428

Název nakladatele

University of Ballarat

Místo vydání

Ballarat, Victoria

Místo konání akce

Ballarat, Victoria, Australia

Datum konání akce

18. 9. 2005

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

WRD - Celosvětová akce

Kód UT WoS článku

—