Python3 - verlustfreie Komprimierung von langen verschachtelten Listen

Question

Ich schreibe einen Komprimierungsalgorithmus, um die Größe einer kombinatorischen Ausgabe zu reduzieren, die eine Permutation vieler Eingangszustände ist. Das Ändern des Formats ist keine Option.

Ziel ist es, Informationen über Kombinationen von Eingaben zu erhalten, die eine bestimmte Ausgabe erzeugen, so dass einzelne Eingabezustände in Token umgewandelt werden können, wenn sie die Ausgabe nicht beeinflussen, abhängig von allen anderen Eingabezuständen.

Ich habe zwei Liste von Listen,

inputs = [      | outputs = [ 
      [1,0,0.5,"foo"], |     [-0.25,"cold"],  
      [0,1,-0.5,"poo"], |     [0.66,"hot"], 
        .    |      . 
        .    |      . 
        .    |      . 
     ]      |    ] 

Eigenschaften:

• Ein- und Ausgangslisten sind gleich lang und sehr lang, so dass Speicher ist ein Anliegen

• Bereits gepaart mit Index

• Unterlisten sind kurz a nd intern konsistent in Länge und Art innerhalb der Eingangs- und Ausgangslisten

• Teillisten von heterogenem Typ zusammengesetzt sind, aber ich kann sie alle zu bespannen gegossen, wenn nötig

Ich werde sie in eine Hash passieren Funktion wie so:

list(map(lambda results: hashfunction(results[0],results[1]), list(zip(inputs,outputs)))) 

Soweit ich weiß, das ist ein Speicher effizienter Weg, um sie zu durchlaufen, aber bevor ich das tue, möchte ich ihre Länge so viel wie möglich reduzieren.

Da die Unterlisten intern konsistent sind, und ich weiß, einige Indizes boolean sind, für gleiche Ausgangsteillisten kann ich die Eingangsunterlisten wie dies ohne Informationsverlust reduzieren:

inputs = [... ,[1,0,0.5,1],[0,0,0.5,1], ...] 
outputs = [... ,[0.3,"warm"],[0.3,"warm"], ...] 

Ist tokenized in-situ als:

inputs = [... ,["don't care",0,0.5,1], ...] 
outputs = [... ,[0.3,"warm"], ...] 

und die Länge der beiden Ein- und Ausgänge von 1.

Weiterhin reduziert werden, will ich höhere Radix Eingangs col zusammenzupressen UMNS, zum Beispiel, wenn ich weiß, dass Index 2 in jedem Eingang sublist nimmt nur die Werte [-0.5,0,0.5], wenn ich dieses Muster finden:

inputs = [... ,["don't care",0,-0.5,1],["don't care",0,0,1],["don't care",0,0.5,1], ...] 
outputs = [... ,[0.1,"cake"],[0.1,"cake"],[0.1,"cake"], ...] 

Ich mag sie reduzieren ähnlich:

inputs = [... ,["don't care",0,"don't care",1], ...] 
outputs = [... ,[0.1,"cake"], ...] 

Leider sind die Muster möglicherweise nicht nebeneinander, so dass ich zu großen Mengen an Sortierung und Neusortierung zurückgreifen muss, um reduzierbare Muster zu finden und nicht nur die Ergebnismenge nicht genug zu komprimieren, die Laufzeit/Speicher ist unhaltbar.

Alle Ratschläge sehr geschätzt.

Dank

Answer 1

ich dies zu betrachten und denken: "map-reduzieren".

Insbesondere möchten Sie jeden Index auf einen Schlüssel, der die Ausgabe ist, und einen Wert, der die Eingabe ist, zuordnen. Für jede mögliche Ausgabe möchten Sie alle möglichen Eingabewerte betrachten und eine Reihe von Operationen ausführen, um den Ausdruck für die Eingabe zu komprimieren. Sie können diese Operation jedoch jeweils an einem Ausgang ausführen.

Wenn Speicher kein Problem wäre, würden Sie einfach Schlüssel/Werte-Paar in einem Wörterbuch speichern, dessen Schlüssel die Ausgabe ist. Und iteriere durch das Wörterbuch.

Wenn der Speicher eine Herausforderung darstellt, können Sie Daten in eine Datei im Format output, input schreiben, ein externes sort-Dienstprogramm verwenden, um es zu sortieren und dann zu verarbeiten. (Sei gewarnt, Unix-Sortierung benötigt ein wenig Nachhilfe, um eine ascibetische Sortierung zu machen, und das musst du wirklich getan haben.) Wenn du diese Datei bearbeitest, solltest du einen Iterator haben, der Zeile für Zeile liest und eine Ausgabe mit ergibt alle Eingänge, die dort angekommen sind. Dieser Iterator wird von einer Funktion verarbeitet, die diese Daten manipuliert und Ihre komprimierten Ein-/Ausgabe-Regeln ausgibt.