字符串模糊搜索：通过计算莱文斯坦距离实现

public-time:2020-10-16 23:41

1. 一般情况下：

# @File    : main.py
import Levenshtein
import englishwords

lis = englishwords.lis


def fuzzysearch(str_, lis_):
    lis = [Levenshtein.distance(str_, i) for i in lis_]
    # 分别计算莱文斯坦距离（Levenshtein）
    return lis_[lis.index(min(lis))]
    # 返回列表中莱文斯距离的最小值的字符串


print(fuzzysearch('directy', lis))
print(fuzzysearch('dieooooooocty', lis))

# 输出：
# directly
# discomfort

# =======
# 注意：englishwords.py文件在文章尾部

除上面外我还想到了其他两点:

在你给定字符串str后一般你想要的结果r_str应该有一定的长度限制，如
```
|len(r_str)-len(str)|<len(str)*125%
```
计算的莱文斯距离也应该存在一个上限,如
```
Levenshtein.distance(str_, i)<=len(str)*25%
```

2. 在有一些限制的情况下

于是有下面改进的代码：
返回列表中莱文斯距离的最小，且长度相对差最小的项的集合

import Levenshtein
import englishwords

lis = englishwords.lis

infinity = float("inf")


def same_value(value_, lis_1, lis_, difmax_=infinity):
    return [lis_[i] for i in range(len(lis_1)) if lis_1[i] == value_ and lis_1[i] < difmax_]
    # 返回列表莱文斯坦距离相同的项，如果存在为参数difmax赋值则返回的项被这个容许差值限制


def min_len_dif(value_, lis_, difmax_=infinity):
    min_dif_set = set()  # 可能有多以上距离差值相同
    if lis_:
        # 在距离限制下的列表不为空
        len_dif_min = abs(len(lis_[0]) - len(value_))
        # 先取第一项的距离
        for i in lis_:
            len_dif = abs(len(i) - len(value_))
            if len_dif <= len_dif_min and len_dif<difmax_:
                # 字符串长度的差距小于最小值且小于限定的最小值
                if len_dif < len_dif_min:
                    min_dif_set.clear()
                    # 如果出现一个新的最小值，则清空集合
                    len_dif_min = len_dif
                    # 记录最小值
                min_dif_set.add(i)
    if min_dif_set:
        return min_dif_set
        # 返回列表中长度相差最小的项的集合

def fuzzy_search(str_, lis_, maxl=infinity, maxk=infinity):
    lis_1 = [Levenshtein.distance(str_, i) for i in lis_]
    # 分别计算莱文斯坦距离（Levenshtein）
    same_Leve = same_value(min(lis_1), lis_1, lis_, maxl)
    # 记录所有莱文斯坦最小且相同的项
    return min_len_dif(str_, same_Leve,maxk)
    # 返回列表中莱文斯距离的最小，且长度相对差最小的项


s1 = 'directy'
maxl1 = int(len(s1) * 50 / 100)
maxk1 = int(len(s1) * 50 / 100)
print(fuzzy_search(s1, lis, maxl=maxl1, maxk=maxk1))
print('-----------')


s2 = 'dieooooooocty'
maxl2 = int(len(s2) * 50 / 100)
maxk2 = int(len(s2) * 200 / 100)
maxk3 = int(len(s2) * 20 / 100)
maxk4 = int(len(s2) * 50 / 100)

print('maxl2=0.5','maxk2=2:',fuzzy_search(s2, lis, maxl=maxl2, maxk=maxk2))
print('maxk4=0.2:',fuzzy_search(s2, lis, maxk=maxk3))
print('maxk4=0.5:',fuzzy_search(s2, lis, maxk=maxk4))

# 输出:
# {'directly'}
# -----------
# maxl2=0.5 maxk2=2: None
# maxk4=0.2: None
# maxk4=0.5: {'discomfort'}

# @File    : englishwords.py
lis = ['', 'settle', 'oppose', 'mood', 'craftsman',
            'agitate', 'catholic', 'go-ahe', 'bribery',
            'emphasize']

👆这儿的列表只列了列表lis=..的部分,完整的文件(一些英语单词)： englishwords.py