查看“WikiEdge:ArXiv-2409.02852v1/methods”的源代码

<div style="float: right;">[{{fullurl:WikiEdge:ArXiv-2409.02852v1/methods|action=edit}} 编辑]</div>
这篇论文的工作部分详细介绍了如何开发和评估 [[k-最小值草图]]（KMV）的压缩算法。以下是这部分的主要内容：
# '''压缩算法理论基础'''：
#* 论文首先提出了基于对数据集条目进行哈希处理并存储生成的 k 个最小哈希键的 KMV 数据草图算法。作者展示了基于对键进行排序和编码连续差值的压缩方法，可以在期望存储节省中为每个键提供 O(log n) 位，其中 n 是数据集中唯一值的数量。
# '''压缩算法的最优性证明'''：
#* 论文证明了对于任何形式的压缩，k 个最小值的 n 个随机值的 O(log n) 期望位保存是最优的，并展示了所提出的编码方法是编码 KMV 草图的近最优方法。
# '''实际压缩方法的实现'''：
#* 作者提出了一种实用的压缩方法，展示了其计算效率，并证明了在实践中其平均节省量接近基于熵的理论最小值的 95%。
# '''压缩方法的验证'''：
#* 论文通过使用真实和合成数据验证了所提出方法的性能，证明了其优于现成的压缩方法，并且是实用的。
# '''压缩算法的实验评估'''：
#* 通过实验，作者展示了压缩算法在不同数据集上的性能，包括与通用压缩算法（如 [[zlib]] 和 [[bzip2]]）的比较，以及在不同输入基数下的压缩比率和序列化时间。
# '''熵的估计和理论分析'''：
#* 论文进一步发展了熵的界限，证明了所提出的压缩方法是近最优的。包括对连续差值之间分布的熵的估计，以及对随机样本中最小 k 个元素的熵的估计。