I am trying to filter overlap rows in a big file in python.The overlap degrees is set to 25%. In other words,the number of element of intersection between any two rows is less than 0.25 times of union of them.if more than 0.25,one row is deleted.So if I have a big file with 1000 000 rows in total, the first 5 rows are as follows:
c6 c24 c32 c54 c67
c6 c24 c32 c51 c68 c78
c6 c32 c54 c67
c6 c32 c55 c63 c85 c94 c75
c6 c32 c53 c67
Because the number of element of intersection between the 1st row and 2nd row is 3,(such as c6,c24,c32 ),the number of union between them is 8,(such as c6,c24,c32,c54,c67,c51,c68,c78). The overlap degrees is 3/8=0.375 > 0.25,the 2nd row is deleted.so do the 3rd and 5th rows.The final answer is the 1st and 4th row.
c6 c24 c32 c54 c67
c6 c32 c55 c63 c85 c94 c75
The pseudo code are as follows:
for i=1:(n-1) # n is the number of rows of the big filefor j=(i+1):n if overlap degrees of the ith row and jth row is more than 0.25delete the jth row from the big fileendend
end
how to solve this problem in python? Thank you!
The tricky part is that you have to modify the list you're iterating over and still keep track of two indices. One way to do that is to go backwards, since deleting an item with index equal to or larger than the indices you keep track of will not influence them.
This code is untested, but you get the idea:
with open("file.txt") as fileobj:sets = [set(line.split()) for line in fileobj]for first_index in range(len(sets) - 2, -1, -1):for second_index in range(len(sets) - 1, first_index, -1):union = sets[first_index] | sets[second_index]intersection = sets[first_index] & sets[second_index]if len(intersection) / float(len(union)) > 0.25:del sets[second_index]
with open("output.txt", "w") as fileobj:for set_ in sets:# order of the set is undefined, so we need to sort each setoutput = " ".join(sorted(set_, key=lambda x: int(x[1:])))fileobj.write("{0}\n".format(output))
Since it's obvious how to sort the elements of each line we could do it like this. If the order was somehow custom, we'd have to couple the read line with each set element so that we could write back exactly the line that was read at the end, instead of regenerating it.