Elias omega coding

Elias ω kodlama veya Elias omega kodlama, Peter Elias tarafından geliştirilen pozitif tam sayıları kodlayan evrensel bir koda sahiptir. Elias gamma kodlama ve Elias delta kodlama gibi çalışır ancak kodların başına büyüklük sırasının bir temsilini ekliyor. Farklı olarak, Elias omega kodlaması bu öneki kodu yinelemeli olarak kodlar. Bu nedenle, bazen bu kodlar yinelemeli Elias kodları olarak da bilinir.

Omega kodlama, en büyük kodlanan değer bilinmediği uygulamalarda veya küçük değerlerin sıklıkla kullanıldığı verileri sıkıştırmak için kullanılır.

Bir pozitif tam sayı N'yi kodlamak için:

1. Kodun sonuna bir "0" yerleştirin.
2. Eğer N = 1 ise, durun; kodlama tamamlandı.
3. Kodun başına N'ın ikili temsilini ekleyin. Bu en az iki bit olacaktır, ilk bit 1 olacaktır.
4. N'i, yeni eklenen bit sayısından bir eksiği olan değere eşit yapın.
5. 2. adıma dönerek yeni N'ın kodlamasını öneklemeye devam edin.

Bir Elias omega kodlanmış pozitif tam sayıyı çözmek için:

1. N adında bir değişkenle başlayın ve onu 1 değerine ayarlayın.
2. Eğer sonraki bit "0" ise, durun. Çözülen sayı N'dır.
3. Eğer sonraki bit "1" ise, bir bit ve N kadar daha bit okuyun ve bu ikili sayıyı N'in yeni değeri olarak kullanın. 2. adıma geri dönün.

Örnekler

Omega kodları bazen "gruplar" olarak düşünülebilir. Bir grup, ya tek bir "0" bit, kodu sonlandıran bir bit olur veya en az iki bitlik bir grup olur. Bu gruplar 1 ile başlar ve başka bir grup izler.

İlk birkaç kod aşağıda gösterilmiştir. Ayrıca, "öngörülen dağılım" değeri için bu kodlama ile minimum uzunlukta kod elde edilecek değerlerin dağılımını tanımlar; evrensel kodlama ile gerçek sıkıştırmanın ilişkisine detaylı bilgi için bakınız.

Değer	Kod	Öngörülen olasılık
1	0	1/2
2	10 0	1/8
3	11 0	1/8
4	10 100 0	1/64
5	10 101 0	1/64
6	10 110 0	1/64
7	10 111 0	1/64
8	11 1000 0	1/128
9	11 1001 0	1/128
10	11 1010 0	1/128
11	11 1011 0	1/128
12	11 1100 0	1/128
13	11 1101 0	1/128
14	11 1110 0	1/128
15	11 1111 0	1/128
16	10 100 10000 0	1/2048
17	10 100 10001 0	1/2048
...
100	10 110 1100100 0	1/8192
1000	11 1001 1111101000 0	1/131,072
10,000	11 1101 10011100010000 0	1/2,097,152
100,000	10 100 10000 11000011010100000 0	1/268,435,456
1,000,000	10 100 10011 11110100001001000000 0	1/2,147,483,648

1 googol, 10¹⁰⁰, kodlaması şu şekildedir: 11 1000 101001100 (15 bit uzunluğundaki başlık), ardından 1 googol'un 333 bit ikili temsili, 10010 01001001 10101101 00100101 11001010 01100001 10111100 11101011 00001011 00100111 10000100 11000100 11001110 00001011 11110011 10001010 11001110 01000000 10001110 00100001 00011010 01111100 10101010 10110010 01000011 00001000 10101000 00101110 10001111 00010000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ve sonunda bir "0", toplam 349 bit.

10¹⁰⁰⁰⁰ gücündeki bir googol (10¹⁰⁰⁰⁰), 33,220 bit uzunluğundaki bir ikili sayıdır. Omega kodlaması 33,243 bit uzunluğundadır: 11 1111 1000000111000100 (22 bit), 33,220 bit değer ve son bir "0". Elias delta kodlama ile aynı sayı 33,250 bit uzunluğundadır: 000000000000000 1000000111000100 (31 bit) ve 33,219 bit değer. Omega ve delta kodlamaları, sıradan 33,220 bit uzunluğundaki ikili temsili sırasıyla %0.07 ve %0.09 daha uzundur.

Kod uzunluğu

Pozitif bir tam sayı Şablon:Math için gerekli bit sayısı, Şablon:Math, yinelemeli olarak:

$${\begin{aligned}B(0)&=0\,,\\B(N)&=1+\lfloor \log _{2}(N)\rfloor +B(\lfloor \log _{2}(N)\rfloor )\,.\end{aligned}}$$

Yani, tam sayı $N$ için Elias omega kodunun uzunluğu

$$1+(1+\lfloor \log _{2}N\rfloor {})+(1+\lfloor \log _{2}\lfloor \log _{2}N\rfloor {}\rfloor {})+\cdots$$

dir, burada terim sayısı, ikili yinelemeli logaritma ile sınırlandırılmıştır.

Daha açık olmak gerekirse, $f(x)=\lfloor \log _{2}x\rfloor {}$ olsun. $N>f(N)>f(f(N))>\cdots >f^{k}(N)=1$ için bir $k$ için, kodun uzunluğu $(k+1)+f(N)+f^{2}(N)+\dots +f^{k}(N)$dır. Çünkü $f(x)\leq \log _{2}x$, $k\leq \log _{2}^{*}(N)$dir.

Yinelemeli logaritma, herhangi bir sabit $n$ için tüm $\log _{2}^{n}N$'lerden daha yavaş büyür, bu nedenle asimptotik büyüme hızı $\Theta (\log _{2}N+\log _{2}^{2}N+\cdots )$dır, burada toplam bir altına düşünce durur.

Asimptotik optimumluk

Elias omega kodlama asimptotik olarak optimum bir önek kodudur.

Kanıt taslağı. Önek kod, Kraft eşitsizliği'ni karşılamalıdır. Elias omega kodlaması için Kraft eşitsizliği şu şekildedir:

$$\sum _{n=1}^{\infty }{\frac {1}{2^{O(1)+\log _{2}n+\log _{2}\log _{2}n+\cdots }}}\leq 1$$

Şimdi, toplam asimptotik olarak bir integral ile aynıdır, bize

$$\int _{1}^{\infty }{\frac {dx}{x\times \ln x\times \ln \ln x\cdots }}\leq O(1)$$

verir. Eğer görevci $\ln ^{k}x$ noktasında sonlandırılırsa, integral $\ln ^{k+1}\infty$ olarak dağılır. Ancak eğer görevci $(\ln ^{k}x)^{1+\epsilon }$ noktasında sonlandırılırsa, integral ${\frac {1}{(\ln ^{k}\infty )^{\epsilon }}}$ olarak bir araya gelir. Elias omega kodu, dağılma ve bir araya gelme arasındaki sınırda yer alır.

Örnek kod

Kodlama

void eliasOmegaEncode(char* source, char* dest)
{
    IntReader intreader(source);
    BitWriter bitwriter(dest);
    while (intreader.hasLeft())
    {
        int num = intreader.getInt();
        BitStack bits;
        while (num > 1) {
            int len = 0;
            for (int temp = num; temp > 0; temp >>= 1)  // calculate 1+floor(log2(num))
                len++;
            for (int i = 0; i < len; i++)
                bits.pushBit((num >> i) & 1);
            num = len - 1;
        }
        while (bits.length() > 0)
            bitwriter.putBit(bits.popBit());
        bitwriter.putBit(false);                        // write one zero
    }
    bitwriter.close();
    intreader.close();
}

Çözme

void eliasOmegaDecode(char* source, char* dest) {
    BitReader bitreader(source);
    IntWriter intwriter(dest);
    while (bitreader.hasLeft())
    {
        int num = 1;
        while (bitreader.inputBit())     // potentially dangerous with malformed files.
        {
            int len = num;
            num = 1;
            for (int i = 0; i < len; ++i)
            {
                num <<= 1;
                if (bitreader.inputBit())
                    num |= 1;
            }
        }
        intwriter.putInt(num);           // write out the value
    }
    bitreader.close();
    intwriter.close();
}

Genelleştirmeler

Şablon:See also Elias omega kodlama sıfır veya negatif tam sayıları kodlamaz. Tüm olumsuz tam sayıları kodlamak için bir yol, kodlamadan önce 1 eklemek ve sonrasında kodlamadan çıkarmaktır, veya Levenshtein coding kullanmaktır. Tüm tam sayıları kodlamak için bir yol, tüm sayıları (0, 1, -1, 2, -2, 3, -3, ...) kesin pozitif tam sayılara (1, 2, 3, 4, 5, 6, 7, ...) eşleştiren bir bijection kurmaktır.

Ayrıca bakınız

• Elias delta (δ) coding
• Elias gamma (γ) coding
• Even-Rodeh coding

İleri okuma

• Elias, Peter (March 1975). "Universal codeword sets and representations of the integers". IEEE Transactions on Information Theory. 21 (2): 194–203. doi:10.1109/tit.1975.1055349. 
• Şablon:Cite encyclopedia

• Python'da Uygulama

---

 Facebook Page

🐤 Twitter Follow us on Twitter !

Read or create/edit this page in another language

• Elias omega coding in English