Anonymous user
Huffman coding: Difference between revisions
no edit summary
No edit summary |
|||
Line 3,403:
6 ‘ ’ “101”
</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}}==
| |||