如何在python中過濾大文件中兩行的重疊

Question

我想在python中的大文件中過濾重疊行。

重疊度設置爲兩行和另外兩行的25％。換言之，重疊度是a*b/(c+d-a*b)>0.25，a是第1行和第3行之間的交叉的數目，b是的第二行和第四行之間的交叉的數目，c是元件的數量第一行乘以第二行的元素數，d是第三行的元素數乘以第四行的元素數。如果重疊度大於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

由於重疊度第一兩行和第二行的是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行不被刪除。接下來，前兩行和第三兩行的重疊度爲5*4/(25+28-5*4)=0.61>0.25，第三兩行被刪除。
最終答案是第1和第2兩行。

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，並使其返回一個自定義的迭代器，而非的默認值。只要列表中的項目被刪除，我們就會調用self.iterators列表中每個項目的item_deleted方法。下面的代碼爲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 

所以迭代器增加了本身的迭代器的列表中，當它完成從相同的列表中移除。如果索引小於當前索引的項目被刪除，我們將當前索引減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屬性是兩行的元組直接從輸入文件讀取，完全用換行。我們稍後使用它將該對寫回文件。我們還將這兩行轉換爲一組並計算c屬性，這是每對行的屬性。最後我們制定一個方法來計算一個LinePair和另一個LinePair之間的重疊。請注意0​​已經不存在了，因爲那只是另一對的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所述。 「

Answer 2

堆棧溢出不在這裏爲您編程或解決一般調試任務。這是針對你試圖解決但不能解決的具體問題。作爲一名程序員，你應該提出的問題應該能夠弄清楚自己。啓動你的程序是這樣的：

python -m pdb my_script.py 

現在，你可以通過你的腳本逐行使用n命令步驟。如果您想查看變量內部的內容，只需鍵入該變量的名稱即可。通過使用這種方法，你會發現爲什麼事情不能自己工作。使用pdb（python調試器）可以做很多其他聰明的事情，但對於這種情況，n命令就足夠了。

請在這裏提出另一個問題之前，自己花更多的精力來解決您的問題。

話雖這麼說，這裏是什麼不對您的修改後的腳本：

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]) 
      # Error 1: 
      ab = len(sets[first_index] & sets[second_index]) * \ 
       len(sets[first_index + 1] & sets[second_index + 1]) 
      # Error 2: 
      overlap = (float(ab)/(c + d - ab)) 
      if overlap > 0.25: 
       # Error 3: 
       del sets[second_index + 1] 
       del sets[second_index] 
    with open("outputfile.txt", "w") as fileobj: 
     for set_ in sets: 
      # You've removed the sorting, I assume it's because the order 
      # is unimportant 
      output = " ".join(set_) 
      fileobj.write("{0}\n".format(output)) 

的錯誤是：

• 錯誤1：交集是&。 Union是|。
• 錯誤2：因爲所有的變量都是整數，所以結果也是一個整數，除非你使用python 3.如果你是這樣，這不是錯誤。如果你不是，你需要確保其中一個變量是一個浮點數，以強制結果爲浮點數。因此float(ab)。
• 錯誤3：記得總是從前後方向工作。當您刪除sets[second_index]時，曾經在sets[second_index + 1]處取代它，因此刪除sets[second_index + 1]之後將刪除曾經在sets[second_index + 2]上的內容，這不是您想要的內容。所以我們先刪除最大的索引。