algorithm - 与特定数字组的莱文斯坦距离

Question

我的输入是三个数字 - 一个数字和一个范围s的开头b和结尾。任务是找到range 和所有数字之间的最小 Levenstein 距离。不需要找到最小化距离的数字，最小距离就足够了。e0 <= s,b,e <= 10^1000s[b, e]

显然我必须将数字读取为字符串，因为标准 C++ 类型无法处理如此大的数字。为可能很大范围内的每个数字计算 Levenstein 距离是不可行的。

有任何想法吗？

score 3 · Accepted Answer

[编辑 10/8/2013：DP 算法中考虑的某些情况实际上根本不需要考虑，尽管考虑它们不会导致错误:)]

在下文中，我描述了一个需要 O(N^2) 时间的算法，其中 N 是b、e 或 s 中的最大位数。由于所有这些数字都限制为 1000 位，这意味着最多有几百万个基本操作，这在任何现代 CPU 上都需要几毫秒。

假设 s 有 n 个数字。在下文中，“之间”是指“包容”；如果我的意思是“排除它的端点”，我会说“严格介于”。指数以 1 为基础。x[i] 表示 x 的第 i 个数字，例如 x[1] 是它的第一个数字。

拆分问题

首先要做的是将问题分解为一系列子问题，其中每个 b 和 e 具有相同的位数。假设 e 的位数比 s 多 k >= 0：将问题分解为 k+1 个子问题。例如，如果 b = 5 和 e = 14032，则创建以下子问题：

b = 5, e = 9
b = 10，e = 99
b = 100，e = 999
b = 1000，e = 9999
b = 10000，e = 14032

我们可以解决这些子问题中的每一个，并采取最小解决方案。

简单的案例：中间

简单的案例是中间的案例。每当 e 的位数比 b 多 k >= 1 时，就会有 k-1 个子问题（例如上面的 3 个），其中 b 是 10 的幂，e 是 10 的下一个幂，减 1。假设 b 是 10^m . 请注意，选择 1 和 9 之间的任何数字，然后选择 0 和 9 之间的任何 m 个数字，会产生一个范围为 b <= x <= e 的数字 x。此外，在这个范围内没有数字不能以这种方式产生。s（或者实际上任何给定的长度为 n 的不以 0 开头的数字字符串）和任何之间的最小 Levenshtein 距离10^m <= x <= 10^(m+1)-1 范围内的数字 x 必然是 abs(m+1-n)，因为如果 m+1 >= n 可以简单地选择前 n 位x 与 s 中的相同，并删除余数，如果 m+1 < n 则选择第一个 m+1 与 s 中的相同并插入余数。

事实上，我们可以在单个恒定时间操作中处理所有这些子问题：如果最小的“简单”子问题有 b = 10^m，而最大的“简单”子问题有 b = 10^u，那么最小的 Levenshtein 距离如果 n < m，则为 mn，如果 n > u，则为 nu，否则为 0。

困难的情况：结束

困难的情况是 b 和 e 不限于分别具有 b = 10^m 和 e = 10^(m+1)-1 的形式。任何主问题最多可以产生两个这样的子问题：两个“结束”（由 b 和 e 具有不同位数的主问题产生，例如顶部的示例）或单个子问题（即主问题）问题本身，根本不需要细分，因为 b 和 e 已经有相同的位数）。请注意，由于前面对问题的拆分，我们可以假设子问题的 b 和 e 具有相同的位数，我们将其称为 m。

超级Levenshtein！

我们要做的是设计 Levenshtein DP 矩阵的变体，它计算给定数字字符串 (s) 与范围 b <= x <= e 内的任何数字 x 之间的最小 Levenshtein 距离。尽管增加了“力量”，但该算法仍将在 O(n^2) 时间内运行 :)

首先，观察如果 b 和 e 具有相同的位数并且 b != e，那么它们一定是由一些数字 q >= 0 的左侧相同数字组成，然后是一个更大的数字在 e 中比在 b 中。现在考虑以下生成随机数字字符串 x 的过程：

将 x 设置为 b 的前 q 个数字。
将 b[i] 和 e[i] 之间随机选择的数字 d 附加到 x。
如果 d == b[i]，我们“拥抱”下界：
- 对于从 q+1 到 m 的 i：
  - 如果 b[i] == 9 则附加 b[i]。 [编辑 2013 年 10 月 8 日：实际上这不可能发生，因为我们选择了 q，因此 e[i] 将大于 b[i]，并且没有大于 9 的数字！]
  - 否则，掷硬币：
    - 头：附加 b[i]。
    - 尾部：附加一个随机选择的数字 d > b[i]，然后转到 6。
- 停止。
否则，如果 d == e[i]，我们“拥抱”上限：
- 对于从 q+1 到 m 的 i：
  - 如果 e[i] == 0 则附加 e[i]。 [编辑 10/8/2013：实际上这不可能发生，因为我们选择了 q，因此 b[i] 将小于 e[i]，并且没有小于 0 的数字！]
  - 否则，掷硬币：
    - 头：附加 e[i]。
    - 尾部：附加一个随机选择的数字 d < e[i]，然后转到 6。
- 停止。
否则（如果 d 严格介于 b[i] 和 e[i] 之间），则跳至步骤 6。
继续将随机选择的数字附加到 x 直到它有 m 个数字。

基本思想是，在包含所有必须包含的数字之后，您可以“拥抱”下界的数字，只要您愿意，或者只要您愿意，就可以“拥抱”上限的数字，并且尽快当你决定停止“拥抱”时，你可以选择任何你想要的数字。对于合适的随机选择，此过程将生成所有且仅生成满足 b <= x <= e 的数字 x。

在长度分别为 n 和 m 的两个字符串 s 和 x 之间的“通常”Levenshtein 距离计算中，我们有一个从 (0, 0) 到 (n, m) 的矩形网格，并且在每个网格点 (i, j)我们记录前缀 s[1..i] 和前缀 x[1..j] 之间的 Levenshtein 距离。(i, j) 处的分数是使用自下而上的动态规划从 (i-1, j)、(i, j-1) 和 (i-1, j-1) 处的分数计算得出的。为了适应这一点，将 x 视为一组可能的字符串之一（特别是对应于 b 和 e 之间的数字的数字字符串）而不是特定的给定字符串，我们需要做的不是为每个网格点记录一个而是两个分数：一个用于我们假设数字位于位置 j 被选择拥抱下限，而我们假设它被选择拥抱上限。第三种可能性（上面的第 5 步）实际上不需要 DP 矩阵中的空间，因为我们可以立即计算出整个其余输入字符串的最小 Levenshtein 距离，这与我们为“简单“第一节中的子问题。

超级Levenshtein DP递归

调用网格点 (i, j) v(i, j) 处的总体最低分数。如果字符 a 和 b 不同，则令 diff(a, b) = 1，否则为 0。如果字符 a 在 b..c 范围内，则 inrange(a, b..c) 为 1，否则为 0。计算如下：

# The best Lev distance overall between s[1..i] and x[1..j]
v(i, j) = min(hb(i, j), he(i, j))

# The best Lev distance between s[1..i] and x[1..j] obtainable by
# continuing to hug the lower bound
hb(i, j) = min(hb(i-1, j)+1, hb(i, j-1)+1, hb(i-1, j-1)+diff(s[i], b[j]))

# The best Lev distance between s[1..i] and x[1..j] obtainable by
# continuing to hug the upper bound
he(i, j) = min(he(i-1, j)+1, he(i, j-1)+1, he(i-1, j-1)+diff(s[i], e[j]))

在计算 v(i, j) 的时间点，我们还将计算由于选择“停止拥抱”而产生的 Levenshtein 距离，即通过选择严格介于 b[j] 和 e[j 之间的数字] (if j == q) 或 (if j != q) 要么高于 b[j] 要么低于 e[j]，然后自由选择数字以使 x 的后缀与 s 的后缀尽可能匹配：

# The best Lev distance possible between the ENTIRE STRINGS s and x, given that
# we choose to stop hugging at the jth digit of x, and have optimally aligned
# the first i digits of s to these j digits
sh(i, j) = if j >= q then shc(i, j)+abs(n-i-m+j)
           else infinity

shc(i, j) = if j == q then
              min(hb(i, j-1)+1, hb(i-1, j-1)+inrange(s[i], (b[j]+1)..(e[j]-1)))
            else
              min(hb(i, j-1)+1, hb(i-1, j-1)+inrange(s[i], (b[j]+1)..9),
                  he(i, j-1)+1, he(i-1, j-1)+inrange(s[i], (0..(e[j]-1)))

shc(i, j) 的公式不需要考虑“向下”移动，因为此类移动不涉及 x 的任何数字选择。

对于所有 0 <= i <= n 和 0 <= j <= m，整体最小 Levenshtein 距离是 v(n, m) 和 sh(i, j) 的最小值。

复杂

取 N 为 s、b 或 e 中的最大位数。原始问题可以在线性时间内最多拆分为一组简单问题，这些问题总共需要 O(1) 时间来解决，以及 2 个困难子问题，每个问题需要 O(N^2) 时间来解决，使用超级 Levenshtein 算法，所以总的来说这个问题可以在 O(N^2) 时间内解决，即时间与位数的平方成正比。

score 0 · Accepted Answer

加速计算的第一个想法（如果|e-b|不是太大也可以）：

问题：当我们与比较s时，Levestein 距离可以改变多少？nn+1
答：不要太多！

s = 12007让我们看看两个连续的动态规划表n

n = 12296

0 1 2 3 4 5 
1 0 1 2 3 4 
2 1 0 1 2 3 
3 2 1 1 2 3 
4 3 2 2 2 3 
5 4 3 3 3 3

和

n = 12297

0 1 2 3 4 5 
1 0 1 2 3 4 
2 1 0 1 2 3 
3 2 1 1 2 3 
4 3 2 2 2 3 
5 4 3 3 3 2

如您所见，只有最后一列发生变化，因为n和n+1具有相同的数字，除了最后一个。

s = 12001如果你有和的编辑距离的动态规划表n = 12296，你已经有了的表n = 12297，你只需要更新最后一列！

显然，如果n = 12299那时n+1 = 12300并且您需要更新上表的最后 3 列.. 但这每 100 次迭代只会发生一次。

一般来说，你必须

更新每次迭代的最后一列（因此，长度单元格）
也更新倒数第二个，每 10 次迭代一次
每 100 次迭代也更新倒数第三个

所以让L = length(s)和D = e-b。s首先计算和之间的编辑距离b。[b,e]然后，您可以在区间中的每个整数上循环找到最小 Levenstein 距离。它们有D，所以执行时间大约是：

在此处输入图像描述

现在自从

在此处输入图像描述

我们有一个算法

在此处输入图像描述

algorithm - 与特定数字组的莱文斯坦距离

2 回答 2

拆分问题

简单的案例：中间

困难的情况：结束

超级Levenshtein！

超级Levenshtein DP递归

复杂

Related

Reference