On-line weighted pattern matching
| Autor: | Solon P. Pissis, Jakub Radoszewski, Panagiotis Charalampopoulos, Costas S. Iliopoulos |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Sequence
0102 computer and information sciences 02 engineering and technology Space (mathematics) 01 natural sciences Computer Science Applications Theoretical Computer Science Combinatorics Computational Theory and Mathematics 010201 computation theory & mathematics Position (vector) Product (mathematics) Line (geometry) 0202 electrical engineering electronic engineering information engineering C++ string handling Probability distribution 020201 artificial intelligence & image processing Pattern matching Information Systems Mathematics |
| Zdroj: | Information and Computation. 266:49-59 |
| ISSN: | 0890-5401 |
| Popis: | 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 1 z , 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 1 z . 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 2 m ) time per arriving position; with the space requirement however being O ( m min ( σ , 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect