logo标签列表

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

pythondifference
6
我的问题是如何计算与特定组对应的任意两个字符串之间的最大距离。 我的文件中每行都以“组号”开头，后跟一个长字符串。 对于每个组，我想知道该组中任意两个字符串之间的最大距离。 下面是我正在使用的文件类型（字符串已缩短）。 请注意，组不一定按顺序排列，我的一些组仅有一个与它们相关联的字符串，因此我将跳过它们（下面示例中的第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个字符长。

我认为我可以通过查看此问题来解决此问题，但我不知道如何仅计算同一组中的字符串的百分比差异，避免只有一个字符串的组，并计算所有组的总平均百分比差异。任何帮助都将不胜感激，非常感谢任何想法！

编辑：下面是我正在处理的文件的几行截断。 'group'编号范围从0到〜6000。字母字符串实际上有426个字符长。文件格式为[number][一个空格][字母字符串][换行符]

7 UGGCGAACGGGUGAGUAAC
35 GUGGGGAUUAGUGGCGAAC
50 AAACGAGAUGUAGCAAUAC
82 GGAGAGAGCUUGCUCUCUU
479 UCAGGAGCUUGCUCCUGU
46 CGAGGAGCUUGCUCCUUU
24 AACUGGGUCUAAUACCUU

1
我不认为你正在询问如何计算字符串之间的差异 - 你从发布的问题中已经知道了如何做到这一点。你在询问一个更基本的问题，如何处理来自文件的字符串列表，是吗？ - GreenAsJade
1
使用Levenshtein距离计算两个字符串之间的差异，并将每个修改操作的权重设为1。你将得到一个衡量两个字符串需要进行多少字符编辑才能相等的指标。然后，您可以将其作为字符串长度的百分比。 - yǝsʞǝla
这就是为什么我认为另一个问题有一些可能有用的元素，但只适用于查看2个字符串时。 - Jen
@GreenAsJade 我知道的是每个字符串（无论组别如何）都有400个字符长，所以我想要弄清楚的是一组中的字符串彼此之间有多相似。也许对于大多数组来说，所有字符串都是相同的！或者它们非常接近（只有在400个字符中相互之间有5个不同！）。这就是我的意思，这样更清楚吗？我认为百分比差异是最好的方法。 - Jen
1
那么，你觉得知道“这组字符串中任意两个字符串之间的最大距离是多少”有意义吗？也许这就是你想问的？ - GreenAsJade
显示剩余11条评论
3个回答
5

您也可以尝试使用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：优化问题

最后，根据您的最后一条评论，我不确定您是否能够在当前形式下对这个函数进行过多的优化。如果您的计算机无法处理它，您可能需要处理更小的文本块，然后在最后编译结果。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}

如果你的机器能够承受，我建议直接运行此函数，并准备等待两到三个小时。在这里会有很多事情发生，以便逐个字符比较这些字符串。
谢谢！如果这是一个愚蠢的问题，我很抱歉。在最后一行中，当它说print find_max_ratio(t)时，我需要将t设置为我正在使用的文件吗？ - Jen
1
谢谢！当我输入t = open('test.txt', 'w').readlines()这行代码时（别担心，我记得改文件名了哈哈！），我遇到了这个错误：Traceback (most recent call last): File "<stdin>", line 1, in <module> IOError: File not open for reading。 - Jen
非常感谢，运行得很好！我有一个最后的问题，如果这应该是一个新问题，我会发布它（抱歉！），但是如果我想更改函数find_max_ratio(lines)，使其可以找到最小比率（这样我就可以为每个组设置范围），那么我需要处理这两行吗？similarity = s.ratio() if s.ratio() < similarity else similarity和group_max[line1[0]] = 1 - similarity - Jen
我跳过了前面的部分，但当我只输入这一行 print find_max_ratio(t) 时，所有的比率都显示为0.5 '1866': 0.5, '4024': 0.5, '4025': 0.5，你知道可能是什么原因吗？ - Jen
太好了，谢谢！输入的形式为0 GCAGACGGGUGAGUAACGCGUGGGAACGUACC（尽管字母串大约有400个字符长）。此外，文件中可能会再次出现组号（因此在开头有3行带有零组的内容，但后面关于她的零组的内容不同）。这会影响什么吗？感谢您再次查看！ - Jen
显示剩余14条评论
1
seq_file = open("sequences.txt", 'r')

# make an dict of groups, each group is a list of sequences in that group

groups = {}

for item in seq_file.readlines():
    (group, sequence) = item.split()
    try:
        groups[group].append(sequence)
    except:
        groups[group] = [sequence]

# measure the distance from every seq in a group to every other seq in that group,
# keep a record of the maximum found in each group.  (It doesn't matter that we 
# compare a sequence to itself during this process).

max_distances = {}
for group_num, group_seqs in groups.iteritems():
    greatest_distance = 0
    for seq in group_seqs:
        for other_seq in group_seqs:
            greatest_distance = max(greatest_distance, levenshtein_distance(seq, other_seq))

    max_distances[group_num] = greatest_distance          
    print "max for group %s is %s" % (group_num, greatest_distance)

# Average maximum distance, across the groups

max_distanace_list = max_distances.values()
av_max_dist = float(sum(max_distanace_list)/len(max_distanace_list))

你提供的链接展示了如何使用 levenshtein_distance() 函数。

啊，我的疏忽，你需要将组从字符串“1”转换为整数1。我已经进行了编辑... - GreenAsJade
是的 - 不用过分仔细地看，似乎你可以直接从那个答案中复制levenshtein_distance的定义。你需要将它放在我展示给你的内容之前（这样函数在使用前就被定义了）。不要复制贴到该函数定义的结尾 :) - GreenAsJade
搞定了，感谢你的帮助！我在这一行又遇到了一个错误，我尝试使用 float 来修复它，但是没有成功，你觉得怎么样？group = int(float(group)) ValueError: could not convert string to float: AM158981 - Jen
你从 group=int(group) 得到了什么错误信息？如果 group 能够正确地从项目中分离出来，那么 int(group) 应该可以正常工作。 - GreenAsJade
对不起，这里有错误！group = int(group) ValueError:使用10进制int()时的无效Unicode文字：'AM158981' - Jen
显示剩余3条评论
0
你可以通过以下方式计算两个字符串之间的百分比差异：
a="GCAUGC"
b="GCAACC"

differences=0

for i in xrange(len(a)):
    if a[i]!=b[i]:
         differences+=1

percentageDifference = 100 * float(difference)/len(a)

这是假设字符串的长度都相同，从你的示例中看起来是这样。

现在取决于你对一组中所有字符串之间百分比差异的真正意义以及你想要做什么。例如，你可能想要检查组中任意两个字符串之间的差异并获得平均值。

只针对每个组进行此操作的问题可以通过预处理数据来解决。如果数据像你展示的那样，那么你可以将每行按空格拆分，并使用组号作为字典中的键，并将字符串附加到列表中作为项。类似于：

groupDictionary = {}

groupStringPair = line.split()
group = groupStringPair[0]
stringToAdd = groupStringPair[1]

try:
    groupDictionary[group].append(stringToAdd)
except KeyError:
    groupDictionary[group] = [stringToAdd]

然后你将会得到一个字典，其中每个组都有一个键，每个组的项都是一个字符串列表。如果你想忽略只有一个字符串的组，那么你可以从字典中删除它们或者忽略它们。你可以通过以下方式实现：

for k, v in groupDictionary.items():
    if len(v)==1:
        del groupDictionary[v]
貌似我现在还不能评论别人的帖子，但是看起来你可能想计算几个不同的平均差值，以便更好地了解数据。正如GreenAsJade所指出的那样，您可以获得最大差异。但是，您还可以查看所有差异的最小差异、平均值和中位数，甚至可能是模式。这可能会给您提供比单个数字更好的数据概述。 - Andrew Robinson
这是一个好主意，可以获取多个信息点。我想尽可能了解这些群组和它们中的序列（字符串）！ - Jen
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接