I have a collection of strings which have a lot of common substrings, and I'm trying to find a good way to define tokens to compress them.

For instance, if my strings are:

s1 = "String"
s2 = "Bool"
s3 = "String -> Bool"
s4 = "String -> String"
s5 = "(String -> String) -> String -> [Bool]"

then I might want to use the tokens:

$1 = "String"
$2 = "Bool"
$3 = "$1 -> $1"

so that the strings may be defined as:

s1 = "$1"
s2 = "$2"
s3 = "$1 -> $2"
s4 = "$3"
s5 = "($3) -> $1 -> [$2]"

(In fact, now it's clear that the definition $4 = " -> " might be good one to add.)

I'm looking for a good (perhaps the best?) way to choose the token definitions. I'm interested in minimizing the total length of the token definitions + the resulting string definitions.

Any ideas?


It's kinda related to this SO question: Huffman encoding with variable length symbols

  • 1
    Couldn't you just use an existing compression library? May 27, 2016 at 2:18
  • 1
    Well - I want to use this particular compression algorithm partly because the decompression routine is very easy to implement. Also, it allows me to decompress any one of the strings without having to expand any of the others. Most compression altos require you to decompress bytes 1 - n in order to determine what byte n+1 is.
    – ErikR
    May 27, 2016 at 7:09
  • It's actually completely orthogonal to Huffman coding.
    – gnasher729
    Jun 3, 2016 at 17:18

2 Answers 2


The generic term for what you're trying to do is grammar-based compression. In particular, you seem to be trying to solve the smallest grammar problem.

See e.g. Charikar, Lehman, Lehman, Liu, Panigrahy, Prabhakaran, Sahai, Shelat (2005). The Smallest Grammar Problem. IEEE Transactions on Information Theory 51 (7): 2554–2576


Lempel-Ziv style compression does the kind of thing you're looking for.

For your application, it sounds like you want a fixed "string dictionary" (LZ's internal representation of your token definitions), rather than the dynamic one used by standard streaming compression programs like gzip or compress. The general Lempel-Ziv scheme is readily adaptable to this kind of thing.

If nothing else, be aware that Lempel-Ziv-style techniques can naturally help compress the token definition data itself.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.