论文标题
使用范围最小查询加速两个数量级的AIFV- $ 2 $动态程序
Speeding up the AIFV-$2$ dynamic programs by two orders of magnitude using Range Minimum Queries
论文作者
论文摘要
AIFV- $ 2 $代码是一种用于为无内存源构建无损代码的新方法，该代码可提供比Huffman代码更好的最差案例冗余。他们通过使用两个代码树而不是一个代码树来做到这一点，并且还允许解码过程中一些有限的延迟。构建AIFV代码的已知算法是迭代的。在每个步骤中，他们都用“更好”的一对替换当前的代码树对。执行此替换的目前最新技术是一对动态编程（DP）算法，使用$ O（n^5）$时间填写两个表，每个表格$ O（n^3）$（其中$ n $是源中不同字符的数量）。 本文介绍了如何减少两个数量级填充DP表的时间，降低到$ O（n^3）$。它通过引入一种允许将$θ（n^3）$ - 空间表分隔为$θ（n）$组的分组技术，每个大小$ o（n^2）$，然后使用二维范围最小的查询（rmq）来填充该集团的桌子中的$ O（n^2）$时间。这种RMQ加速技术似乎是新的，并且可能具有独立的兴趣。
AIFV-$2$ codes are a new method for constructing lossless codes for memoryless sources that provide better worst-case redundancy than Huffman codes. They do this by using two code trees instead of one and also allowing some bounded delay in the decoding process. Known algorithms for constructing AIFV-code are iterative; at each step they replace the current code tree pair with a "better" one. The current state of the art for performing this replacement is a pair of Dynamic Programming (DP) algorithms that use $O(n^5)$ time to fill in two tables, each of size $O(n^3)$ (where $n$ is the number of different characters in the source). This paper describes how to reduce the time for filling in the DP tables by two orders of magnitude, down to $O(n^3)$. It does this by introducing a grouping technique that permits separating the $Θ(n^3)$-space tables into $Θ(n)$ groups, each of size $O(n^2)$, and then using Two-Dimensional Range-Minimum Queries (RMQs) to fill in that group's table entries in $O(n^2)$ time. This RMQ speedup technique seems to be new and might be of independent interest.
