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%2F08%3A03130018" target="_blank" >RIV/68407700:21230/08:03130018 - 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 alphabet. A string x containing indeterminate positions is therefore also said to be indeterminate. Indeterminate strings can arise inDNA and amino acid sequences as well as in cryptological applications and the analysis of musical texts. In this paper we describe fast algorithms for finding all occurrences of a pattern p in a given text x, where either or both of p and x can be indeterminate. Our algorithms 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 asHorspool'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 alphabet. A string x containing indeterminate positions is therefore also said to be indeterminate. Indeterminate strings can arise inDNA and amino acid sequences as well as in cryptological applications and the analysis of musical texts. In this paper we describe fast algorithms for finding all occurrences of a pattern p in a given text x, where either or both of p and x can be indeterminate. Our algorithms 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 asHorspool'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

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F06%2F1039" target="_blank" >GA201/06/1039: Analýza a zpracování textu</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2008

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 periodika

Journal of Discrete Algorithms

ISSN

1570-8667

e-ISSN

—

Svazek periodika

6

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

14

Strana od-do

—

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—