串哈希

Algorithm

June 26, 2023

概念基础

字符串哈希是从 Rabin-Karp 算法 (1987) 衍生出来的，用于解决基于字符串子串比较问题的一种思路。

RK 算法使用了一个简单的多项式滚动哈希算法¹，对于任意子串 $\text{substr}[l..r]$ ，它的哈希值可以由两端对应的前缀字符串 $\text{substr}[0..l-1]$ 和 $\text{substr}[0..r]$ 的哈希值计算得到，也就是说如果提前计算了字符串所有前缀的哈希，那么它的任意子串的哈希都可以在常量时间计算得到。

同时作为滚动哈希，每个前缀 $\text{substr}[0..i]$ 的哈希也可以由子前缀 $\text{substr}[0..i-1]$ 直接计算得出，这样就可以在 $O(n)$ 的时间计算出所有前缀的哈希，并用 $O(1)$ 的时间做子串的比较。

下面介绍这个哈希算法：

哈希算法²³

对于串 $s$

\[\begin{array}{l} \text{hash}(s) &= s[0]\cdot p^0 + s[1] \cdot p^1 + s[2] \cdot p^2 + ... + s[n-1] \cdot p^{n-1} \pmod m \\ &= \displaystyle\sum_{i=0}^{n-1} s[i] \cdot p^i \pmod m \end{array}\]

其中， $n$ 为串的长度，$m$ 和 $p$ 是根据需要挑选的一个正整数。

一般可以令 $p$ 为字母表（alphabet）大小的质数，比如对于只包含小写字母的串，$p=31$；对于大小写字母，$p=53$ 。

$m$ 作为模除运算的除数，需要是一个很大的整数，因为两个随机字符串发生哈希碰撞的概率 $\approx \frac{1}{m}$，可以取 $2^{64}$ ，这样做的好处是用 u64 保存数值时不需要显式地进行取模运算，等待数值自然溢出即可，但这样必然存在方法，用来构造无关于 $p$ 的产生哈希碰撞的字符串，更好的方法是选取一个大素数，比如 $10^9 + 9$ ，这个大小的素数有一个好处，就是确保 u64 类型足以容纳计算结果而不会溢出⁴

$s[i]$ 是在位置 $i$ 处字符的值，这个值是字符在字母表里的排名，而一般空串的哈希值为 $0$ ，因此字符的排名最好从 $1$ 开始，来避免字母表里最小字符与与空串的值相同。

子串的哈希值则有如下的关系：

\[p^{l}\cdot \text{hash}(s[l..r]) \pmod m =\text{hash}(s[0..r]) - \text{hash}(s[0..l-1]) \pmod m\]

这样需要再额外计算一步 $p^l$ 的模乘逆元，可以通过拓展欧几里得算法，以 $p^l$ 和 $m$ 为参数直接求解模乘逆元。

可以通过换一下多项式滚动哈希的计算方向，来避免求解模乘逆元这一步操作。

反向计算

可以认为串 $s$ 的哈希是一个由串上每个字符组成的 $p$ 进制的数字，前面的计算方法是小端序（LSB，Least Significant Bit)

而我们更改为大端序（MSB，Most Significant Bit）：

\[\begin{array}{l} \text{hash}(s) &= s[0]\cdot p^{n-1} + s[1] \cdot p^{n-2} + ... + s[n-1] \cdot p^{0} \pmod m \\ &= \displaystyle\sum_{i=0}^{n-1} s[i] \cdot p^{n-1-i} \pmod m \end{array}\]

左端点前缀哈希：

\[\text{hash}(s[0..l-1]) = s[0]\cdot p^{l-1} + \dots+ s[l-1]\cdot p^0 \pmod m\]

右端点前缀哈希：

\[\begin{array}{l} \text{hash}(s[0..r]) &= s[0]\cdot p^{r} + \dots + s[l-1]\cdot p^{r-(l-1)} + s[l]\cdot p^{r-l} +\dots+ s[r]\cdot p^0 \pmod m\\ &= s[0]\cdot p^{r} + \dots + s[l-1]\cdot p^{r-(l-1)} + \text{hash}(s[l..r]) \pmod m\\ &= \text{hash}(s[0..l-1])\cdot p^{r-(l-1)} + \text{hash}(s[l..r]) \pmod m \end{array}\]

于是子串哈希与前缀哈希就有如下的关系：

\[\text{hash}(s[l..r]) = \text{hash}(s[0..r]) - \text{hash}(s[0..l-1]) \cdot p^{r-(l-1)} \pmod m\]

对子串哈希的查询总让人想起树状数组（BIT）里面用前缀来计算区间的类似操作

当然实际上也可以用后缀哈希来计算小端哈希串，这和大端哈希串与前缀哈希是等价的

哈希碰撞

用哈希来做串的映射时总要考虑串不同但哈希值相同的情况，在广泛地基于概率的算法与数据结构⁵中习惯用假阳性（False Positive）来表示这种情况。

大量比较

在考虑到串的比较次数较多时，比如 $10^6$ 个不同字符串的两两比较，会有 $10^{6+6} = 10^{12}$ 个情况，这时 $10^9$ 的碰撞空间就不够用了，这时总是会发生碰撞。

这时就必须扩大碰撞空间，而单一地增大 $m$ ，然后对应地把计算的数据类型从 u64 提升到 u128 乃至专门的 Big Int 类型，实在不怎么可取，不如独立计算几组哈希值，采用不同的 $p$ 或者 $m$ ，比如两组，就可以让碰撞空间扩大到 $(10^9)^2=10^{18}$ 从而满足前面的情况，当然还可以有更多的组数来得到更大的哈希空间。

绝对正确

如果对判断的结果要求绝对正确，可以在哈希判等的情况下再用原始的文本串进行比较。

实现

将用 Rust 来实现字符串哈希，并在此基础上实现 Rabin-Karp 算法。

字母表

在计算串哈希的时候，首先要考虑串的构成字符的字母表，这涉及字符值的计算与 $p$ 的选取。

于是我们可以把字母表抽象出来，规定它应该有：

查询给定字符的排名，rank ，排名用作计算哈希时字符的值，从 $1$ 开始；
给出字母表的大小，len；
给出字母表大小对应的 $p$ ，prime

pub trait AlphaBet {
    /// None for char out of scope of the alphabet
    fn rank(&self, c: char) -> Option<u64>;
    fn len(&self) -> usize;
    fn prime(&self) -> u64;
}

定义几个字母表实例作为示范：

不得不称赞 Rust 原生的模式匹配语法让代码干净简洁许多！

数字字母

pub struct DigitsLetters;

impl AlphaBet for DigitsLetters {
    fn rank(&self, c: char) -> Option<u64> {
        Some(match c {
            '0'..='9' => c as u64 - '0' as u64 + 1,
            'A'..='Z' => c as u64 - 'A' as u64 + 1 + 10,
            'a'..='z' => c as u64 - 'a' as u64 + 1 + 10 + 26,
            _ => return None
        })
    }

    fn len(&self) -> usize {
        26 * 2 + 10
    }

    fn prime(&self) -> u64 {
        79 // 0x4F
    }
}

常见中文

/// Common CJK + CJK Symbols and Punctuation + ASCII
pub struct CommonChinese;

impl AlphaBet for CommonChinese {
    fn rank(&self, c: char) -> Option<u64> {
        let c = c as u64;

        Some(match c {
            0..=127 => c + 1,  // ASCII
            0x3000..=0x303F => c - 0x3000 + 1 + 128,  // CJK Symbols and Punctuation
            0x4E00..=0x9FFF => c - 0x4E00 + 1 + 128 + 0x40,  // Common CJK
            _ => return None,
        })
    }

    /// 21184
    fn len(&self) -> usize {
        (0x9FFF - 0x4E00 + 1) + (127 - 0 + 1) + (0x303F - 0x3000 + 1)
    }

    fn prime(&self) -> u64 {
        21187
    }
}

计算哈希

多组哈希

$p$ 与字母表的大小是绑定的，选择用一组不同的 $m$ 来独立计算多组哈希。

const M: [u64; 2] = [
    1_000_000_000 + 9,
    1_000_000_000 + 7
];


macro_rules! check_n {
    () => {
        if N == 0 || N > 2 {
            unimplemented!("N should be in [1, 2], however {N} found")
        }
    };
}

一次性计算

比如用在模式串的计算上

macro_rules! check_n {
    () => {
        if N == 0 || N > 2 {
            unimplemented!("N should be in [1, 2], however {N} found")
        }
    };
}


pub fn rolling_hash<const N: usize>(
    s: &str,
    alphabet: &dyn AlphaBet,
) -> Result<[u64; N], ComputeRollingHashError> {
    check_n!();

    let mut nacc = [0; N];

    if s.is_empty() {
        return Ok(nacc);
    }

    let p = alphabet.prime();

    for c in s.chars() {
        let c = alphabet
            .rank(c)
            .ok_or(ComputeRollingHashError::CharOutOfScope(c))?;

        for n in 0..N {
            if nacc[n] == 0 {
                nacc[n] = c;
            }
            else {
                nacc[n] = (nacc[n] * p % M[n] + c) % M[n];
            }
        }
    }

    Ok(nacc)
}

前缀计算

比如用在文本串的计算上

/// [msb] polynomial rolling computing
#[repr(transparent)]
pub struct PrefixRollingHash<const N: usize = 1>
{
    nprefix: [Vec<u64>; N],
}

/// String Prefix (MSB) Plynomial Rolling Hash
impl<const N: usize> PrefixRollingHash<N> {
    pub fn new(
        s: &str,
        alphabet: &dyn AlphaBet,
    ) -> Result<Self, ComputeRollingHashError> {
        check_n!();

        // Create chars
        let mut chars = vec![];

        // Init chars
        for c in s.chars() {
            chars.push(
                alphabet
                    .rank(c)
                    .ok_or(ComputeRollingHashError::CharOutOfScope(c))?,
            );
        }

        // Create nprefix
        let mut nprefix: [Vec<u64>; N] = unsafe { zeroed() };
        let p = alphabet.prime();

        // Init nprefix
        for n in 0..N {
            let mut prefix = vec![0; chars.len()];

            if !chars.is_empty() {
                prefix[0] = chars[0];

                for i in 1..chars.len() {
                    prefix[i] = (prefix[i - 1] * p % M[n] + chars[i]) % M[n];
                }
            }

            nprefix[n] = prefix;
        }


        Ok(Self { nprefix })
    }

    // ...
}

子串查询

impl<const N: usize> PrefixRollingHash<N> {
    pub fn query<R: RangeBounds<usize>>(&self, range: R, npows: &[[u64; N]]) -> [u64; N] {
        let (l, r) = parse_range!(range, self.len());

        let mut res = [0; N];

        if l == 0 {
            for n in 0..N {
                res[n] = self.nprefix[n][r];
            }
        }
        else {
            for n in 0..N {
                // coefficent
                let coeff = npows[r - (l - 1)][n];

                let a = self.nprefix[n][r];
                let b = self.nprefix[n][l - 1]
                * coeff
                % M[n];

                res[n] = if a < b { M[n] - (b - a) } else { a - b };
            }
        };

        res
    }
}

应用

查询回文串

注解

注意区别于同作者的另一个更正式的多项式滚动哈希算法，Rabin fingerprint ，据说有一些 RK 算法的实现在内部使用了这个算法而不是原始提出的更简单的那一个。 ↩
https://cp-algorithms.com/string/string-hashing.html ↩
https://oi-wiki.org/string/hash/ ↩
$2^{64} \approx 2^4 \cdot (10^3)^6 = 16 \cdot 10^{18} $ ↩
比如前面Boyer-Moore算法里介绍过的 Bloom Filter ↩

串哈希