在LZ-end解析中对上限和线性空间查询进行上限和线性空间查询
1Johns Hopkins University.
概括
这项研究确定了LZ-End压缩的第一个非微不足道的上限,证明了其相对于Lempel-Ziv (LZ77) 压缩的效率. 一个新的数据结构还可以在LZ-End压缩数据上实现高效的随机访问和最长常见扩展查询.
科学领域:
- 数据压缩数据压缩
- 字符串算法 字符串算法
- 信息理论 信息理论
背景情况:
- 伦佩尔-齐夫 (LZ77) 是一个广泛使用的基于短语匹配的无损压缩算法.
- 作为LZ77的变体,LZ-End对短语的出现施加了更严格的条件,显示出实际的希望.
- 之前还不知道一个理论上限,将LZ-End压缩尺寸与LZ77尺寸联系起来.
研究的目的:
- 在LZ77压缩方面建立一个可证明的LZ-End压缩的上限.
- 为查询LZ-End压缩数据开发高效的数据结构.
- 探索LZ-End变种和其他压缩措施的极限.
主要方法:
- 数学证明,推导出 LZ-End 和 LZ77 段落中的短语数量之间的关系.
- 开发一种用于随机访问和最长常见扩展 (LCE) 查询的新型数据结构.
- 对LZ-End变体和替代压缩指标的分析.
主要成果:
- 证明了一个非微不足道的上限:LZ-End短语的数量上限为LZ77短语的数量.
- 引入了线性大小的数据结构,支持随机访问查询.
- 这些技术可以在LZ-End压缩数据上进行高效的LCE查询.
结论:
- 由于已建立的理论界限,LZ-End被列为最强大的字典压缩机之一.
- 新的数据结构为LZ-End压缩文本提供了高效的查询功能,克服了以前的限制.
- 这些发现促进了对LZ-End压缩及其在压缩数据结构中的应用的理解.
更多相关视频
08:32Examining Online Syntactic Processing of Spoken Complex Sentences in Chinese Using Dual-Modal Interference Tasks
Published on: September 5, 2019
5.6K
09:27Using Eye Movements Recorded in the Visual World Paradigm to Explore the Online Processing of Spoken Language
Published on: October 13, 2018
10.0K
相关概念视频
Hybridization of Atomic Orbitals I
47.0K
The mathematical expression known as the wave function, ψ, contains information about each orbital and the wavelike properties of electrons in an isolated atom. When atoms are bound together in a molecule, the wave functions combine to produce new mathematical descriptions that have different shapes. This process of combining the wave functions for atomic orbitals is called hybridization and is mathematically accomplished by the linear combination of atomic orbitals. The new orbitals that...
47.0K
¹H NMR: Long-Range Coupling
1.7K
The coupling interactions of nuclei across four or more bonds are usually weak, with J values less than 1 Hz. While these are usually not observed in spectra, the presence of multiple bonds along the coupling pathway can result in observable long-range coupling.
In alkenes, spin information is communicated via σ–π overlap, as seen in allylic (four-bond) and homoallylic (five-bond) couplings. These coupling interactions are stronger when the σ bond is parallel to the alkene...
In alkenes, spin information is communicated via σ–π overlap, as seen in allylic (four-bond) and homoallylic (five-bond) couplings. These coupling interactions are stronger when the σ bond is parallel to the alkene...
1.7K
Lumber
110
Lumber is derived from logs which are harvested, debarked, and processed into long pieces with a rectangular cross-section. The transformation of logs into lumber involves multiple steps, beginning with an automated saw that slices the log into slabs. These slabs are then transported via a conveyor belt to smaller saws, where they are cut into square-edged pieces of specific widths.
Initially, the surfaces of these lumber pieces are rough, and their dimensions may vary slightly from one end to...
Initially, the surfaces of these lumber pieces are rough, and their dimensions may vary slightly from one end to...
110
VSEPR Theory
9.4K
Valence shell electron-pair repulsion theory (VSEPR theory) enables us to predict the molecular structure around a central atom from an examination of the number of bonds and lone electron pairs in its Lewis structure. The VSEPR model assumes that electron pairs in the valence shell of a central atom will adopt an arrangement that minimizes repulsions between these electron pairs by maximizing the distance between them. The electrons in the valence shell of a central atom form either bonding...
9.4K
Mass Spectrometry: Long-Chain Alkane Fragmentation
1.6K
The molecular ions of linear alkanes prefer to fragment at the carbon-carbon bond away from the end of the chain since the cleavage of an inner bond creates a stable carbocation and a stable radical. Consequently, the mass signals of linear alkanes feature intense peaks in the middle of the mass-to-charge ratio plot with weaker peaks on either end. The fragmentation of each carbon-carbon bond with the release of a methyl group in each splitting leads to prominent peaks in the mass spectra...
1.6K
VSEPR Theory and the Effect of Lone Pairs
42.2K
Effect of Lone Pairs of Electrons on Molecule Geometry
42.2K
