基于压缩树的低峰值内存占用方法及实验分析

CSTStCST可在www.sciencedirect.com在线获取理论计算机科学电子笔记302（2014）73-94www.elsevier.com/locate/entcs一种基于压缩树的低峰值内存占用实现方法DanielSaadNogueiraNunes2MauricioAyala-Rinc'on3InstitutodeCiEschenciasExatasDepartamentosdeCiEschencidaComputaEschencaoeMatem'atica布拉迪斯拉发大学摘要SU_X树和SU_X数组是众所周知的索引，它们对于大输入需要太多的空间。最近，一些作品探索了一种名为压缩的sunix树（）的数据结构，它具有相同的它的功能比sunix树更强大，并且基于压缩的sunix数组、压缩的最长公共前缀信息和导航操作。本文实现了一个基于范围最小值查询和最近较小值查询的查询，它所需的空间大致超过了所需的空间来表示施工期间的指标。实验表明，该指标是有用的对于许多应用程序，因为一方面，可以执行复杂的遍历，例如，对于处理关于序列的组合结构的几个问题来说必不可少的sunix链接和最长共同祖先查询;另一方面，对于使用其中可用存储器的量受到限制的计算环境的应用程序来说，结构结果具有实际意义，因为它适合于普通计算机的主存储器。关键词：sunix树，sunix数组，最长公共前缀，压缩sunix树，字符串处理。1介绍苏诺克斯树（ST）是一种非常通用的数据结构，在计算机科学的几个领域（如计算生物学）中有广泛的应用，如[14]所示。与其他数据结构（如try）相比，文本的ST1由联邦区研究基金会FAPDF的PRONEX赠款和科学和技术企业基金会FINATEC的旅行赠款支持的工作。2电子邮件：daniel.saad. gmail.com作者由高等教育人员CAPES提高协调的研究生奖学金支持。3电子邮件：ayala@unb.br作者部分得到国家技术和科学发展委员会CNPq的资助。http://dx.doi.org/10.1016/j.entcs.2014.01.0211571-0661© 2014 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。74 D.S. Nogueira Nunes，M. Ayala-Rincón/电子笔记在理论计算机科学302（2014）73-94在相关问题的求解中，树的连接和最低共同祖先查询（LCA）等操作是必不可少的因此，在实践中，通常需要具有完整功能的ST，支持许多复杂的遍历ST的主要问题是在实践中的空间消耗。虽然长度为n的文本的ST渐进地需要Θ（nlogn）位，但实际上需要输入大小的15倍[19]，这导致例如用于构建人类基因组结构的45GB主存提出了SU_MAX阵列，以便使用比ST更少的空间来解决字符串处理问题[23]。然而，su_x数组的信息仅对应于按字典顺序排列的ST的叶子。尽管如此，可以使用最长公共前缀信息（LCP）来增强sunix数组，该信息隐式地编码了相关ST的拓扑。因此，如果提供了LCP信息和导航操作，则sunix数组可以完全取代ST[2]。虽然占用的空间较少，但sunix数组仍然需要Θ（nlogn）位，通常每个输入符号4个字节，如果使用LCP信息增强，则为8个字节。该结构所需的空间量仍然是巨大的，不允许它们用于中等大小的文本。最近，已经做了大量的工作，以压缩sunix数组数据结构，如[12]和[8]所示压缩结构可以实现空间的Θ（nH0）比特，其中H0代表零阶熵。因此，在实践中需要更少的空间来表示suprix数组信息，尽管压缩增加了对结构的查询时间。一般来说，压缩系数是很大的。可以在每个输入符号的几个比特内表示结构，如[16]所示It’s also possible to represent the 因此，在LCP中使用用于导航操作的压缩数据结构， 在实践中节省了大量的空间这种压缩数据结构由压缩子树数组、压缩LCP信息和压缩导航信息组成，称为压缩子树（CST）。Sadakane in [31].尽管需要一些额外的位来表示CST并支持复杂的遍历，但需要更多的时间来回答查询。 通常，在每个子元素数组、LCP或导航操作中存在一个因子Θ（logn），θ>当大量内存不可用时，空间和时间之间的权衡是高度可接受的。我们的贡献是一个CST的低内存峰值使用率相比，与其他国家的最先进的指数的实施。它使用基于[5]的压缩数据结构用于范围最小查询（RMQ），以前的较小值查询（PSV）和下一个较小值查询（NSV），以在压缩LCP信息编码的拓扑中导航。为了减少结构构建过程中所需的峰值内存，使用增量算法在Θ（nH0）工作空间内构建压缩后的su_x数组，而不是压缩原始su_x数组[15]。这种增量算法避免了构建原始sunix数组D.S. Nogueira Nunes，M.Ayala-Rincón/电子笔记在理论计算机科学302（2014）7375| |然后由于所使用的在线方法而对其进行压缩。为了评估所提出的实现，实验进行了两个指数。第一个是基于[25]提供的未压缩suprix数组和使用[18]中的方法计算的未压缩LCP信息。第二个索引是由赫尔辛基大学的简洁数据结构组（SuDS）提出的CST[34][33]，它基于[31]。本文的结构如下。所有必要的基本概念在第2节中给出;压缩的sunix数组和LCP在第3节中介绍，然后在第4节中介绍压缩的sunix树。然后，在第5节和第6节中介绍了相关工作和实验结果，然后在第7节中总结并介绍了未来的工作。2基本概念字母表是符号的有限集合{α0，α1，.，ασ−1}，总阶为α0<α1<。. . <ασ−1，其中Σ =σ，字母表的基数或大小。文本是符号的有限字符串。长度为n的文本T的第i个符号表示为T [i]，从第i个符号到第j个符号的子串表示为T [i，j]，0 ≤ i ≤ j ≤ n −1。SU_xT [i，n-1]记为Ti。假设任何文本T的最后一个字符是符号$，它属于，在字典上比的任何其他符号都小，并且只出现在T的最后一个位置。给定文本R和S，只要两个字符串的前k个符号相等，就说R=kS根据[14]，T的ST是一个有根有向树，有n个叶子，编号从0到n-1。每个内部节点，除了根节点，至少有两个子节点，每个边用T的非空子串标记。节点外的边不能具有以相同字符开头的边标签。STs的关键特征是从根到任何叶子i的路径上的边标签的级联拼出Ti。图1显示了文本T=acaaacatat$的一个子树一个子集数组A是一个整数数组，它包含T的子集的开始位置，按照由符号的顺序引起的字典顺序。[1]<[2][3][4][5][6<] . . < TA[n− 1].76 D.S. Nogueira Nunes，M. Ayala-Rincón/电子笔记在理论计算机科学302（2014）73-94一CA不⎨·$····T4T5一个CAT·T3T7·T10T8T3T71T10T8图1.对于T=acaaacatat$的Su树。表1用于acaaacatat$和LCP信息的Sux数组。我T A [i]A[i]LCP[i]0$1001aaacatat$222阿卡塔$313acaaacatat$034acatat$415在$826atat$607caaacatat$128猫$509不是$9110价格$70LCP信息保存一个sunix数组的两个相邻条目正式地，它被定义为：LCP[i]=max {k|TA[i]= kTA[i +1]}，i< n− 1n =0，i =n− 1（一）表1中显示了T=acaaacatat$的 suprix数组和LCP信息的示例。10597230486D.S. Nogueira Nunes，M.Ayala-Rincón/电子笔记在理论计算机科学302（2014）73773压缩sunix阵列和LCP通过只对少数几个条目进行采样，可以实现对sunix数组的压缩这种数据结构的非抽样条目可以通过计算恢复。 如果采样因子是K ∈Θ（logn），则将仅需要Θ（n）比特来表示采样条目。一个压缩的suprix数组数据结构的核心是suprix函数，它允许我们在suprix数组中导航该函数定义为：n（i）=j，A[j]=（A[i] +1）modn（2）换句话说，如果A[i]=k，则（i）给出了su x的字典序T（k +1） mod n在所有其他summixes中。简单地说，将使用Θ（nlogn）位来表示θ。然而，可以在Θ（nH0）比特内表示θ。由于数组是按字典顺序排列的，所以对于从相同符号开始的supraxes，supraxes保持递增序列，如表2所示。因此，有可能使用莱斯编码将每个递增序列编码在Θ（n）位中，同时允许使用对位向量的秩和选择查询对Θ（1）时间查询到θ（n）值的任何位置，如[12]中所示。尽管Rank和Select查询有Θ（1）解，但由于性能更好且占用空间更少，因此在实践中通常会获得ω（1）结果，如[11]所示。对于tR的访问时间由tR表示。表2函数遍历suprix数组。一旦构建了suprix数据结构，就可以使用此函数遍历suprix数组来恢复未采样的suprix数组条目。 以表2为例，A[2]没有被采样，因此，函数会被调用4次，直到找到一个采样值;因此，A[2] =A[10]− 4 = 7− 4 = 3。平均而言，对A[i]的访问，记为tA，需要O（tK），如[16]所示所提出的CST使用来自[15]的增量出租来构建压缩的suprix阵列。该算法只占用了工作空间的Θ（nH0）位和Θ（nlogn）78 D.S. Nogueira Nunes，M. Ayala-Rincón/电子笔记在理论计算机科学302（2014）73-94lognn表3LCP[i]+A[i]保持一个递增序列，如果后缀是按文本顺序检查的我TA[i]A[i]LCP[i]A[i]+LCP[i]0$100101aaacatat$2242阿卡塔$3143acaaacatat$0334acatat$4155在$82106atat$6067caaacatat$1238猫$5059不是$911010价格$707时间，因此，创建压缩的sunix数组，而无需首先构建原始sunix数组。这个想法是从文本的结尾到开头递增地计算。 对于每个大小为B的块∈θ（），一个需要计算的位置-它们之间的新添加的子集的位置以及每个新添加的子集在现有子集中的位置，并且最终使用该新信息来为添加的子集构建查询函数。总体上存在B∈Θ（logn）个块在[30]中表明，LCP信息最多可以使用2n比特，同时允许快速访问。这是可能的，因为LCP[i] +A[i]值保持递增的序列，如果在子集的递减长度中检查条目。因此，它可以用与用于表示的方法相同的方法来表示。 例如，在表3中，当以子集长度的降序检查条目时，A[i]+LCP[i]值存在递增序列（3， 3， 4， 4， 5， 5， 6， 7， 10， 10， 10）[18]中的方法基于此顺序计算LCP信息，建议CST的选择方法也是如此。由于编码的信息不是按照字典顺序存储的，因此需要对A[i]进行额外的访问以检索LCP[i]，因此，对LCP[i]的访问需要tLCP∈Θ（tA）。4压缩树一旦LCP信息隐式地编码了关联的sunix树拓扑，就需要浏览该信息，以便进行复杂的树遍历。但首先，有必要识别LCP信息中的拓扑。这可以使用l-区间的概念来完成，它拥有一对一的D.S. Nogueira Nunes，M.Ayala-Rincón/电子笔记在理论计算机科学302（2014）7379≤k≤j----与关联ST[2]的内部概念相对应。一个i-区间val[i，j]是一个l-区间，记为l-[i，j]，如果：i= 0LCP [i−1]

下载后可阅读完整内容，剩余1页未读，立即下载