变量对变量的哈夫曼编码:最佳和贪的方法
1School of Mathematical Sciences, Yangzhou University, 88 South Daxue Road, Yangzhou 225002, China.
Entropy (Basel, Switzerland)
|July 8, 2023
概括
这项研究引入了m-gram变量到变量编码,扩展了符号序列的Huffman编码. 一种近似的线性复杂度方法产生了接近最佳的结果,并且在某些数据中超过了DEFLATE/PPM.
科学领域:
- 信息理论 信息理论
- 计算机科学 计算机科学
- 数据压缩数据压缩
背景情况:
- 经典的哈夫曼编码仅限于单个符号.
- 符号序列 (m-grams) 的变量到变量编码是一种扩展.
研究的目的:
- 为了扩展哈夫曼编码的m-gram变量到变量编码.
- 为m-gram编码开发一个最佳的算法和一个高效的近似方法.
主要方法:
- 开发了一种确定m-gram频率的程序.
- 制定了一个具有O(mn2) 复杂度的最佳编码算法.
- 提出了一种基于贪的启发式的近似方法,具有线性复杂性.
主要成果:
- 最优算法的复杂度是O(mn2).
- 大致的方法实现了接近最佳的结果.
- 在具有稳定统计数据的数据上,近似方法的表现优于DEFLATE和PPM.
结论:
- 拟议的近似方法为m-gram编码提供了一个实际的解决方案.
- 这种方法对于具有可预测的统计性质的数据尤其有效.
更多相关视频
21:55Engineering and Evolution of Synthetic Adeno-Associated Virus AAV Gene Therapy Vectors via DNA Family Shuffling
Published on: April 2, 2012
28.6K
09:23Quantification of Information Encoded by Gene Expression Levels During Lifespan Modulation Under Broad-range Dietary Restriction in C. elegans
Published on: August 16, 2017
8.1K
相关概念视频
Heuristics
111
Heuristics are problem-solving strategies that use mental shortcuts to simplify decision-making. Unlike algorithms, which must be followed precisely to achieve a correct result, heuristics offer a general problem-solving framework. They save time and energy but can sometimes lead to less rational decisions.
People often rely on heuristics when faced with an overload of information, limited time, low importance of the decision, limited information, or when a heuristic readily comes to mind. For...
People often rely on heuristics when faced with an overload of information, limited time, low importance of the decision, limited information, or when a heuristic readily comes to mind. For...
111
Statically Indeterminate Problem Solving
455
Statically indeterminate problems are those where statics alone can not determine the internal forces or reactions. Consider a structure comprising two cylindrical rods made of steel and brass. These rods are joined at point B and restrained by rigid supports at points A and C. Now, the reactions at points A and C and the deflection at point B are to be determined. This rod structure is classified as statically indeterminate as the structure has more supports than are necessary for maintaining...
455
Routh-Hurwitz Criterion I
289
Consider an electrical power grid, where stability is essential to prevent blackouts. The Routh-Hurwitz criterion is a valuable tool for assessing system stability under varying load conditions or faults. By analyzing the closed-loop transfer function, the Routh-Hurwitz criterion helps determine whether the system remains stable.
To apply the Routh-Hurwitz criterion, a Routh table is constructed. The table's rows are labeled with powers of the complex frequency variable s, starting from the...
To apply the Routh-Hurwitz criterion, a Routh table is constructed. The table's rows are labeled with powers of the complex frequency variable s, starting from the...
289
Reducing Line Loss
174
In a three-phase circuit, line loss is an indicator of energy dissipated as heat due to the resistance of transmission lines. To address this, incorporating transformers into the system—a step-up transformer at the source and a step-down transformer at the load—is a strategic solution. Two three-phase transformers are introduced to improve this.
With a step-up transformer at the source, the voltage is increased, thereby reducing the current in the transmission lines since power loss...
With a step-up transformer at the source, the voltage is increased, thereby reducing the current in the transmission lines since power loss...
174
Maxam-Gilbert Sequencing
11.3K
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.3K
Extraction: Partition and Distribution Coefficients
2.6K
The distribution law or Nernst's distribution law is the law that governs the distribution of a solute between two immiscible solvents. This law, also known as the partition law, states that if a solute is added to the mixture of two immiscible solvents at a constant temperature, the solute is distributed between the two solvents in such a way that the ratio of solute concentrations in the solvents remains constant at equilibrium.
For extracting a solute from an aqueous phase into an...
For extracting a solute from an aqueous phase into an...
2.6K
