python - 如何在python中过滤大文件中两行的重叠

Question

我正在尝试在 python 中过滤大文件中的重叠行。

两行和另外两行的重叠度设置为 25%。也就是说，重叠度为 a*b/(c+d-a*b)>0.25 , a是第一行和第三行之间的交集数，b是第 2 行和第 4 行之间的交集数，c是第一行的元素数量乘以第二行的元素数量，d是第 3 行的元素数量乘以第 4 行的元素数量。如果重叠度大于0.25，则删除第3行和第4行。因此，如果我有一个总共有 1000 000 行的大文件，则前 6 行如下:

c6 c24 c32 c54 c67
k6 k12 k33 k63 k62
c6 c24 c32 c51 c68 c78
k6 k12 k24 k63
c6 c32 c24 c63 c67 c54 c75
k6 k12 k33 k63

因为第1两行和第2行的重叠度为a=3 ，(如c6,c24,c32)，b=3 ,(如 k6,k12,k63 ), c=25,d=24 , a*b/(c+d-a*b)=9/40<0.25 ，第3行和第4行不被删除。接下来第1两行和第3两行的重叠度为5*4/(25+28-5*4)=0.61>0.25 ,删除第三两行。
最终答案是第一和第二两行。

c6 c24 c32 c54 c67
k6 k12 k33 k63 k62
c6 c24 c32 c51 c68 c78
k6 k12 k24 k63

伪代码如下:

for i=1:(n-1)    # n is a half of the number of rows of the big file
    for j=(i+1):n  
        if  overlap degrees of the ith two rows and jth two rows is more than 0.25
          delete the jth two rows from the big file
        end
    end
end

Python代码如下，但错误。如何解决？

with open("iuputfile.txt") as fileobj: 
    sets = [set(line.split()) for line in fileobj]
    for first_index in range(len(sets) - 4, -2, -2):
        c=len(sets[first_index])*len(sets[first_index+1])
        for second_index in range(len(sets)-2 , first_index, -2):
            d=len(sets[second_index])*len(sets[second_index+1])
            ab = len(sets[first_index] | sets[second_index])*len(sets[first_index+1] | sets[second_index+1])
            if (ab/(c+d-ab))>0.25:
                del sets[second_index]
                del sets[second_index+1]
with open("outputfile.txt", "w") as fileobj:
    for set_ in sets:
        # order of the set is undefined, so we need to sort each set
        output = " ".join(set_)
        fileobj.write("{0}\n".format(output))

类似的问题可以在https://stackoverflow.com/questions/17321275/中找到

如何修改该代码来解决Python中的这个问题？谢谢!

Answer 1

我一直在思考如何以更好的方式解决这个问题，而不需要所有的逆向和索引之类的东西，我想出了一个更长、更复杂的解决方案，但更容易阅读，更漂亮，恕我直言，更易于维护和扩展。

首先，我们需要一种特殊类型的列表，即使其中的项目被删除，我们也可以“正确”地迭代它。 Here是一篇博客文章，详细介绍了列表和迭代器的工作原理，阅读它将帮助您了解这里发生的事情:

class SmartList(list):
    def __init__(self, *args, **kwargs):
        super(SmartList, self).__init__(*args, **kwargs)
        self.iterators = []

    def __iter__(self):
        return SmartListIter(self)

    def __delitem__(self, index):
        super(SmartList, self).__delitem__(index)
        for iterator in self.iterators:
            iterator.item_deleted(index)

我们扩展了内置的list并使其返回自定义迭代器而不是默认迭代器。每当列表中的项目被删除时，我们都会调用 item_deleted self.iterators中每一项的方法列表。这是 SmartListIter 的代码:

class SmartListIter(object):
    def __init__(self, smartlist, index=0):
        self.smartlist = smartlist
        smartlist.iterators.append(self)
        self.index = index

    def __iter__(self):
        return self

    def next(self):
        try:
            item = self.smartlist[self.index]
        except IndexError:
            self.smartlist.iterators.remove(self)
            raise StopIteration
        index = self.index
        self.index += 1
        return (index, item)

    def item_deleted(self, index):
        if index >= self.index:
            return
        self.index -= 1

因此，迭代器将自身添加到迭代器列表中，并在完成后从同一列表中删除自身。如果删除索引小于当前索引的项目，我们会将当前索引减一，这样我们就不会像普通列表迭代器那样跳过项目。

next方法返回一个元组 (index, item)而不仅仅是项目，因为当需要使用这些类时，这会让事情变得更容易——我们不必乱搞 enumerate .

因此，这应该能够解决必须向后返回的问题，但我们仍然需要使用大量索引来处理每个循环中的四条不同的行。由于两行和两行在一起，让我们为此创建一个类:

class LinePair(object):
    def __init__(self, pair):
        self.pair = pair
        self.sets = [set(line.split()) for line in pair]
        self.c = len(self.sets[0]) * len(self.sets[1])

    def overlap(self, other):
        ab = float(len(self.sets[0] & other.sets[0]) * \
            len(self.sets[1] & other.sets[1]))
        overlap = ab / (self.c + other.c - ab)
        return overlap

    def __str__(self):
        return "".join(self.pair)

pair attribute 是直接从输入文件读取的两行元组，包含换行符。我们稍后使用它将该对写回到文件中。我们还将这两行转换为一个集合并计算 c attribute，即每对线的属性。最后，我们创建了一种方法来计算一个 LinePair 与另一个 LinePair 之间的重叠。请注意 d消失了，因为那只是 c另一对的属性。

现在是大结局:

from itertools import izip

with open("iuputfile.txt") as fileobj:
    pairs = SmartList([LinePair(pair) for pair in izip(fileobj, fileobj)])

for first_index, first_pair in pairs:
    for second_index, second_pair in SmartListIter(pairs, first_index + 1):
        if first_pair.overlap(second_pair) > 0.25:
            del pairs[second_index]

with open("outputfile.txt", "w") as fileobj:
    for index, pair in pairs:
        fileobj.write(str(pair))

请注意，阅读这里的中心循环是多么容易，而且它是多么短。如果您将来需要更改此算法，则使用此代码可能比使用我的其他代码更容易完成。 izip用于对输入文件的两行和两行进行分组，如here所述.