检查一个字符串是否包含与其他字符串的 Levenshtein 距离为 1 的子字符串

Question

我的问题是，我们希望用户输入这样的代码： 639195-EM-66-XA-53-WX在输入中的某处，因此结果可能如下所示：The code is 639195-EM-66-XA-53-WX, let me in。如果他们在代码中犯了一个小错误（编辑距离为 1），我们仍然希望匹配该字符串。例如The code is 739195-EM-66-XA-53-WX, let me in。（改为6代码7的第一个字母）

即使用户跳过破折号，算法也应该匹配，并且应该忽略小写/大写字母。这些要求很容易满足，因为我可以删除所有破折号并执行 to_uppercase。

有类似的算法吗？

生成与原始代码距离为 1 的所有字符串的计算成本很高。

我也在考虑使用类似 Levenshtein distance 的东西，但忽略用户在第二个字符串中添加的缺失字母，但这会允许代码中间出现错误的字母。

在用户输入中搜索代码似乎好一点，但仍然不是很干净。

Answer 1

我有一个解决方案的想法，也许这对你来说已经足够了：

正如您所说，首先删除破折号并将所有内容设为大写（或小写）：

句子：THE CODE IS 639195EM66XA53WX, LET ME IN

代码：639195EM66XA53WX

将代码拆分在中间（c1 和 c2），因为编辑距离为 1 意味着只能出现一个错误（插入、删除或替换单个字符），因此如果代码是，则 c1 或 c2 必须匹配出现在句子中，只有 1 个或更少的错误。在中间拆分，因为代码的两个子字符串越长，您获得的匹配项就越少：

c1:639195EM

c2:66XA53WX

现在尝试在句子中找到 c1 和 c2，如果找到匹配，则必须在句子中向前（c1 匹配）或向后（c2 匹配）来检查缺失部分的编辑距离是否为 1 或更小。

所以在你的例子中你会找到 c2 然后：

1. 将指针设置为 c1 的最后一个字符以及匹配项之前的字符。
2. 当字符相同时，将两个指针都减 1（在两个字符串中向后移动）。

3. 如果您可以通过这种方式完全消耗 c1，您就找到了完全匹配（编辑距离为 0）。

4. 否则尝试编辑距离为 1 的 3 种可能性：

   1. 只将c1的指针向后移动，看​​看其余的是否匹配（删除）。

   2. 只将句子的指针向后移动，看​​看其余部分是否匹配（插入）。

   3. 将两个指针向后移动，看​​看其余的是否匹配（替换）。

5. 如果其中一个成功，您将找到 Levenshtein 距离为 1 的匹配项，否则距离会更高。