Repository: keon/algorithms
Pull request #564 (2019-10-17 21:02:31)

Added elias gamma and delta data compression codings
(Put an `X` inside the `[ ]` to denote check mark `[X]`.)
Elias gamma and delta data compression algorithms to expand the category.

- [X] **If creating a new file :**
  - [X] added links to it in the README files ?
  - [X] included tests with it ?
  - [X] added description (overview of algorithm, time and space complexity, and possible edge case) in docstrings ?

- [ ] **if done some changes :**
  - [ ] wrote short description in the PR explaining what the changes do ?
  - [ ] Fixes #[issue number] if related to any issue

- [ ] **other**



Patch:
diff --git a/README.md b/README.md
index 4b67fe5..be4c3e5 100644
--- a/README.md
+++ b/README.md
@@ -116,6 +116,7 @@ If you want to uninstall algorithms, it is as simple as:
 - [compression](algorithms/compression)
     - [huffman_coding](algorithms/compression/huffman_coding.py)
     - [rle_compression](algorithms/compression/rle_compression.py)
+    - [elias](algorithms/compression/elias.py)
 - [dfs](algorithms/dfs)
     - [all_factors](algorithms/dfs/all_factors.py)
     - [count_islands](algorithms/dfs/count_islands.py)
diff --git a/algorithms/compression/elias.py b/algorithms/compression/elias.py
new file mode 100644
index 0000000..bdeb7fd
--- /dev/null
+++ b/algorithms/compression/elias.py
@@ -0,0 +1,49 @@
+"""
+Elias γ code or Elias gamma code is a universal code encoding positive integers.
+It is used most commonly when coding integers whose upper-bound cannot be determined beforehand.
+Elias δ code or Elias delta code is a universal code encoding the positive integers,
+that includes Elias γ code when calculating.
+Both were developed by Peter Elias.
+
+"""
+from math import log,ceil
+
+log2 = lambda x: log(x,2)
+
+# Calculates the binary number
+def binary(x,l=1):
+	fmt = '{0:0%db}' % l
+	return fmt.format(x)
+
+# Calculates the unary number
+def unary(x):
+	return (x-1)*'1'+'0'
+
+def elias_generic(lencoding, x):
+	"""
+	The compressed data is calculated in two parts. 
+	The first part is the unary number of 1 + ⌊log2(x)⌋. 
+	The second part is the binary number of x - 2^(⌊log2(x)⌋).
+	For the final result we add these two parts.
+	"""
+	if x == 0: return '0'
+	
+	first_part = 1 + int(log2(x))
+	
+	a = x - 2**(int(log2(x)))
+	
+	k = int(log2(x))
+
+	return lencoding(first_part) + binary(a,k)
+
+def elias_gamma(x):
+	"""
+	For the first part we put the unary number of x.
+	"""
+	return elias_generic(unary, x)
+
+def elias_delta(x):
+	"""
+	For the first part we put the elias_g of the number.
+	"""
+	return elias_generic(elias_gamma,x)


Test patch:
diff --git a/tests/test_compression.py b/tests/test_compression.py
index 144d944..cd41283 100644
--- a/tests/test_compression.py
+++ b/tests/test_compression.py
@@ -1,5 +1,6 @@
 from algorithms.compression.huffman_coding import HuffmanCoding
 from algorithms.compression.rle_compression import (decode_rle, encode_rle)
+from algorithms.compression.elias import (elias_gamma, elias_delta)
 
 import unittest
 
@@ -44,6 +45,25 @@ class TestRLECompression(unittest.TestCase):
         self.assertEqual('WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW', 
             decode_rle('12W1B12W3B24W1B14W'))
 
+class TestEliasCoding(unittest.TestCase):
+
+    def test_elias_gamma(self):
+        correct_result = ['0', '00', '100', '101', '11000', '11001', '11010', '11011', '1110000', '1110001', '1110010']
+        
+        result = []
+        for i in range(11):	
+            result.append(elias_gamma(i))
+
+        self.assertEqual(correct_result, result)
+
+    def test_elias_delta(self):
+        correct_result = ['0', '000', '1000', '1001', '10100', '10101', '10110', '10111', '11000000', '11000001', '11000010']
+
+        result = []
+        for i in range(11):	
+            result.append(elias_delta(i))
+
+        self.assertEqual(correct_result, result)        
 
 if __name__ == "__main__":
     unittest.main()