Kompaktowa reprezentacja ścieżek na wykresie

Mam podzbiór prostych ścieżek na wykresie. Długość ścieżek jest ograniczona $d$ .

Jaki jest najbardziej zwarty sposób (pod względem pamięci), w jaki sposób mogę reprezentować ścieżki, tak aby nie były reprezentowane żadne inne ścieżki oprócz wybranych?

Zauważ, że chcę użyć tej reprezentacji w algorytmie, który będzie powtarzał się przez ten podzbiór ścieżek w kółko i że chcę być dość szybki, więc na przykład nie mogę używać żadnych standardowych algorytmów kompresji.

Jedną z wyobrażeń, które przyszły mi do głowy, było przedstawienie ich jako zbioru drzew. Zgaduję jednak, że doprowadzenie do optymalnej liczby drzew jest trudne NP? Jakie inne reprezentacje byłyby dobre?

graphs data-structures Optować
źródło

Kiedy „iterując ten podzbiór”, jakich informacji na temat każdej ścieżki potrzebujesz? Długość? Odwiedzone węzły? Skrzyżowanie z innymi ścieżkami? ... Tam może być

2^{d}

$2^d$ wielu, więc musisz być przygotowany na „niezbyt szybki”, jeśli chcesz przechowywać całe ścieżki.

Raphael

Nie wiem, czy otrzymałeś ścieżki przez jakiś nieznany proces, czy nie, ale być może możesz zrobić księgowość podczas obliczania interesujących ścieżek. Szybki pomysł: niech

G

$G$ być grafem nadrzędnym i ustawić wagę każdej krawędzi na zero. Kiedy znajdziesz ścieżkę zainteresowania

P

$P$ , zwiększ wagę każdej krawędzi w

G

$G$ to jest w

P

$P$ . Na koniec waga krawędzi informuje, ile ścieżek pojawia się na tej krawędzi. Może mógłbyś teraz obliczyć minimalne drzewo rozpinające

G

$G$ i upuść wszystkie krawędzie o zerowej wadze lub coś w tym rodzaju.

Juho

Cóż, nawet połączenie dwóch rozłącznych krawędzi prostych ścieżek może stworzyć cykl, więc obliczenie MST spowoduje, że zgubisz jedną ze ścieżek. Ale powyższe może dać ci kilka pomysłów.

Juho

Możesz sprawdzić artykuł Eppsteina na

k

$k$ najkrótsze ścieżki i związana z nimi literatura. Dotyczą one również zwartych reprezentacji.

Juho

istnieje pewna możliwość użycia FSM do reprezentowania ścieżek, a następnie można wykonać podstawowe operacje, takie jak połączenia, skrzyżowania, odejmowanie itp., a także operacja „kompresji” minimalizacji FSM jest dobrze zrozumiana / optymalna i wydajna. nie widziałem tego w artykule, ale zaproponował inny, nieco podobny problem ...

dniu

Odpowiedzi:

Trie może załatwić sprawę: http://en.wikipedia.org/wiki/Trie

Oznacz każdą krawędź wykresu literą. Następnie dodaj ciągi, które reprezentują ścieżki przez wykres do trie. Aby spełnić wymóg „nie są reprezentowane żadne inne ścieżki oprócz wybranych”, możesz pozostawić wszystkie wierzchołki trie puste i oznaczyć krawędzie, chyba że krawędzie prowadzące od nasady do wierzchołka reprezentują jedną z twoich ścieżek, a następnie oznacz wierzchołek czymś. Wartość bool, liczba ścieżek w ramach niektórych zamówień itp.

Po zbudowaniu trie istnieją algorytmy kompresji w celu uzyskania optymalnej (lub prawie optymalnej) reprezentacji. (zobacz powiązany artykuł w Wikipedii).

Prawdziwy John Connor
źródło

Ciekawy. Trie ma jednak znacznie większy zestaw specyfikacji, na których tak naprawdę mi nie zależy (szybkie wyszukiwanie, skojarzenie z kluczem itp.), Więc zastanawiam się, czy możliwe jest coś lepszego ...

Opt

Być może powinieneś rzucić okiem na zwięzłe struktury danych . Są to struktury danych, które próbują przechowywać informacje w przestrzeni blisko teoretycznej dolnej granicy, zachowując jednocześnie możliwość wykonywania na nich operacji.

Istnieją takie struktury dla drzew, słowników itp. Nie przypominam sobie żadnych, które mogłyby zrobić dokładnie to, co chcesz, ale być może niektóre ich kombinacje lub modyfikacje mogłyby ci pomóc.

Jakub Kotowski
źródło

W zależności od złożoności i przetwarzania wstępnego / końcowego wymaganego dla algorytmu, być może najprostszą opcją jest sposób. Możesz w prosty sposób przedstawić je jako tablice i zapisać w postaci skompresowanej w HDF5. Ta biblioteka jest wyposażona w niektóre algorytmy szybkiej kompresji, dzięki czemu odczytywanie i zapisywanie skompresowanych danych może być nawet szybsze niż nieskompresowane.

Oto kilka wątków:

Czas sekwencyjnego dostępu do elementu dla tablicy 15 GB i różnych wielkości porcji:

Szybkość dekompresji za pomocą Blosc na PyTables: wprowadź opis zdjęcia tutaj

A jeśli są ograniczone długością, można je przechowywać w tabeli, a tym samym prawdopodobnie zyskać nieco więcej miejsca. A podczas pobierania ich z pamięci masz je już w bardzo dogodnej formie, aby zastosować swój algorytm.

Davidmh
źródło