Optymalizacja tablicę tribools na przestrzeni

Question

Zacznę jakimś tle:

Przez „tribool” Rozumiem zmienną, która może pomieścić jedną z następujących wartości: true, false lub null.

W pytaniu Copying array of ints vs pointers to bools, OP chciał mieć szereg tribooli (mniej więcej), które byłyby tak małe, jak to tylko możliwe.

Z "odrobiną" większości podstawowych bit-fu znalazłem rozwiązanie, które wykorzystywało 2 bity na tribool i pozwalało przechowywać tablicę OP z 64 tribools w 16 bajtach, co jest w porządku.

Mechanicy tribool używałem były proste, jak:

• Boolean oznacza "null lub nie null",
• logiczna B oznacza "prawda czy fałsz, jeśli nie jest pusta".

---

Ale potem pomyślałem ... An algorytmicznych definicja „bit” jest:

nieco to ilość informacji, która określa, który z dwóch równie prawdopodobnych zdarzeń powinien pojawić się.

Oczywiście wartość true/false jest 1-bitowa. Dwie wartości true-false jako całość są 2-bitowe.

A co z naszym konceptualnym tryboolem?

Moja uwaga: Pod względem wielkości zawartych informacji, tribool jest większy niż 1 bit, ale mniejszy niż 2 bity.

• Uzasadnienie 1: Załóżmy, że implementujemy nasze, jeśli boolean, jak opisano powyżej. Jeśli wartość logiczna A jest "null", wartość boolean B jest nadmiarowa i nie zawiera żadnych istotnych informacji.
• Uzasadnienie 2: To jest niemożliwe do przechowywania informacji z 2 niezależnych wartości logicznych w jednym tribool, więc ma

(Żadne z powyższych jest formalny dowód, ale wierzę, że możemy się zgodzić, że o " wielkość”tribool ściśle większe niż 1 bit i ściśle mniejsza niż 2.)

---

Moje pytanie brzmi:

Jak programowo skorzystać z faktu, że tribool mniej informacje niż 2 bity i implementować w oprogramowaniu (c, C++?) tablicę N tribooli, które miałyby ślad pamięci mniejszy niż N/4 bajtów dla niektórych N?

Tak, rozumiem, że taka implementacja nie jest naprawdę przyjazna sprzętowo i działałaby wolniej niż jakikolwiek typowy roztwór z nadmiarowości (jak te przedstawione w pytaniu PO). Po prostu zoptymalizujmy przestrzeń, a nie wydajność.

Oczywiście ta implementacja wymaga innej reprezentacji triboola niż pary zmiennych (która sama w sobie jest zbędna, jak opisano wcześniej). Teoria mówi, że możliwe jest osiągnięcie tego celu i chciałbym zobaczyć rzeczywistą implementację. Jakieś pomysły?

Answer 1

Twoja intuicja jest poprawna, jest to z pewnością możliwe. Jest to zasadniczo forma arithmetic coding lub przynajmniej prosta jej instancja.

Najprościej o tym myśleć, wyobrażając sobie kodowanie swojej tablicy "trybooli" jako liczby w bazie 3 - np. 0 = FALSE, 1 = TRUE, 2 = NULL. Następnie po tablicy:

{TRUE, FALSE, NULL, NULL, FALSE, FALSE, TRUE} 

koduje do liczby

1022001 

które można następnie przekształcić na dziesiętne w normalny sposób:

(1*3^0)+(0*3^1)+(0*3^2)+(2*3^3)+(2*3^4)+(0*3^5)+(1*3^6) = 946 

Każdy tribool zajmuje ln (3)/ln (2) bity (około 1,58), więc za pomocą tej metody można zapisać 20 tribooli w 32 bitach - tak więc można przechowywać tablicę N=20 w 4 bajtach (gdzie N/4 jest 5).

Answer 2

To rozwiązanie wymaga znajomości z góry liczby "niezerowych" wartości, które będziesz mieć (tj. Podczas kompilacji lub możesz zacząć liczyć ile nie-zer jest dostępnych przed udostępnieniem miejsca).

Następnie można zakodować go w następujący sposób:

0 dla wartości null 1 dla niezerowe, a następnie przez 1 lub 0 za prawdziwe lub fałszywe.

Może to skutkować maksymalnie 2 bitami na tribool i 1 bitem, jeśli wszystkie są zerowe.

Answer 3

MOŻESZ teoretycznie pakietu zmienne X N państwowe w

ln(N^X)/ln M 

M stanu (lub log_M (n^X) w notacji lateks podobne) zmiennych. Do przechowywania zmiennych trójstanowe w dwójkowym powyżej wzór przedstawia się następująco:

ln(3^N)/ln 2 

W 8-bitowego bajtu, przykładowo można dopasować 5 zmiennych trójstanowe.

Rozpakowywanie/modyfikowanie tych wartości byłoby o wiele trudniejsze i wolniejsze, ponieważ pakiety są gęstsze. W powyższym przykładzie musiałbyś przeliczyć cały bajt, aby zmienić pojedynczą zmienną trójstanową.

Należy zauważyć, że bajt dla 5 zmiennych trójstanowych jest dość wydajny przestrzennie. Gęstość pozostaje taka sama w bajtach, dopóki nie masz paczki 22 bajty, która może zmieścić 111 wartości tri-state, zamiast 110. Jednakże obsługa tego rodzaju pakowania byłaby bałaganem.

Czy coś wartego dodatkowej pracy w porównaniu do bezpośredniego przechowywania 4 wartości tri-state w bajcie?

Answer 4

@psmears ma rację, w przypadku, gdy wszystkie 3 wartości są jednakowo prawdopodobne. Jeśli jednak nie były one jednakowo prawdopodobne lub nie były niezależne, gdybyś miał ich wystarczająco długi ciąg, możesz po prostu użyć swojego 2-bitowego lub innego kodu i uruchomić na nim gzip. To powinno zmniejszyć ją do teoretycznego limitu. Podobnie jak w przypadku limitu, w którym wszystkie wartości wynosiły 0, powinien wyjść nie większy niż log długości łańcucha.

BTW: Mówimy tutaj o entropii tutaj. Prostą definicją w tym przypadku jest -P (0) logP (0) - P (1) logP (1) - P (zero) logP (null). Na przykład jeśli P (0) = P (1) = 1/2 i P (zero) = 0, to entropia jest 1 bitowa. Jeśli P (0) = 1/2, P (1) = 1/4, P (zero) = 1/4, to entropia wynosi 1/2 * 1 + 1/4 * 2 + 1/4 * 2 również = 1 bit. Jeśli prawdopodobieństwa wynoszą 1022/1024, 1/1024, 1/1024, to entropia wynosi (prawie 1) * (prawie 0) + 10/1024 + 10/1024, co jest około równe 20/1024 lub około 2 setne trochę! Im bardziej pewne jest coś, tym mniej mówi o tym, kiedy się pojawia, więc im mniej miejsca zajmuje.

Answer 5

Podoba mi się rozwiązanie zaproponowane przez @psmears, ale jego wadą jest to, że jest wolniejsze niż bezpośrednie podejście. Możesz użyć nieco zmodyfikowanej wersji, która również powinna być szybka:

3 ** 5 == 243, czyli prawie 256. Oznacza to, że możesz łatwo wycisnąć 5 wartości tribooli w bajcie. Ma taki sam współczynnik kompresji, ale ponieważ każdy bajt jest niezależny, może być zaimplementowany przy użyciu LUT:

unsigned char get_packed_tribool(unsigned char pk, int num) 
{ // num = (0..4), pk = (0..242) 
    return LUT[num][pk]; // 5*243 bytes of LUTs 
}; 

unsigned char update_packed_tribool(unsigned char old_pk, int num, int new_val) 
{ // new_val = 0..2 
    return old_pk + (new_val - LUT[num][old_pk])*POW3_LUT[num]; 
};