Skip to content

Instantly share code, notes, and snippets.

@NTT123

NTT123/arithmetic-coding.ipynb

Created June 24, 2018 07:30
Show Gist options
  • Save NTT123/9b730e84af0883628b5944dfb43b2d8b to your computer and use it in GitHub Desktop.
Save NTT123/9b730e84af0883628b5944dfb43b2d8b to your computer and use it in GitHub Desktop.
Download ZIP
Arithmetic Coding
Display the source blob
Display the rendered blob
Raw
arithmetic-coding.ipynb
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"name": "Arithmetic Coding",
"version": "0.3.2",
"provenance": [],
"collapsed_sections": [
"a7t_ijvhspaj"
],
"toc_visible": true,
"include_colab_link": true
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3"
}
},
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "view-in-github",
"colab_type": "text"
},
"source": [
"[View in Colaboratory](https://colab.research.google.com/gist/NTT123/9b730e84af0883628b5944dfb43b2d8b/arithmetic-coding.ipynb)"
]
},
{
"metadata": {
"id": "KvZ4NIrxwVTb",
"colab_type": "text"
},
"cell_type": "markdown",
"source": [
"#Arithmetic Coding \n",
"\n",
"Arithmetic coding (AC) là thuật toán nén dữ liệu dựa trên lý thuyết thông tin. Nó cho phép chúng ta lưu trữ thông tin với số lượng bits tối thiểu. Claude Shannon chỉ ra rằng không thể nào lưu trữ thông tin với số bits nhỏ hơn entropy của thông tin này. AC cho phép chúng ta tiến tới gần giới hạn entropy này với khoảng cách 2 bits."
]
},
{
"metadata": {
"id": "KkvgLr2ZBiM_",
"colab_type": "text"
},
"cell_type": "markdown",
"source": [
"## Giới thiệu về nén dữ liệu"
]
},
{
"metadata": {
"id": "lPzuyNlIyKaK",
"colab_type": "text"
},
"cell_type": "markdown",
"source": [
"\n",
"Đối tượng ta đang xem xét ở đây là **thông tin** và câu hỏi ta muốn trả lời là: cần bao nhiêu bits dữ liệu để lưu trữ thông tin trên máy tính?\n",
"\n",
"Giả sử rằng thông tin $T$ ta muốn truyền đi hay lưu trữ là một trong 4 khả năng $$ T \\in \\left\\{ a, b, c, d\\right\\}$$\n",
"Một phương pháp đơn giản để lưu trữ thông tin là ra sẽ dùng $\\log_2 (4)$ bits thông tin để lưu trữ $T$. Ta xây dựng một bảng dùng để encode và decode thông tin như sau:\n",
"\n",
"| Symbol | Code |\n",
"|--------|------|\n",
"| a | 00 |\n",
"| b | 01 |\n",
"| c | 10 |\n",
"| d | 11 |\n",
"\n",
"Như vậy ta cần 2 bits để lưu trữ $T$ trong cả 4 giá trị có thể nhận của nó.\n",
"\n",
"Tuy nhiên, ta nhận thấy cách thức mã hóa như trên chỉ phù hợp khi xác suất $T$ nhận một giá trị bất kì là bằng nhau cho mọi khả năng:\n",
"$$\n",
"P(T = a) = P(T= b) = P(T=c) = P(T = d) = \\frac 1 4\n",
"$$\n",
"\n",
"Do đó, độ dài mà ta kỳ vọng khi lưu trữ $T$ trên máy tính là:\n",
"$$\n",
"\\mathrm E[\\textrm{length}(\\textrm{code}(T))] = \\frac 1 4 \\times 2 + \\frac 1 4 \\times 2 + \\frac 1 4 \\times 2 + \\frac 1 4 \\times 2 = 2\n",
"$$\n",
"\n",
"Nếu phân phối xác suất của $a, b, c, d$ không đồng đều thì ta có một phương pháp tốt hơn.\n",
"Giả dụ, ta có bảng phân phối xác suất như sau:\n",
"\n",
"| Symbol | Probability |\n",
"|--------|------|\n",
"| a | 0.9 |\n",
"| b | 0.05 |\n",
"| c | 0.025 |\n",
"| d | 0.025 |\n",
"\n",
"Thuật toán tối ưu được dùng ở đây là Huffman coding (được sử dụng rộng rãi trong định dạng file MP3 và JPEG).\n",
"\n",
"**Huffman coding**:\n",
"\n",
"Bước 0: khởi tạo $code(x) = \\emptyset$, cho mọi $x \\in \\{a, b, c, d\\}$\n",
"\n",
"Bước 1: Chọn hai khả năng có xác suất nhỏ nhất.\n",
"Ở đây ta chọn $c$ và $d$.\n",
"\n",
"Bước 2: Thêm $1$ và $0$ vào code của hai trường hợp được chọn.\n",
"\n",
"$\\textrm {code}(c) \\gets \\textrm {code}(c) + 1 = 1$ và $\\textrm{code} (d) \\gets \\textrm {code}(d) + 0 = 0$.\n",
"\n",
"Bước 3: Gộp hai trường hợp được chọn thành một trường hợp mới với xác suất là tổng của hai xác suất nhỏ nhất.\n",
"Ở đây ta thay $c$ và $d$ bởi $\\{c, d\\}$ với xác suất $0.05$.\n",
"\n",
"Quay lại bước 1\n",
"\n",
"\n",
"Kết thúc quá trình này, ta xây dựng được 1 cây nhị phân như sau:\n",
"\n",
"```\n",
" .\n",
" / \\\n",
" 1 / \\ 0\n",
" / \\\n",
" a .\n",
" / \\\n",
" 1 / \\ 0\n",
" / \\\n",
" b .\n",
" / \\\n",
" 1 / \\ 0\n",
" / \\\n",
" c d\n",
" \n",
"\n",
"```\n",
"\n",
"Bảng encode/decode tương ứng là:\n",
"\n",
"| Symbol | Code |\n",
"|--------|------|\n",
"| a | 1 |\n",
"| b | 01 |\n",
"| c | 001 |\n",
"| d | 000 |\n",
"\n",
"Độ dài bits mà ta kỳ vọng khi lưu trữ thông tin của $T$ lúc này là:\n",
"$$\n",
"\\mathrm E[\\textrm{length}(\\textrm{code}(T))] = 1 \\times 0.9 + 2 \\times 0.05 + 3 \\times 0.025 + 3 \\times 0.025 = 1.15~~\\mathrm{ bits }\n",
"$$\n",
"\n"
]
},
{
"metadata": {
"id": "8m5aq5h8BrRX",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 34
},
"outputId": "f17e67d4-37c4-4448-b817-32b839e74648"
},
"cell_type": "code",
"source": [
"print(1*0.9 + 2* 0.05 + 3 * 0.025*2, \" bits\")"
],
"execution_count": 221,
"outputs": [
{
"output_type": "stream",
"text": [
"1.15 bits\n"
],
"name": "stdout"
}
]
},
{
"metadata": {
"id": "br33DK2U_TuR",
"colab_type": "text"
},
"cell_type": "markdown",
"source": [
"Claude Shannon định nghĩa entropy của $T$ như sau:\n",
"$$H(T) = \\sum_{x \\in \\left\\{ a, b, c, d\\right\\}} \\log\\left( \\frac 1 {P(x)}\\right) \\times P(x) = \\mathrm E\\left[ \\log\\left(\\frac {1}{P(T)}\\right)\\right] $$\n",
"\n",
"Từ đó ông chứng minh rằng, \n",
"$$\n",
"\\mathrm E[\\textrm{length}(\\textrm{code}(T))] ]\\geq H(T)\n",
"$$\n",
"\n",
"Thuật toán Huffman coding đảm bảo rằng:\n",
"$$\n",
"\\mathrm E[\\textrm{length}(\\textrm{code}(T))] ]\\leq H(T) + 1\n",
"$$\n",
"\n",
"Ta thử tính entropy của $T$,\n",
"$$\n",
"H(T) = -0.9 \\times \\log(0.9) - 0.05 \\times \\log(0.05) - 2 \\times 0.025 \\times \\log(0.025) \\approx 0.619 ~~\\mathrm{bits} \n",
"$$\n",
"\n"
]
},
{
"metadata": {
"id": "ZS6mJ_FrB3pY",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 34
},
"outputId": "2192ed05-ecad-4f26-e118-04810950d4f5"
},
"cell_type": "code",
"source": [
"import math\n",
"print( -0.9 * math.log2(0.9) - 0.05 * math.log2(0.05) - 2 * 0.025 * math.log2(0.025), \" bits\")"
],
"execution_count": 222,
"outputs": [
{
"output_type": "stream",
"text": [
"0.6189955935892812 bits\n"
],
"name": "stdout"
}
]
},
{
"metadata": {
"id": "fOUQ-TDVBj4B",
"colab_type": "text"
},
"cell_type": "markdown",
"source": [
"## Arithmetic coding"
]
},
{
"metadata": {
"id": "yC4xAcDDBmmn",
"colab_type": "text"
},
"cell_type": "markdown",
"source": [
"Một giới hạn của Huffman coding là nó chỉ hoạt động khi $T$ nhận giá trị từ một tập hữu hạn các khả năng có thể. Trong thực tế, ta muốn nén một file có độ dài bất kỳ. Nói cách khác, ta muốn tìm một phương pháp nén mà $T$ có thể nhận vô hạn các khả năng khác nhau.\n",
"\n",
"Thậm chí nếu ta giới hạn $T$ là một chuỗi hữu hạn 512 bits, thì Huffman coding cần xây dựng một cây nhị phân có $2^{512}$ lá. Điều này là không khả thi trong thực tế.\n",
"\n",
"Còn nếu ta áp dụng thuật toán Huffman coding cho mỗi một chuỗi $5$ bits, thì ứng với mỗi 5 bits này, ta có thể bị phung phí 1 bit so với giới hạn entropy của 5 bits này. Số lượng bits bị phung phí sẽ cộng dồn càng nhiều với một file có độ dài càng lớn.\n",
"\n",
"Thêm vào đó, phân phối xác suất của bit hiện thời rất nhiều khả năng là phụ thuộc vào giá trị của các bits xuất hiện trước nó trong chuỗi bit. Cho nên ta muốn xây dựng một phương pháp nén khai thác việc phụ thuộc này.\n",
"\n",
"\n",
"Ta sẽ lấy ví dụ cho phần này như sau:\n",
"\n",
"Xét một đồng xu $X$ bị thiên vị:\n",
"$$\n",
"P(X = 1) = 0.9\n",
"$$\n",
"và\n",
"$$\n",
"P(X =0) = 0.1\n",
"$$\n",
"\n",
"Ta muốn lưu trữ một chuỗi 512 bits $T = x_1 \\dots, x_{512}$ sao cho:\n",
"$$\n",
"x_i \\sim P(X)\n",
"$$\n",
"\n",
"Nếu ta dùng Huffman coding, thì ta cần xây dựng 1 cây nhị phân $2^{512}$ lá! Còn nếu ta dùng Huffman coding cho mỗi $x_i$, thì ta cần $512$ bits để lưu trữ vì mỗi $x_i$ cần $1$ bit để mã hóa.\n",
"\n",
"Arithmetic coding giải quyết bài toán trên bằng cách encode mỗi khả năng $x$ của $T$, trong $2^{512}$ khả năng, bằng một khoảng $[a, b] \\subset [0, 1]$ sao cho độ dài của khoảng này $b - a$ bằng chính xác suất của $x$:\n",
"$$\n",
"\\begin{align}\n",
"\\textrm{code}(x) &= [a, b], \\\\\n",
"\\textrm{such that}~~~~~~~~~~~~~~~~~& \\\\\n",
"P(x) &= b- a\n",
"\\end{align}\n",
"$$\n",
"\n",
"Nói cách khác, ta chia khoảng số thực $[0, 1]$ ra thành $2^{512}$ khoảng nhỏ, sao cho độ dài mỗi khoảng là xác suất $T$ nhận giá trị tương ứng.\n",
"\n",
"Tiếp theo, để xác định được khoảng $[a, b]$ tương ứng với một giá trị $x = x_1, \\dots, x_{512}$ bất kì, ta dùng chain rule:\n",
"$$\n",
"P(x) = P(x_1) \\times P(x_2 \\mid x_1) \\times P(x_3 \\mid x_1, x_2) \\times \\cdots \\times P(x_{512} \\mid x_1,\\dots, x_{511})\n",
"$$\n",
"\n",
"Nói cách khác, ta cần một probabilistic model của $T$ cho phép ta tính $P(x_t \\mid x_1, \\dots, x_{t-1})$, i.e., auto-regressive model. \n",
"\n",
"Trong ví dụ của ta, $$P(x_t \\mid x_1, \\dots, x_{t-1}) = P(X)$$\n",
"\n",
"Bây giờ ta bắt đầu xét khoảng $k^{(1)} = [0, 1]$ và $x_1$, ta sẽ chia ra $k$ ra thành hai khoảng con : $k^{(1)}_1 = [0, 0.9]$ và $k^{(1)}_0 = [0.9, 1.0]$.\n",
"\n",
"Nếu $x_1 = 1$, ta sẽ chọn $k^{(2)} = k^{(1)}_1$ và ngược lại nếu $x_1 = 0$ ta chọn $k^{(2)} = k^{(1)}_0$,\n",
"$$\n",
"k^{(2)} = k^{(1)}_{x_1}\n",
"$$\n",
"\n",
"Giờ ta xét $x_2$, ta cũng chia khoảng $k^{(2)}$ ra làm 2 khoảng con $k^{(2)}_1$ và $k^{(2)}_0$ với tỉ lệ tương ứng là $0.9$ và $0.1$. Tùy thuộc vào giá trị của $x_2$ mà ta chọn được khoảng $k^{(3)}$ phụ hợp.\n",
"\n",
"Lặp lại các hành động này $512$ lần cho ta khoảng $[a, b]$ ứng với $x$.\n",
"\n",
"Tiếp theo, chúng ta sẽ giới thiệu cách để encode khoảng $[a, b]$ bởi chuỗi bits $y= y_1, \\dots, y_t$ sao cho $y_i \\in \\left\\{0, 1\\right\\}$.\n",
"Tương tự như cách làm với $x$, tuy nhiên, ở đây $P(y_i = 1) = 0.5$.\n",
"\n",
"Ta chia khoảng $[0, 1]$ ra làm hai khoảng con $[0, 0.5]$ ứng với $y_1=1$ và $[0.5, 1.0]$ ứng với $y_1 = 0$, ta sẽ chọn giá trị của $y_1$ sao cho khoảng tương ứng của nó chứa $[a, b]$.\n",
"\n",
"Lặp lại quá trình này $t$ lần cho tới khi ta tìm được một khoảng $[t, q]$ nằm trong $[a, b]$,\n",
"$$\n",
"[t, q] \\subset [a, b]\n",
"$$\n",
"\n",
"Vì mỗi lần ta giảm độ dài của khoảng đi $\\frac 1 2 $, nên ước tính, ta cần tối đa $\\log_2 \\frac 1 {b-a} + 2= \\log_2 \\frac 1 {P(x)} + 2 $, bits để encode khoảng $[a, b]$.\n",
"\n",
"Cũng bởi vì vậy mà ta đảm bảo được rằng, độ dài mà ta kì vọng khi encode $T$ không lớn hơn $2$ bits so với entropy của $T$."
]
},
{
"metadata": {
"id": "8f5yHIjDbDLH",
"colab_type": "text"
},
"cell_type": "markdown",
"source": [
"## Thực hành\n",
"\n",
"Ta sinh ra một chuỗi dài $512$ bits như bên dưới:"
]
},
{
"metadata": {
"id": "FlAPF0U5bJ-2",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 289
},
"outputId": "a17da5e4-efc2-42da-effe-9c59432a518d"
},
"cell_type": "code",
"source": [
"#@title\n",
"import numpy as np\n",
"from fractions import Fraction\n",
"\n",
"\n",
"p = Fraction(9, 10)\n",
"\n",
"def Bernoulli(p):\n",
" if np.random.uniform() < p:\n",
" return 1\n",
" else:\n",
" return 0\n",
"\n",
"def tostr(bits):\n",
" txt = \"\".join(str(i) for i in bits)\n",
" import textwrap\n",
" return textwrap.fill(txt, 32)\n",
"\n",
"bits = [Bernoulli(p) for i in range(512)]\n",
"\n",
"print(tostr(bits))"
],
"execution_count": 223,
"outputs": [
{
"output_type": "stream",
"text": [
"11111110100111111110111111111111\n",
"11111011111111111101111110111011\n",
"11101101111111111111111111111100\n",
"11111101111111111111011111111111\n",
"11111101111011111110111111111111\n",
"11110111011110111111101111111111\n",
"11111111011111111111110111111111\n",
"11111111111101111111010111111111\n",
"11111111111011111110111111111111\n",
"11011111111111111111100111111111\n",
"11101111011111111111101011011011\n",
"01011111101111111111111001101111\n",
"10111111101101111011111111111111\n",
"11111111111111000111111111111111\n",
"01011011111111111111101111101111\n",
"11111011110111101111111110111011\n"
],
"name": "stdout"
}
]
},
{
"metadata": {
"id": "jhQmVXtYma7c",
"colab_type": "text"
},
"cell_type": "markdown",
"source": [
"Entropy của chuỗi nhị phân $x$ là:"
]
},
{
"metadata": {
"id": "wJFauu5dg0wk",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 34
},
"outputId": "9a083190-3ccd-4c0d-b9aa-825b08a6b792"
},
"cell_type": "code",
"source": [
"#@title\n",
"entropy = (-math.log2(p) * p - math.log2(1-p) * (1-p)) * 512\n",
"print(\"Entropy: \", entropy, \" bits\")"
],
"execution_count": 224,
"outputs": [
{
"output_type": "stream",
"text": [
"Entropy: 240.125743917712 bits\n"
],
"name": "stdout"
}
]
},
{
"metadata": {
"id": "FDrjst6gsmWA",
"colab_type": "text"
},
"cell_type": "markdown",
"source": [
"### Encoding"
]
},
{
"metadata": {
"id": "c4wydWFblYKZ",
"colab_type": "text"
},
"cell_type": "markdown",
"source": [
"Tiếp theo, ta sẽ encode chuỗi $512$ bits này bởi khoảng số thực $[a, b]$:"
]
},
{
"metadata": {
"id": "Xrmr3uopbdvy",
"colab_type": "code",
"colab": {}
},
"cell_type": "code",
"source": [
"def findEncodeSegment(bits):\n",
" left = Fraction(0, 1)\n",
" right = Fraction(1, 1)\n",
" \n",
" for xi in bits:\n",
" boundary = left + (right-left) * (1-p)\n",
" left, right = [ (left, boundary), (boundary, right) ] [xi]\n",
" \n",
" return left, right"
],
"execution_count": 0,
"outputs": []
},
{
"metadata": {
"id": "nASIldAtcayY",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 34
},
"outputId": "1f81b669-8aca-48d7-874d-c9ac898e868c"
},
"cell_type": "code",
"source": [
"seg = findEncodeSegment(bits)\n",
"left, right = seg\n",
"print(\"[a, b] = [%0.5f, %0.5f]\" % (float(left), float(right)))"
],
"execution_count": 226,
"outputs": [
{
"output_type": "stream",
"text": [
"[a, b] = [0.52675, 0.52675]\n"
],
"name": "stdout"
}
]
},
{
"metadata": {
"id": "dEYDPFnUl3Z6",
"colab_type": "text"
},
"cell_type": "markdown",
"source": [
"Sau đó ta sẽ encode khoảng $[a, b]$ bởi 1 chuỗi bits nhị phân $y$:"
]
},
{
"metadata": {
"id": "wHlpNkpydjEo",
"colab_type": "code",
"colab": {}
},
"cell_type": "code",
"source": [
"def encodeSegmentInBinary(seg):\n",
" left, right = seg\n",
" mid = (left + right) / 2\n",
" \n",
" l = Fraction(0, 1)\n",
" r = Fraction(1, 1)\n",
" zipbits = []\n",
" while True:\n",
" m = (l + r) / 2\n",
" if m <= mid:\n",
" l, r= m, r\n",
" zipbits.append(1)\n",
" else:\n",
" l, r = l, m\n",
" zipbits.append(0)\n",
" if l > left and r < right:\n",
" break\n",
" return zipbits, l, r"
],
"execution_count": 0,
"outputs": []
},
{
"metadata": {
"id": "98lQ-do1cjYu",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 272
},
"outputId": "15d11865-2722-48f1-b134-5da996fd620b"
},
"cell_type": "code",
"source": [
"zipbits, l, r = encodeSegmentInBinary(seg)\n",
"print(\"y = '''\\n%s '''\\n\" % tostr(zipbits))\n",
"print(\"Length: \", len(zipbits), \" bits \\n\")\n",
"print(l)\n",
"print(r)"
],
"execution_count": 228,
"outputs": [
{
"output_type": "stream",
"text": [
"y = '''\n",
"10000110110110001110001010000101\n",
"00000101111101010100001000111111\n",
"10110001001011110100001101000010\n",
"10101110100001101010010010111101\n",
"10000111001011000011010101111110\n",
"10011000001001001100110010101001\n",
"01010111000100110100001100011011\n",
"11111001110011100001001000000100\n",
"1101010010000 '''\n",
"\n",
"Length: 269 bits \n",
"\n",
"31228479517247776525239335495674436425470614754624879890030345077825170825284009/59285549689505892056868344324448208820874232148807968788202283012051522375647232\n",
"499655672275964424403829367930790982807529836073998078240485521245202733204544145/948568795032094272909893509191171341133987714380927500611236528192824358010355712\n"
],
"name": "stdout"
}
]
},
{
"metadata": {
"id": "a7t_ijvhspaj",
"colab_type": "text"
},
"cell_type": "markdown",
"source": [
"### Decoding"
]
},
{
"metadata": {
"id": "c48ckRxsmijn",
"colab_type": "text"
},
"cell_type": "markdown",
"source": [
"\n",
"\n",
"Tại đây ta sẽ thực hiện các thao tác ngược để giải mã chuỗi bits $y$:"
]
},
{
"metadata": {
"id": "UzR9yddmhiEQ",
"colab_type": "code",
"colab": {}
},
"cell_type": "code",
"source": [
"def decodeBinaryToSegment(zipbits):\n",
" l = Fraction(0, 1)\n",
" r = Fraction(1, 1)\n",
" for bit in zipbits:\n",
" m = (l + r) / 2\n",
" l, r = [(l, m), (m, r) ][bit]\n",
" return l, r"
],
"execution_count": 0,
"outputs": []
},
{
"metadata": {
"id": "_kqx6wMHh7Wa",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 51
},
"outputId": "9ff9fea9-fb4d-4d60-9d7b-c1bf5fba2d89"
},
"cell_type": "code",
"source": [
"decode_seg = decodeBinaryToSegment(zipbits)\n",
"print(decode_seg[0])\n",
"print(decode_seg[1])"
],
"execution_count": 230,
"outputs": [
{
"output_type": "stream",
"text": [
"31228479517247776525239335495674436425470614754624879890030345077825170825284009/59285549689505892056868344324448208820874232148807968788202283012051522375647232\n",
"499655672275964424403829367930790982807529836073998078240485521245202733204544145/948568795032094272909893509191171341133987714380927500611236528192824358010355712\n"
],
"name": "stdout"
}
]
},
{
"metadata": {
"id": "85wzwhBQiHSR",
"colab_type": "code",
"colab": {}
},
"cell_type": "code",
"source": [
"def decodeSegmentToBits(decode_seg):\n",
" l, r = decode_seg\n",
" m = (l + r) /2\n",
" left = Fraction(0, 1)\n",
" right = Fraction(1, 1)\n",
" bits = []\n",
" for i in range(512):\n",
" boundary = left + (right-left) * (1-p)\n",
" if boundary < m:\n",
" bit = 1\n",
" else:\n",
" bit = 0\n",
" \n",
" left, right = [ (left, boundary), (boundary, right) ] [bit]\n",
"\n",
" bits.append(bit)\n",
" return bits"
],
"execution_count": 0,
"outputs": []
},
{
"metadata": {
"id": "9BfDm2nvjSBq",
"colab_type": "code",
"colab": {}
},
"cell_type": "code",
"source": [
"unzipbits = decodeSegmentToBits(decode_seg)"
],
"execution_count": 0,
"outputs": []
},
{
"metadata": {
"id": "mfvHXSPUm7cK",
"colab_type": "text"
},
"cell_type": "markdown",
"source": [
"Chuỗi bits sau decode là:"
]
},
{
"metadata": {
"id": "7AVdz4bgm-5z",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 289
},
"outputId": "673d5310-45fa-438f-f354-567ca5c30c78"
},
"cell_type": "code",
"source": [
"print(tostr(unzipbits))"
],
"execution_count": 233,
"outputs": [
{
"output_type": "stream",
"text": [
"11111110100111111110111111111111\n",
"11111011111111111101111110111011\n",
"11101101111111111111111111111100\n",
"11111101111111111111011111111111\n",
"11111101111011111110111111111111\n",
"11110111011110111111101111111111\n",
"11111111011111111111110111111111\n",
"11111111111101111111010111111111\n",
"11111111111011111110111111111111\n",
"11011111111111111111100111111111\n",
"11101111011111111111101011011011\n",
"01011111101111111111111001101111\n",
"10111111101101111011111111111111\n",
"11111111111111000111111111111111\n",
"01011011111111111111101111101111\n",
"11111011110111101111111110111011\n"
],
"name": "stdout"
}
]
},
{
"metadata": {
"id": "03SMq8gYjb4n",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 34
},
"outputId": "836f955f-cec9-4643-bdae-986ca06f0461"
},
"cell_type": "code",
"source": [
"## Check\n",
"print( unzipbits == bits)"
],
"execution_count": 234,
"outputs": [
{
"output_type": "stream",
"text": [
"True\n"
],
"name": "stdout"
}
]
},
{
"metadata": {
"id": "6QF7KjCMjsM2",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 51
},
"outputId": "62e17429-186e-4b8e-c78b-315a23943d92"
},
"cell_type": "code",
"source": [
"print( len(zipbits) / len(unzipbits) * 100, \"% in size\" )\n",
"print(\"Encoded in %d bits compared to entropy %0.3f bits \" %(len(zipbits), entropy))"
],
"execution_count": 235,
"outputs": [
{
"output_type": "stream",
"text": [
"52.5390625 % in size\n",
"Encoded in 269 bits compared to entropy 240.126 bits \n"
],
"name": "stdout"
}
]
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment