Wie listet man eine Bildsequenz auf effiziente Weise auf? Numercial Sequenzvergleich in Python

Question

Ich habe ein Verzeichnis von 9 Bilder:

 
image_0001, image_0002, image_0003 
image_0010, image_0011 
image_0011-1, image_0011-2, image_0011-3 
image_9999 

Ich möchte in der Lage sein, sie auf eine effiziente Art und Weise zu verzeichnen, wie folgt aus (4 Einträge für 9 Bilder):

 
(image_000[1-3], image_00[10-11], image_0011-[1-3], image_9999) 

Gibt es einen Weg in Python, um ein Verzeichnis von Bildern auf eine kurze/klare Art und Weise zurückzugeben (ohne jede Datei aufzulisten)?

Also, vielleicht so etwas wie dieses:

Liste alle Bilder, sortiert numerisch, erstellen Sie eine Liste (jedes Bild in der Reihenfolge von Startzählung). Wenn ein Bild fehlt (eine neue Liste erstellen), fahren Sie fort, bis die ursprüngliche Dateiliste beendet ist. Jetzt sollte ich nur einige Listen haben, die nicht gebrochene Sequenzen enthalten.

Ich versuche es zu erleichtern, eine Liste von Zahlen zu lesen/zu beschreiben. Wenn ich eine Abfolge von 1000 aufeinanderfolgenden Dateien hätte, könnte es eindeutig als Datei [0001-1000] anstelle der Datei ['0001', '0002', '0003' usw. aufgeführt werden]

Edit1 (basierend auf Vorschlag): Wie würden Sie die Glob-Muster ableiten, wenn Sie eine abgeflachte Liste verwenden?

Edit2 Ich versuche, das Problem in kleinere Stücke zu zerlegen. Hier ist ein Beispiel für einen Teil der Lösung: data1 Werke, Daten2 kehrt 0010 als 64, data3 (die reale Welt Daten) funktioniert nicht:

# Find runs of consecutive numbers using groupby. The key to the solution 
# is differencing with a range so that consecutive numbers all appear in 
# same group. 
from operator import itemgetter 
from itertools import * 

data1=[01,02,03,10,11,100,9999] 
data2=[0001,0002,0003,0010,0011,0100,9999] 
data3=['image_0001','image_0002','image_0003','image_0010','image_0011','image_0011-2','image_0011-3','image_0100','image_9999'] 

list1 = [] 
for k, g in groupby(enumerate(data1), lambda (i,x):i-x): 
    list1.append(map(itemgetter(1), g)) 
print 'data1' 
print list1 

list2 = [] 
for k, g in groupby(enumerate(data2), lambda (i,x):i-x): 
    list2.append(map(itemgetter(1), g)) 
print '\ndata2' 
print list2 

kehrt:

data1 
[[1, 2, 3], [10, 11], [100], [9999]] 

data2 
[[1, 2, 3], [8, 9], [64], [9999]] 

Answer 1

Hier ist ein Arbeits Umsetzung von dem, was Sie erreichen wollen, den Code mit Ihnen als Ausgangspunkt hinzugefügt:

#!/usr/bin/env python 

import itertools 
import re 

# This algorithm only works if DATA is sorted. 
DATA = ["image_0001", "image_0002", "image_0003", 
     "image_0010", "image_0011", 
     "image_0011-1", "image_0011-2", "image_0011-3", 
     "image_0100", "image_9999"] 

def extract_number(name): 
    # Match the last number in the name and return it as a string, 
    # including leading zeroes (that's important for formatting below). 
    return re.findall(r"\d+$", name)[0] 

def collapse_group(group): 
    if len(group) == 1: 
     return group[0][1] # Unique names collapse to themselves. 
    first = extract_number(group[0][1]) # Fetch range 
    last = extract_number(group[-1][1]) # of this group. 
    # Cheap way to compute the string length of the upper bound, 
    # discarding leading zeroes. 
    length = len(str(int(last))) 
    # Now we have the length of the variable part of the names, 
    # the rest is only formatting. 
    return "%s[%s-%s]" % (group[0][1][:-length], 
     first[-length:], last[-length:]) 

groups = [collapse_group(tuple(group)) \ 
    for key, group in itertools.groupby(enumerate(DATA), 
     lambda(index, name): index - int(extract_number(name)))] 

print groups 

Dieser druckt ['image_000[1-3]', 'image_00[10-11]', 'image_0011-[1-3]', 'image_0100', 'image_9999'], das ist, was Sie wollen.

GESCHICHTE: Ich antwortete zunächst die Frage rückwärts, wie @Mark Ransom unten hingewiesen. Aus Gründen der Geschichte war meine ursprüngliche Antwort:

Sie suchen nach glob. Versuchen:

import glob 
images = glob.glob("image_[0-9]*") 

Oder mit Ihrem Beispiel:

images = [glob.glob(pattern) for pattern in ("image_000[1-3]*", 
    "image_00[10-11]*", "image_0011-[1-3]*", "image_9999*")] 
images = [image for seq in images for image in seq] # flatten the list 

Answer 2

def ranges(sorted_list): 
    first = None 
    for x in sorted_list: 
     if first is None: 
      first = last = x 
     elif x == increment(last): 
      last = x 
     else: 
      yield first, last 
      first = last = x 
    if first is not None: 
     yield first, last 

Die increment Funktion wird für den Leser als Übung.

Bearbeiten: Hier ist ein Beispiel, wie es mit Ganzzahlen anstelle von Strings als Eingabe verwendet werden würde.

def increment(x): return x+1 

list(ranges([1,2,3,4,6,7,8,10])) 
[(1, 4), (6, 8), (10, 10)] 

Für jeden zusammenhängenden Bereich im Eingang erhalten Sie ein Paar, das den Anfang und das Ende des Bereichs angibt.Wenn ein Element nicht Teil eines Bereichs ist, sind die Start- und Endwerte identisch.

Answer 3

Okay, ich fand Ihre Frage zu einem faszinierenden Puzzle. Ich habe wie man "komprimiert" die numerischen Bereiche bis zu Ihnen (als TODO markiert), da gibt es verschiedene Möglichkeiten, das zu erreichen, je nachdem, wie Sie es formatiert und wenn Sie die Mindestanzahl von Elementen oder möchten die minimale Zeichenfolge Beschreibung Länge.

Diese Lösung verwendet einen einfachen regulären Ausdruck (Ziffernfolgen), um jede Zeichenfolge in zwei Gruppen zu klassifizieren: statisch und variabel. Nachdem die Daten klassifiziert sind, verwende ich groupby, um die statischen Daten in die längsten übereinstimmenden Gruppen zu sammeln, um den Zusammenfassungseffekt zu erzielen. Ich mische ganzzahlige index sentinals in das Ergebnis (in matchGrouper), so dass ich die variierenden Teile von allen Elementen (im entpacken) wieder auswählen kann.

import re 
import glob 
from itertools import groupby 
from operator import itemgetter 

def classifyGroups(iterable, reObj=re.compile('\d+')): 
    """Yields successive match lists, where each item in the list is either 
    static text content, or a list of matching values. 

    * `iterable` is a list of strings, such as glob('images/*') 
    * `reObj` is a compiled regular expression that describes the 
      variable section of the iterable you want to match and classify 
    """ 
    def classify(text, pos=0): 
     """Use a regular expression object to split the text into match and non-match sections""" 
     r = [] 
     for m in reObj.finditer(text, pos): 
      m0 = m.start() 
      r.append((False, text[pos:m0])) 
      pos = m.end() 
      r.append((True, text[m0:pos])) 
     r.append((False, text[pos:])) 
     return r 

    def matchGrouper(each): 
     """Returns index of matches or origional text for non-matches""" 
     return [(i if t else v) for i,(t,v) in enumerate(each)] 

    def unpack(k,matches): 
     """If the key is an integer, unpack the value array from matches""" 
     if isinstance(k, int): 
      k = [m[k][1] for m in matches] 
     return k 

    # classify each item into matches 
    matchLists = (classify(t) for t in iterable) 

    # group the matches by their static content 
    for key, matches in groupby(matchLists, matchGrouper): 
     matches = list(matches) 
     # Yield a list of content matches. Each entry is either text 
     # from static content, or a list of matches 
     yield [unpack(k, matches) for k in key] 

Schließlich fügen wir genug Logik hinzu, um ein hübsches Drucken der Ausgabe durchzuführen, und führen ein Beispiel aus.

def makeResultPretty(res): 
    """Formats data somewhat like the question""" 
    r = [] 
    for e in res: 
     if isinstance(e, list): 
      # TODO: collapse and simplify ranges as desired here 
      if len(set(e))<=1: 
       # it's a list of the same element 
       e = e[0] 
      else: 
       # prettify the list 
       e = '['+' '.join(e)+']' 
     r.append(e) 
    return ''.join(r) 

fnList = sorted(glob.glob('images/*')) 
re_digits = re.compile(r'\d+') 
for res in classifyGroups(fnList, re_digits): 
    print makeResultPretty(res) 

Meine Auswahl von Bildern aus Ihrem Beispiel erstellt. Sie können fnList mit der folgenden Liste für die Prüfung ersetzen:

fnList = [ 
'images/image_0001.jpg', 
'images/image_0002.jpg', 
'images/image_0003.jpg', 
'images/image_0010.jpg', 
'images/image_0011-1.jpg', 
'images/image_0011-2.jpg', 
'images/image_0011-3.jpg', 
'images/image_0011.jpg', 
'images/image_9999.jpg'] 

Und wenn ich gegen dieses Verzeichnis laufen, meine Ausgabe wie folgt aussieht:

StackOverflow/3926936% python classify.py 
images/image_[0001 0002 0003 0010].jpg 
images/image_0011-[1 2 3].jpg 
images/image_[0011 9999].jpg