Zmiana kolejności danych (zestawu ciągów) w celu zoptymalizowania pod kątem kompresji?

12

Czy są jakieś algorytmy zmiany kolejności danych w celu optymalizacji pod kątem kompresji? Rozumiem, że jest to specyficzne dla danych i algorytmu kompresji, ale czy jest jakieś słowo na ten temat? Gdzie mogę znaleźć badania w tej dziedzinie?

W szczególności mam listę jsonów o wartości 1,5 miliona ciągów i chcę zmienić kolejność ciągów, aby zoptymalizować kompresję gzip (dla HTTP). Sortowanie ciągów ma się całkiem dobrze, ale tak naprawdę nie wiem, czy to jest optymalne.

optimization permutations

— Jayen
źródło

1

Optymalnie zmieniające kolejność struny do kompresji gzip (LZ77 z małym przesuwnym oknem) brzmi jak trudny NP. Prawdopodobnie możesz wymyślić redukcję najkrótszego typowego problemu superstrun.

— Jouni Sirén,

@ JouniSirén Myślę, że najdłuższy wspólny podciąg jest lepszym podejściem, ponieważ najkrótszy wspólny podciąg ogranicza mnie do posiadania wspólnej części jeden po drugim, prawda? Nie przeszkadza mi NP-trudny, o ile jest to wykonalne (jak bieganie na nowoczesnej maszynie).

— Jayen

6

Jest to dodatek do odpowiedzi Navin Goyal.

Ponieważ plik JSON można traktować jako strukturę danych drzewa, można użyć transformacji XBW dla drzew, która jest rozszerzeniem transformacji Burrows-Wheeler dla łańcuchów.

— Hiroki Yanagisawa
źródło

1

Dziękuję za to. Mam tylko listę / tablicę JSON, a nie żadnych obiektów JSON, więc nie widzę, jak można ją traktować jako drzewo. Mógłbym przekonwertować ciągi na trie, ale potem nie widzę, jak to się odnosi do transformacji XBW.

— Jayen

4

Burrows - Transformacja Wheelera jest dobrze znanym algorytmem kompresji, który działa poprzez zmianę kolejności znaków w ciągu, który ma zostać skompresowany.

— Navin Goyal
źródło

1

Dzięki za to, ale nie jestem pewien, jak mogę wykorzystać te informacje. Chcę zmienić kolejność ciągów na liście do skompresowania, ale nie obchodzi mnie, czy mogę odzyskać pierwotną kolejność.

— Jayen

1

Aby poprawić kompresję gzip, chcesz, aby „podobne” ciągi były blisko listy. Istnieje wiele sposobów zdefiniowania takiego podobieństwa; Pozwól mi opisać rozsądny, który sprawdza się w praktyce. Przypomnij sobie, że rozmiar bloku gzip to 64 KB. W ten sposób dane zostaną podzielone na bloki o wielkości 64 KB, a każdy blok zostanie skompresowany niezależnie. Aby zoptymalizować kompresję, trzeba by zminimalizować liczbę różnych k-merów (podciągów o rozmiarze k) w każdym bloku. Motywacja polega na tym, że wszystkie takie podciągi zostaną zastąpione identyfikatorem.

Chociaż powyższy problem jest trudny teoretycznie (jest to wariant partycjonowania hipergraphowego), istnieją szybkie praktyczne algorytmy. Polecam LSH-jak klastry, które mogą być realizowane w jednym przejściu nad swoimi danymi. Zauważ, że sortowanie (alfabetyczne) to kolejny sposób na „grupowanie” podobnych ciągów razem. Jednak wyspecjalizowane algorytmy klastrowania mogą działać lepiej.

Alternatywą jest użycie zstd , który jest (i) szybszy, (ii) uzyskuje wyższe współczynniki kompresji, a (iii) nie ma ograniczeń rozmiaru bloku (a zatem równie dobrze kompresuje ciągi, niezależnie od kolejności wprowadzania).

— Siergiej Pupyrev
źródło

0

Jakiś czas temu widziałem algorytm, który może być przydatny. Wykorzystuje algorytm edycji odległości do obliczania odległości między każdym słowem. W ten sposób tworzy wykres, dla którego każda krawędź jest tą odległością. Wreszcie, otrzymuje polecenie wyboru ścieżki, która ma najniższą sumę wag. Może to może poprawić gzip.

— Rafael Ribeiro
źródło

to nie brzmi wykonalnie, ale jeśli ktoś spróbuje, napisz komentarz z wynikami

— Jayen

Spróbuję to przetestować. Jestem ciekawy tego problemu. Poza tym, dlaczego według ciebie nie jest to wykonalne?

— Rafael Ribeiro,

o ile wiem, odległość edycji wynosi O (nm), gdzie n i m to liczba liter w parze łańcuchów i musisz to zrobić dla każdej pary łańcuchów O (s ^ 2), więc jeśli n = m, to jest O (s ^ 2 * n ^ 2), co dla mnie brzmi dla 1,5 miliona strun.

— Jayen

Och, nie martwiłem się tak bardzo o złożoność, ponieważ myślałem, że twoim problemem jest zmniejszenie tylko rozmiaru binarnego. Więc ta operacja będzie występować częściej, prawda?

— Rafael Ribeiro

Szukałem tutaj i być może koszt edytowania można zmniejszyć za pomocą automatów levenshtein

— Rafael Ribeiro