搜索的压缩方法总结

搜索的压缩是搜索中的常用技巧，能够使搜索更便于保存状态、查询状态。

本文递交已结束。

进制压缩法

我的黑白棋游戏二进制压缩的代码如下：

int binary_hash(char str[][]) {
    int ans=0;	
    REP(i,1,4) REP(j,1,4)
    	ans=(ans<<1)+str[i][j]-'0';	
    return ans;
}

二进制压缩适用于对于状态的每一个位置有且仅有两种可能值的情况，否则需要多进制的压缩方式。其支持 $\Theta(1)$ 的单位置查询、 $\Theta(n)$ 的压缩。

康托展开压缩法

康托展开的公式如下：

\begin{aligned} X&=\sum_{i=1}^na_i\prod_{j=1}^{i-1}j\\ &=a_n(n-1)!+a_{n-1}(n-2)!+...+a_1*0! \end{aligned}

其中， $a_i$ 表示的是表示原数的第i 位在当前未出现的元素中是排在第几个。

康拓展开求出的是一个序列在对应长度序列的全排列中由小到大的顺序。求解某一序列的康托序与通过康托序逆推排列都是可以完成的。但是康托展开的朴素复杂度为 $\Theta(n^2)$ ，用 $\log$ 的数据结构优化可以实现 $\Theta(n\log n)$ 但是实现过于复杂，逆康托展开的复杂度则更高，优化更为复杂。

哈希压缩法

还有另一种高效率的状压方法是哈希，它能够适用于各种类型的序列，例如字符串、矩阵，不受限于状态的位置及可能情况。但是无法做到通过散列值逆推出原序列，只能保证在大概率下每个序列有且仅有一个对应散列值。所以哈希更广泛应用于去重与互联网加密等环节中。哈希仍可能存在冲突即多个序列对应一个散列值的情况，但是发生错误的概率极低。无错哈希对内存的占用较高也不常用。

哈希的代码如下：

int hash(char s[]) {
    int len=strlen(s);
    int ans=0;
    REP(i,0,len-1)
        ans=(ans*base+s[i])%mod+prime;
    return ans;
}

朴素哈希的复杂度为 $\Theta(len)$ ，STLmap映射的复杂度要再乘上一个 $\log$ 的级别。

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。