通过MAX-SAT计算NP难度的重复性度量

《ACM Transactions on Algorithms》：Computing NP-hard Repetitiveness Measures via MAX-SAT

字符串吸引子、双向宏方案和直线程序的精确计算存在NP难解问题，本文提出基于MAX-SAT的数学模型实现首次非平凡精确求解，实验表明该方法对百万级文本的字符串吸引子计算有效，对直线程序和双向宏方案的优化性能显著。

　　

摘要

重复性度量能够揭示数据集的深刻特征，并促使人们开发出在压缩空间中运行的压缩数据结构和算法。遗憾的是，其中一些度量的计算属于NP难问题，即使对于规模较小的数据集，直接计算也是不可行的。三种这样的度量包括：字符串吸引子的最小大小、双向宏方案的最小大小以及直线程序的最小大小。尽管存在大量用于启发式计算这些度量近似值的实现方法，但对这些度量的精确计算却鲜有关注。在本文中，我们提出了MAX-SAT公式，为精确计算字符串吸引子、双向宏方案和直线程序的最小大小提供了首个非平凡的实现方法。计算实验表明，我们的实现方法能够处理长度达到几百的直线程序和双向宏方案文本，以及长度超过一百万的字符串吸引子文本。