从LZ77解析器中快速和空间高效地构建AVL语法
1Department of Computer Science, Johns Hopkins University, Baltimore, MD, USA.
概括
我们介绍了一种新的技术,用于从LZ77解析器构建更小,更实用的AVL语法. 这种方法显著减少了语法大小和内存使用量,使得数据结构的创建速度更快.
科学领域:
- 字符串压缩算法 字符串压缩算法
- 数据结构优化数据结构优化
- 理论计算机科学理论计算机科学
背景情况:
- 语法压缩,包括直线语法 (SLG),提供灵活的字符串表示.
- 一种SLG的AVL语法具有理论上的优势,但由于大小而被认为是不切实际的.
- 目前用于AVL语法构建的现有方法是计算密集的,需要大量内存.
研究的目的:
- 开发一种新的,高效的算法,用于从LZ77解析器构建小型AVL语法.
- 通过改进大小和内存效率来证明AVL语法的实用性.
- 为了更快地构建压缩数据结构,例如运行长度Burrows-Wheeler变换 (RLBWT).
主要方法:
- 从LZ77或LZ77-like解析器快速构建AVL语法的一种新算法.
- 与现有方法 (原始AVL构建,Re-Pair) 相比,对语法大小和峰值RAM使用的比较分析.
- 与近期近似LZ77解析的进展进行整合,以进一步优化.
主要成果:
- 新的算法产生了至少比原始结构小五倍的AVL语法.
- 语法大小与实用的Re-Pair压缩机相比,通常在两倍之内.
- 该方法实现了低峰RAM使用量,有可能在更短的时间和内存中构建RLBWT.
结论:
- 在字符串压缩和数据结构构建方面,AVL语法令人惊地实用.
- 开发的技术克服了以前的大小和效率的限制.
- 这项工作为更快,更有效的内存压缩数据结构铺平了道路.
相关概念视频
Construction of Root Locus
127
The construction of a root locus involves several key steps to analyze and visualize the behavior of a system's poles with varying gain. The number of branches in the root locus equals the number of closed-loop poles and is symmetrical about the real axis.
For positive gain values, the root locus exists on the real axis to the left of an odd number of finite open-loop poles or zeros. The root locus starts at the open-loop poles and traces the paths of the closed-loop poles as the gain...
For positive gain values, the root locus exists on the real axis to the left of an odd number of finite open-loop poles or zeros. The root locus starts at the open-loop poles and traces the paths of the closed-loop poles as the gain...
127
The Aufbau Principle and Hund's Rule
49.5K
To determine the electron configuration for any particular atom, we can build the structures in the order of atomic numbers. Beginning with hydrogen, and continuing across the periods of the periodic table, we add one proton at a time to the nucleus and one electron to the proper subshell until we have described the electron configurations of all the elements. This procedure is called the aufbau principle, from the German word aufbau (“to build up”). Each added electron occupies the...
49.5K
SFG Algebra
121
In Signal Flow Graph (SFG) algebra, the value a node represents is determined by the sum of all signals entering that node. This summed value is then transmitted through every branch leaving the node, making the SFG a powerful tool for visualizing and analyzing control systems.
Each node in an SFG corresponds to a variable, and the interactions between nodes are represented by branches with associated gains. When multiple branches lead into a node, the value at that node is the sum of the...
Each node in an SFG corresponds to a variable, and the interactions between nodes are represented by branches with associated gains. When multiple branches lead into a node, the value at that node is the sum of the...
121
Components of Language
293
Language, whether spoken, signed, or written, consists of specific components: lexicon and grammar. The lexicon is the vocabulary of a language, comprising its words. Grammar is the set of rules used to convey meaning through the lexicon. For example, English grammar adds “-ed” to most verbs to indicate past tense. Words are formed by combining phonemes, which are the basic sound units of a language. Different languages have different sets of phonemes (e.g., “ah” vs.
293
Maxam-Gilbert Sequencing
11.2K
In the same year as the discovery of the Sanger sequencing method, another group of scientists, Allan Maxam and Walter Gilbert, demonstrated their chemical-cleavage method for DNA sequencing. The Maxam-Gilbert method relies on using different chemicals that can cleave the DNA sequence at specific sites, the separation of resulting DNA fragments of variable size using electrophoresis, and deciphering the DNA sequence from the resulting gel bands.
Challenges of the Maxam-Gilbert Method
The...
Challenges of the Maxam-Gilbert Method
The...
11.2K
Language Development
378
Children master language quickly and with relative ease, supported by both biological predisposition and reinforcement. B. F. Skinner (1957) proposed that language is learned through reinforcement, while Noam Chomsky (1965) argued that language acquisition mechanisms are biologically determined.
The critical period for language acquisition suggests that the ability to acquire language is at its peak early in life. As people age, this proficiency decreases. Language development begins very...
The critical period for language acquisition suggests that the ability to acquire language is at its peak early in life. As people age, this proficiency decreases. Language development begins very...
378


