A prefix array for parameterized strings
| Autor: | Richard Beal, William F. Smyth, Donald A. Adjeroh |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Sequence String (computer science) Parameterized complexity 0102 computer and information sciences 02 engineering and technology Construct (python library) Data structure 01 natural sciences Theoretical Computer Science Prefix High Energy Physics::Theory Computational Theory and Mathematics 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Bijection Discrete Mathematics and Combinatorics 020201 artificial intelligence & image processing Pattern matching Algorithm Mathematics |
| Zdroj: | Journal of Discrete Algorithms. 42:23-34 |
| ISSN: | 1570-8667 |
| DOI: | 10.1016/j.jda.2016.11.002 |
| Popis: | A parameterized string (p-string) is a generalization of the traditional string over two alphabets: a constant alphabet and a parameter alphabet. A parameterized match (p-match) exists between two p-strings if the constants match exactly and if there exists a bijection between the parameter symbols. Historically, p-strings have been leveraged for source code cloning, plagiarism detection, and biological sequence structural similarity. In this work, we identify the connection between the p-match and music, one of several applications to motivate our study of holes in p-strings, and prefix array-based data structures for p-strings. First, we introduce the parameterized prefix array ( pPA ) for p-strings and its succinct representation, the compact parameterized prefix array ( cpPA ). We show an interesting construction of the cpPA via the parameterized longest previous factor ( pLPF ), a more recently proposed array with connections to various pattern matching data structures and LZ factorization. Next, we introduce the parameterized string with holes (hp-string), needed to address a special form of indeterminate pattern matching with p-strings. Then, we show how to construct the compact prefix array for hp-strings. Finally, we discuss applications for our data structures. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect