[Scala] Lempel-Ziv-Welch text compression

Deque · 11-20-2012, 02:10 PM

Hello HC,

this is the first tool I created with Scala, it is also the first time I am dealing with text compression. But it was a lot of fun. I want to provide some code and perfomance measurements here, maybe also some insight for everyone interested.
If anyone of you is good with Scala I would like some feedback for coding too.

This progam uses the LZW algorithm to compress text files. It is a lossless compression. Tools like gzip use it in combination with Huffman coding to compress their data (called Deflate).

LZW is described here: https://en.wikipedia.org/wiki/Lempel%E2%...80%93Welch

First some info about my code:

Download

http://www.multiupload.nl/LONF1GLJH0

Usage

Run:

For compression:

scala lzw.jar -c <filename> [<wordsize>]

For decompression:

scala lzw.jar -d <filename> [<wordsize>]

For version:

scala lzw.jar -v

Example:

scala lzw.jar -c input.txt 16

Example Output:

Compression done. Created output file input1.lzw
size of the input file: 1257260
size of the compressed file: 539175
compression ratio: 57%

Additional information:

A wordsize of 12 is usually good for small files, a wordsize of 16 or more for large files. The default wordsize used will be 14 bits.

The wordsize for decompression must be the same as you used for compression. Otherwise it won't work.

Source

LempelZivWelch.scala

Code:
package model

import scala.collection.breakOut
import scala.collection.mutable.{ Map, HashMap }
import java.io.{
  File,
  FileOutputStream,
  FileInputStream,
  FileWriter,
  FileReader,
  BufferedReader
}

/**
* @constructor
* @param wordSize size of one word in bit, must be greater than 0, values from
*                 10 to 20 are recommended.
*/
class LempelZivWelch(wordSize: Int) {

  require(wordSize > 8) 

  private val EOF = -1

  /**
   * Compresses the given input file and writes the result to the output file.
   * It needs an initial dictionary that contains every possible character of the
   * file.
   *
   * @param dict initial dictionary to be used by the compression algorithm
   * @param inFile
   * @param outFile
   */
  def compress(dict: Dictionary[String, Int], inFile: File, outFile: File): Unit = {
    val writer = new BitOutputStream(new FileOutputStream(outFile))
    val reader = new FileReader(inFile)
    var str = "" //TODO perfomance check with StringBuilder
    var strch: String = null
    var i = reader.read()

    try {

      while (i != -1) {
        var char = i.toChar
        strch = str + char
        if (dict.contains(strch)) {
          str = strch
        } else {
          if (dict.contains(str)) { //skip non-ASCII symbols
            bitOutput(dict(str), writer)

            dict += (strch -> dict.size)
            str = Character.toString(char)
          }
        }
        i = reader.read()
      }
      if (dict.contains(strch)) { //skip non-ASCII symbols
        bitOutput(dict(strch), writer)
      }
    } finally {
      writer.close()
      reader.close()
    }
  }

  /**
   * Decompresses the given input file and writes the result to the output file.
   * It needs an initial dictionary to work properly. It must have the same content
   * as the initial dictionary used for compression.
   *
   * @param dict initial dictionary to be used by the compression algorithm
   * @param inFile
   * @param outFile
   */
  def decompress(dict: Dictionary[Int, String], inFile: File, outFile: File): Unit = {
    val writer = new FileWriter(outFile)
    val reader = new BitInputStream(new FileInputStream(inFile))

    var prevCode: Int = bitInput(reader)
    if (prevCode == EOF) {
      writer.close()
      reader.close()
      return
    }

    textOutput(dict(prevCode), writer)

    var char = dict(prevCode).charAt(0)
    var currCode = 0

    try {
      if (prevCode != EOF) currCode = bitInput(reader)

      while (currCode != EOF) {
        var entry: String = null

        if (dict.contains(currCode)) {
          entry = dict(currCode)
        } else {
          entry = dict(prevCode) + char
        }

        textOutput(entry, writer)
        char = entry.charAt(0)
        dict += (dict.size -> (dict(prevCode) + char))
        prevCode = currCode
        currCode = bitInput(reader)
      }

    } catch {
      case e: NoSuchElementException =>
        Console.err.println("no compressed file given or wrong wordsize used")
        sys.exit(1);
    } finally {
      writer.close()
      reader.close()
    }

  }

  /**
   * Gets the next word from the BitInputStream
   *
   * @param reader
   * @return next word
   */
  private def bitInput(reader: BitInputStream): Int = {
    val bits = Array.fill[Int](wordSize)(0)
    for (i <- 0 until wordSize) {
      bits(i) = reader.readBit()
      if (bits(i) == EOF) return EOF
    }
    return createWordForBits(bits)
  }

  /**
   * Prints the given word (integer result of compression) to the writer
   *
   * @param word
   * @param writer
   */
  private def bitOutput(word: Int, writer: BitOutputStream): Unit = {
    val bits = createBitsForWord(word)
    bits.foreach(writer.writeBit)
  }

  /**
   * Prints the text to the writer
   *
   * @param text
   * @param writer
   */
  private def textOutput(text: String, writer: FileWriter): Unit = {
    writer.write(text)
  }

  /**
   * Returns an array containing the bits that represent the word.
   * Bits are saved as little endian.
   *
   * @param word
   * @return bit array in little endian
   */
  private def createBitsForWord(word: Int): Array[Int] = {
    var w = word
    val bits = new Array[Int](wordSize)
    for (i <- 0 until wordSize) {
      bits(i) = w % 2
      w = w / 2
    }
    return bits
  }

  /**
   * Returns the integer value that is represented by the array of bits.
   * Bits have to be saved in little endian.
   *
   * @param bits
   * @return word/integer that represents the given bits
   */
  private def createWordForBits(bits: Array[Int]): Int =
    bits.foldRight(0)((bit, sum) => sum * 2 + bit)

}

object LempelZivWelch {

  private val version = "lzw version: 0.2\n" +
    "author: Deque\n" +
    "last update: 13. Mai 2012"

  private val usage = """
    Usage: scala lzw.jar -c <filename> [<wordsize>]
           scala lzw.jar -d <filename> [<wordsize>]
  """
  private type OptionMap = Map[Symbol, String]

  def main(args: Array[String]): Unit = {
    invokeCLI(args)
  }

  private def nextOption(map: OptionMap, list: List[String]): OptionMap = {
    list match {
      case Nil => map
      case "-d" :: value :: tail =>
        nextOption(map += ('decompress -> value), tail)
      case "-c" :: value :: tail =>
        nextOption(map += ('compress -> value), tail)
      case "-v" :: tail =>
        nextOption(map += ('version -> ""), tail)
      case value :: Nil => nextOption(map += ('wordsize -> value), list.tail)
      case option :: tail =>
        println("Unknown option " + option + "\n" + usage)
        sys.exit(1)
    }
  }

  private def notExistingFileWithEnding(filename: String, ending: String): File = {
    def setEnding(string: String) = string.split("\\.")(0) + "." + ending
    var file = new File(setEnding(filename))
    var counter = 0
    while (file.exists()) {
      counter += 1
      file = new File(filename.split("\\.")(0) + counter + "." + ending)
    }
    return file
  }

  /**
   * Creates the initial compression dictionary for ASCII
   *
   * @param wordSize size of one word in bit
   */
  def createComprDict(wordSize: Int): Dictionary[String, Int] = {
    val map: HashMap[String, Int] = (for (i <- 0 to 255)
      yield (i.toChar.toString -> i))(breakOut)
    return new Dictionary[String, Int](wordSize, map)
  }

  /**
   * Creates the initial decompression dictionary for ASCII
   *
   * @param wordSize size of one word in bit
   */
  def createDecomprDict(wordSize: Int): Dictionary[Int, String] = {
    val map: HashMap[Int, String] = (for (i <- 0 to 255)
      yield (i -> i.toChar.toString))(breakOut)
    return new Dictionary[Int, String](wordSize, map)
  }

  /**
   * Prints the given file to stdout
   *
   * @param file
   */
  def printFile(file: File): Unit = {
    val reader = new BufferedReader(new FileReader(file));
    try {
      var line = reader.readLine()
      while (line != null) {
        println(line)
        line = reader.readLine()
      }
    } finally {
      reader.close()
    }
  }

  /**
   * Compresses the given input file with the specified wordsize. Result is saved
   * into compressedFile.
   *
   * @param inputFile
   * @param compressedFile
   * @param wordSize size of one word in bit
   */
  def compress(inputFile: java.io.File,
    compressedFile: java.io.File, wordSize: Int): Unit = {
    val lzw = new LempelZivWelch(wordSize)
    lzw.compress(createComprDict(wordSize), inputFile, compressedFile)
  }

  /**
   * Decompresses the given input file with the specified wordsize. Result is saved
   * into decompressedFile.
   */
  def decompress(compressedFile: java.io.File,
    decompressedFile: java.io.File, wordSize: Int): Unit = {
    val lzw = new LempelZivWelch(wordSize)
    lzw.decompress(createDecomprDict(wordSize), compressedFile, decompressedFile)
  }

  /**
   * Prints the size of the input file, the size of the output file and the
   * compression ratio to stdout. The ratio says how much smaller the resulting
   * file is.
   */
  def printCompressionRatio(inputFile: java.io.File,
    compressedFile: java.io.File): Unit = {

    val inputSize = inputFile.length()
    val outputSize = compressedFile.length()
    println("size of uncompressed file: " + inputSize)
    println("size of compressed file: " + outputSize)
    println("compression ratio: "
      + ((inputSize - outputSize) * 100 / inputSize) + "%")
  }

  private def performDecompression(options: model.LempelZivWelch.OptionMap,
    wordSize: Int): Unit = {
    val compressedFile = new File(options('decompress))

    if (!compressedFile.exists()) {
      Console.err.println("file doesn't exist")
      sys.exit(1)
    }

    val decompressedFile = notExistingFileWithEnding(options('decompress), "txt")
    decompress(compressedFile, decompressedFile, wordSize)
    println("Decompression done. Created output file "
      + decompressedFile.getAbsolutePath())
    printCompressionRatio(decompressedFile, compressedFile)
  }

  private def performCompression(options: model.LempelZivWelch.OptionMap,
    wordSize: Int): Unit = {
    val inputFile = new File(options('compress))

    if (!inputFile.exists()) {
      Console.err.println("file doesn't exist")
      sys.exit(1)
    }

    val compressedFile = notExistingFileWithEnding(options('compress), "lzw")
    compress(inputFile, compressedFile, wordSize)
    println("Compression done. Created output file "
      + compressedFile.getAbsolutePath())
    printCompressionRatio(inputFile, compressedFile)
  }

  private def invokeCLI(args: Array[String]): Unit = {
    val options = nextOption(Map(), args.toList)
    if (args.length < 2) {
      if (options.contains('version)) {
        println(version)
      } else {
        println(usage)
        sys.exit(1)
      }
    }

    var wordSize = 14;

    try {
      if (options.contains('wordsize)) {
        wordSize = options('wordsize).toInt
      }
      if (options.contains('decompress)) {
        performDecompression(options, wordSize)
      }
      if (options.contains('compress)) {
        performCompression(options, wordSize)
      }

    } catch {
      case e: NumberFormatException =>
        Console.err.println("wordsize has to be a number")
    }
  }
}

Dictionary.scala

Code:
package model

import scala.collection.mutable.{ HashMap, Map, MapLike }

/**
* LZW-Dictionary
* A wrapper class for a HashMap that implements additional features needed
* for Lempel-Ziv-Welch dictionaries, like freezing. (I will add others in
* the next version)
*
* @constructor Creates a dictionary with the content of the given map.
* @param wordSize size of one word in bit
* @param map
*/
class Dictionary[A, B](wordSize: Int, map: Map[A, B] = new HashMap[A, B])
    extends Map[A, B] with MapLike[A, B, Dictionary[A, B]] {

  private val store: HashMap[A, B] = map match {
    case x: HashMap[A, B] => x
    case x: scala.collection.Map[A, B] => HashMap[A, B](x.toArray: _*)
  }

  private val MAX_DICT_SIZE = math.pow(2, wordSize)
  private var frozen = false

  def +=(kv: (A, B)): this.type = {
    if (!frozen) store += kv
    if (store.size >= MAX_DICT_SIZE) frozen = true
    this
  }

  def -=(key: A): this.type = {
    store -= key
    if (store.size < MAX_DICT_SIZE) frozen = false
    this
  }

  /***** the following functions are only wrappers for the map *****/

  def get(key: A): Option[b] = [/b]store.get(key)
  def iterator: Iterator[(A, B)] = store.iterator  override def size(): Int = store.size
  override def foreach(f: ((A, B)) ⇒ U): Unit = store.foreach(f)
  override def apply(key: A): B = store(key)
  override def empty = new Dictionary[A, B](wordSize)

}

Measurements

Why is the default wordsize 14?

I made some tests to get a value that is good for most cases. I tested 50 books from project gutenberg.
Here is the result of some of my tests (i tested all wordsizes from 9 to 22):

[Image: kwzyrlsi.gif]

The tests are done with this code (beware that this code is only used once, hence I didn't take care to make it nice):

Code:
package model

import java.io.{ File, FileWriter }
import scala.collection.mutable.{ Map, HashMap }

object PerformanceTester {

  val folder = new File("texts/")
  val TESTS_PER_FILE = 5

  def main(args: Array[String]): Unit = {
    performCompressionRatioTest()
  }

  private def performCompressionRatioTest(): Unit = {
    val compressedFile = new File("compressed.txt")
    val compressionData = new HashMap[Long, String]()

    //compression test
    for (wordSize <- 9 to 22) {
      for (inputFile <- folder.listFiles) {
        println("testing file " + inputFile.getAbsolutePath())
        LempelZivWelch.compress(inputFile, compressedFile, wordSize)
        var ratio = compressionRatio(inputFile, compressedFile).toString()
        var value: String = ratio + " '" + inputFile.getName() + "'"
        compressionData += (inputFile.length() -> value)
      }
      printStatistics(compressionData, "ratio" + wordSize)
      println
    }
  }

  private def writeStatistics(file: File, data: scala.collection.Map[Long, String]): Unit = {
    val writer = new FileWriter(file)
    try {
      data.foreach { case (key, value) => writer.write(key + " " + value + "\n") }
    } finally {
      writer.close()
    }
  }

  /**
   * @return compression ratio percentage
   */
  private def compressionRatio(inFile: File, compressedFile: File): Int =
    ((inFile.length() - compressedFile.length()) * 100 / inFile.length()).toInt

  private def printStatistics(compressionData: Map[Long, String], title: String): Unit = {
    println
    println(title + ":")
    var t = scala.collection.immutable.TreeMap(compressionData.toArray: _*)
    t.foreach(println)
    writeStatistics(new File(title + ".csv"), t)
    println("number of entries: " + t.size)
  }

  private def performRuntimeTest(): Unit = {
    var wordSize = 16

    val compressedFile = new File("compressed.txt")
    val decompressedFile = new File("decompressed.txt")
    val compressionData = new HashMap[Long, String]()
    val decompressionData = new HashMap[Long, String]()

    LempelZivWelch.compress(new File("input.txt"), compressedFile, wordSize)

    for (inputFile <- folder.listFiles) {

      println("testing file " + inputFile.getAbsolutePath())

      //compression test
      var sum = 0.0
      for (i <- 1 to TESTS_PER_FILE) {
        val start = System.nanoTime()
        LempelZivWelch.compress(inputFile, compressedFile, wordSize)
        val end = System.nanoTime()
        val seconds = (end - start) / 1000000000.0
        sum += seconds
      }
      var ratio = compressionRatio(inputFile, compressedFile).toString()
      var value: String = (sum / TESTS_PER_FILE).toString() +
        " " + ratio + " '" + inputFile.getName() + "'"
      compressionData += (inputFile.length() -> value)

      //decompression test
      sum = 0
      for (i <- 1 to TESTS_PER_FILE) {
        val start = System.nanoTime()
        LempelZivWelch.decompress(compressedFile, decompressedFile, wordSize)
        val end = System.nanoTime()
        val seconds = (end - start) / 1000000000.0
        sum += seconds
      }
      ratio = compressionRatio(decompressedFile, compressedFile).toString()
      value = (sum / TESTS_PER_FILE).toString() + " " +
        ratio + " '" + inputFile.getName() + "'"
      decompressionData += (compressedFile.length() -> value)
    }

    printStatistics(compressionData, "compression")
    printStatistics(decompressionData, "decompression")

    println
    println("number of files: " + folder.listFiles().length)
  }

}

As you can see I also did some performance tests. Here is a result of that:

[Image: 5vrozubj.png]

The expected runtime is at O(n * log(d)) where n is the length of the file and d is the maximum size of the dictionary. Since d is constant, log(d) is constant too, which means the time complexity is linear. The graph shows just that.

Question to those who are into cryptography: Should you do compression first and encryption afterwards or vice versa?
In case you ever wondered about this, here is the answer:

Spoiler:

This shows the results of my compression tool. It compares randomly generated texts and real texts (books from Project Gutenberg). Compression only works, if there are redundancies that can be removed.

An encryption (one that is actually in use and somewhat safe, I am not talking about caesar cipher or similar) removes redunancies to ensure that there is no pattern in the encrypted text that can be used for cracking. The encrypted text shall look like it was random.

So doing an encryption first and a compression afterwards will make a much worse compression ratio than vice versa.

Have fun
Deque