从列表中将相似的字符串分组在一起

Question

从列表中将相似的字符串分组在一起

pythonstringgroupingsimilaritylevenshtein-distance

4

今天早晨我在办公室遇到了一个问题。

我需要找一种方法，将列表中的字符串分组。很难解释，下面是一个例子:

假设我有以下列表:

['MONTREAL EDUCATION BOARD', 'Île de Montréal', 'Montréal',
       'Ville de Montréal', 'MONTREAL CITY', 'Monrtéal', 'Mont-réal',
       'Toronto', 'Toronto city', 'Tornoto', 'What is this', 'Bananasplit',
       'Banana', 'StLouis', 'St-Louis', 'Saint Louis']

我需要找到一种方法根据它们的相似性将这些值分组在一起：

[['MONTREAL EDUCATION BOARD'],
 ['Île de Montréal', 'Montréal','Ville de Montréal', 'MONTREAL CITY', 'Monrtéal', 'Mont-réal'],
 ['Toronto', 'Toronto city', 'Tornoto'],
 ['anything'],
 ['Bananasplit', 'Banana'],
 ['StLouis', 'St-Louis', 'Saint Louis']
]

那将是最完美的情况。显然它可能会有错误（并且确实会有）。我需要对大约10,000个列表执行此操作，其中每个列表包含5到15,000个字符串。我需要尽量减少错误，并获得最好的分组。

我正在使用略微修改过的fuzzywuzzy版本。我首先去掉重音符号并将所有字母大写，以获得更准确的Levenshtein距离。

我尝试设置一个阈值（比如80），遍历列表，将每个字符串分组并删除重复元素。显然，这不是我需要的结果，因为我需要每个元素仅出现在一个列表中（而这种情况并非总是成立，因为A可以与B联系，B可以与C联系，但A不能与C联系）。

    groups = []
    for curr in lst:
        curr_grp = []
        for item in lst:
            ratio = normalized.partial_ratio(curr, item)
            if ratio > SET_THRESHOLD:
                curr_grp.append((item, ratio))

        groups.append(curr_grp)

我认为可以从我的输出中找到最优配置的方法：

[[('MONTREAL EDUCATION BOARD', 100),
  ('Montréal', 100), # Will probably have to use ratio() and not partial_ratio() because
  ('Monrtéal', 88),  # this can't happen, EDUCATION BOARD is NOT Montreal
  ('Mont-réal', 89)],
 [('Île de Montréal', 100),
  ('Montréal', 100),
  ('Ville de Montréal', 93),
  ('Monrtéal', 88),
  ('Mont-réal', 94)],
 [('MONTREAL EDUCATION BOARD', 100),
  ('Île de Montréal', 100),
  ('Montréal', 100),
  ('Ville de Montréal', 100),
  ('MONTREAL CITY', 100),
  ('Monrtéal', 88),
  ('Mont-réal', 88)],
 [('Île de Montréal', 93),
  ('Montréal', 100),
  ('Ville de Montréal', 100),
  ('Monrtéal', 88),
  ('Mont-réal', 94)],
 [('Montréal', 100),
  ('MONTREAL CITY', 100),
  ('Monrtéal', 88),
  ('Mont-réal', 89)],
 [('MONTREAL EDUCATION BOARD', 88),
  ('Île de Montréal', 88),
  ('Montréal', 88),
  ('Ville de Montréal', 88),
  ('MONTREAL CITY', 88),
  ('Monrtéal', 100)],
 [('MONTREAL EDUCATION BOARD', 89),
  ('Île de Montréal', 94),
  ('Montréal', 88),
  ('Ville de Montréal', 94),
  ('MONTREAL CITY', 89),
  ('Mont-réal', 100)],
 [('Toronto', 100), ('Toronto city', 100), ('Tornoto', 86)],
 [('Toronto', 100), ('Toronto city', 100), ('Tornoto', 86)],
 [('Toronto', 86), ('Toronto city', 86), ('Tornoto', 100)],
 [('What is this', 100)],
 [('Bananasplit', 100), ('Banana', 100)],
 [('Bananasplit', 100), ('Banana', 100)],
 [('StLouis', 100), ('St-Louis', 86), ('Saint Louis', 86)],
 [('StLouis', 86), ('St-Louis', 100)],
 [('StLouis', 86), ('Saint Louis', 100)]]

是否可能找到这个列表中最优的子集，使得每个元素只在一个组中出现？（因此具有最高分数？）考虑到我的列表将更大，因此我无法测试每个配置，因为这将需要很多时间。

否则，有没有其他更有效的方法可以做到我想做的事情？

谢谢！

- Tommy-Xavier Robillard

取一个字典，在其中有最大数94对应的键值对('Ville de Montréal', 94)，先检查字典，如果找到了新更高的值，则更新字典，不要盲目地追加列表。 - Jainil Patel

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alain T. · Accepted Answer

您可以使用字典逐步形成组，只包含尚未分组的城市。

请注意，我没有fussywuzzy，因此我创建了一个简陋的比率计算器来测试解决方案。为了使这更容易（我的目标不是创建一个良好的字符串比较函数），我还去掉了重音字符。

from collections import Counter
stripJunk = str.maketrans("","","- ")
def getRatio(a,b):
    a = a.lower().translate(stripJunk)
    b = b.lower().translate(stripJunk)
    total  = len(a)+len(b)
    counts = (Counter(a)-Counter(b))+(Counter(b)-Counter(a))
    return 100 - 100 * sum(counts.values()) / total

这里是分组逻辑（您可以使用fuzzywuzzy的函数替换我的自定义getRatio（）函数）：

data = ['MONTREAL EDUCATION BOARD', 'Ile de Montreal', 'Montreal',
       'Ville de Montreal', 'MONTREAL CITY', 'Monrteal', 'Mont-real',
       'Toronto', 'Toronto city', 'Tornoto', 'What is this', 'Bananasplit',
       'Banana', 'StLouis', 'St Louis', 'Saint Louis']

treshold     = 75
minGroupSize = 1

from itertools import combinations

paired = { c:{c} for c in data }
for a,b in combinations(data,2):
    if getRatio(a,b) < treshold: continue
    paired[a].add(b)
    paired[b].add(a)

groups    = list()
ungrouped = set(data)
while ungrouped:
    bestGroup = {}
    for city in ungrouped:
        g = paired[city] & ungrouped
        for c in g.copy():
            g &= paired[c] 
        if len(g) > len(bestGroup):
            bestGroup = g
    if len(bestGroup) < minGroupSize : break  # to terminate grouping early change minGroupSize to 3
    ungrouped -= bestGroup
    groups.append(bestGroup)

groups变量是一个列表，其中包含一组城市名称(即分组)。每个城市只会在一个组中出现。

# With a treshold of 75%:
{'MONTREAL CITY', 'Montreal', 'Monrteal', 'Mont-real'}
{'St Louis', 'StLouis', 'Saint Louis'}
{'Toronto', 'Toronto city', 'Tornoto'}
{'Ville de Montreal', 'Ile de Montreal'}
{'MONTREAL EDUCATION BOARD'}
{'Bananasplit'}
{'Banana'}
{'What is this'}

如果使用更低的阈值（或更好的比较函数），你会得到更少的分组：

# With a treshold of 65%:
{'Monrteal', 'Montreal', 'Ville de Montreal', 'MONTREAL CITY', 'Mont-real', 'Ile de Montreal'}
{'Toronto', 'Toronto city', 'Tornoto'}
{'Saint Louis', 'StLouis', 'St Louis'}
{'Banana', 'Bananasplit'}
{'What is this'}
{'MONTREAL EDUCATION BOARD'}

从性能角度来看，这对于相对较小的数据集可以在合理的时间内产生结果。将1600个城市分组花费了83秒的时间。由于combinations()循环的O(N^2)特性，在列表中达到15000个项目时，这可能变得不切实际。

分组循环从更大的组开始。它占用了约半数的处理时间。通过在达到足够小的组时停止它，您可能可以节省一些时间。也就是说，如果您不需要数不清的1-2个城市组。当组大小小于3时尝试停止分组循环，处理1600个城市只需48秒（对于模拟数据而言是一个显著的节省）。但是对于实际数据，您可能不会获得这么多的性能提升。