Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb6dbcfb

Browse files
Nikolaos Karampinaskeon
Nikolaos Karampinas
authored andcommitted
Added elias gamma and delta data compression codings (keon#564)
* Added elias gamma and delta data compression algorithms* Added more info about the codings.
1 parentebf96fa commitb6dbcfb

File tree

3 files changed

+70
-0
lines changed

3 files changed

+70
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -116,6 +116,7 @@ If you want to uninstall algorithms, it is as simple as:
116116
-[compression](algorithms/compression)
117117
-[huffman_coding](algorithms/compression/huffman_coding.py)
118118
-[rle_compression](algorithms/compression/rle_compression.py)
119+
-[elias](algorithms/compression/elias.py)
119120
-[dfs](algorithms/dfs)
120121
-[all_factors](algorithms/dfs/all_factors.py)
121122
-[count_islands](algorithms/dfs/count_islands.py)

‎algorithms/compression/elias.py

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
"""
2+
Elias γ code or Elias gamma code is a universal code encoding positive integers.
3+
It is used most commonly when coding integers whose upper-bound cannot be determined beforehand.
4+
Elias δ code or Elias delta code is a universal code encoding the positive integers,
5+
that includes Elias γ code when calculating.
6+
Both were developed by Peter Elias.
7+
8+
"""
9+
frommathimportlog,ceil
10+
11+
log2=lambdax:log(x,2)
12+
13+
# Calculates the binary number
14+
defbinary(x,l=1):
15+
fmt='{0:0%db}'%l
16+
returnfmt.format(x)
17+
18+
# Calculates the unary number
19+
defunary(x):
20+
return (x-1)*'1'+'0'
21+
22+
defelias_generic(lencoding,x):
23+
"""
24+
The compressed data is calculated in two parts.
25+
The first part is the unary number of 1 + ⌊log2(x)⌋.
26+
The second part is the binary number of x - 2^(⌊log2(x)⌋).
27+
For the final result we add these two parts.
28+
"""
29+
ifx==0:return'0'
30+
31+
first_part=1+int(log2(x))
32+
33+
a=x-2**(int(log2(x)))
34+
35+
k=int(log2(x))
36+
37+
returnlencoding(first_part)+binary(a,k)
38+
39+
defelias_gamma(x):
40+
"""
41+
For the first part we put the unary number of x.
42+
"""
43+
returnelias_generic(unary,x)
44+
45+
defelias_delta(x):
46+
"""
47+
For the first part we put the elias_g of the number.
48+
"""
49+
returnelias_generic(elias_gamma,x)

‎tests/test_compression.py

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,6 @@
11
fromalgorithms.compression.huffman_codingimportHuffmanCoding
22
fromalgorithms.compression.rle_compressionimport (decode_rle,encode_rle)
3+
fromalgorithms.compression.eliasimport (elias_gamma,elias_delta)
34

45
importunittest
56

@@ -44,6 +45,25 @@ def test_decode_rle(self):
4445
self.assertEqual('WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW',
4546
decode_rle('12W1B12W3B24W1B14W'))
4647

48+
classTestEliasCoding(unittest.TestCase):
49+
50+
deftest_elias_gamma(self):
51+
correct_result= ['0','00','100','101','11000','11001','11010','11011','1110000','1110001','1110010']
52+
53+
result= []
54+
foriinrange(11):
55+
result.append(elias_gamma(i))
56+
57+
self.assertEqual(correct_result,result)
58+
59+
deftest_elias_delta(self):
60+
correct_result= ['0','000','1000','1001','10100','10101','10110','10111','11000000','11000001','11000010']
61+
62+
result= []
63+
foriinrange(11):
64+
result.append(elias_delta(i))
65+
66+
self.assertEqual(correct_result,result)
4767

4868
if__name__=="__main__":
4969
unittest.main()

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp