regex - 匹配允许有少量差异的单词

Question

我想知道是否有任何工具可以为 bash 终端匹配 几乎 相同的单词。

在以下名为 list.txt 的文件中，每行包含 1 个单词:

ban
1ban
12ban
12ban3

很容易找到包含“ban”的词

grep -E "*ban*" list.txt

问题:

如何实际匹配具有 x 个字母差异的单词？对于搜索词“ban”，我希望 X=1 的匹配项是“1ban”。

关于距离的概念，我想有最大值:X删除或 X 替换或 X 插入

任何工具，但最好是可以在 bash 终端上调用为命令行的工具。

注意:Levenshtein 距离将插入 2 个字母视为 1 个差异。这不是我想要的。

Answer 1

您可以使用 Python PyPi regex支持模糊匹配的类。

由于您实际上想要匹配具有最大 X 差异的单词(1 个删除或 1 个替换或 1 个删除)，您可以创建一个 Python 脚本，如

#!/usr/bin/env python3
import regex, io, sys

def main(argv):
        if len(argv) < 3:
                # print("USAGE: fuzzy_search -searchword -xdiff -file")
                exit(-1)
        search=argv[0]
        xdiff=argv[1]
        file=argv[2]
        # print("Searching for {} in {} with {} differences...".format(search, file, xdiff))
        with open(file, "r") as f:
                contents = f.read()
                print(regex.findall(r"\b(?:{0}){{s<={1},i<={1},d<={1}}}\b".format(regex.escape(search), xdiff), contents))

if __name__ == "__main__":
        main(sys.argv[1:])

在这里，{s<=1,i<=1,d<=1}意味着我们允许我们搜索的词有 1 次或 0 次替换 (s<=1)、1 次或 0 次插入 (i<=1) 或 1 次或 0 次删除 (d<=1)。

\b是单词边界，由于该构造，只有整个单词被匹配(cat 中的vacation 将被匹配)。

另存为 fuzzy_search.py .

那么，你可以称它为

python3 fuzzy_search.py "ban" 1 file

哪里"ban"是正在执行模糊搜索的词并且 1是差异的上限。

我得到的结果是

['ban', '1ban']

您可以将输出格式更改为仅行:

print("\n".join(regex.findall(r"\b(?:{0}){{s<={1},i<={1},d<={1}}}\b".format(regex.escape(search), xdiff), contents)))

那么，结果就是

ban
1ban