On-line weighted pattern matching

Panagiotis Charalampopoulos; Costas S. Iliopoulos; Solon P. Pissis; Jakub Radoszewski

doi:10.1016/j.ic.2019.01.001

On-line weighted pattern matching

Panagiotis Charalampopoulos, Costas S. Iliopoulos, Solon P. Pissis, Jakub Radoszewski^*

^*Corresponding author for this work

University of Warsaw, Institute of Informatics

Research output: Contribution to journal › Article › peer-review

5 Citations (Scopus)

Abstract

A weighted sequence is a sequence of probability distributions over an alphabet of size σ. Weighted sequences arise naturally in many applications. We study the problem of weighted pattern matching in which we are given a string pattern P of length m, a weight threshold [Formula presented], and a weighted text X arriving on-line. We say that P occurs in X at position i if the product of probabilities of the letters of P at positions i−m+1,…,i in X is at least [Formula presented]. We first discuss how to apply a known general scheme that transforms off-line pattern matching algorithms to on-line algorithms to obtain an on-line algorithm that requires O((σ+log⁡z)log⁡m) or O(σlog²⁡m) time per arriving position; with the space requirement however being O(mmin⁡(σ,z)). Our main result is a new algorithm that processes each arriving position of X in O(z+σ) time using O(m+z) extra space.

Original language	English
Pages (from-to)	49-59
Number of pages	11
Journal	INFORMATION AND COMPUTATION
Volume	266
Early online date	3 Jan 2019
DOIs	https://doi.org/10.1016/j.ic.2019.01.001
Publication status	Published - 1 Jun 2019

Keywords

On-line pattern matching
Position weight matrix (PWM)
String matching automaton
Uncertain sequence
Weighted sequence

Access to Document

10.1016/j.ic.2019.01.001

Cite this

@article{8052c0a61e4f414a82f9ce48d9a3cd78,

title = "On-line weighted pattern matching",

abstract = "A weighted sequence is a sequence of probability distributions over an alphabet of size σ. Weighted sequences arise naturally in many applications. We study the problem of weighted pattern matching in which we are given a string pattern P of length m, a weight threshold [Formula presented], and a weighted text X arriving on-line. We say that P occurs in X at position i if the product of probabilities of the letters of P at positions i−m+1,…,i in X is at least [Formula presented]. We first discuss how to apply a known general scheme that transforms off-line pattern matching algorithms to on-line algorithms to obtain an on-line algorithm that requires O((σ+log⁡z)log⁡m) or O(σlog2⁡m) time per arriving position; with the space requirement however being O(mmin⁡(σ,z)). Our main result is a new algorithm that processes each arriving position of X in O(z+σ) time using O(m+z) extra space.",

keywords = "On-line pattern matching, Position weight matrix (PWM), String matching automaton, Uncertain sequence, Weighted sequence",

author = "Panagiotis Charalampopoulos and Iliopoulos, {Costas S.} and Pissis, {Solon P.} and Jakub Radoszewski",

year = "2019",

month = jun,

day = "1",

doi = "10.1016/j.ic.2019.01.001",

language = "English",

volume = "266",

pages = "49--59",

journal = "INFORMATION AND COMPUTATION",

issn = "0890-5401",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - On-line weighted pattern matching

AU - Charalampopoulos, Panagiotis

AU - Iliopoulos, Costas S.

AU - Pissis, Solon P.

AU - Radoszewski, Jakub

PY - 2019/6/1

Y1 - 2019/6/1

N2 - A weighted sequence is a sequence of probability distributions over an alphabet of size σ. Weighted sequences arise naturally in many applications. We study the problem of weighted pattern matching in which we are given a string pattern P of length m, a weight threshold [Formula presented], and a weighted text X arriving on-line. We say that P occurs in X at position i if the product of probabilities of the letters of P at positions i−m+1,…,i in X is at least [Formula presented]. We first discuss how to apply a known general scheme that transforms off-line pattern matching algorithms to on-line algorithms to obtain an on-line algorithm that requires O((σ+log⁡z)log⁡m) or O(σlog2⁡m) time per arriving position; with the space requirement however being O(mmin⁡(σ,z)). Our main result is a new algorithm that processes each arriving position of X in O(z+σ) time using O(m+z) extra space.

AB - A weighted sequence is a sequence of probability distributions over an alphabet of size σ. Weighted sequences arise naturally in many applications. We study the problem of weighted pattern matching in which we are given a string pattern P of length m, a weight threshold [Formula presented], and a weighted text X arriving on-line. We say that P occurs in X at position i if the product of probabilities of the letters of P at positions i−m+1,…,i in X is at least [Formula presented]. We first discuss how to apply a known general scheme that transforms off-line pattern matching algorithms to on-line algorithms to obtain an on-line algorithm that requires O((σ+log⁡z)log⁡m) or O(σlog2⁡m) time per arriving position; with the space requirement however being O(mmin⁡(σ,z)). Our main result is a new algorithm that processes each arriving position of X in O(z+σ) time using O(m+z) extra space.

KW - On-line pattern matching

KW - Position weight matrix (PWM)

KW - String matching automaton

KW - Uncertain sequence

KW - Weighted sequence

UR - http://www.scopus.com/inward/record.url?scp=85059699088&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2019.01.001

DO - 10.1016/j.ic.2019.01.001

M3 - Article

AN - SCOPUS:85059699088

SN - 0890-5401

VL - 266

SP - 49

EP - 59

JO - INFORMATION AND COMPUTATION

JF - INFORMATION AND COMPUTATION

ER -

On-line weighted pattern matching

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this