Kompakte Darstellung von Pfaden in einem Diagramm

Ich habe eine Teilmenge der einfachen Pfade in einem Diagramm. Die Länge der Pfade wird durch . $d$

Was ist die kompakteste Art (speichertechnisch), wie ich die Pfade so darstellen kann, dass außer den ausgewählten Pfaden keine anderen Pfade dargestellt werden?

Beachten Sie, dass ich diese Darstellung in einem Algorithmus verwenden möchte, der diese Teilmenge von Pfaden immer wieder durchläuft, und dass ich ziemlich schnell sein möchte, sodass ich beispielsweise keine Standardkomprimierungsalgorithmen verwenden kann.

Eine Darstellung, die mir in den Sinn kam, war die Darstellung als eine Reihe von Bäumen. Ich vermute aber, dass es NP-schwer ist, es auf eine optimale Anzahl von Bäumen zu bringen? Welche anderen Darstellungen wären gut?

graphs data-structures Opt
quelle

Welche Informationen zu jedem Pfad benötigen Sie beim "Durchlaufen dieser Teilmenge"? Länge? Besuchte Knoten? Schnittpunkte mit anderen Pfaden? ... Es kann viele geben, also müssen Sie auf "nicht wirklich schnell" vorbereitet sein, wenn Sie ganze Pfade speichern müssen.

2^{d}

$2^d$

Raphael

Ich weiß nicht, ob Sie die Pfade nur durch einen unbekannten Prozess erhalten haben oder nicht, aber vielleicht können Sie eine Buchhaltung durchführen, während Sie die Pfade von Interesse berechnen. Schnelle Idee: Lassen Sie das Host-Diagramm sein und setzen Sie das Gewicht jeder Kante auf Null. Wenn Sie einen Pfad von Interesse , erhöhen Sie das Gewicht jeder Kante in , die in . Am Ende gibt das Kantengewicht an, in wie vielen Pfaden diese Kante angezeigt wird. Vielleicht könnten Sie jetzt einen minimalen Spannbaum von berechnen und alle Kanten mit dem Gewicht Null oder so etwas fallen lassen.

G

$G$

P

$P$

G

$G$

P

$P$

G

$G$

Juho

Nun, selbst die Vereinigung von zwei kantendisjunkten einfachen Pfaden kann einen Zyklus erzeugen. Wenn Sie also den MST berechnen, verlieren Sie einen der Pfade, die ich denke. Aber das Obige könnte Ihnen einige Ideen geben.

Juho

k

$k$

Es gibt eine Möglichkeit, FSMs zur Darstellung von Pfaden zu verwenden, und dann kann man grundlegende Operationen wie Gewerkschaften, Schnittpunkte, Subtraktionen usw. ausführen, und auch die "Komprimierungs" -Operation zur Minimierung von FSMs ist gut verstanden / optimal und effizient. Ich habe dies nicht in einem Papier gesehen, sondern es für ein anderes, etwas ähnliches Problem vorgeschlagen ...

vzn

Antworten:

Ein Trie könnte den Trick machen: http://en.wikipedia.org/wiki/Trie

Beschriften Sie jede Kante Ihres Diagramms mit einem Buchstaben. Fügen Sie dann die Zeichenfolgen, die Pfade durch Ihr Diagramm darstellen, zum Versuch hinzu. Um die Anforderung zu erfüllen, dass "außer den ausgewählten Pfaden keine anderen Pfade dargestellt werden", können Sie alle Scheitelpunkte des Versuchs leer lassen und die Kanten beschriften, es sei denn, die von der Wurzel zum Scheitelpunkt führenden Kanten stellen dann einen Ihrer Pfade dar Beschriften Sie den Scheitelpunkt mit etwas. Ein Bool, die Nummer des Pfades unter einer bestimmten Reihenfolge usw.

Sobald Sie Ihren Versuch erstellt haben, gibt es Algorithmen, um ihn auf eine optimale (oder nahezu optimale) Darstellung zu komprimieren. (Siehe den verlinkten Wikipedia-Artikel.)

Echter John Connor
quelle

Interessant. Ein Trie kommt jedoch mit einem viel größeren Satz von Spezifikationen, die mir nicht wirklich wichtig sind (schnelle Suche, Zuordnung zu einem Schlüssel usw.), also frage ich mich, ob etwas Besseres möglich ist ...

Opt

Vielleicht sollten Sie sich prägnante Datenstrukturen ansehen . Es handelt sich um Datenstrukturen, die versuchen, Informationen in einem Raum nahe der informationstheoretischen Untergrenze zu speichern, während die Fähigkeit erhalten bleibt, Operationen an ihnen durchzuführen.

Es gibt solche Strukturen für Bäume, Wörterbücher usw. Ich erinnere mich an keine, die genau das tun würden, was Sie wollen, aber vielleicht würde Ihnen eine Kombination oder Modifikation davon helfen.

Jakub Kotowski
quelle

Abhängig von der Komplexität und der für Ihren Algorithmus erforderlichen Vor- / Nachbearbeitung ist die einfachste Option möglicherweise der Weg. Sie können sie trivial als Arrays darstellen und in einem HDF5 komprimiert speichern. Diese Bibliothek ist mit einigen schnellen Komprimierungsalgorithmen ausgestattet, sodass das Lesen und Schreiben komprimierter Daten möglicherweise noch schneller als unkomprimiert ist.

Hier sind einige Handlungen:

Sequentielle Zugriffszeit pro Element für ein 15 GB EArray und verschiedene Blockgrößen:

Dekomprimierungsgeschwindigkeit mit Blosc auf PyTables: Geben Sie hier die Bildbeschreibung ein

Und wenn sie in der Länge begrenzt sind, können Sie sie in einem Tisch aufbewahren und so wahrscheinlich etwas mehr Platz gewinnen. Und wenn Sie sie aus dem Speicher abrufen, haben Sie sie bereits in einer sehr praktischen Form, um Ihren Algorithmus anzuwenden.

Davidmh
quelle