今天早上我在办公室遇到了一个问题。你知道吗
我需要找到一种方法从一个列表中把字符串组合在一起。很难解释,所以举个例子:
假设我有一个清单如下:
['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']
]
那将是一个完美的案例。很明显,它可能会有(而且会有)错误。我需要用大约10000个列表来完成,每个列表包含5到15000个字符串。我需要尽量减少错误,得到最好的群体,我可以。你知道吗
我使用的是稍微修改过的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)]]
有没有可能找到这个列表中每个元素只出现在一个组中的最佳子集?(那么最高分呢?)考虑到我的列表要大得多,所以我不能测试每一个配置,因为这需要很多年。你知道吗
否则,有没有其他更有效的方法来做我想做的事?你知道吗
谢谢你!你知道吗
您可以使用字典逐步从组中删除尚未分组的城市。你知道吗
请注意,我没有烦躁不安,所以我创建了一个贫民区比率计算器来测试解决方案。我还删除了重音字符以使这更容易(我的目标不是创建一个好的字符串比较函数)
下面是分组逻辑(您可以用fuzzyfuzzy中的函数替换我的自定义getRatio()函数):
groups
变量是一个包含城市名称集(组)的列表。城市只会出现在一组中。你知道吗使用较低的treshold(或更好的比较函数),您将得到较少的组:
从性能的角度来看,对于相对较小的数据集,这将在合理的时间内产生结果。把1600个城市分组花了83秒。由于combinations()循环的O(N^2)性质,当您得到列表中的15000个项目时,这可能变得不切实际。你知道吗
分组循环从较大的组开始。它占用了大约一半的处理时间。一旦你接触到一个足够小的群体,你可以通过停止它来节省一些时间。如果你不需要1-2个城市群的话。当分组大小小于3时,我尝试停止分组循环,1600个城市在48秒内处理完毕(这对我的模拟数据来说是一个显著的节省)。不过,使用实际数据可能无法获得如此大的性能提升。你知道吗
相关问题 更多 >
编程相关推荐