匹配所有相关字符串

Question

我有一个文本文件，其中包含一些文本文件如下。你知道吗

文件.txt

leptop
pencil
group
leptop
book
gruop
buk
grop
laftop
pensil
laptop
pancil
laptop bag
bok

从该文件中，我需要找出相关的查询，并存储在下面的列表中。你知道吗

  [leptop,leptop,laftop,laptop]
  [pencil,pensil,pancil]
  [group,gruop,grop]
  [book,buk,bok]
  [laptop bag]  

我发现了类似的东西在它下面它工作得很好。但我想修改一下。你知道吗

import keyword
from difflib import get_close_matches

lis = ["leptop","pencil","group","leptop","book","gruop","bowk","grop","laftop","pensil","laptop","pancil","laptop bag","bok"]
print get_close_matches("laptop",lis, n = len(lis))
print get_close_matches("pencil", lis, n = len(lis))
print get_close_matches("group", lis, n = len(lis))
print get_close_matches("book", lis, n = len(lis))

你知道吗输出：-你知道吗

['laptop', 'leptop', 'leptop', 'laftop', 'laptop bag'] # i don't want "laptop bag" as output over here. 
['pencil', 'pensil', 'pancil']
['group', 'grop', 'gruop']
['book', 'bok', 'bowk']

Answer 1

首先你需要定义“相关”的含义。你知道吗

从你的例子来看，如果a“在字符上有一个小的变化以获得b”，那么单词a和b似乎是相关的。。。请参阅有关Levenshtein距离的其他注释，这正是您想要使用的：Levenshtein或Minimum Edit Distance接受两个单词a和b，并为您提供一个数字dist（a，b），如果a=b，则该值为0，并且需要对a进行更多更改才能获得b

有了这个“工具”，你可以开始建立一个解决你的问题的算法，例如通过定义一个表示“相关”的距离，逐行检查每个单词是否与下面的任何单词有一个小距离。你知道吗

然而，你真的需要考虑你想要实现什么。使用一个简单的方法可以将输入中的所有单词放在一个“类”中，如果它们都是传递相关的。你知道吗

示例：foo/fool相关，fool/pool相关，pool/bool相关。 根据你最初的想法，foo可能与bool没有“关联”，但它是通过一系列相关的词来关联的。你知道吗

如果您同意foo/fool/pool/bool都在一个类中结束的解决方案，那么您可以使用一个简单的方法，否则您需要更聪明的方法。你知道吗

Answer 2

我认为正则表达式不是正确的方法。你知道吗

但是，您可以使用Union Find和Minimum Edit Distance的组合来实现这一点。你知道吗

对于每个单词组合，确定min_edit_dist，如果距离小于某个阈值，则union将这些单词放在一起。为阈值选择合适的值可能取决于单词的选择。用你的话说，3或4似乎效果不错。你知道吗

import collections, itertools

# initialize 'leaders' dictionary, used in union and find
leaders = {word: None for word in words}

# union similar words together
for u, v in itertools.combinations(words, 2):
    if find(u) != find(v) and min_edit_dist(u, v) < 3:
        union(u, v)

# determine groups of similar words by their leaders
groups = collections.defaultdict(set)
for x in leaders:
    groups[find(x)].add(x)
print groups.values()

输出，对于union、find和min_edit_dist的实现：

[set(['laptop bag']), 
 set(['gruop', 'grop', 'group']), 
 set(['buk', 'book', 'bok']), 
 set(['laftop', 'laptop', 'leptop']), 
 set(['pencil', 'pancil', 'pensil'])]

有关union和find函数，请参阅this answer。min_edit_dist函数的实现留给读者作为练习。你知道吗

这种方法可能存在的一个问题是，如果所有组之间存在足够密切的差异，它可能最终会合并所有组。你知道吗

---

关于您自己使用difflib.find_close_matches的方法：

您可以使用cutoff参数来微调匹配的“接近”程度。但是，我没有找到一个适用于所有示例的值，更不用说适用于可能存在的所有其他示例了。0.8适用于laptop，但对book过于严格。还要注意，使用这种方法时，您需要知道哪些是“根词”，这在实践中可能是个问题。你知道吗

另一方面，我的方法不需要先验地知道哪些词是这个群体的“领导者”，而是找到它们本身。对于类似的技术，您可能还想看看cluster analysis algorithms。你知道吗