检索结果-内蒙古大学图书馆

Range Majorities and Minorities in Arrays

ALGORITHMICA 2021年第6期83卷 1707-1733页

作者： Belazzougui, Djamal Gagie, Travis Munro, J. Ian Navarro, Gonzalo Nekrich, Yakov Res Ctr Tech & Sci Informat CERIST Algiers Algeria Dalhousie Univ Fac Comp Sci Halifax NS Canada Univ Waterloo David Cheriton Sch Comp Sci Waterloo ON Canada Univ Chile Dept Comp Sci Millennium Inst Fdn Res Data Santiago Chile Michigan Technol Univ Dept Comp Sci Houghton MI 49931 USA

The problem of parameterized range majority asks us to preprocess a string of length n such that, given the endpoints of a range, one can quickly find all the distinct elements whose relative frequencies in that range are more than a threshold tau. This is a more tractable version of the classical problem of finding the range mode, which is unlikely to be solvable in polylogarithmic time and linear space. In this paper we give the first linear-space solution with optimal O(1/tau) query time, even when tau can be specified with the query. We then consider data structures whose space is bounded by the entropy of the distribution of the symbols in the sequence. For the case when the alphabet size sigma is polynomial on the computer word size, we retain the optimal time within optimally compressed space (i.e., with sublinear redundancy). Otherwise, either the compressed space is increased by an arbitrarily small constant factor or the time rises to any function in (1 /tau) . omega(1). We obtain the same results on the complementary problem of parameterized range minority.

关键词： compressed data structures Range majority and minority Range mode

来源：评论

学校读者我要写书评

暂无评论

Indexing Highly Repetitive String Collections, Part I: Repetitiveness Measures

引用

ACM COMPUTING SURVEYS 2021年第2期54卷 1–31页

作者： Navarro, Gonzalo Univ Chile Ctr Biotechnol & Bioengn CeBiB Dept Comp Sci Beauchef 851 Santiago Chile Univ Chile Millennium Inst Foundat Res Data IMFD Dept Comp Sci Beauchef 851 Santiago Chile

Two decades ago, a breakthrough in indexing string collections made it possible to represent them within their compressed space while at the same time offering indexed search functionalities. As this new technology permeated through applications like bioinformatics, the string collections experienced a growth that outperforms Moore's Law and challenges our ability to handle them even in compressed form. It turns out, fortunately, that many of these rapidly growing string collections are highly repetitive, so that their information content is orders of magnitude lower than their plain size. The statistical compression methods used for classical collections, however, are blind to this repetitiveness, and therefore a new set of techniques has been developed to properly exploit it. The resulting indexes form a new generation of data structures able to handle the huge repetitive string collections that we are facing. In this survey, formed by two parts, we cover the algorithmic developments that have led to these data structures. In this first part, we describe the distinct compression paradigms that have been used to exploit repetitiveness, and the algorithmic techniques that provide direct access to the compressed strings. In the quest for an ideal measure of repetitiveness, we uncover a fascinating web of relations between those measures, as well as the limits up to which the data can be recovered, and up to which direct access to the compressed data can be provided. This is the basic aspect of indexability, which is covered in the second part of this survey.

关键词： Text indexing string searching compressed data structures repetitive string collections

来源：评论

学校读者我要写书评

暂无评论

Efficient Compression and Indexing for Highly Repetitive DNA Sequence Collections

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2021年第6期18卷 2394-2408页

作者： Huo, Hongwei Chen, Xiaoyang Guo, Xu Vitter, Jeffrey Scott Xidian Univ Sch Comp Sci & Technol Xian 710071 Shaanxi Peoples R China Univ Mississippi Dept Comp & Informat Sci University MS 38677 USA

In this paper, we focus upon the important problem of indexing and searching highly repetitive DNA sequence collections. Given a collection G of t sequences Si of length n each, we can represent G succinctly in 2(n)H(k)(T) + O(n' log log n) +o(qn') + o(tn) bits using O(tn(2) + qn') time, where H-k(T) is the kth-order empirical entropy of the sequence T is an element of G that is used as the reference sequence, n0 is the total number of variations between T and the sequences in G, and q is a small fixed constant. We can restore any length len substring S[sp;..., sp + l] of S is an element of G in O(n's + lenol)(2)/=log log n) time and report all positions where P occurs in G in O(m. t + occ . t . (log n)(2) /log log n) time. In addition, we propose a dynamic programming method to find the variations between T and the sequences in G in a space-efficient way, with which we can build succinct structures to enable efficient search. For highly repetitive sequences, experimental results on the tested data demonstrate that the proposed method has significant advantages in space usage and retrieval time over the current state-of-the-art methods. The source code is available online.

关键词： Repetitive DNA sequences compressed data structures indexing retrieval string searching

来源：评论

学校读者我要写书评

暂无评论

Block trees

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2021年 117卷 1-22页

作者： Belazzougui, Djamal Caceres, Manuel Gagie, Travis Gawrychowski, Pawel Kaerkkaeinen, Juha Navarro, Gonzalo Ordonez, Alberto Puglisi, Simon J. Tabei, Yasuo DTISI CERIST Algiers Algeria Univ Chile Ctr Biotechnol & Bioengn CeBiB Santiago Chile Univ Chile Dept Comp Sci Santiago Chile Dalhousie Univ Fac Comp Sci Halifax NS Canada Univ Wroclaw Wroclaw Poland Univ Helsinki Helsinki Inst Informat Technol HIIT Helsinki Finland Univ Helsinki Dept Comp Sci Helsinki Finland Pinterest Inc San Francisco CA USA Japan Sci & Technol Agcy PRESTO Saitama Japan

Let string S[1..n] be parsed into z phrases by the Lempel-Ziv algorithm. The corresponding compression algorithm encodes S in O(z) space, but it does not support random access to S. We introduce a data structure, the block tree, that represents S in O(z log(n/z)) space and extracts any symbol of S in time O(log(n/z)), among other space-time tradeoffs. The structure also supports other queries that are useful for building compressed data structures on top of S. Further, block trees can be built in linear time and in a scalable manner. Our experiments show that block trees offer relevant space-time tradeoffs compared to other compressed string representations for highly repetitive strings. (C) 2020 Elsevier Inc. All rights reserved.

关键词： compressed data structures Repetitive string collections Lempel-Ziv compression

来源：评论

学校读者我要写书评

暂无评论

PTHash: Revisiting FCH Minimal Perfect Hashing 21

PTHash: Revisiting FCH Minimal Perfect Hashing

引用

44th International ACM SIGIR Conference on Research and Development in Information Retrieval

作者： Pibiri, Giulio Ermanno Trani, Roberto ISTI CNR Pisa Italy

ISBN: (纸本)9781450380379

Given a set S of n distinct keys, a function f that bijectively maps the keys of S into the range {0, ..., n - 1} is called a minimal perfect hash function for S. Algorithms that find such functions when n is large and retain constant evaluation time are of practical interest;for instance, search engines and databases typically use minimal perfect hash functions to quickly assign identifiers to static sets of variable-length keys such as strings. The challenge is to design an algorithm which is efficient in three different aspects: time to find f (construction time), time to evaluate f on a key of S (lookup time), and space of representation for f. Several algorithms have been proposed to trade-off between these aspects. In 1992, Fox, Chen, and Heath (FCH) presented an algorithm at SIGIR providing very fast lookup evaluation. However, the approach received little attention because of its large construction time and higher space consumption compared to other subsequent techniques. Almost thirty years later we revisit their framework and present an improved algorithm that scales well to large sets and reduces space consumption altogether, without compromising the lookup time. We conduct an extensive experimental assessment and show that the algorithm finds functions that are competitive in space with state-of-the art techniques and provide 2 - 4x better lookup time.

关键词： Minimal Perfect Hashing FCH XOR compressed data structures

来源：评论

学校读者我要写书评

暂无评论

Novel Results on the Number of Runs of the Burrows-Wheeler-Transform 47th

Novel Results on the Number of Runs of the Burrows-Wheeler-T...

引用

47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)

作者： Giuliani, Sara Inenaga, Shunsuke Liptak, Zsuzsanna Prezza, Nicola Sciortino, Marinella Toffanello, Anna Univ Verona Dipartimento Informat Verona Italy Kyushu Univ Dept Informat Fukuoka Japan Japan Sci & Technol Agcy PRESTO Kawaguchi Saitama Japan LUISS Univ Dept Business & Management Rome Italy Univ Palermo Dipartimento Matemat & Informat Palermo Italy

ISBN: (纸本)9783030677305;9783030677312

The Burrows-Wheeler-Transform (BWT), a reversible string transformation, is one of the fundamental components of many current data structures in string processing. It is central in data compression, as well as in efficient query algorithms for sequence data, such as webpages, genomic and other biological sequences, or indeed any textual data. The BWT lends itself well to compression because its number of equal-letter-runs (usually referred to as r) is often considerably lower than that of the original string;in particular, it is well suited for strings with many repeated factors. In fact, much attention has been paid to the r parameter as measure of repetitiveness, especially to evaluate the performance in terms of both space and time of compressed indexing data structures. In this paper, we investigate rho(v), the ratio of r and of the number of runs of the BWT of the reverse of v. Kempa and Kociumaka [FOCS 2020] gave the first non-trivial upper bound as rho(v) = O(log(2) (n)), for any string v of length n. However, nothing is known about the tightness of this upper bound. We present infinite families of binary strings for which rho(v) = T(log n) holds, thus giving the first non-trivial lower bound on rho(n), the maximum over all strings of length n. Our results suggest that r is not an ideal measure of the repetitiveness of the string, since the number of repeated factors is invariant between the string and its reverse. We believe that there is a more intricate relationship between the number of runs of the BWT and the string's combinatorial properties.

关键词： Burrows-Wheeler-Transform compressed data structures String indexing Repetitiveness Combinatorics on words

来源：评论

学校读者我要写书评

暂无评论

Dynamic index and LZ factorization in compressed space

引用

DISCRETE APPLIED MATHEMATICS 2020年 274卷 116-129页

作者： Nishimoto, Takaaki Tomohiro, I Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki RIKEN Ctr Adv Intelligence Project Tokyo Japan Kyushu Univ Dept Informat Fukuoka Japan Kyushu Inst Technol Fukuoka Japan

In this paper, we propose a new dynamic compressed index of O(w) space for a dynamic text T, where w = O(min(z log N lot M, N)) is the size of the signature encoding of T, z is the size of the Lempel Ziv77 (L277) factorization of T, N is the length of T, and M >= N is the maximum length of T. Our index supports searching for a pattern P in T in O(vertical bar P vertical bar f(A)+log w log vertical bar P vertical bar log* M(log N+log vertical bar P vertical bar log* M)+occ log N) time and insertion/deletion of a substring of lengthy in O((y + log N log* M) log w log N log* M) time, where occ is the number of occurrences of P in T and f(A) = O(min{log logM log log w/log log log M, root log w/log log w}).Also, we propose a new space-efficient 1277 factorization algorithm for a given text T, which runs in O(Nf(A) + z log w log(3) N(log* N)(2)) time with O(w) working space. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Dynamic texts 1277 factorization Dynamic index compressed data structures Dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

A Hybrid compressed data Structure Supporting Rank and Select on Bit Sequences 39

A Hybrid Compressed Data Structure Supporting Rank and Selec...

引用

39th International Conference of the Chilean-Computer-Science-Society (SCCC)

作者： Arroyuelo, Diego Weitzman, Manuel Univ Tecn Federico Santa Maria Dept Informat Valparaiso Chile Millennium Inst Fdn Res Data IMFD Santiago Chile Cornershop Santiago Chile

ISBN: (纸本)9781728183282

We introduce a practical data structure for supporting the fundamental operations rank, select, and member on integer sets (and their corresponding characteristic bit vector). Our data structure uses a hybrid compression approach to achieve compressed space, while still supporting the operations efficiently. Our aim is to take advantage of the long runs of successive elements that arise in several practical scenarios. Our experimental results indicate that our approach is highly competitive in these cases with the most efficient state-of-The-Art data structures. © 2020 IEEE.

关键词： Succinct and compact data structures compressed data structures Rank and select operations on bit sequences

来源：评论

学校读者我要写书评

暂无评论

Faster Online Computation of the Succinct Longest Previous Factor Array 16th

Faster Online Computation of the Succinct Longest Previous F...

引用

16th Conference on Computability in Europe (CiE)

作者： Prezza, Nicola Rosone, Giovanna Univ Pisa Pisa Italy LUISS Guido Carli Rome Italy

ISBN: (纸本)9783030514662;9783030514655

We consider the problem of computing online the Longest Previous Factor array LPF[1, n] of a text T of length n. For each 1 <= i <= n, LPF[i] stores the length of the longest factor of T with at least two occurrences, one ending at i and the other at a previous position j < i. We present an improvement over the previous solution by Okanohara and Sadakane (ESA 2008): our solution uses less space (compressed instead of succinct) and runs in O(n log(2) n) time, thus being faster by a logarithmic factor. As a by-product, we also obtain the first online algorithm computing the Longest Common Suffix (LCS) array (that is, the LCP array of the reversed text) in O(n log(2) n) time and compressed space. We also observe that the LPF array can be represented succinctly in 2n bits. Our online algorithm computes directly the succinct LPF and LCS arrays.

关键词： Longest Previous Factor Online compressed data structures

来源：评论

学校读者我要写书评

暂无评论

Subpath Queries on compressed Graphs: A Survey

引用

ALGORITHMS 2021年第1期14卷

作者： Prezza, Nicola Ca Foscari Univ Dept Environm Sci Informat & Stat Dorsoduro 3246 I-30123 Venice Italy

Text indexing is a classical algorithmic problem that has been studied for over four decades: given a text T, pre-process it off-line so that, later, we can quickly count and locate the occurrences of any string (the query pattern) in T in time proportional to the query's length. The earliest optimal-time solution to the problem, the suffix tree, dates back to 1973 and requires up to two orders of magnitude more space than the plain text just to be stored. In the year 2000, two breakthrough works showed that efficient queries can be achieved without this space overhead: a fast index be stored in a space proportional to the text's entropy. These contributions had an enormous impact in bioinformatics: today, virtually any DNA aligner employs compressed indexes. Recent trends considered more powerful compression schemes (dictionary compressors) and generalizations of the problem to labeled graphs: after all, texts can be viewed as labeled directed paths. In turn, since finite state automata can be considered as a particular case of labeled graphs, these findings created a bridge between the fields of compressed indexing and regular language theory, ultimately allowing to index regular languages and promising to shed new light on problems, such as regular expression matching. This survey is a gentle introduction to the main landmarks of the fascinating journey that took us from suffix trees to today's compressed indexes for labeled graphs and regular languages.

关键词： indexing compressed data structures labeled graphs

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：