regex - 正则表达式中的 Levenshtein 距离

Question

是否可以在正则表达式查询中包含 Levenshtein 距离？

（除了在排列之间进行联合，像这样用 Levenshtein 距离 1 搜索“hello”：

.ello | h.llo | he.lo | hel.o | hell.

因为这对于较大的 Levenshtein 距离来说是愚蠢且无法使用的。）

Answer 1

您可以以编程方式生成正则表达式。我将把它作为练习留给读者，但是对于这个假设函数的输出（给定“word”的输入），你需要这样的字符串：

"^(?>word|wodr|wrod|owrd|word.|wor.d|wo.rd|w.ord|.word|wor.?|wo.?d|w.?rd|.?ord)$"

在英语中，首先您尝试匹配单词本身，然后匹配每个可能的单个换位，然后匹配每个可能的单个插入，然后匹配每个可能的单个省略或替换（可以同时进行）。

给定长度为 n 的单词，该字符串的长度与 n 呈线性关系（尤其是非指数）。

我认为这是合理的。

你把它传递给你的正则表达式生成器（就像在 Ruby 中，它会是 Regexp.new(str)）和 bam，你得到一个匹配器，匹配任何单词，与给定单词的 Damerau-Levenshtein 距离为 1。

（2 的 Damerau-Levenshtein 距离要复杂得多。）

注意使用 (?> 非回溯构造，这意味着该输出中各个 |'d 表达式的顺序很重要。

我想不出一种方法来“压缩”该表达式。

编辑：我让它工作，至少在 Elixir 中！https://github.com/pmarreck/elixir-snippets/blob/master/damerau_levenshtein_distance_1.exs

我不一定会推荐这个（除了教育目的），因为它只会让你达到 1 的距离；一个合法的 DL 库将让您计算距离 > 1。虽然这是正则表达式，但一旦构建它可能会很快工作（请注意，您应该将“编译的”正则表达式保存在某处，因为此代码当前在每次比较时都会重建它！）

Answer 2

有几种正则表达式方言具有近似匹配的特性——即TRE库和regexPython 的 PyPI 模块。

TRE 近似匹配语法在https://laurikari.net/tre/documentation/regex-syntax/的“近似匹配设置”部分中进行了描述。匹配 Levenshtein 距离 1 内的内容的 TRE 正则表达式hello将是：

(hello){~1}

该regex模块的近似匹配语法在https://pypi.org/project/regex/中以 text 开头的项目符号点中进行了描述Approximate “fuzzy” matching。regex匹配 Levenshtein 距离 1 内的东西的正则表达式hello是：

(hello){e<=1}

也许这些语法中的一种或另一种会及时被其他正则表达式实现采用，但目前我只知道这两种。

Answer 3

是否有可能如何在正则表达式查询中包含 levenshtein 距离？

不，不是以理智的方式。实施 - 或使用现有的 - Levenshtein 距离算法是要走的路。