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

A Learned Approach to Design compressed Rank/Select data structures

ACM TRANSACTIONS ON ALGORITHMS 2022年第3期18卷 24-24页

作者： Boffa, Antonio Ferragina, Paolo Vinciguerra, Giorgio Univ Pisa Largo Bruno Pontecorvo 3 I-56127 Pisa Italy

We address the problem of designing, implementing, and experimenting with compressed data structures that support rank and select queries over a dictionary of integers. We shine a new light on this classical problem by showing a connection between the input integers and the geometry of a set of points in a Cartesian plane suitably derived from them. We then build upon some results in computational geometry to introduce the first compressed rank/select dictionary based on the idea of "learning" the distribution of such points via proper linear approximations (LA). We therefore call this novel data structure the la_vector. We prove time and space complexities of the la_vector in several scenarios: in the worst case, in the case of input distributions with finite mean and variance, and taking into account the kth order entropy of some of its building blocks. We also discuss improved hybrid data structures, namely, ones that suitably orchestrate known compressed rank/select dictionaries with the la_vector. We corroborate our theoretical results with a large set of experiments over datasets originating from a variety of applications (Web search, DNAsequencing, information retrieval, and natural language processing) and show that our approach provides new interesting space-time tradeoffs with respect to many well-established compressed rank/select dictionary implementations. In particular, we show that our select is the fastest, and our rank is on the space-time Pareto frontier.

关键词： compressed data structures rank/select dictionaries piecewise linear approximations high order entropy algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Computing MEMs and Relatives on Repetitive Text Collections

引用

ACM TRANSACTIONS ON ALGORITHMS 2025年第1期21卷 1-33页

作者： Navarro, Gonzalo Univ Chile Ctr Biotechnol & Bioengn CeBiB Dept Comp Sci Beauchef 851 Santiago Chile

We consider the problem of computing the Maximal Exact Matches (MEMs) of a given pattern P[1..m] on a large repetitive text collection T[1..n] over an alphabet of size sigma, which is represented as a (hopefully much smaller) run-length context-free grammar of size g(rl). We show that the problem can be solved in time O(m(2) log(is an element of) n), for any constant is an element of > 0, on a data structure of size O(g(rl)). Further, on a locally consistent grammar r of size O(delta log n log sigma/delta log n), the time decreases to O(mlog m(log m+log (is an element of) n)). The value delta is a function of the substring complexity of T and Omega(delta log n log sigma/delta log n) a tight lower bound on the compressibility of repetitive texts T, so our structure has optimal size in terms of n, sigma, and 8. We extend our results to several related problems, such as finding k-MEMs, MUMs, rare MEMs, and applications.

关键词： Repetitive texts Substring complexity Grammar compression Locally consistent parsing compressed data structures MEMs MUMs

来源：评论

学校读者我要写书评

暂无评论

Algorithms and Complexity on Indexing Founder Graphs

引用

ALGORITHMICA 2023年第6期85卷 1586-1623页

作者： Equi, Massimo Norri, Tuukka Alanko, Jarno Cazaux, Bastien Tomescu, Alexandru, I Makinen, Veli Univ Helsinki Dept Comp Sci POB 68Pietari Kalmin Katu 5 Helsinki 00014 Finland Dalhousie Univ Fac Comp Sci POB 150006050 Univ Ave Halifax NS Canada Univ Montpellier CNRS LIRMM LIRMM UMR 5506 CC477161 Rue Ada F-34095 Montpellier 5 France

We study the problem of matching a string in a labeled graph. Previous research has shown that unless the Orthogonal Vectors Hypothesis (OVH) is false, one cannot solve this problem in strongly sub-quadratic time, nor index the graph in polynomial time to answer queries efficiently (Equi et al. ICALP 2019, SOFSEM 2021). These conditional lower-bounds cover even deterministic graphs with binary alphabet, but there naturally exist also graph classes that are easy to index: For example, Wheeler graphs (Gagie et al. Theor. Comp. Sci. 2017) cover graphs admitting a Burrows-Wheeler transform -based indexing scheme. However, it is NP-complete to recognize if a graph is a Wheeler graph (Gibney, Thankachan, ESA 2019). We propose an approach to alleviate the construction bottleneck of Wheeler graphs. Rather than starting from an arbitrary graph, we study graphs induced from multiple sequence alignments (MSAs). Elastic degenerate strings (Bernadini et al. SPIRE 2017, ICALP 2019) can be seen as such graphs, and we introduce here their generalization: elastic founder graphs. We first prove that even such induced graphs are hard to index under OVH. Then we introduce two subclasses, repeat-free and semi-repeat-free graphs, that are easy to index. We give a linear time algorithm to construct a repeat-free (non-elastic) founder graph from a gapless MSA, and (parameterized) near-linear time algorithms to construct a semi-repeat-free (repeat-free, respectively) elastic founder graph from general MSA. Finally, we show that repeat-free founder graphs admit a reduction to Wheeler graphs in polynomial time.

关键词： Graph algorithms Computational complexity compressed data structures String matching Multiple sequence alignment Segmentation algorithms Pangenomics

来源：评论

学校读者我要写书评

暂无评论

Practical High-Order Entropy-compressed Text Self-Indexing

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND data ENGINEERING 2023年第3期35卷 2943-2960页

作者： Huo, Hongwei Long, Peng Vitter, Jeffrey Scott Xidian Univ Comp Sci & Technol Xian 710071 Shaanxi Peoples R China Xidian Univ Xian 710071 Shaanxi Peoples R China Univ Mississippi Oxford MS 38677 USA Tulane Univ New Orleans LA 70118 USA

compressed self-indexes are used widely in string processing applications, such as information retrieval, genome analysis, data mining, and web searching. The index not only indexes the data, but also encodes the data, and it is in compressed form. Moreover, the index and the data it encodes can be operated upon directly, without need to uncompress the entire index, thus saving time while maintaining small storage space. In some applications, such as in genome analysis, existing methods do not exploit the full possibilities of compressed self-indexes, and thus we seek faster and more space-efficient indexes. In this paper, we propose a practical high-order entropy-compressed self-index for efficient pattern matching in a text. We give practical implementations of compressed suffix arrays using a hybrid encoding in the representation of the neighbor function F. We analyze the performance in theory and practice of our recommended indexing method, called GeCSA. We can improve retrieval time further using an iterated version of the neighbor function. Experimental results on the tested data demonstrate that the proposed index GeCSA has good overall advantages in space usage and retrieval time over the state-of-the-art indexing methods, especially on the repetitive data.

关键词： Entropy Arrays Indexing Bioinformatics Pattern matching Genomics Encoding Text indexing text retrieval entropy-compressed compressed data structures pattern matching

来源：评论

学校读者我要写书评

暂无评论

A parallel finite volume method for incompressible and slightly compressible reactive flows

引用

INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING 2022年第16期123卷 3800-3846页

作者： de Andrade, Henrique C. C. Ribeiro, Fernando L. B. Carlos Wrobel, Luiz COPPE Univ Fed Rio Janeiro Programa Engn Civil Rio De Janeiro Brazil Pontificia Univ Catol Rio Janeiro Dept Engn Civil Ambiental Rio De Janeiro Brazil

In this article, a parallel formulation of the finite volume method is presented for solving three-dimensional, turbulent, mixed, reactive, and slightly compressible flows. It can also be used for incompressible laminar/turbulent flows. The method is designed for nonorthogonal meshes, and oscillations caused by the advective terms are treated by a deferred correction technique. The chosen finite volume scheme is cell centered. The studied fluid is a single-phase multicomponent gas with Newtonian behavior. The focus is mainly on gas mixtures with predominance of N2$$ {}_2 $$, since the chemical reaction of greatest interest is the combustion process in the air. The buoyancy is caused by the gradient of the specified mass, which is a function of the temperature and the composition of the gas mixture. The mathematical model uses an approximation for low Mach numbers, describing slightly compressible flows. The coupling between the fluid dynamic equations is given by the nonlinear Picard's method, with the pressure-velocity coupling treatment given by the SIMPLE algorithm (semi-implicit method for pressure-linked equations). The complete mathematical model includes the sensitive enthalpy equation for the conservation of energy. The LES (large eddy simulation) model is used for modeling the turbulence. The chemical reactions are implemented using the EDC (eddy dissipation concept) and the EDM (eddy dissipation model) approaches. The parallel strategy is based on a subdomain-by-subdomain approach, and uses the MPI and OpenMP standards in a hybrid parallel scheme. compressed data structures are used to store the matrix coefficients.

关键词： compressed data structures finite volume method message passing interface parallel computing slightly compressible reactive flows

来源：评论

学校读者我要写书评

暂无评论

Compressing and Querying Integer Dictionaries Under Linearities and Repetitions

引用

IEEE ACCESS 2022年 10卷 118831-118848页

作者： Ferragina, Paolo Manzini, Giovanni Vinciguerra, Giorgio Univ Pisa Dept Comp Sci I-56127 Pisa Italy

We revisit the fundamental problem of compressing an integer dictionary that supports efficient ${\mathsf {rank}}$ and ${\mathsf {select}}$ operations by exploiting simultaneously two kinds of regularities arising in real data: repetitiveness and approximate linearity. We attack this problem by proposing two novel compressed indexing approaches that extend the classic Lempel-Ziv compression scheme and the more recent block tree data structure with new algorithms and data structures that allow them to also capture regularities in terms of the approximate linearity in the data. Finally, we corroborate these theoretical results with a wide set of experiments on real and synthetic datasets, which allow us to show that our approaches achieve new interesting space-time trade-offs that characterise them as more robust in most practical scenarios compared to the known data structures that exploit only one of the two regularities.

关键词： compressed data structures data compression entropy

来源：评论

学校读者我要写书评

暂无评论

Longest Common Prefix Arrays for Succinct k-Spectra 1

引用

30th International Symposium on String Processing and Information Retrieval (SPIRE) / 18th Workshop on Compression, Text, and Algorithms (WCTA)

作者： Alanko, Jarno N. Biagi, Elena Puglisi, Simon J. Univ Helsinki Dept Comp Sci HIIT Helsinki Finland

ISBN: (数字)9783031439803

ISBN: (纸本)9783031439797;9783031439803

The k-spectrum of a string is the set of all distinct substrings of length k occurring in the string. K-spectra have many applications in bioinformatics including pseudoalignment and genome assembly. The Spectral Burrows-Wheeler Transform (SBWT) has been recently introduced as an algorithmic tool to efficiently represent and query these objects. The longest common prefix (LCP) array for a k-spectrum is an array of length n that stores the length of the longest common prefix of adjacent k-mers as they occur in lexicographical order. The LCP array has at least two important applications, namely to accelerate pseudo-alignment algorithms using the SBWT and to allow simulation of variable-order de Bruijn graphs within the SBWT framework. In this paper we explore algorithms to compute the LCP array efficiently from the SBWT representation of the k-spectrum. Starting with a straightforward O(nk) time algorithm, we describe algorithms that are efficient in both theory and practice. We show that the LCP array can be computed in optimal O(n) time, where n is the length of the SBWT of the spectrum. In practical genomics scenarios, we show that this theoretically optimal algorithm is indeed practical, but is often outperformed on smaller values of k by an asymptotically suboptimal algorithm that interacts better with the CPU cache. Our algorithms share some features with both classical Burrows-Wheeler inversion algorithms and LCP array construction algorithms for suffix arrays. Our C++ implementations of these algorithms are available at https://***/jnalanko/kmer-lcs.

关键词： longest common prefix LCP longest common suffix k-mer string algorithms compressed data structures de Bruijn graph Burrows-Wheeler transform BWT

来源：评论

学校读者我要写书评

暂无评论

compressed String Dictionaries via data-Aware Subtrie Compaction 29th

Compressed String Dictionaries via Data-Aware Subtrie Compac...

引用

29th International Symposium on String Processing and Information Retrieval (SPIRE)

作者： Boffa, Antonio Ferragina, Paolo Vinciguerra, Giorgio Tosoni, Francesco Univ Pisa Dept Comp Sci Pisa Italy

ISBN: (纸本)9783031206429;9783031206436

String dictionaries are a core component of a plethora of applications, so it is not surprising that they have been widely and deeply investigated in the literature since the introduction of tries in the '60s. We introduce a new approach to trie compression, called compressed COllapsed Trie (CoCo-trie), that hinges upon a data-aware optimisation scheme that selects the best subtries to collapse based on a pool of succinct encoding schemes in order to minimise the overall space occupancy. CoCo-trie supports not only the classic lookup query but also the more sophisticated rank operation, formulated over a sorted set of strings. We corroborate our theoretical achievements with a large set of experiments over datasets originating from a variety of sources, e.g., URLs, DNA sequences, and databases. We show that our CoCo-trie provides improved space-time trade-offs on all those datasets when compared against well-established and highly-engineered trie-based string dictionaries.

关键词： String dictionaries Tries compressed data structures

来源：评论

学校读者我要写书评

暂无评论

The membership problem for subsemigroups of GL2(Z) is NP-complete

引用

INFORMATION AND COMPUTATION 2024年 296卷

作者： Bell, Paul C. Hirvensalo, Mika Potapov, Igor Keele Univ Sch Comp Sci & Math Keele ST5 5BG Staffs England Univ Turku Dept Math & Stat Turku 20014 Finland Univ Liverpool Dept Comp Sci Liverpool L69 3BX England

We show that the problem of determining if the identity matrix belongs to a finitely generated semigroup of 2 x 2 matrices from the General Linear Group GL2(Z) is solvable in NP. We extend this to prove that the membership problem is decidable in NP for GL2(Z) and for any arbitrary regular expression over matrices from the Special Linear group SL2(Z). We show that determining if a given finite set of matrices from SL2(Z) or the modular group PSL2(Z) generates a group or a free semigroup are decidable in NP. Previous algorithms, shown in 2005 by Choffrut and Karhumaki, were in EXPSPACE. Our algorithm is based on new techniques allowing us to operate on compressed word representations of matrices without explicit expansions. When combined with known NPhard lower bounds, this proves that the membership problem over GL2(Z) is NP -complete, and the group problem and the non -freeness problem in SL2(Z) are NP -complete. 1 (c) 2023 The Authors. Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： General linear group Special linear group Nonnumerical algorithms NP-completeness Matrix semigroups compressed data structures Computational group theory

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：