zde*_*ine 9 regex levenshtein-distance
是否有可能在正则表达式查询中包含levenshtein距离？
除了在排列之间建立联合.喜欢用Ld 1搜索"你好"
.ello | h.llo | he.lo | hel.o | hell.
对于大量的Ld来说,这是非常愚蠢和无法使用的
您可以以编程方式生成正则表达式.我将把它作为读者的练习,但是对于这个假设函数的输出(给出"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的匹配器.
(Damerau-Levenshtein距离2更复杂.)
注意使用(？>非回溯构造,这意味着该输出物质中各个|'d表达式的顺序.
我想不出一种"压缩"这种表达方式的方法.
编辑:我得到它的工作,至少在Elixir!https://github.com/pmarreck/elixir-snippets/blob/master/damerau_levenshtein_distance_1.exs
我不一定会推荐这个(除了教育目的),因为它只能让你达到1的距离; 一个合法的DL库可以让你计算距离> 1.虽然这是正则表达式,但一旦构造它可能会很快工作(注意你应该在某处保存"编译"正则表达式,因为这个代码目前在每次比较时重建它!)
有几个具有近似匹配功能的正则表达式方言 - 即TRE库和regexPython的PyPI 模块。
TRE 近似匹配语法在https://laurikari.net/tre/documentation/regex-syntax/的“近似匹配设置”部分中进行了描述。匹配 Levenshtein 距离 1 内的内容的 TRE 正则表达式hello是：
(hello){~1}
该regex模块的近似匹配语法在https://pypi.org/project/regex/以文本开头的项目符号点中进行了描述Approximate “fuzzy” matching。regex匹配 Levenshtein 距离 1 内的东西的正则表达式hello是：
(hello){e<=1}
也许这些语法中的一种或另一种会被其他正则表达式实现采用，但目前我只知道这两种。