Huffman coding: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 3,403: | Line 3,403: | ||
6 ‘ ’ “101” |
6 ‘ ’ “101” |
||
</pre> |
</pre> |
||
=={{header|M2000 Interpreter}}== |
|||
<lang M2000 Interpreter> |
|||
Module Huffman { |
|||
comp=lambda (a, b) ->{ |
|||
=array(a, 0)<array(b, 0) |
|||
} |
|||
module InsertPQ (a, n, &comp) { |
|||
if len(a)=0 then stack a {data n} : exit |
|||
if comp(n, stackitem(a)) then stack a {push n} : exit |
|||
stack a { |
|||
push n |
|||
t=2: b=len(a) |
|||
m=b |
|||
While t<=b { |
|||
t1=m |
|||
m=(b+t) div 2 |
|||
if m=0 then m=t1 : exit |
|||
If comp(stackitem(m),n) then t=m+1: continue |
|||
b=m-1 |
|||
m=b |
|||
} |
|||
if m>1 then shiftback m |
|||
} |
|||
} |
|||
a$="this is an example for huffman encoding" |
|||
inventory freq |
|||
For i=1 to len(a$) { |
|||
b$=mid$(a$,i,1) |
|||
if exist(freq, b$) then Return freq, b$:=freq(b$)+1 : continue |
|||
append freq, b$:=1 |
|||
} |
|||
b=stack |
|||
K=each(freq) |
|||
LenA=len(a$) |
|||
While k { |
|||
InsertPQ b, (Round(Eval(k)/lenA, 4), eval$(k, k^)), &comp |
|||
} |
|||
While len(b)>1 { |
|||
Stack b { |
|||
Read m1, m2 |
|||
InsertPQ b, (Array(m1)+Array(m2), (m1, m2) ), &comp |
|||
} |
|||
} |
|||
Print "Size of stack object (has only Root):"; len(b) |
|||
Print "Root probability:";Round(Array(Stackitem(b)), 3) |
|||
inventory encode, decode |
|||
Traverse(stackitem(b), "") |
|||
message$="" |
|||
For i=1 to len(a$) |
|||
message$+=encode$(mid$(a$, i, 1)) |
|||
Next i |
|||
Print message$ |
|||
j=1 |
|||
check$="" |
|||
For i=1 to len(a$) |
|||
d=each(encode) |
|||
While d { |
|||
code$=eval$(d) |
|||
if mid$(message$, j, len(code$))=code$ then { |
|||
check$+=decode$(code$) |
|||
Print decode$(code$); : j+=len(code$) |
|||
} |
|||
} |
|||
Next i |
|||
Print |
|||
Print len(message$);" bits ", if$(a$=check$->"Encoding/decoding worked", "Encoding/Decoding failed") |
|||
Sub Traverse(a, a$) |
|||
local b=array(a,1) |
|||
if type$(b)="mArray" Else { |
|||
' Print @(10); quote$(array$(a, 1));" "; a$,@(20),array(a) |
|||
Append decode, a$ :=array$(a, 1) |
|||
Append encode, array$(a, 1):=a$ |
|||
Exit Sub |
|||
} |
|||
traverse(array(b), a$+"0") |
|||
traverse(array(b,1), a$+"1") |
|||
End Sub |
|||
} |
|||
Huffman |
|||
</lang> |
|||
{{out}} |
|||
<pre > |
|||
"r" 00000 0,0256 |
|||
"l" 00001 0,0256 |
|||
"c" 00010 0,0256 |
|||
"u" 00011 0,0256 |
|||
"g" 00100 0,0256 |
|||
"d" 00101 0,0256 |
|||
"o" 0011 0,0513 |
|||
"m" 0100 0,0513 |
|||
"s" 0101 0,0513 |
|||
"n" 011 0,1026 |
|||
"h" 1000 0,0513 |
|||
"t" 10010 0,0256 |
|||
"p" 100110 0,0256 |
|||
"x" 100111 0,0256 |
|||
"a" 1010 0,0769 |
|||
"i" 1011 0,0769 |
|||
"f" 1100 0,0769 |
|||
"e" 1101 0,0769 |
|||
" " 111 0,1538 |
|||
1001010001011010111110110101111101001111111011001111010010010011000001110111111000011000001111000000111100110001001010011111110101100010001100101101101100100 |
|||
this is an example for huffman encoding |
|||
157 bits Encoding/decoding worked |
|||
</pre > |
|||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |