Order-preserving indexing

详细信息    查看全文

• 作者：Maxime Crochemore^a ; ^{maxime.crochemore@kcl.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Costas S. Iliopoulos^a ; ^{c.iliopoulos@kcl.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Tomasz Kociumaka^b ; ^{kociumaka@mimuw.edu.pl" class="auth_mail" title="E-mail the corresponding author} ; Marcin Kubica^b ; ^{kubica@mimuw.edu.pl" class="auth_mail" title="E-mail the corresponding author} ; Alessio Langiu^c ; ^{alessio.langiu@iamc.cnr.it" class="auth_mail" title="E-mail the corresponding author} ; Solon P. Pissis^a ; ^{solon.pissis@kcl.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Jakub Radoszewski^b ; ^{jrad@mimuw.edu.pl" class="auth_mail" title="E-mail the corresponding author} ; Wojciech Rytter^b ; ^{rytter@mimuw.edu.pl" class="auth_mail" title="E-mail the corresponding author} ; Tomasz Waleń^b ; ^{walen@mimuw.edu.pl" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Order-preserving matching ; Order-preserving indexing ; Suffix tree
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：25 July 2016
• 年：2016
• 卷：638
• 期：Complete
• 页码：122-135
• 全文大小：526 K

文摘

Kubica et al. [33] and Kim et al. [29] introduced order-preserving pattern matching: for a given text the goal is to find its factors having the same ‘shape’ as a given pattern. Known results include a linear-time algorithm for this problem (in case of polynomially-bounded alphabet) and a generalization to multiple patterns. We propose an index that enables order-preserving pattern matching queries in time proportional to pattern length. The index can be constructed in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515005605&_mathId=si1.gif&_user=111111111&_pii=S0304397515005605&_rdoc=1&_issn=03043975&md5=2820969bc52e04b15a1d8efd935af960" title="Click to view the MathML source">O(nlog⁡log⁡n)class="mathContainer hidden">class="mathCode">$O(n\log \log n)$ expected time or in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515005605&_mathId=si11.gif&_user=111111111&_pii=S0304397515005605&_rdoc=1&_issn=03043975&md5=f8c5bd4ae42a9021f41c00bb596f096a" title="Click to view the MathML source">O(nlog²⁡log⁡n/log⁡log⁡log⁡n)class="mathContainer hidden">class="mathCode">$O(n{\log }^2\log n/\log \log \log n)$ worst-case time. It is an incomplete order-preserving suffix tree which may miss a single edge label at each branching node. For most applications such incomplete suffix trees provide the same functional power as the complete ones. We show a number of their applications, including computation of longest common factors, longest previously occurring factors and squares in a string in the order-preserving setting. We also give an class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515005605&_mathId=si247.gif&_user=111111111&_pii=S0304397515005605&_rdoc=1&_issn=03043975&md5=463a1d2ecf07bb369fe69371e51ef2ac">class="imgLazyJSB inlineImage" height="19" width="68" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397515005605-si247.gif">class="mathContainer hidden">class="mathCode">$O(n\sqrt{\log n})$-time algorithm constructing complete order-preserving suffix trees.