algorithm - Levenshtein与特定数字组的距离

Question

我的输入是三个数字-一个数字s以及以b为范围的开始e和结束0 <= s,b,e <= 10^1000。任务是找到s与范围[b, e]中所有数字之间的最小Levenstein距离。不必找到最小化距离的数字，最小距离就足够了。

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

有任何想法吗？

Answer 1

[编辑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比k多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（或实际上不是以0开头的任何给定的长度为n的数字字符串）与范围为10 ^ m <= x <= 10 ^（m + 1）-1的任何数字x之间的最小Levenshtein距离一定是abs（m + 1-n），因为如果m + 1> = n，则可以简单地选择x的前n个数字与s中的数字相同，然后删除其余部分，如果m + 1 < n然后选择第一个m + 1与s中的m + 1相同，然后插入剩余的m + 1。

实际上，我们可以在一个恒定时间操作中处理所有这些子问题：如果最小的“简单”子问题具有b = 10 ^ m，最大的“简单”子问题具有b = 10 ^ u，则之间的最小Levenshtein距离s，如果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]。 [EDIT 10/8/2013：实际上这不可能发生，因为我们选择q使得b [i]小于e [i]，并且没有任何数字小于0！]
否则，掷硬币：

标题：附加e [i]。
尾巴：附加一个随机选择的数字d

停止。

否则（如果d严格在b [i]和e [i]之间），则跳至步骤6。
继续在x后面附加随机选择的数字，直到它有m个数字为止。


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

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

Super-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之间的数字]（如果j == q）或（如果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中任何一个的最大位数。原始问题可以在线性时间内分解为最多1组简单问题，总共需要O（1）个时间来解决，还有2个硬子问题，使用Super-Levenshtein算法都需要O（N ^ 2）个时间来解决，因此总的来说，这个问题可以用O（N ^ 2）时间来解决，即与数字位数成正比的时间。