August 27, 2024
P53 - Huffman code (3)
If you are not familiar with Huffman coding, consult internet (or a good book).
a) Given characters with their frequencies, e.g. {a=25, b=21, c=18, d=14, e=9, f=7, g=6}. Our objective is to construct a Map, where key is character and value is the Huffman code for it.
> createEncoding(linkedMapOf(Pair('a', 25), Pair('b', 21), Pair('c', 18), Pair('d', 14), Pair('e', 9), Pair('f', 7), Pair('g', 6)))
{a=10, b=00, c=111, d=110, e=010, f=0111, g=0110}b) Write encode and decode functions for conversion between String and encoded String with zeroes and ones. For example:
"this is a sentence".encode(encoding)
"00110000101011100101011101001110101111011001111011000111"
"00110000101011100101011101001110101111011001111011000111".decode(encoding)
"this is a sentence"kotlin
w IllegalStateException("Unexpected code '$code'")
}
override fun toString(): String {
var s = "Node($weight"
if (char != null) s += ", '$char'"
if (left != null && right != null) s += ", $left, $right"
return "$s)"
}
}
class P50Test {
@Test fun `letter to code mapping`() {
assertThat(
createEncoding(linkedMapOf(
Pair('a', 25), Pair('b', 21), Pair('c', 18), Pair('d', 14), Pair('e', 9), Pair('f', 7), Pair('g', 6)
)).codeByChar,
equalTo(linkedMapOf(
Pair('a', "10"), Pair('b', "00"), Pair('c', "111"), Pair('d', "110"), Pair('e', "010"), Pair('f', "0111"), Pair('g', "0110")
))
)
}
@Test fun `encoding and decoding a string`() {
val string = "this is a sentence"
val encoding = string.createEncoding()
val encodedString = string.encode(encoding)
assertThat(encodedString, equalTo("00110000101011100101011101001110101111011001111011000111"))
val decodedString = encodedString.decode(encoding)
assertThat(decodedString, equalTo("this is a sentence"))
}
}
Be first to comment