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
źródło
Odpowiedzi:
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.
źródło
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.
źródło
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).
źródło
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.
źródło