Huffman coding: Difference between revisions
add FreeBASIC
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
(add FreeBASIC) |
||
Line 2,543:
end program
</lang>
=={{header|FreeBASIC}}==
<lang freebasic>type block
freq as uinteger
chars as string
end type
type code
char as string*1
code as string
end type
sub bubble( lst() as block, n_l as uinteger )
for j as integer = n_l-1 to 0 step -1
if j>0 andalso lst(j).freq > lst(j-1).freq then
swap lst(j), lst(j-1)
endif
next j
end sub
dim as string Sample = "this is an example for huffman encoding"
redim as block hufflist(0)
hufflist(0).freq = 1 : hufflist(0).chars = mid(Sample,1,1)
dim as boolean newchar
dim as string*1 currchar
dim as uinteger n_h = 1, n_c
'read characters in one-by-one and simultaneously bubblesort them
for i as uinteger = 2 to len(Sample)
currchar = mid(Sample,i,1)
newchar = true
for j as uinteger = 0 to n_h-1
if mid(Sample,i,1) = hufflist(j).chars then
hufflist(j).freq += 1
newchar = false
end if
if j>0 andalso hufflist(j).freq > hufflist(j-1).freq then
swap hufflist(j), hufflist(j-1)
endif
next j
if newchar then
redim preserve hufflist(0 to n_h)
hufflist(n_h).chars = currchar
hufflist(n_h).freq = 1
n_h+=1
end if
next i
'one final pass of bubblesort may be necessary
bubble hufflist(), n_h
'initialise huffman code
redim as code codelist(0 to n_h-1)
for i as uinteger = 0 to n_h-1
codelist(i).char = hufflist(i).chars
codelist(i).code = ""
next i
n_c = n_h
do
'characters in the least common block get "0" appended
for i as uinteger = 1 to len(hufflist(n_h-1).chars)
for j as uinteger = 0 to n_c-1
if codelist(j).char = mid(hufflist(n_h-1).chars,i,1) then
codelist(j).code = "0" + codelist(j).code
end if
next j
next i
'characters in the second-least common block get "1" appended
for i as uinteger = 1 to len(hufflist(n_h-2).chars)
for j as uinteger = 0 to n_c-1
if codelist(j).char = mid(hufflist(n_h-2).chars,i,1) then
codelist(j).code = "1" + codelist(j).code
end if
next j
next i
'combine the two least frequent blocks
hufflist(n_h-2).chars = hufflist(n_h-2).chars + hufflist(n_h-1).chars
hufflist(n_h-2).freq = hufflist(n_h-2).freq + hufflist(n_h-1).freq
redim preserve hufflist(0 to n_h-2)
n_h -= 1
'move the new combined block to its proper place in the list
bubble hufflist(), n_h
loop until n_h = 1
for i as uinteger = 0 to n_c - 1
print "'"+codelist(i).char+"'", codelist(i).code
next i
</lang>
{{out}}
<pre>' ' 111
'n' 001
'a' 1011
'e' 1010
'f' 1101
'i' 1100
's' 1000
'h' 0101
'm' 0100
'o' 0111
't' 10010
'x' 100111
'p' 100110
'l' 00001
'r' 00000
'u' 00011
'c' 00010
'd' 01101
'g' 01100</pre>
=={{header|Go}}==
| |||