A prefix array for parameterized strings

详细信息    查看全文

• 作者：Richard Beal^a ; ^{richard.a.beal@gmail.com} ; Donald A. Adjeroh^a ; ^{don@csee.wvu.edu} ; W.F. Smyth^b ; ^c ; ^{smyth@mcmaster.ca}
• 关键词：Parameterized prefix array ; Compact parameterized prefix array ; Parameterized string with holes ; Parameterized longest previous factor ; p-string ; hp-string ; p-match ; hp-match ; pPA ; cpPA ; chpPA ; pLPF
• 刊名：Journal of Discrete Algorithms
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：42
• 期：Complete
• 页码：23-34
• 全文大小：513 K
• 卷排序：42

文摘

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.