python - 使用 Python 计算一组中任意两个字符串之间的最大距离

Question

我的问题是如何计算对应于某个组的任意两个字符串之间的最大距离。我文件中的每一行都以“组号”开头，后跟一个长字符串。我想知道，对于每组，每组中任意两个字符串之间的最大距离是多少。以下是我正在使用的文件类型(字符串已缩短)。请注意，这些组不一定按顺序排列，我的一些组只有一个字符串与之相关联，所以我想跳过它们(下面示例中的组“3”):

 0 GCAGACGGGUGAGUAACGCGUGGGAACGUACCAUUUGCUACGGAAUAACUCAGG
 0 GCAGACGGGUGAGUAACGCGUGGGAACGUACCAUUUGCUACGGAAUAACUCAGG
 1 CGAACGGGUGAGUAACACGUGGGCAAUCUGCCCUGCACUCUGGGACAAGCCCUG
 1 CGAACGGGUGAGUAACACGUGGGCAAUCUGCCCUGCACUCUGGGACAAGCCCUG
 1 CGAACGGGUGAGUAACACGUGGGCAAUCUGCCCUGCACUCUGGGACAAGCCCUG
 2 GCCCUUCGGGGUACUCGAGUGGCGAACGGGUGAGUAACACGUGGGUGAUCUGCC
 2 GCCCUUCGGGGUACUCGAGUGGCGAACGGGUGAGUAACACGUGGGUGAUCUGCC
 2 GCCCUUCGGGGUACUCGAGUGGCGAACGGGUGAGUAACACGUGGGUGAUCUGCC
 0 GCAGACGGGUGAGUAACGCGUGGGAACGUACCAUUUGCUACGGAAUAACUCAGG
 0 GCAGACGGGUGAGUAACGCGUGGGAACGUACCAUUUGCUACGGAAUAACUCAGG
 3 GCAGACGGGUGAGUAACAAAAAGGAACGUACCAUUUGCUACGGAAUAACUCAGG

我想创建一些东西来创建一个看起来像这样的输出:

 Group0 = 0
 Group1 = 1.2
 Group2 = 2.1

 Average = 1.1

这个输出会给我组号，然后是该组的最大差异。以及所有组之间最大差异的总体平均值(再次跳过只有一个字符串与之关联的组):

我的真实文件有大约 5000 个组，我正在比较的字符串大约有 400 个字符长。

我想我可以通过查看这个 Question 来开始解决这个问题，但我不确定如何只计算同一组中字符串的百分比差异，避免只有一个字符串的组，以及计算所有组的总体平均百分比差异。任何帮助将不胜感激，非常感谢您的任何想法!

编辑:这是我正在使用的文件中的一些截断行。 “组”数字的范围从 0 到 ~ 6000。字母串实际上有 426 个字符长。文件格式为[数字][空格][字母串][行尾字符]

7 UGGCGAACGGGUGAGUAAC<br/>
35 GUGGGGAUUAGUGGCGAAC<br/>
50 AAACGAGAUGUAGCAAUAC<br/>
82 GGAGAGAGCUUGCUCUCUU<br/>
479 UCAGGAGCUUGCUCCUGU<br/>
46 CGAGGAGCUUGCUCCUUU<br/>
24 AACUGGGUCUAAUACCUU

Answer 1

您也可以尝试使用 difflib来自标准库的 SequenceMatcher:

>>> import difflib
>>> from itertools import groupby, combinations

>>> def find_max_ratio(lines):
    lines = [row.split() for row in lines]  # the file should already break at each line break
    lines = [(int(row[0]), row[1]) for row in lines]
    lines = groupby(sorted(lines), lambda x: x[0])  # combine strings into their respective groups, sorting them first on int of first element
    group_max = dict()
    for group in lines:
        strings = list(group[1])  # need to convert group[1] from iterator into list
        if len(strings) > 1:  # if the number of strings is 1, then there is nothing to compare the string with in its group
            similarity = 1
            for line1, line2 in combinations(strings, 2):
                s = difflib.SequenceMatcher(None, line1[1], line2[1])  # need to compare second element in each list and exclude the first element (which is the group number)
                similarity = s.ratio() if s.ratio() < similarity else similarity
            group_max[line1[0]] = 1 - similarity  # gives difference ratio
    return group_max

>>> t = open('test.txt')
>>> print find_max_ratio(t)  # it appears that your examples don't have any differences
{'1': 0, '0': 0, '2': 0}

然后您可以按如下方式计算平均值:

>>> max_ratios = find_max_ratio(t)
>>> average = sum(max_ratios.values())/float(len(max_ratios))
>>> average
0.0  # there are no differences in your test data above

编辑:写入文件

>>> output = sorted(max_ratios.items(), key=lambda x: x[1], reverse=True)  # sorting by descending ratios
>>> with open('test2.txt', 'w') as f:  # a new file name
>>>     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]  # the file should already break at each line break
    lines = [(int(row[0]), row[1]) for row in lines]
    lines = groupby(sorted(lines), lambda x: x[0])  # combine strings into their respective groups, sorting them first on int of first element
    group_minmax = dict()
    for index, group in lines:
        strings = list(group)  # need to convert group[1] from iterator into list
        if len(strings) > 1:  # if the number of strings is 1, then there is nothing to compare the string with in its group
            max_similarity = 1
            min_similarity = 0
            for line1, line2 in combinations(strings, 2):
                s = difflib.SequenceMatcher(None, line1[1], line2[1])  # need to compare second element in each list and exclude the first element (which is the group number)
                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)  # gives max difference ratio and then min difference ratio
    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)}  # again, no differences in your test data
>>> 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)  # no differences in your test data

编辑 3:优化问题

最后，根据您最后的评论，我不确定您是否能够以目前的形式过度优化此功能。如果您的计算机无法处理它，您可能需要处理较小的文本 block ，然后在最后编译结果。 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  # if your data is not random, you should do CONSIDERABLY better than this

请注意，大部分 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}

如果你的机器能搞定，我就运行这个函数，做好等两三个小时的准备。为了逐个字符地比较这些字符串，这里发生了很多事情。