Question

How to perform high‑performance reversible text compression using a word dictionary in Kotlin

Answer 1

/*
    =====================================================================
    High‑Performance Reversible Text Compression Using a Word Dictionary
    ---------------------------------------------------------------------
    This program compresses text by replacing repeated words with tokens
    like @0, @1, @2... and stores each unique word in a dictionary.

    The compressed text is fully reversible.

    WHY THIS VERSION IS FAST (Kotlin):
    ----------------------------------
    • Uses HashMap<String, Int> for O(1) average lookup.
    • Uses MutableList<String> for compact dictionary storage.
    • Manual scanning avoids regex overhead.
    • Uses StringBuilder for efficient string construction.
    • Clean, idiomatic, modern Kotlin design.
    =====================================================================
*/

import kotlin.text.StringBuilder

// ---------------------------------------------------------------------
// Dictionary structure: MutableList + HashMap
// ---------------------------------------------------------------------
class WordDictionary {
    val words: MutableList<String> = mutableListOf()          // index → word
    val indexMap: HashMap<String, Int> = HashMap()            // word → index
}

// ---------------------------------------------------------------------
// Find or add a word to the dictionary (O(1) average)
// ---------------------------------------------------------------------
fun findOrAdd(dict: WordDictionary, word: String): Int {
    dict.indexMap[word]?.let { return it }

    val newIndex = dict.words.size
    dict.words.add(word)
    dict.indexMap[word] = newIndex
    return newIndex
}

// ---------------------------------------------------------------------
// Compress text into @ID tokens
// ---------------------------------------------------------------------
fun compress(input: String, dict: WordDictionary): String {
    val out = StringBuilder(input.length * 2)
    var i = 0
    val n = input.length

    while (i < n) {
        val c = input[i]

        // Pass punctuation/spaces directly
        if (!c.isLetterOrDigit()) {
            out.append(c)
            i++
            continue
        }

        // Extract word
        val start = i
        while (i < n && input[i].isLetterOrDigit()) {
            i++
        }

        val word = input.substring(start, i)

        // Get dictionary index
        val id = findOrAdd(dict, word)

        // Write token
        out.append('@').append(id)
    }

    return out.toString()
}

// ---------------------------------------------------------------------
// Decompress @ID tokens back into original text
// ---------------------------------------------------------------------
fun decompress(compressed: String, dict: WordDictionary): String {
    val out = StringBuilder(compressed.length * 2)
    var i = 0
    val n = compressed.length

    while (i < n) {
        val c = compressed[i]

        // Token?
        if (c == '@') {
            i++
            var id = 0

            // Parse digits
            while (i < n && compressed[i].isDigit()) {
                id = id * 10 + (compressed[i] - '0')
                i++
            }

            if (id in dict.words.indices) {
                out.append(dict.words[id])
            }
        } else {
            // Pass punctuation/spaces
            out.append(c)
            i++
        }
    }

    return out.toString()
}

// ---------------------------------------------------------------------
// Main
// ---------------------------------------------------------------------
fun main() {
    val original =
        "this is is a test test compression string string test " +
        "this is a test compression"

    val dict = WordDictionary()

    val compressed = compress(original, dict)
    val decompressed = decompress(compressed, dict)

    println("Original:      \"$original\"")
    println("Compressed:    \"$compressed\"")
    println("Decompressed:  \"$decompressed\"\n")

    println("Dictionary:")
    dict.words.forEachIndexed { i, w ->
        println("  @$i => $w")
    }
}


/*
run:

Original:      "this is is a test test compression string string test this is a test compression"
Compressed:    "@0 @1 @1 @2 @3 @3 @4 @5 @5 @3 @0 @1 @2 @3 @4"
Decompressed:  "this is is a test test compression string string test this is a test compression"

Dictionary:
  @0 => this
  @1 => is
  @2 => a
  @3 => test
  @4 => compression
  @5 => string

*/

 

70+ SQL courses for beginners and professionals