Python Сравнете припокриването на множество речници от диапазони

Имам няколко набора от файлове, които бих искал да сравня въз основа на колона с идентификатор, начална стойност и крайна стойност. Всеки файл има следното оформление: Пр.

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)

Малко съм блокиран, когато става въпрос за сравнението...


person user2165857    schedule 30.04.2013    source източник
comment
Бихте ли били по-конкретни с това, което имате предвид под Така че, ако друг файл има A 150 1000, ще получа и ще се припокрия между двата файла? Това базирано ли е на числов диапазон или просто текстово сравнение или нещо друго?   -  person mdscruggs    schedule 01.05.2013
comment
Третирам стойностите като диапазони с начална и крайна стойност. Така че един от диапазоните за A във файл A ще бъде 200-900, а диапазон за A във FileB ще бъде 150-1000. След това искам да сравня колко от диапазоните за A се припокриват с диапазони във FileB, което в горния пример би било едно.   -  person user2165857    schedule 01.05.2013


Отговори (1)


Бих предложил да получите за всеки файл диапазоните в този формат:

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