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

Question

我想知道是否有任何工具可以将 almost 同一个词匹配到 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

可以使用支持模糊匹配的PythonPyPi regexclass

由于您实际上想要匹配具有最大 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 是 单词边界 ，由于该构造，只有整个单词匹配（vacation 中的 cat 不会得到匹配）。

另存为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

Answer 2

您可以通过使用 python、

检查每个字符来检查差异，如下所示

def is_diff(str1, str2):
    diff = False
    for char1, char2 in zip(str1, str2):
        if char1 != char2:
            if diff:
                return False
            else:
                diff = True
    return diff
with open('list.txt') as f:
    data = f.readlines()

for line in data:
    print is_diff('ban', line)

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

match words with few differences allowed

regex

linux

bash

terminal

similarity