Jaki jest najskuteczniejszy sposób przechowywania zakresu liczbowego?

To pytanie dotyczy liczby bitów wymaganych do przechowywania zakresu. Lub inaczej: dla określonej liczby bitów jaki jest maksymalny zakres, który można zapisać i jak?

Wyobraź sobie, że chcemy przechowywać podzakres w zakresie 0–255.

Na przykład 45-74.

Możemy zapisać powyższy przykład jako dwa niepodpisane bajty, ale uderza mnie, że musi tam być pewna nadmiarowość informacji. Wiemy, że druga wartość jest większa niż pierwsza, więc w przypadku, gdy pierwsza wartość jest duża, dla drugiej wartości wymaganych jest mniej bitów, a w przypadku, gdy druga wartość jest duża, dla pierwszej wartości wymagana jest mniejsza liczba bitów .

Podejrzewam, że jakakolwiek technika kompresji przyniosłaby marginalny wynik, więc lepszym pytaniem może być pytanie „jaki jest maksymalny zakres, który można zapisać w jednym bajcie?”. To powinno być większe niż to, co można osiągnąć, przechowując dwie liczby osobno.

Czy są jakieś standardowe algorytmy do robienia takich rzeczy?

Wystarczy policzyć liczbę możliwych zakresów. Istnieje 256 zakresów z dolną granicą 0 (0-0, 0-1, ... 0-254, 0-255), 255 zakresów z dolną granicą 1, ... i wreszcie 1 zakres z dolną granicą 255 (255- 255). Łączna liczba wynosi (256 + 255 + ... + 1) = 257 * 128 = 32 896. Ponieważ jest to nieco więcej niż 2 ¹⁵ = 32 768, nadal będziesz potrzebować co najmniej 16 bitów (2 bajty) do przechowywania tych informacji.

Ogólnie dla liczb od 0 do n-1 liczba możliwych zakresów wynosi n * (n + 1) / 2. Jest to mniej niż 256, jeśli n wynosi 22 lub mniej: n = 22 daje 22 * ​​23/2 = 253 możliwości. Zatem jeden bajt wystarcza na podzakresy 0–21 .

Innym sposobem spojrzenia na problem jest: przechowywanie pary liczb całkowitych w zakresie od 0 do n-1 jest prawie takie samo jak przechowywanie podzakresu 0- (n-1) plus pojedynczy bit, który określa, czy pierwsza liczba jest niższy lub wyższy niż drugi. (Różnica polega na tym, że obie liczby całkowite są równe, ale ta szansa staje się coraz mniejsza, gdy n rośnie). Dlatego dzięki tej technice możesz zaoszczędzić tylko jeden bit i prawdopodobnie główny powód, dla którego jest rzadko używany.

W przypadku tak małej liczby bitów nie można zapisać wielu bitów, jak zauważył Glorfindel . Jeśli jednak domena, której używasz, ma jeszcze kilka bitów, możesz uzyskać znaczne oszczędności w przypadku średniej wielkości, kodując zakresy wartością początkową i deltą.

Załóżmy, że domeną są liczby całkowite, czyli 32 bity. Przy naiwnym podejściu potrzebujesz 64 bitów (początek, koniec) do przechowywania zakresu.

Jeśli przejdziemy do kodowania (start, delta), możemy z tego skonstruować koniec zakresu. Wiemy, że w najgorszym przypadku początek wynosi 0, a delta ma 32 bity.

2 ^ 5 wynosi 32, więc kodujemy długość delty w pięciu bitach (bez długości zerowej, zawsze dodajemy 1), a kodowanie staje się (początek, długość, delta). W najgorszym przypadku kosztuje to 32 * 2 + 5 bitów, czyli 69 bitów. W najgorszym przypadku, jeśli wszystkie zakresy są długie, jest to gorsze niż naiwne kodowanie.

W najlepszym przypadku kosztuje 32 + 5 + 1 = 38 bitów.

Oznacza to, że jeśli musisz zakodować wiele zakresów, a każdy z tych zakresów obejmuje tylko niewielką część Twojej domeny, to ostatecznie zużywasz mniej miejsca przy użyciu tego kodowania. Nie ma znaczenia, w jaki sposób rozdzielone są początki, ponieważ start zawsze zajmie 32 bity, ale ma znaczenie, w jaki sposób długości przedziałów są rozdzielone. Jeśli im więcej masz małych długości, tym lepsza kompresja, tym więcej zakresów, które pokrywają całą długość domeny, tym gorsze będzie to kodowanie.

Jeśli jednak masz wiele zakresów zgrupowanych wokół podobnych punktów początkowych (na przykład ponieważ otrzymujesz wartości z czujnika), możesz osiągnąć jeszcze większe oszczędności. Możesz zastosować tę samą technikę do wartości początkowej i użyć odchylenia, aby zrównoważyć wartość początkową.

Powiedzmy, że masz 10000 zakresów. Zakresy są pogrupowane wokół określonej wartości. Kodujesz odchylenie za pomocą 32 bitów.

Stosując podejście naiwne, potrzebujesz 32 * 2 * 10 000 = 640 000 bitów do przechowywania wszystkich tych zakresów.

Kodowanie odchylenia zajmuje 32 bity, a kodowanie każdego zakresu w najlepszym przypadku to 5 + 1 + 5 + 1 = 12 bitów, co daje w sumie 120 000 + 32 = 120 032 bitów. W najgorszym przypadku potrzebujesz 5 + 32 + 5 + 32 bitów, a więc 74 bitów, co daje łącznie 740 032 bitów.

Oznacza to, że dla 10 000 wartości w domenie, która wymaga 32 bitów do kodowania, otrzymujemy

• W najlepszym przypadku 120 032 bitów z inteligentnym kodowaniem delta
• 640 000 bitów z naiwnym początkowym, końcowym kodowaniem, zawsze (bez najlepszego lub najgorszego przypadku)
• 740 032 bitów w najgorszym przypadku z inteligentnym kodowaniem delta

Jeśli zastosujesz naiwne kodowanie jako punkt odniesienia, oznacza to oszczędność do 81,25% lub nawet 15 625% więcej kosztów.

W zależności od podziału wartości, oszczędności te są znaczące. Poznaj swoją domenę biznesową! Dowiedz się, co chcesz zakodować.

Jako rozszerzenie możesz również zmienić nastawienie. Jeśli analizujesz dane i identyfikujesz grupy wartości, możesz sortować dane do segmentów i kodować każdy z tych segmentów osobno, z własnym nastawieniem. Oznacza to, że możesz zastosować tę technikę nie tylko do zakresów zgrupowanych wokół jednej wartości początkowej, ale także do zakresów zgrupowanych wokół wielu wartości.

Jeśli punkty początkowe są równo rozłożone, to kodowanie nie działa tak dobrze.

To kodowanie jest oczywiście bardzo złe do indeksowania. Nie można po prostu odczytać x-tej wartości. Można go odczytać tylko sekwencyjnie. Co jest odpowiednie w niektórych sytuacjach, np. Przesyłanie strumieniowe przez sieć lub pamięć masową (np. Na taśmie lub HDD).

Ocena danych, grupowanie ich i wybranie właściwego odchylenia może być znaczną pracą i może wymagać pewnego dopracowania w celu uzyskania optymalnych wyników.

Tego rodzaju problem jest przedmiotem przełomowej pracy Claude'a Shannona „ Matematyczna teoria komunikacji” , która wprowadziła słowo „bit” i mniej więcej wymyśliła kompresję danych.

Ogólna idea jest taka, że ​​liczba bitów użytych do zakodowania zakresu jest odwrotnie proporcjonalna do prawdopodobieństwa wystąpienia tego zakresu. Załóżmy na przykład, że zakres 45–74 pojawia się około 1/4 czasu. Można powiedzieć, że sekwencja 00 odpowiada 45–74. Aby zakodować zakres 45–74, wyprowadzasz „00” i tam się zatrzymujesz.

Załóżmy również, że zakresy 99–100 i 140–155 pojawiają się mniej więcej w 1/8 czasu. Możesz zakodować każdy z nich za pomocą 3-bitowej sekwencji. Wszelkie 3 bity będą działać, o ile nie zaczynają się od „00”, który został już zarezerwowany dla zakresu 45–74.

00: 45-74
010: 99-100
101: 140-155

Możesz kontynuować w ten sposób, aż każdy możliwy zakres będzie kodowany. Najmniej prawdopodobny zakres może wymagać ponad 100 bitów. Ale to w porządku, ponieważ rzadko się pojawia.

Tam są algorytmy do znalezienia optymalnego kodowania. Nie będę próbował ich tutaj wyjaśniać, ale możesz znaleźć więcej, odwiedzając powyższy link lub szukając „Teorii informacji”, „Kodowania Shannon-fano” lub „Kodowania Huffmana”.

Jak zauważyli inni, prawdopodobnie lepiej jest przechowywać numer początkowy i różnicę między numerem początkowym i końcowym. Powinieneś użyć jednego kodowania na początek, a drugiego dla różnicy, ponieważ mają one różne rozkłady prawdopodobieństwa (i przypuszczam, że ten drugi jest bardziej zbędny). Jak sugeruje polygnome, najlepszy algorytm zależy od domeny.

Aby rozwinąć odpowiedź z @Glorfindel:

Jak n → ∞, (n - 1) → n. Zatem Ω (zakresy) → n² / 2 i log (Ω (zakresy)) → (2n - 1). Ponieważ naiwne kodowanie zajmuje 2 bity, asymptotyczna maksymalna kompresja oszczędza tylko 1 bit.

Istnieje podobna odpowiedź, ale aby uzyskać optymalną kompresję, potrzebujesz:

1. Optymalna metoda kodowania entropijnego (odczyt na temat kodowania arytmetycznego i zasadniczo równoważny (ten sam współczynnik kompresji, nieco szybszy, ale także trudniejszy do uchwycenia) ANS )
2. Jak najwięcej informacji o dystrybucji danych. Co najważniejsze, nie polega tylko na zgadywaniu, jak często może się pojawiać jedna liczba, ale często na pewno można wykluczyć pewne możliwości. Na przykład można wykluczyć przedziały o ujemnym rozmiarze i ewentualnie o rozmiarze 0, w zależności od sposobu zdefiniowania prawidłowego odstępu. Jeśli masz wiele interwałów do zakodowania jednocześnie, możesz je posortować, np. W kolejności malejącej szerokości lub zwiększającej wartość początkową / końcową, i wykluczyć wiele wartości (np. Jeśli gwarantujesz zamówienie przez zmniejszenie szerokości, poprzedni interwał miał szerokość 100, a wartość początkowa dla następnej wynosi 47, wystarczy wziąć pod uwagę możliwości do 147 dla wartości końcowych).

Co ważne, liczba 2 oznacza, że ​​chcesz zakodować rzeczy w taki sposób, aby na pierwszym miejscu były najbardziej wartościowe wartości (na kodowany bit). Na przykład, chociaż zasugerowałem kodowanie posortowanej listy „w stanie, w jakim się znajduje”, zwykle rozsądniej byłoby zakodować ją jako „drzewo binarne” - tzn. Jeśli są one posortowane według szerokości, a masz lenelementy, zacznij od kodowania elementu len/2. Powiedzmy, że miała szerokość w. Teraz znasz wszystkie elementy, zanim mają szerokość gdzieś w [0, w], a wszystkie elementy po nim mają szerokość gdzieś w [w, max val akceptujesz]. Powtarzaj rekurencyjnie (dzieląc każdą połowę listy ponownie na pół itp.), Dopóki nie obejmiesz lenelementów (chyba że zostanie to naprawione, będziesz chciał zakodowaćlennajpierw, abyś nie musiał zawracać sobie głowy końcowymi tokenami). Jeśli „max val you accept” jest naprawdę otwarte, może być mądre, aby najpierw zakodować najwyższą wartość, która faktycznie pojawia się w twoich danych, tj. Ostatni element, a następnie wykonać partycjonowanie binarne. Ponownie, cokolwiek jest najbardziej pouczające na bit.

Ponadto, jeśli najpierw kodujesz szerokość przedziału i znasz maksymalną możliwą wartość, z którą masz do czynienia, oczywiście możesz wykluczyć wszystkie wartości początkowe, które spowodowałyby przepełnienie ... masz pomysł. Przekształć i uporządkuj swoje dane w taki sposób, abyś mógł wnioskować jak najwięcej o reszcie danych podczas ich dekodowania, a optymalny algorytm kodowania entropijnego zapewni, że nie będziesz marnować bitów na informacje, które „już znasz” .