《统计学习方法》啃书手册｜字符串核函数动态规划的实现

位置：《统计学习方法》啃书手册 > 第7章 支持向量机 > 字符串核函数动态规划的实现

已知两个字符串 $s$ 和 $t$ 上的字符串核函数是基于映射 ${\varphi }_n$ 的特征空间中的内积，即字符串 $s$ 和 $t$ 中长度等于 $n$ 的所有子串组成的特征向量的余弦相似度。其计算公式如下：

k n ( s , t ) = ∑ u ∈ Σ n [ ϕ n ( s ) ] u [ ϕ n ( t ) ] u = ∑ u ∈ Σ n ∑ ( i , j ) : s ( i ) = t ( j ) = u λ l ( i ) λ l ( j )

kn​(s,t)​=u∈Σn∑​[ϕn​(s)]u​[ϕn​(t)]u​=u∈Σn∑​(i,j):s(i)=t(j)=u∑​λl(i)λl(j)​

其中 $\lambda$ 是衰减参数，$u$ 是相同子序列，$l(i)$ 为子序列在 $s$ 中的长度（最后 1 个字符的下标-第 1 个字符的下标+1），$l(j)$ 为子序列在 $t$ 中的长度。

观察上式，我们可以发现，每一个相同子串所提供的相似度，都是 ${\lambda }^{l(i)+l(j)}$，即衰减参数的两个子串的长度之和次方；于是有长度每增加 $1$，所提供的相似度都只需要乘以 $\lambda$ 即可。

于是，我们很自然地想到，可以用类似计数 DP 的方法，当前状态（$s1$ 的前 $i$ 个字符和 $s2$ 的前 $j$ 个字符），只需要记录所有长度为 $l$ 为相同子序列提供的相似度之和即可。当考虑下一个状态（例如 $s1$ 的前 $i+1$ 个字符和 $s2$ 的前 $j$ 个字符）时，只需要简单地将上一个状态乘以衰减因子 $\lambda$ 即可。需要注意的是，我们需要考虑可能存在的被重复计算的问题。

具体地，状态矩阵如下：

dp[l][i]][j]：$s1$ 的前 $i$ 个字符和 $s2$ 的前 $j$ 个字符中，所有长度为 $l$ 的相同子序列所提供的相似度的和。因为考虑到状态转移中，只会用到 $l$ 和 $l-1$，所以可以省略 $l$ 以节约空间。

状态转移方程如下（其中att为衰减因子）：

dp[l][i][j] = dp[l][i-1][j] * att + dp[l][i][j-1] * att + dp[l][i-1][j-1] * att * att（第 3 项是在处理被重复计算的问题）

在当前字符相同时，额外增加使用当前相同字符的情况：dp[l][i][j] += dp[l-1][i-1][j-1] * att * att；同时，当前子序列长度的核函数的结果由这部分累加即可。

【源码地址】

def count_kernel_function_for_string(s1, s2, length: int, att: float):
    """计算字串长度等于n的字符串核函数的值

    :param s1: 第1个字符串
    :param s2: 第2个字符串
    :param length: 需要查找的英文字符集长度
    :param att: 衰减参数
    :return: 字符串核函数的值
    """

    # 计算字符串长度
    n1, n2 = len(s1), len(s2)

    # 定义状态矩阵
    dp1 = [[1] * (n2 + 1) for _ in range(n1 + 1)]

    # 字符串的核函数的值的列表：ans[i] = 子串长度为(i+1)的字符串核函数的值
    ans = []

    # 依据子串长度进行状态转移：[1,n]
    for l in range(length):
        dp2 = [[0] * (n2 + 1) for _ in range(n1 + 1)]

        # 定义当前子串长度的核函数的值
        res = 0

        # 进行状态转移
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
                dp2[i][j] += dp2[i - 1][j] * att + dp2[i][j - 1] * att - dp2[i - 1][j - 1] * att * att
                if s1[i - 1] == s2[j - 1]:
                    dp2[i][j] += dp1[i - 1][j - 1] * att * att
                    res += dp1[i - 1][j - 1] * att * att  # 累加当前长度核函数的值

        dp1 = dp2
        ans.append(res)

    return ans[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

时间复杂度、空间复杂度分析：

• 时间复杂度：$O(N1\times N2\times Length)$；其中 $N1$ 为第 1 个字符串的长度，$N2$ 为第 2 个字符串的长度，$Length$ 为子串长度
• 空间复杂度：$O(N1\times N2)$