是否可以在正则表达式查询中包含 Levenshtein 距离?
(除了在排列之间进行联合,像这样用 Levenshtein 距离 1 搜索“hello”:
.ello | h.llo | he.lo | hel.o | hell.
因为这对于较大的 Levenshtein 距离来说是愚蠢且无法使用的。)
是否可以在正则表达式查询中包含 Levenshtein 距离?
(除了在排列之间进行联合,像这样用 Levenshtein 距离 1 搜索“hello”:
.ello | h.llo | he.lo | hel.o | hell.
因为这对于较大的 Levenshtein 距离来说是愚蠢且无法使用的。)
您可以以编程方式生成正则表达式。我将把它作为练习留给读者,但是对于这个假设函数的输出(给定“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。虽然这是正则表达式,但一旦构建它可能会很快工作(请注意,您应该将“编译的”正则表达式保存在某处,因为此代码当前在每次比较时都会重建它!)
有几种正则表达式方言具有近似匹配的特性——即TRE库和regex
Python 的 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}
也许这些语法中的一种或另一种会及时被其他正则表达式实现采用,但目前我只知道这两种。
是否有可能如何在正则表达式查询中包含 levenshtein 距离?
不,不是以理智的方式。实施 - 或使用现有的 - Levenshtein 距离算法是要走的路。