{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "bea729e2",
   "metadata": {},
   "source": [
    "## Sample implementation of Variable byte codes and (s,c) dense codes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8d691caa",
   "metadata": {},
   "source": [
    "### Auxialiary functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "30590e5d",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math, random \n",
    "# sample implementation of byte codes\n",
    "# and (s,c) dense codes \n",
    "\n",
    "\n",
    "# convert to base 128 big endian form\n",
    "def tobase128(n):\n",
    "  assert(n>=0), \"input must be non-negative\"\n",
    "  if n==0: \n",
    "    return [0]  # special case to simplify the while loop \n",
    "  a = []\n",
    "  while n>0:\n",
    "    nextd = n%128     # remainder\n",
    "    a.insert(0,nextd) # insert at the beginning of the list\n",
    "    n = n//128        # integer division\n",
    "  return a\n",
    "\n",
    "\n",
    "\n",
    "# --- auxiliary functions (currently not used)\n",
    "\n",
    "# convert n to binary using at least d bits  \n",
    "def dec2bin(n,d=8):\n",
    "  assert n>=0\n",
    "  return f\"{n:0{d}b}\"\n",
    "\n",
    "# convert a list of integers in binary using at least d bits\n",
    "def list2bin(lis,d=8):\n",
    "  return [dec2bin(i) for i in lis]\n",
    "\n",
    "# convert from binary \n",
    "def bin2dec(s):\n",
    "    return int(s, 2)\n",
    "\n",
    "# number of bits required to encode k different values\n",
    "def bits(k):\n",
    "    assert k > 0\n",
    "    if k == 1:\n",
    "        return 0\n",
    "    bits = 1\n",
    "    values = 2  # 1 bit -> 2 values\n",
    "    while values < k:\n",
    "        bits += 1\n",
    "        values *= 2\n",
    "    return bits\n",
    "\n",
    "\n",
    "\n",
    "# --- list creation for experiments\n",
    "\n",
    "# given a list of pairs of positive integers \n",
    "# (i1,n1) (i2,n2) ... (ik,nk)\n",
    "# creates a random integer array with n_h copies of i_h \n",
    "def random_ia(lis):\n",
    "  a = []\n",
    "  for (i,n) in lis:\n",
    "    a += n*[i]\n",
    "  random.shuffle(a)  # permutes a's elements in place\n",
    "  return a\n",
    "\n",
    "# creates a random array with  x^{-1} distribution\n",
    "# with values between 1 and nmax \n",
    "def random_list(n,nmax):\n",
    "  a = [ (i, 1+n//i) for i in range(1,nmax+1) ]\n",
    "  return random_ia(a)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a03682f5",
   "metadata": {},
   "source": [
    "### Main functions for coding/decoding"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "ecaa95fd",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute VB coding of n, big endian\n",
    "def vb_encode(n):\n",
    "  a = tobase128(n)\n",
    "  for i in range(len(a)-1):\n",
    "    a[i] += 128    # turning on the most significant bit\n",
    "  return a\n",
    "    \n",
    "def vb_encode_array(a):    \n",
    "  out = []\n",
    "  for i in a:\n",
    "    out.extend(vb_encode(i))\n",
    "  return out\n",
    "    \n",
    "\n",
    "# sc_code big endian of integer n return sequence of bytes  \n",
    "def sc_encode(n,s,c):\n",
    "  assert(n>=0), \"input must be non-negative\"\n",
    "  assert c>1, \"continuation values must be >1\"\n",
    "  assert s>0, \"stop values must be >0\"\n",
    "  a = [n%s]       # less significant digit\n",
    "  n = n//s\n",
    "  while n>0:      # there is something more to encode\n",
    "    n -= 1        # this optimization is missing in VB encoding!\n",
    "    nextd = n%c   # next continuer\n",
    "    n= n//c       # update n\n",
    "    a.insert(0,nextd+s) # +s is same as adding 128 in VB    \n",
    "  return a\n",
    "\n",
    "# decode (s,c) code big endian  \n",
    "def sc_decode(a,s,c):\n",
    "  n = 0;\n",
    "  for d in a[:-1]:\n",
    "    assert s <= d < c+s, \"Illegal c-digit\" \n",
    "    n = n*c + (d-s)+1\n",
    "  d = a[-1]\n",
    "  assert 0 <= d < s, \"Illegal s-digit\"\n",
    "  n = n*s + d\n",
    "  return n\n",
    "\n",
    "# encode an array of integers\n",
    "def sc_encode_array(a,s,c):\n",
    "  out = []\n",
    "  for i in a:\n",
    "    out.extend(sc_encode(i,s,c))\n",
    "  return out\n",
    "\n",
    "# decode an array of codewords \n",
    "def sc_decode_array(a,s,c):\n",
    "  out = []\n",
    "  codeword = []\n",
    "  for i in a:\n",
    "    codeword.append(i)\n",
    "    if i < s:    # is i a stop value?\n",
    "      out.append(sc_decode(codeword,s,c))\n",
    "      codeword = []\n",
    "  assert len(codeword)==0\n",
    "  return out\n",
    "\n",
    "# return size of encoded array using \n",
    "# a (s, 256-s) dense code\n",
    "def encoded_array_size(a,s):\n",
    "  assert 0 < s < 255, \"# stop values must be between 1 and 254\"\n",
    "  e = sc_encode_array(a,s,256-s)\n",
    "  return len(e)\n",
    "\n",
    "\n",
    "# find the optimal value of s for the\n",
    "# (s,c)-dense encoding of array a[]\n",
    "# Assume the cost is a unimodal function with\n",
    "# minimum in (smin,smax) (extremes excluded!)\n",
    "# should be initially called with \n",
    "#  smin=0, smax=255\n",
    "# so that the minimum in sought in the range\n",
    "# [1,254] which are the legal values for s \n",
    "def find_minimum_encoding(a,smin,smax):\n",
    "  assert smin<=smax, \"Illegal interval\"\n",
    "  if smin==smax:\n",
    "    return smin, encoded_array_size(a,smin)\n",
    "  # base case:   \n",
    "  if smin==smax-1:\n",
    "    x1 = smin+1; fx1 = encoded_array_size(a,x1)  \n",
    "  # find two equally spaced points   \n",
    "  x1 = smin + int(round((smax-smin)/3)) \n",
    "  x2 = smax - int(round((smax-smin)/3))\n",
    "  print(\"--->\", smin,x1,x2,smax)\n",
    "  fx1 = encoded_array_size(a,x1) \n",
    "  fx2 = encoded_array_size(a,x2)\n",
    "  if fx1 > fx2:\n",
    "    return find_minimum_encoding(a,x1,smax)\n",
    "  elif fx1 < fx2:\n",
    "    return find_minimum_encoding(a,smin,x2)\n",
    "  elif x1!=x2:\n",
    "    return find_minimum_encoding(a,x1,x2)\n",
    "  else:   # case x1==x2 (base case of the recursion)\n",
    "    return  x1, fx1 \n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e49974af",
   "metadata": {},
   "source": [
    "### Experiments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "ee78df1f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1266750"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# random array with the values 1-10000 \n",
    "# with zipfian distribution\n",
    "a = random_list(100000,100000)\n",
    "len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "56d71b17",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2221216"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# encode with traditional VB codes\n",
    "avb = vb_encode_array(a)\n",
    "len(avb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "ded9a8b0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2227309"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# encode with dense code with s=120, c=136 \n",
    "asc = sc_encode_array(a,120,136)\n",
    "len(asc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "97efb21c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---> 0 85 170 255\n",
      "---> 85 142 198 255\n",
      "---> 85 123 160 198\n",
      "---> 123 148 173 198\n",
      "---> 148 165 181 198\n",
      "---> 148 159 170 181\n",
      "---> 159 166 174 181\n",
      "---> 166 171 176 181\n",
      "---> 166 169 173 176\n",
      "---> 166 168 171 173\n",
      "---> 168 170 171 173\n",
      "---> 170 171 172 173\n",
      "---> 170 171 171 172\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(171, 2203877)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# find optimal s value\n",
    "find_minimum_encoding(a,0,255)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "58f9dbf9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2203877"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# encode with the best s,c parameters\n",
    "scbest = sc_encode_array(a,171,256-171)\n",
    "len(scbest)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "960ce253",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# decode compressed sequence scbest\n",
    "adec = sc_decode_array(scbest,171,256-171)\n",
    "adec==a"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}