Python - Golomb編碼 (b=2n 和 b!=2n)

---

Golomb編碼是一種用於對具有特定分佈的非負整數進行編碼的資料壓縮技術。它由所羅門·W·戈隆佈於1966年提出，並已廣泛應用於各種應用中，包括影片和影像壓縮、資訊檢索和資料儲存。在本文中，我們將探討Golomb編碼，並瞭解兩種情況，即基數為2的冪(b=2^n)和基數不為2的冪(b ≠ 2^n)。

Golomb編碼 (b=2^n，基數為2的冪)

當基數為2的冪時，Golomb編碼變得相對簡單。讓我們考慮一個b = 4 (2^2)的例子。

當基數為2的冪時，查詢數字Golomb編碼的步驟。

確定商和餘數

要對一個數字(n)進行編碼，我們首先將其除以b，並得到商(q)和餘數(r)。在我們的例子中，假設n = 12。

n = 12

b = 4

q = n // b # quotient
r = n % b # remainder

因此，在我們的例子中

• q = 12 // 4 = 3

• r = 12 % 4 = 0

對商進行編碼

商(q)使用一元編碼進行編碼，這意味著它由q個連續的1後面跟著一個0表示。在我們的例子中，q = 3，所以q的一元編碼是“1110”（三個1後面跟著一個0）。

對餘數進行編碼

餘數(r)使用二進位制編碼進行編碼。由於b = 4，我們需要使用2位來編碼r。在我們的例子中，r = 0，可以用二進位制“00”表示。n = 12和b = 4的最終Golomb編碼是商的一元編碼和餘數的二進位制編碼的連線。因此，n = 12的Golomb編碼是“111000”。

Golomb編碼 (b ≠ 2^n，基數不為2的冪)

當基數不為2的冪時，編碼過程會稍微複雜一些。讓我們考慮一個b = 7的例子。

當基數不為2的冪時，查詢數字Golomb編碼的步驟。

確定商和餘數

與前面的情況類似，我們將數字(n)除以b以獲得商(q)和餘數(r)。假設n = 23。

n = 23

b = 7

q = n // b # quotient
r = n % b # remainder

在我們的例子中

• q = 23 // 7 = 3

• r = 23 % 7 = 2

對商進行編碼

商(q)使用一元編碼進行編碼，與前面的情況相同。因此，q = 3將在一元中表示為“1110”。

對餘數進行編碼

餘數(r)使用Rice編碼或二進位制編碼進行編碼。Rice編碼透過將r分成兩部分來對r進行編碼：字首和字尾。

字首計算

字首是透過計算k確定的，k是滿足2^k ≥ b的最小整數。在我們的例子中，b = 7，所以k = 3。我們計算範圍(R)為R = 2^k − b。在這種情況下，R = 2^3 − 7 = 1。如果r < R，我們使用k−1位二進位制編碼對r進行編碼。否則，我們使用k位二進位制編碼對r+R進行編碼。在我們的例子中，r = 2且R = 1。由於r < R，我們使用k−1 = 2位二進位制編碼對r = 2進行編碼。因此，r = 2將用二進位制“10”表示。n = 23和b = 7的最終Golomb編碼是商的一元編碼和編碼後的餘數r的連線。因此，n = 23的Golomb編碼是“111010”。

Golomb編碼實現

我們可以使用Python透過為一元編碼、二進位制編碼建立函式來實現Golomb編碼背後的邏輯。Golomb編碼的程式碼實現如下所示。

示例

在下面的示例中，unary_encoding函式對給定的商(q)執行一元編碼。它建立了一個由q個連續的“1”後跟一個“0”組成的字串，以一元表示商。binary_encoding函式對給定的餘數(r)和字首長度(k)執行二進位制編碼。如果r小於2^k和r的差，則它使用k−1位二進位制對r進行編碼。否則，它使用k位二進位制對r+2^k−r進行編碼。golomb_encoding函式對給定的數字(n)和基數(b)執行Golomb編碼。它分別透過執行整數除法和模運算來計算商(q)和餘數(r)。以下示例中涵蓋的案例是

• 如果基數(b)是2的冪（使用b & (b − 1) == 0檢查），它直接將餘數(r)轉換為二進位制，並用零填充以匹配b的二進位制表示的長度。

• 如果基數(b)不是2的冪，則它透過從b的二進位制表示的長度中減去3來計算字首長度(k)。然後，它呼叫binary_encoding函式使用字首長度(k)對餘數(r)進行編碼。

編碼後的Golomb數字是透過連線一元編碼的商(q)和二進位制編碼的餘數(r)獲得的。

def unary_encoding(q):
    """
    Perform unary encoding for the given quotient (q).
    """
    encoded = "1" * q + "0"
    return encoded


def binary_encoding(r, k):
    """
    Perform binary encoding for the given remainder (r) and prefix length (k).
    """
    if r < 2 ** k - r:
        encoded = bin(r)[2:].zfill(k - 1)
    else:
        encoded = bin(r + 2 ** k - r)[2:].zfill(k)
    return encoded


def golomb_encoding(n, b):
    """
    Perform Golomb encoding for the given number (n) and base (b).
    """
    q = n // b  # quotient
    r = n % b   # remainder

    unary_encoded = unary_encoding(q)
    if b & (b - 1) == 0:  # Check if b is a power of 2
        binary_encoded = bin(r)[2:].zfill(len(bin(b)) - 2)
    else:
        k = len(bin(b)) - 3  # Prefix length
        binary_encoded = binary_encoding(r, k)

    encoded = unary_encoded + binary_encoded
    return encoded


# Example usage
number = 23
base = 7

encoded_number = golomb_encoding(number, base)
print("Golomb Encoding for number", number, "with base", base, ":", encoded_number)

輸出

Golomb Encoding for number 23 with base 7 : 1110100

結論

在本文中，我們討論了Golomb編碼及其相關的兩種情況，即b=2^n和b ≠ 2^n。Golomb編碼是一種有用的資料壓縮技術，尤其適用於具有某些模式的非負整數分佈。在處理壓縮演算法、資訊檢索系統和其他資料密集型應用程式時，瞭解Golomb編碼非常有價值。