首页    期刊浏览 2024年11月07日 星期四
登录注册

文章基本信息

  • 标题:Structural Pattern Matching - Succinctly
  • 本地全文:下载
  • 作者:Arnab Ganguly ; Rahul Shah ; Sharma V. Thankachan
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2017
  • 卷号:92
  • 页码:35:1-35:13
  • DOI:10.4230/LIPIcs.ISAAC.2017.35
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:Let T be a text of length n containing characters from an alphabet \Sigma, which is the union of two disjoint sets: \Sigma_s containing static characters (s-characters) and \Sigma_p containing parameterized characters (p-characters). Each character in \Sigma_p has an associated complementary character from \Sigma_p. A pattern P (also over \Sigma) matches an equal-length substring $S$ of T iff the s-characters match exactly, there exists a one-to-one function that renames the p-characters in S to the p-characters in P, and if a p-character x is renamed to another p-character y then the complement of x is renamed to the complement of y. The task is to find the starting positions (occurrences) of all such substrings S. Previous indexing solution [Shibuya, SWAT 2000], known as Structural Suffix Tree, requires \Theta(n\log n) bits of space, and can find all occ occurrences in time O(|P|\log \sigma+ occ), where \sigma = |\Sigma|. In this paper, we present the first succinct index for this problem, which occupies n \log \sigma + O(n) bits and offers O(|P|\log\sigma+ occ\cdot \log n \log\sigma) query time.
  • 关键词:Parameterized Pattern Matching; Suffix tree; Burrows-Wheeler Transform; Wavelet Tree; Fully-functional succinct tree
国家哲学社会科学文献中心版权所有