您也可以尝试使用difflib的SequenceMatcher标准库:
>>> import difflib
>>> from itertools import groupby, combinations
>>> def find_max_ratio(lines):
lines = [row.split() for row in lines]
lines = [(int(row[0]), row[1]) for row in lines]
lines = groupby(sorted(lines), lambda x: x[0])
group_max = dict()
for group in lines:
strings = list(group[1])
if len(strings) > 1:
similarity = 1
for line1, line2 in combinations(strings, 2):
s = difflib.SequenceMatcher(None, line1[1], line2[1])
similarity = s.ratio() if s.ratio() < similarity else similarity
group_max[line1[0]] = 1 - similarity
return group_max
>>> t = open('test.txt')
>>> print find_max_ratio(t)
{'1': 0, '0': 0, '2': 0}
您可以按以下方式计算平均值:
>>> max_ratios = find_max_ratio(t)
>>> average = sum(max_ratios.values())/float(len(max_ratios))
>>> average
0.0
编辑:写入文件
>>> output = sorted(max_ratios.items(), key=lambda x: x[1], reverse=True)
>>> with open('test2.txt', 'w') as f:
>>> f.write('\n'.join([group + ': ' + str(ratio) for group, ratio in output])
+ '\n\nAverage: ' + str(average))
编辑2: 添加最小差异
您可以将最小差异添加到您的结果中(这里以元组(<max_difference>, <min_difference>)
的形式表示),如下所示:
def find_maxmin_ratios(lines):
lines = [row.split() for row in lines]
lines = [(int(row[0]), row[1]) for row in lines]
lines = groupby(sorted(lines), lambda x: x[0])
group_minmax = dict()
for index, group in lines:
strings = list(group)
if len(strings) > 1:
max_similarity = 1
min_similarity = 0
for line1, line2 in combinations(strings, 2):
s = difflib.SequenceMatcher(None, line1[1], line2[1])
max_similarity = s.ratio() if s.ratio() < max_similarity else max_similarity
min_similarity = s.ratio() if s.ratio() > min_similarity else min_similarity
group_minmax[index] = (1 - max_similarity, 1 - min_similarity)
return group_minmax
然后,您可以像这样找到相应的平均值:
>>> t = open('test.txt')
>>> maxmin_ratios = find_maxmin_ratios(t)
>>> maxmin_ratios
{'1': (0, 0.0), '0': (0, 0.0), '2': (0, 0.0)}
>>> average_max = sum([maxmin[0] for maxmin in maxmin_ratios.values()])/float(len(maxmin_ratios))
>>> average_min = sum([maxmin[1] for maxmin in maxmin_ratios.values()])/float(len(maxmin_ratios))
>>> average_max, average_min
(0.0, 0.0)
编辑3:优化问题
最后,根据您的最后一条评论,我不确定您是否能够在当前形式下对这个函数进行过多的优化。如果您的计算机无法处理它,您可能需要处理更小的文本块,然后在最后编译结果。difflib
并不需要大量的内存,但它确实要做很多工作。您的性能应该比我的好得多(取决于您的机器),因为我的每一行都是随机的。如果您的行相似度高于不相似度,则应该表现得更好。以下是在我的机器上进行的cProfile的结果,针对以下情况(总共3.172小时):
text2.txt
- 9700 lines of text
- each line begins with one random number (1 to 10)
- each line has 400 random characters that follow the random number
请注意,大部分cumtime(给定函数及其以下所有函数的总时间)都花费在difflib上,这是当前函数无法控制的。实际上,其余部分几乎不需要花费多少时间。
4581938093 function calls in 11422.852 seconds
Ordered by: tottime # the total time spent in a given function, excluding time spent in subfunctions
ncalls tottime percall cumtime percall filename:lineno(function)
81770876 8579.568 0 9919.636 0 difflib.py:350(find_longest_match)
-724102230 1268.238 0 1268.238 0 {method 'get' of 'dict' objects}
4700900 874.878 0 1143.419 0 difflib.py:306(__chain_b)
9401960 160.366 0 10183.511 0.001 difflib.py:460(get_matching_blocks)
2060343126 141.242 0 141.242 0 {method 'append' of 'list' objects}
1889761800 110.013 0 110.013 0 {method 'setdefault' of 'dict' objects}
81770876 32.433 0 55.41 0 <string>:8(__new__)
130877001 32.061 0 32.061 0 {built-in method __new__ of type object at 0x1E228030}
81770876 29.773 0 29.773 0 {method 'pop' of 'list' objects}
1 23.259 23.259 11422.852 11422.852 <pyshell#50>:1(find_maxmin_ratios)
49106125 21.45 0 33.218 0 <string>:12(_make)
9401960 20.539 0 10239.234 0.001 difflib.py:636(ratio)
335752019 17.719 0 17.719 0 {len}
9401960 17.607 0 30.829 0 {_functools.reduce}
4700900 16.778 0 49.996 0 {map}
230344786 16.42 0 16.42 0 {method __contains__' of 'set' objects}
191093877 14.962 0 14.962 0 {method 'add' of 'set' objects}
98214517 13.222 0 13.222 0 difflib.py:658(<lambda>)
4700900 6.428 0 6.428 0 {method 'sort' of 'list' objects}
4700900 5.794 0 5.794 0 {method 'items' of 'dict' objects}
4700900 5.339 0 1148.758 0 difflib.py:261(set_seq2)
4700900 4.333 0 1160.351 0 difflib.py:154(__init__)
4700900 3.83 0 1156.018 0 difflib.py:223(set_seqs)
4700900 3.43 0 3.43 0 difflib.py:235(set_seq1)
9401960 3.162 0 3.162 0 difflib.py:41(_calculate_ratio)
9700 0.003 0 0.003 0 {method 'strip' of 'str' objects}
1 0.003 0.003 0.003 0.003 {sorted}
9700 0.001 0 0.001 0 <pyshell#50>:3(<lambda>)
1 0 0 11422.852 11422.852 <string>:1(<module>)
1 0 0 0 0 {method 'disable' of '_lsprof.Profiler' objects}
如果你的机器能够承受,我建议直接运行此函数,并准备等待两到三个小时。在这里会有很多事情发生,以便逐个字符比较这些字符串。