Huffman coding in Kotlin
Ik kwam dit artikel tegen dat precies uitlegt hoe Huffman codes werken, en daarbij een algoritme geeft in Haskell.
Wist je dat Huffman codes aan de basis liggen van JPEG image compression?
Ik woon niet in een ivoren toren en spreek geen Haskell. Ik kende het algoritme ook niet precies. Ik kreeg wel zin om te kijken of de code net zo kort en fraai kan in kotlin.
spoiler: het komt in de buurt. Misschien is het zelfs beter!
huffman coding
Huffman coding is een lossless compressie techniek. Stel dat je een tekst wil comprimeren, dan zijn er de volgende stappen:
- maak een frequentie tabel voor elk karakter
- maak een binary tree van de karakters en hun gewicht (de frequentie)
- ken vanuit de tree een binaire code toe aan elk karakter, zodanig dat:
- de meest voorkomende karakters de kortste code krijgen
- de codes (achter elkaar geplakt, zoals de oorspronkelijke tekst) leesbaar blijven (zonder separators)
Voor details, lees het artikel. Ik ga het niet herhalen, maar puur de vergelijking doen van haskell en kotlin (wat ik ervan gemaakt heb althans…).
1. frequenties tellen
Maak een Map van elk karakter als sleutel naar het aantal keer dat dat karakter voorkomt.
haskell
1
2
3
4
type FreqMap = Map Char Int
countFrequency :: String -> FreqMap
countFrequency = Map.fromListWith (+) . fmap (,1)
kotlin
1
2
3
4
typealias FreqMap = Map<Char, Int>
fun countFrequency(data: String): FreqMap =
data.toList().groupingBy { it }.eachCount()
Ik had even nodig om de haskell te begrijpen. De declaratie en de implementatie staan op 2 opvolgende regels en herhalen de functie naam. fmap (,1)
ziet eruit als een hack!
De kotlin code is net zo kort én beter leesbaar. Het mimict een SQL statement: select ..., count(1) from ... group by ...
De type alias van kotlin verhoogt net als bij Haskell de leesbaarheid en de typesafety. En is wel zo handig dat elke Map<Char, Int>
automatisch een FreqMap is. Het feit dat kotlin de conversie van String naar List
2. de tree opbouwen
De bedoeling is:
- maak van de frequentie map een (op gewicht) gesorteerde lijst Leaf nodes
- combineer steeds twee opeenvolgende nodes in een Fork node (de merge functie)
- zorg dat de lijst nodes (Leaf of Fork) steeds gesorteerd blijft.
haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
data HTree
= Leaf Weight Char
| Fork Weight HTree HTree
deriving Eq
instance Ord HTree where
compare x y = compare (weight x) (weight y)
buildTree :: FreqMap -> HTree
buildTree = build . sort . fmap (\(c,w) -> Leaf w c ) . Map.toList
where
build trees = case trees of
[] -> error "empty trees"
[x] -> x
[x:y:rest] -> build $ insert (merge x y) rest
merge x y = Fork (weight x + weight y) x y
weight
is een functie die de weight van de node geeft.merge
is een functie die van 2 nodes een (bovenliggende) Fork node maakt met de twee input nodes als children en het gecombineerde gewicht van beide
Haskell is inderdaad briljant hier met pattern matching en ADT’s (Algebraic Data Type, de HTree), maar weer moeilijker leesbaar (IMHO). Merk op dat de nested build
functie recursief wordt aangeroepen en dat de ‘aanroep’ (rg 10) vóór de declaratie staat (rg 12 ev)
- Lees
$...
als: ‘resultaat van …’ insert
is een functie die de sorteervolgorde handhaaft als het lijst elementOrd
is.
kotlin
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
sealed class HTree(open val weight: Int) {
data class Leaf(override val weight: Int, val char: Char) : HTree(weight)
data class Fork(override val weight: Int, val left: HTree, val right: HTree) : HTree(weight)
}
fun buildTree(freqMap: FreqMap): HTree {
val sortedFreqMap = freqMap.toList().sortedBy { it.second }
val trees: MutableList<HTree> = sortedFreqMap.map { Leaf(it.second, it.first) }.toMutableList()
while (trees.size > 1) {
val first = trees.removeFirst()
val second = trees.removeFirst()
trees.add(merge(first, second))
trees.sortBy { it.weight }
}
return trees[0]
}
Algoritme: Maak een boom structuur die elementen met een hoge weight (frequentie) bovenin plaatst. Op deze manier krijgen veel voorkomende karakters een korter pad en daarmee een kortere binaire code.
Kotlin komt krachtig uit de hoek met de HTree definitie, die veel compacter is dan java, maar zeker niet zo fraai als haskell’s union
(vgl rust enums!). In plaats van recursie, gebruiken we een MutableList die we in-place muteren. Het leidt tot dezelfde uitkomst als de haskell code.
Heel jammer vind ik dat we de lijst handmatig moeten sorteren, en geen gebruik kunnen maken van een SortedSet. Hoewel alle HTree instanties als data classes een correcte equals methode hebben, ziet de Set ze als duplicates, als de comparator op gewicht leidt tot gelijke gewichten. Deze manier performt ook slechter, omdat het op volgorde toevoegen aan een lijst goedkoper is dan steeds de hele lijst sorteren. Misschien is hier nog verbetering (van deze code) mogelijk?
3. binaire codes toekennen
We moeten voor elke leaf node het unieke pad aflopen. We doen dit door elk pad af te lopen en per node een lijst met 0/1 bij te houden. Elke keer als we links gaan, voegen we een 0 toe en voor rechts 1. Voor elke fork maken we een kopie van de lijst (met elementen 0/1) en zetten er 0 of 1 achter.
haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
data Bit = One | Zero
deriving Show
type Code = [Bit]
type CodeMap = Map Char Code
buildCodes :: HTree -> CodeMap
buildCodes = Map.fromList . go []
where
go :: Code -> HTree -> [(Char, Code)]
go prefix tree = case tree of
Leaf _ char -> [(char, reverse prefix)]
Fork _ left right ->
go (One : prefix) left ++
go (Zero: prefix) right
Voor kotlin heb ik de code aangepast (nieuw element achteraan en geen reverse bij de leaf node). Ik weet niet waarom de haskell code dit anders doet.
kotlin
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
enum class Bit(val int: Int) {
Zero(0),
One(1)
}
typealias Code = List<Bit>
typealias CodeMap = Map<Char, Code>
fun buildCodes(hTree: HTree, prefix: Code = listOf()): CodeMap {
return when (hTree) {
is Leaf -> mapOf(hTree.char to prefix)
is Fork -> {
buildCodes(hTree.left, prefix.toList() + listOf(Zero)) +
buildCodes(hTree.right, prefix.toList() + listOf(One))
}
}
}
Deze code is verder haast identiek. Het algoritme kent binaire codes toe aan de chars op de manier die we willen.
De Haskell code is recursief zowel in de aanroep als in de declaratie van de go
functie. Kotlin heeft deze geneste functie niet nodig. De plus (+) operator op List
is handig, maar maakt wel dat we Zero en One eerst in een lijst moeten zetten.
De Bit enum is niet echt nodig (een Int volstaat, evt met controle of het 0/1 is, óf je gebruikt de enum ordinal), maar had ik toegevoegd, om het te laten lijken op de haskell code.
Test
Als we de volgende main
toevoegen, kunnen we vaststellen dat de uitkomst identiek is met die van het genoemde artikel.
1
2
3
4
5
6
7
8
fun main() {
val string = "Try it out with your own content."
val freqMap = countFrequency(string)
val tree = buildTree(freqMap)
val codemap = buildCodes(tree)
println(codemap.map { "'${it.key}'" to it.value.map { it.int } })
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[
('n', [0, 0, 0]),
('.', [0, 0, 1, 0]),
('r', [0, 0, 1, 1]),
('o', [0, 1, 0]),
('y', [0, 1, 1, 0]),
('i', [0, 1, 1, 1]),
('u', [1, 0, 0, 0]),
('w', [1, 0, 0, 1]),
('T', [1, 0, 1, 0, 0]),
('h', [1, 0, 1, 0, 1]),
('c', [1, 0, 1, 1, 0]),
('e', [1, 0, 1, 1, 1]),
('t', [1, 1, 0]),
(' ', [1, 1, 1])
]
Conclusie
Qua expressieve kracht kan kotlin de vergelijking met haskell prima aan. Qua leesbaarheid is het sterker, maar dat is altijd ook een kwestie van kennisniveau en smaak.
De manier waarop is vaak vergelijkbaar maar vaak ook anders. Object inheritance in plaats van algebraic datatypes, bijvoorbeeld. De buildTree in kotlin is minder functioneel en behoorlijk imperatief vanwege de while-loop.
Tot slot: ik hoop dat union types (of rust enums) in alle talen worden toegevoegd!