Python Сравните перекрытие нескольких словарей диапазонов

У меня есть несколько наборов файлов, которые я хотел бы сравнить на основе столбца идентификатора, начального значения и конечного значения. Каждый файл имеет следующую структуру: Ex.

A    200    900
A    300    1200
B    100    700
B    900    1000

Идентификаторы и значения различаются в каждом файле, и я хотел бы сравнить перекрытие между 2-4 наборами этих файлов. Поэтому, если в другом файле есть «A 150 1000», я бы получил и перекрыл эти два файла.

Например, если я помещаю 4 файла по 100 строк в каждом, я хотел бы знать количество перекрытий (или неперекрытий) между каждым из файлов.

FileA only =
FileB only = 
FileC only = 
FileD only = 
FileA and FileB = 
FileA and FileC =
FileA and FileD =
FileA, FileB and FileC =
....

Мой код в настоящее время выглядит так:

def ReadFile(FileName, LineCount, Ranges)
    with open(FileName, "r") as FileName:
        LineCount = 0
        for Line in FileName:
            if LineCount==0:
                print "Skipping First Line"
            else:
                Line = Line.strip("\n").split("\t")
                Chr = Line[0]
                Start = int(Line[1])
                End = int(Line[2])
                ranges[Ident].append((Start, End))
            LineCount+=1

FileNum = int(raw_input("Number of Files for Comparison"))
rangesA = rangesB = rangesC = rangesD =defaultdict(list)

ReadFile(FileA, LineCountA, rangesA)
ReadFile(FileB, LineCountB, rangesB)
if FileNum >= 3:
    ReadFile(FileC, LineCountC, rangesC)
if FileNum >= 4:
    ReadFile(FileD, LineCountD, rangesD)

Я немного застрял, когда дело доходит до сравнения...


python dictionary range
person user2165857    schedule 30.04.2013    source источник
comment
Не могли бы вы уточнить, что вы подразумеваете под Таким образом, если в другом файле есть A 150 1000, я получу и перекрою два файла? Это основано на числовом диапазоне или простом текстовом сравнении или чем-то еще?   -  person mdscruggs    schedule 01.05.2013
comment
Я рассматриваю значения как диапазоны с начальным и конечным значением. Так что один из диапазонов для A в файле A будет 200-900, а диапазон для A в файле B будет 150-1000. Затем я хочу сравнить, сколько диапазонов для A перекрываются с диапазонами в FileB, который в приведенном выше примере будет одним.   -  person user2165857    schedule 01.05.2013

Ответы (1)


arrow_upward
1
arrow_downward

Я бы предложил получить для каждого файла диапазоны в этом формате:

rangesForFile0[
    ("A", 100, 1500, "file0"),
    ("A", 400, 1000, "file0"),
    ...
]

Затем поместите все диапазоны в один список:

allRanges = rangesForFile0 + rangesForFile1 + ...

Затем отсортируйте список по метке, затем по начальному значению (учитывая порядок полей в кортежах, этого должно быть достаточно):

allRanges.sort()

Затем просмотрите список диапазонов и для каждого диапазона проверьте, с какими другими диапазонами он перекрывается, и отметьте, из каких файлов эти другие диапазоны:

def rangesOverlap(x1, x2, y1, y2):
    return (x1 <= y2) and (y1 <= x2)

fileSetToRangesMap = {}
for i, r in enumerate(allRanges):
    fileSet = set([r[3]])
    x1 = r[1]
    x2 = r[2]
    for j, r2 in enumerate(allRanges):
        y1 = r2[1]
        y2 = r2[2]
        if (r[0] == r2[0]) and rangesOverlap(x1, x2, y1, y2):
            fileSet.add(r2[3])
    fileSetToRangesMap.setdefault(frozenset(fileSet), []).append(r)

После этого fileSetToRangesMap должен содержать в качестве ключей все различные наборы файлов, которые имеют перекрытия, а значениями будут массивы диапазонов, которые имеют перекрывающиеся аналоги в этом наборе файлов. В ключах, содержащих один файл, будут перечислены те диапазоны, которые уникальны в этом файле.

В приведенном выше примере диапазоны (100, 400) и (200, 500) будут рассматриваться как перекрывающиеся. Если вам нужно только подсчитать диапазоны, где один диапазон полностью включает другой диапазон из другого файла, то порядок файлов становится важным, и вам нужно будет построить более сложный граф направленных отношений между диапазонами и, следовательно, файлами.

person astraujums    schedule 30.04.2013
comment
Спасибо за вашу помощь. Я просто столкнулся с одной проблемой при попытке реализовать ваше решение, и я не уверен, что происходит не так. Например, если в файле A 188 строк, а в файле B 121 строка, при запуске программы я получаю: A: 167, B: 111, A_B: 31 - person user2165857; 08.05.2013
comment
Трудно понять, в чем проблема, не зная, как добраться до цитируемого вывода. Последняя версия вашего кода будет полезна, как и (возможно, небольшие) примеры файлов A и B, в которых проявляются проблемы. - person astraujums; 26.08.2013
comment
Я использовал код точно так, как описано выше, но расхождения такие, как я покажу ниже (первое число — это результат, второе — то, что я должен получить): A: 2245 2245, B: 629 671, C: 548 760, A_B: 42 42, B_C: 149 165, A_C: 47 47, A_B_C: 16 16 - person user2165857; 26.08.2013
comment
Произошла ошибка в цикле поиска других диапазонов, пересекающихся с текущим диапазоном. Отредактировал ответ, чтобы исправить это. - person astraujums; 02.09.2013