King's College London

Research portal

On-line weighted pattern matching

Research output: Contribution to journalArticlepeer-review

Standard

On-line weighted pattern matching. / Charalampopoulos, Panagiotis; Iliopoulos, Costas S.; Pissis, Solon P. et al.

In: INFORMATION AND COMPUTATION, Vol. 266, 01.06.2019, p. 49-59.

Research output: Contribution to journalArticlepeer-review

Harvard

Charalampopoulos, P, Iliopoulos, CS, Pissis, SP & Radoszewski, J 2019, 'On-line weighted pattern matching', INFORMATION AND COMPUTATION, vol. 266, pp. 49-59. https://doi.org/10.1016/j.ic.2019.01.001

APA

Charalampopoulos, P., Iliopoulos, C. S., Pissis, S. P., & Radoszewski, J. (2019). On-line weighted pattern matching. INFORMATION AND COMPUTATION, 266, 49-59. https://doi.org/10.1016/j.ic.2019.01.001

Vancouver

Charalampopoulos P, Iliopoulos CS, Pissis SP, Radoszewski J. On-line weighted pattern matching. INFORMATION AND COMPUTATION. 2019 Jun 1;266:49-59. https://doi.org/10.1016/j.ic.2019.01.001

Author

Charalampopoulos, Panagiotis ; Iliopoulos, Costas S. ; Pissis, Solon P. et al. / On-line weighted pattern matching. In: INFORMATION AND COMPUTATION. 2019 ; Vol. 266. pp. 49-59.

Bibtex Download

@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.",

}

RIS (suitable for import to EndNote) Download

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

VL - 266

SP - 49

EP - 59

JO - INFORMATION AND COMPUTATION

JF - INFORMATION AND COMPUTATION

SN - 0890-5401

ER -

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454