Como dividir um conjunto de sobreposição de intervalos em intervalos não sobrepostas?
-
07-07-2019 - |
Pergunta
Vamos dizer que você tem um conjunto de intervalos:
- 0 - 100: 'a'
- 0-75: 'b'
- 95-150: 'c'
- 120-130: 'd'
Obviamente, estes intervalos se sobrepõem em determinados pontos. Como você dissecar esses intervalos para produzir uma lista de intervalos sem sobreposição, enquanto a informação reter associados à sua escala original (neste caso, a letra após o intervalo)?
Por exemplo, os resultados do acima após a execução do algoritmo seria:
- 0-75: 'a', 'b'
- 76-94: 'a'
- 95-100: 'a', 'c'
- 101-119: 'c'
- 120-130: 'c', 'd'
- 131-150: 'c'
Solução
Eu tive a mesma pergunta ao escrever um programa para misturar (parcialmente sobrepostas) amostras de áudio.
O que fiz foi adicionar um "start evento" e "evento de parada" (para cada item) para uma lista, classificar a lista por ponto de tempo, e depois processá-lo em ordem. Você poderia fazer o mesmo, excepto o uso de um ponto inteiro em vez de um tempo, e em vez de misturar sons que você estaria adicionando símbolos para o conjunto correspondente a um intervalo. Se você gerar faixas vazias ou apenas omiti-los seria opcional.
Edit
Talvez algum código ...
# input = list of (start, stop, symbol) tuples
points = [] # list of (offset, plus/minus, symbol) tuples
for start,stop,symbol in input:
points.append((start,'+',symbol))
points.append((stop,'-',symbol))
points.sort()
ranges = [] # output list of (start, stop, symbol_set) tuples
current_set = set()
last_start = None
for offset,pm,symbol in points:
if pm == '+':
if last_start is not None:
#TODO avoid outputting empty or trivial ranges
ranges.append((last_start,offset-1,current_set))
current_set.add(symbol)
last_start = offset
elif pm == '-':
# Getting a minus without a last_start is unpossible here, so not handled
ranges.append((last_start,offset-1,current_set))
current_set.remove(symbol)
last_start = offset
# Finish off
if last_start is not None:
ranges.append((last_start,offset-1,current_set))
Totalmente testado, obviamente.
Outras dicas
Eu diria que criar uma lista de pontos de extremidade e classificá-lo, também indexar a lista de faixas por pontos inicial e final. Em seguida, percorrer a lista de terminais ordenadas, e para cada um, verificar os intervalos para ver quais são iniciar / parar nesse ponto.
Este é provavelmente melhor representados em código ... se seus intervalos são representados por tuplas:
ranges = [(0,100,'a'),(0,75,'b'),(95,150,'c'),(120,130,'d')]
endpoints = sorted(list(set([r[0] for r in ranges] + [r[1] for r in ranges])))
start = {}
end = {}
for e in endpoints:
start[e] = set()
end[e] = set()
for r in ranges:
start[r[0]].add(r[2])
end[r[1]].add(r[2])
current_ranges = set()
for e1, e2 in zip(endpoints[:-1], endpoints[1:]):
current_ranges.difference_update(end[e1])
current_ranges.update(start[e1])
print '%d - %d: %s' % (e1, e2, ','.join(current_ranges))
Embora a olhar para isso em retrospecto, eu ficaria surpreso se não houvesse uma forma mais eficiente (ou pelo menos mais limpo-olhando) maneira de fazê-lo.
O que você descreve é ??um exemplo da teoria dos conjuntos. Para um algoritmo geral para os sindicatos, interseções e diferenças de conjuntos de computação ver:
www.gvu.gatech.edu/~jarek/graphics /papers/04PolygonBooleansMargalit.pdf
Enquanto o papel está voltado para gráficos é aplicável a teoria dos conjuntos em geral. Não é exatamente material de leitura luz.
Pseudocódigo:
unusedRanges = [ (each of your ranges) ]
rangesInUse = []
usedRanges = []
beginningBoundary = nil
boundaries = [ list of all your ranges' start and end values, sorted ]
resultRanges = []
for (boundary in boundaries) {
rangesStarting = []
rangesEnding = []
// determine which ranges begin at this boundary
for (range in unusedRanges) {
if (range.begin == boundary) {
rangesStarting.add(range)
}
}
// if there are any new ones, start a new range
if (rangesStarting isn't empty) {
if (beginningBoundary isn't nil) {
// add the range we just passed
resultRanges.add(beginningBoundary, boundary - 1, [collected values from rangesInUse])
}
// note that we are starting a new range
beginningBoundary = boundary
for (range in rangesStarting) {
rangesInUse.add(range)
unusedRanges.remove(range)
}
}
// determine which ranges end at this boundary
for (range in rangesInUse) {
if (range.end == boundary) {
rangesEnding.add(range)
}
}
// if any boundaries are ending, stop the range
if (rangesEnding isn't empty) {
// add the range up to this boundary
resultRanges.add(beginningBoundary, boundary, [collected values from rangesInUse]
for (range in rangesEnding) {
usedRanges.add(range)
rangesInUse.remove(range)
}
if (rangesInUse isn't empty) {
// some ranges didn't end; note that we are starting a new range
beginningBoundary = boundary + 1
}
else {
beginningBoundary = nil
}
}
}
Teste de unidade:
No final, resultRanges deve ter os resultados que você está procurando, unusedRanges e rangesInUse deve estar vazio, beginningBoundary deve ser nulo, e usedRanges deve conter o que unusedRanges usado para conter (mas classificado por range.end).
Uma resposta similar a Edmunds, testados, incluindo suporte para intervalos como (1,1):
class MultiSet(object):
def __init__(self, intervals):
self.intervals = intervals
self.events = None
def split_ranges(self):
self.events = []
for start, stop, symbol in self.intervals:
self.events.append((start, True, stop, symbol))
self.events.append((stop, False, start, symbol))
def event_key(event):
key_endpoint, key_is_start, key_other, _ = event
key_order = 0 if key_is_start else 1
return key_endpoint, key_order, key_other
self.events.sort(key=event_key)
current_set = set()
ranges = []
current_start = -1
for endpoint, is_start, other, symbol in self.events:
if is_start:
if current_start != -1 and endpoint != current_start and \
endpoint - 1 >= current_start and current_set:
ranges.append((current_start, endpoint - 1, current_set.copy()))
current_start = endpoint
current_set.add(symbol)
else:
if current_start != -1 and endpoint >= current_start and current_set:
ranges.append((current_start, endpoint, current_set.copy()))
current_set.remove(symbol)
current_start = endpoint + 1
return ranges
if __name__ == '__main__':
intervals = [
(0, 100, 'a'), (0, 75, 'b'), (75, 80, 'd'), (95, 150, 'c'),
(120, 130, 'd'), (160, 175, 'e'), (165, 180, 'a')
]
multiset = MultiSet(intervals)
pprint.pprint(multiset.split_ranges())
[(0, 74, {'b', 'a'}),
(75, 75, {'d', 'b', 'a'}),
(76, 80, {'d', 'a'}),
(81, 94, {'a'}),
(95, 100, {'c', 'a'}),
(101, 119, {'c'}),
(120, 130, {'d', 'c'}),
(131, 150, {'c'}),
(160, 164, {'e'}),
(165, 175, {'e', 'a'}),
(176, 180, {'a'})]