9
\$\begingroup\$

Write a program which can compress/decompress randomly generated Lorem Ipsum text.

Devise your own lossless algorithm. You may compress your data further using an existing algorithm afterwards, but you must cite the algorithm used.

You may use dictionaries.


The text does not necessarily start with Lorem ipsum dolor sit amet.

The length of the test cases should be between 6400 and 6600 characters. (A picture from this generator.)

Find some test cases here, here, and here.


The program with the best compression ratio wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ Can you add some test cases? Also maybe specify a minimum length? Since Lorem Ipsums always start with "Lorem ipsum dolor sit amet", if I only compress that phrase I can get an infinite compression ratio, but I imagine thats not what you want :) Edit: you also probably want to specify lossless compression. Edit: Damn thought of another loophole. Disallow calling/implementing other compression tools or algos. \$\endgroup\$ – Casey Apr 30 '11 at 4:48
  • \$\begingroup\$ I wonder if there'll be a program which uses a hash table, or something? I'm interested in seeing how much of a compression ratio you can achieve with a 10-bit/hash compression program. Perhaps compress that data further using another compression algorithm? \$\endgroup\$ – Mateen Ulhaq Apr 30 '11 at 7:31
  • \$\begingroup\$ what if we present an algorithm that compresses the text using an original algorithm and then compresses that with something like bzip2? \$\endgroup\$ – Casey Apr 30 '11 at 16:02
  • \$\begingroup\$ @Casey I suppose that's OK. You're 'optimizing' the data for bzip2, not just bzipping it, and hoping to get a few up votes. \$\endgroup\$ – Mateen Ulhaq Apr 30 '11 at 22:38
6
\$\begingroup\$

C# — compression ratio: ≈ 0.27

Uses arithmetic encoding and a custom-designed frequency table derived from several tens of examples generated by Lorem Ipsum Generator3.

Compression is very slow, decompression is instantaneous.

The three test-cases provided give an average compression ratio of 0.27. Best I’ve seen was 0.22.

using System;
using System.IO;
using System.Linq;

namespace Timwi.Temp
{
    public sealed class ArithmeticCodingReader : IDisposable
    {
        private ulong _high, _low, _code;
        private ulong[] _probs;
        private ulong _totalprob;
        private Stream _basestream;
        private byte _curbyte;
        private int _curbit;

        public ArithmeticCodingReader(Stream basestr, ulong[] probabilities)
        {
            _basestream = basestr;
            _high = 0xffffffff;
            _low = 0;
            _probs = probabilities;
            _totalprob = 0;
            for (int i = 0; i < _probs.Length; i++)
                _totalprob += _probs[i];
            _curbyte = 0;
            _curbit = 8;
            _code = 0;
            for (int i = 0; i < 32; i++)
            {
                _code <<= 1;
                _code |= ReadBit() ? 1UL : 0UL;
            }
        }

        public void Dispose()
        {
            _basestream.Close();
        }

        private bool ReadBit()
        {
            if (_curbit > 7)
            {
                _curbit = 0;
                _curbyte = (byte) _basestream.ReadByte();
            }
            bool ret = (_curbyte & (1 << _curbit)) != 0;
            _curbit++;
            return ret;
        }

        public int ReadSymbol()
        {
            ulong pos = ((_code - _low + 1) * _totalprob - 1) / (_high - _low + 1);
            int symbol = 0;
            ulong postmp = pos;
            while (postmp >= _probs[symbol])
            {
                postmp -= _probs[symbol];
                symbol++;
            }
            pos -= postmp;

            ulong newlow = (_high - _low + 1) * pos / _totalprob + _low;
            _high = (_high - _low + 1) * (pos + _probs[symbol]) / _totalprob + _low - 1;
            _low = newlow;

            while ((_high & 0x80000000) == (_low & 0x80000000))
            {
                _high = ((_high << 1) & 0xffffffff) | 1;
                _low = (_low << 1) & 0xffffffff;
                _code = (_code << 1) & 0xffffffff;
                if (ReadBit()) _code++;
            }

            while (((_low & 0x40000000) != 0) && ((_high & 0x40000000) == 0))
            {
                _high = ((_high & 0x7fffffff) << 1) | 0x80000001;
                _low = (_low << 1) & 0x7fffffff;
                _code = ((_code & 0x7fffffff) ^ 0x40000000) << 1;
                if (ReadBit()) _code++;
            }

            return symbol;
        }
    }

    public sealed class ArithmeticCodingWriter : IDisposable
    {
        private ulong _high, _low;
        private int _underflow;
        private ulong[] _probs;
        private ulong _totalprob;
        private Stream _basestream;
        private byte _curbyte;
        private int _curbit;

        public ArithmeticCodingWriter(Stream basestr, ulong[] probabilities)
        {
            _basestream = basestr;
            _high = 0xffffffff;
            _low = 0;
            _probs = probabilities;
            _totalprob = 0;
            for (int i = 0; i < _probs.Length; i++)
                _totalprob += _probs[i];
            _curbyte = 0;
            _curbit = 0;
            _underflow = 0;
        }

        public void WriteSymbol(int p)
        {
            if (p >= _probs.Length)
                throw new Exception("Attempt to encode non-existent symbol");
            if (_probs[p] == 0)
                throw new Exception("Attempt to encode a symbol with zero probability");

            ulong pos = 0;
            for (int i = 0; i < p; i++)
                pos += _probs[i];

            ulong newlow = (_high - _low + 1) * pos / _totalprob + _low;
            _high = (_high - _low + 1) * (pos + _probs[p]) / _totalprob + _low - 1;
            _low = newlow;

            while ((_high & 0x80000000) == (_low & 0x80000000))
            {
                OutputBit((_high & 0x80000000) != 0);
                while (_underflow > 0)
                {
                    OutputBit((_high & 0x80000000) == 0);
                    _underflow--;
                }
                _high = ((_high << 1) & 0xffffffff) | 1;
                _low = (_low << 1) & 0xffffffff;
            }

            while (((_low & 0x40000000) != 0) && ((_high & 0x40000000) == 0))
            {
                _underflow++;
                _high = ((_high & 0x7fffffff) << 1) | 0x80000001;
                _low = (_low << 1) & 0x7fffffff;
            }
        }

        private void OutputBit(bool p)
        {
            if (p) _curbyte |= (byte) (1 << _curbit);
            if (_curbit >= 7)
            {
                _basestream.WriteByte(_curbyte);
                _curbit = 0;
                _curbyte = 0;
            }
            else
                _curbit++;
        }

        public void Dispose()
        {
            OutputBit((_low & 0x40000000) != 0);
            _underflow++;
            while (_underflow > 0)
            {
                OutputBit((_low & 0x40000000) == 0);
                _underflow--;
            }
            _basestream.WriteByte(_curbyte);
            _basestream.Close();
        }
    }

    public class Program
    {
        static string[] elements = { "conclusionemque", "vituperatoribus", "necessitatibus", "concludaturque", "delicatissimi", "signiferumque", "mediocritatem", "interpretaris", "complectitur", "consequuntur", "intellegebat", "deterruisset", "reprehendunt", "definitionem", "disputationi", "definitiones", "contentiones", "voluptatibus", "comprehensam", "theophrastus", "consectetuer", "suscipiantur", "Theophrastus", "dissentiunt", "ullamcorper", "instructior", "liberavisse", "efficiantur", "referrentur", "accommodare", "eloquentiam", "repudiandae", "appellantur", "reformidans", "adversarium", "persequeris", "philosophia", "Efficiantur", "neglegentur", "scriptorem", "Adolescens", "voluptaria", "maiestatis", "sententiae", "moderatius", "quaerendum", "interesset", "efficiendi", "omittantur", "sadipscing", "forensibus", "scripserit", "argumentum", "rationibus", "dissentiet", "reprimique", "elaboraret", "inciderint", "adipiscing", "Consetetur", "assueverit", "democritum", "intellegat", "expetendis", "mnesarchum", "voluptatum", "adolescens", "constituto", "vituperata", "scribentur", "posidonium", "percipitur", "abhorreant", "dissentias", "consetetur", "intellegam", "constituam", "temporibus", "incorrupte", "honestatis", "disputando", "definiebas", "deseruisse", "Voluptatum", "pertinacia", "suavitate", "laboramus", "aliquando", "patrioque", "consulatu", "torquatos", "similique", "evertitur", "assentior", "tractatos", "ocurreret", "accusamus", "consequat", "gubergren", "Urbanitas", "iudicabit", "urbanitas", "splendide", "principes", "convenire", "hendrerit", "partiendo", "Prodesset", "persecuti", "petentium", "expetenda", "prodesset", "maluisset", "tincidunt", "vulputate", "gloriatur", "iracundia", "salutatus", "salutandi", "molestiae", "postulant", "periculis", "mediocrem", "Petentium", "facilisis", "imperdiet", "Periculis", "Accusamus", "Ocurreret", "dignissim", "euripidis", "sapientem", "repudiare", "corrumpit", "erroribus", "qualisque", "explicari", "conceptam", "platonem", "detracto", "oporteat", "insolens", "aliquyam", "verterem", "percipit", "albucius", "propriae", "noluisse", "nominati", "fabellas", "deleniti", "recusabo", "Legendos", "apeirian", "probatus", "recteque", "antiopam", "volutpat", "vivendum", "mentitum", "lucilius", "offendit", "pericula", "fastidii", "detraxit", "accusata", "suscipit", "Appetere", "phaedrum", "delicata", "atomorum", "praesent", "nominavi", "appareat", "senserit", "indoctum", "sensibus", "legendos", "placerat", "takimata", "invidunt", "omnesque", "facilisi", "menandri", "accumsan", "voluptua", "perfecto", "invenire", "eleifend", "perpetua", "quaestio", "lobortis", "scaevola", "Recusabo", "Menandri", "electram", "copiosae", "epicurei", "mandamus", "Placerat", "appetere", "deserunt", "inimicus", "luptatum", "oportere", "ancillae", "molestie", "delectus", "Lucilius", "officiis", "eligendi", "Vivendum", "Atomorum", "adipisci", "pertinax", "Offendit", "ponderum", "Singulis", "Invidunt", "aeterno", "iuvaret", "feugait", "Nostrum", "fierent", "viderer", "meliore", "admodum", "fabulas", "facilis", "nostrud", "aliquip", "dolorum", "docendi", "dolores", "ornatus", "Diceret", "denique", "eruditi", "ceteros", "alterum", "volumus", "Nonummy", "delenit", "laoreet", "impedit", "virtute", "habemus", "alienum", "numquam", "blandit", "equidem", "vivendo", "epicuri", "bonorum", "integre", "oblique", "prompta", "debitis", "impetus", "maiorum", "labitur", "nostrum", "corpora", "Omittam", "Ceteros", "omittam", "labores", "aperiam", "discere", "regione", "graecis", "Epicuri", "nonummy", "commodo", "malorum", "civibus", "aliquid", "commune", "veritus", "Tritani", "Sanctus", "vidisse", "eripuit", "euismod", "tibique", "dolorem", "Denique", "Prompta", "nusquam", "aliquam", "fuisset", "saperet", "utroque", "Minimum", "legimus", "Fuisset", "quaeque", "Scripta", "persius", "aperiri", "sanctus", "Volumus", "inermis", "Corpora", "minimum", "tamquam", "tritani", "Virtute", "vocibus", "feugiat", "Docendi", "Viderer", "accusam", "Iuvaret", "scripta", "Malorum", "Laoreet", "nonumy", "iudico", "cetero", "putant", "verear", "ignota", "Causae", "audiam", "oratio", "facete", "primis", "populo", "possim", "animal", "utinam", "utamur", "doming", "semper", "mollis", "graeco", "timeam", "graece", "partem", "Soluta", "mucius", "omnium", "quando", "munere", "essent", "causae", "Melius", "Decore", "tation", "consul", "tempor", "tantas", "Veniam", "eirmod", "veniam", "quodsi", "audire", "Munere", "graeci", "Essent", "melius", "nemore", "Soleat", "noster", "everti", "putent", "congue", "nostro", "postea", "Tempor", "iriure", "homero", "quidam", "dicunt", "decore", "Noster", "dictas", "laudem", "exerci", "Exerci", "iisque", "legere", "Iriure", "soluta", "dolore", "vocent", "Nostro", "ubique", "ridens", "Ubique", "option", "Mollis", "Audiam", "Postea", "labore", "Semper", "Partem", "Dolore", "possit", "dicant", "Iudico", "affert", "Labore", "latine", "soleat", "doctus", "Putent", "Congue", "Iisque", "libris", "tollit", "Verear", "Vocent", "Dictas", "Consul", "Affert", "Tantas", "Putant", "altera", "Homero", "Lorem", "ipsum", "liber", "Rebum", "aeque", "magna", "dicat", "Harum", "dicam", ".\r\n\r\n", "omnes", "Dicat", "choro", "Simul", "summo", "ullum", "mutat", "Aeque", "reque", "errem", "porro", "viris", "Erant", "nobis", "justo", "Modus", "velit", "solet", "zzril", "facer", "posse", "dicta", "mazim", "paulo", "inani", "movet", "falli", "Illum", "assum", "dicit", "Fugit", "ferri", "Clita", "solum", "adhuc", "sonet", "Solet", "rebum", "Ullum", "elitr", "Natum", "lorem", "Facer", "idque", "brute", "natum", "modus", "iusto", "Omnis", "illud", "minim", "Elitr", "dolor", "saepe", "Ferri", "autem", "atqui", "malis", "error", "erant", "fugit", "vitae", "nihil", "nulla", "simul", "habeo", "Augue", "harum", "Sonet", "Nobis", "Illud", "Summo", "mundi", "Brute", "Minim", "Autem", "Dicit", "Zzril", "Novum", "novum", "illum", "Nulla", "Error", "Movet", "etiam", "augue", "debet", "omnis", "clita", "probo", "Mundi", "Malis", "prima", "Falli", "vidit", "Debet", "Prima", "Errem", "diam", "alia", "kasd", "Amet", "modo", "wisi", "sint", "meis", "Elit", "enim", "vero", "quot", "tale", "puto", "Cibo", "quod", "quis", "erat", "Hinc", "Quod", "hinc", "Nisl", "dico", "quem", "Vero", "Sumo", "odio", "unum", "duis", "Odio", "eros", "Dico", "stet", "vide", "tota", "Alii", "Puto", "Eius", "sumo", "nisl", "Quas", "sale", "agam", "alii", "quas", "Stet", "Nibh", "cibo", "Agam", "veri", "nibh", "elit", "esse", "eius", "suas", "Quis", "Quot", "Erat", "amet", "vix", "nec", "vis", "est", "Cum", "vim", "pri", "mel", "cum", "qui", "ius", "duo", "Eos", "vel", "sed", "His", "Nec", "usu", "eos", "Pri", "mea", "sit", "sea", "Ius", "eam", "nam", "Duo", "Eum", "Nam", "Eam", "mei", "has", "eum", "pro", "per", "quo", "his", "Vix", "Sed", "Quo", "Est", "Vim", "Per", "Vel", "Mel", "Mei", "Vis", "Mea", "Sea", "Has", "Usu", "Pro", "Sit", "Qui", "no", ", ", "eu", ". ", "ea", "et", "cu", "te", "ut", "Ut", "Et", "ei", "ad", "at", "in", "Ne", "ex", "ne", "id", "Ei", "An", "an", "Ea", "Eu", "At", "Te", "No", "Ex", "In", "Cu", "Id", "Ad", " ", "." };
        static ulong[] frequencies = { 4, 5, 9, 7, 3, 7, 3, 2, 6, 8, 6, 8, 6, 5, 3, 7, 6, 5, 4, 5, 3, 4, 1, 4, 7, 5, 10, 8, 4, 8, 5, 2, 3, 3, 5, 3, 5, 1, 3, 7, 1, 11, 4, 4, 9, 6, 8, 6, 8, 3, 9, 8, 7, 5, 4, 9, 9, 2, 5, 1, 3, 5, 6, 4, 3, 6, 8, 11, 4, 3, 4, 6, 3, 2, 7, 3, 4, 5, 2, 8, 6, 6, 2, 1, 1, 5, 6, 3, 8, 6, 9, 3, 1, 7, 5, 5, 5, 4, 6, 1, 7, 6, 5, 8, 8, 4, 3, 1, 6, 7, 8, 6, 4, 2, 10, 7, 9, 5, 5, 4, 5, 6, 6, 1, 5, 3, 1, 1, 1, 5, 5, 6, 1, 3, 6, 1, 1, 2, 5, 8, 10, 6, 9, 8, 3, 6, 6, 4, 3, 5, 4, 3, 2, 3, 2, 6, 4, 6, 4, 3, 2, 5, 5, 4, 7, 3, 4, 1, 7, 5, 6, 9, 2, 2, 1, 3, 4, 4, 7, 7, 7, 6, 7, 1, 5, 2, 4, 9, 3, 3, 4, 2, 3, 1, 1, 3, 4, 2, 4, 1, 5, 3, 2, 4, 4, 6, 4, 3, 1, 4, 2, 1, 1, 2, 1, 1, 4, 1, 1, 5, 4, 3, 1, 7, 9, 6, 7, 7, 1, 8, 6, 4, 7, 4, 4, 2, 6, 8, 10, 6, 8, 1, 8, 11, 6, 2, 9, 6, 8, 5, 5, 4, 9, 4, 5, 7, 8, 8, 3, 4, 3, 6, 10, 1, 1, 7, 7, 4, 5, 3, 3, 1, 3, 3, 3, 6, 2, 7, 11, 2, 1, 6, 2, 7, 3, 6, 2, 1, 6, 5, 4, 4, 6, 1, 6, 1, 6, 1, 1, 5, 5, 1, 4, 1, 8, 1, 3, 1, 4, 1, 1, 1, 6, 1, 2, 1, 1, 4, 5, 6, 9, 8, 4, 1, 3, 4, 6, 5, 3, 5, 6, 8, 3, 4, 5, 9, 8, 7, 7, 6, 2, 4, 6, 6, 4, 4, 6, 2, 1, 6, 9, 6, 5, 1, 2, 5, 4, 3, 1, 5, 2, 6, 4, 2, 8, 9, 4, 5, 2, 2, 2, 6, 4, 10, 11, 4, 1, 5, 5, 5, 1, 3, 8, 1, 5, 3, 5, 1, 5, 8, 2, 4, 1, 2, 1, 1, 1, 1, 2, 7, 3, 1, 3, 1, 3, 1, 2, 1, 1, 1, 2, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 6, 5, 5, 2, 4, 99, 8, 1, 4, 1, 5, 5, 7, 1, 8, 4, 5, 2, 4, 6, 6, 2, 4, 3, 4, 7, 8, 4, 6, 6, 2, 5, 3, 2, 4, 6, 2, 7, 2, 8, 6, 8, 3, 7, 2, 4, 2, 7, 1, 5, 6, 5, 4, 4, 1, 4, 4, 1, 7, 3, 2, 8, 4, 7, 4, 7, 5, 5, 3, 4, 3, 3, 1, 5, 2, 1, 3, 2, 3, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 5, 7, 4, 2, 6, 3, 8, 4, 2, 7, 6, 2, 4, 6, 1, 4, 6, 8, 1, 2, 5, 2, 4, 5, 2, 1, 4, 2, 3, 1, 8, 2, 4, 2, 3, 1, 2, 1, 2, 4, 1, 5, 5, 2, 2, 2, 3, 4, 1, 3, 2, 3, 2, 3, 1, 1, 1, 1, 2, 21, 26, 35, 26, 9, 23, 34, 30, 33, 28, 30, 38, 4, 36, 20, 10, 3, 31, 21, 8, 34, 29, 26, 9, 25, 29, 11, 6, 7, 11, 32, 38, 23, 34, 22, 22, 33, 4, 6, 7, 4, 7, 7, 5, 8, 8, 7, 6, 4, 9, 7, 4, 5, 4, 70, 458, 57, 401, 52, 47, 63, 65, 59, 10, 12, 56, 42, 46, 45, 15, 53, 57, 55, 9, 9, 45, 9, 5, 8, 12, 14, 13, 5, 11, 8, 7, 3358, 1 };

        static void Main(string[] args)
        {
            if (args.Length != 2 || !new[] { "-c", "-d" }.Contains(args[0]) || !File.Exists(args[1]))
            {
                Console.WriteLine("Command-line parameters:");
                Console.WriteLine(" -c [file]   Compress file. (Output is file + “.compressed”.)");
                Console.WriteLine(" -d [file]   Decompress file. (Output is file + “.decompressed.txt”.)");
                return;
            }

            var freqs = Enumerable.Range(0, 129).Select(i => 1UL).Concat(frequencies).ToArray();

            if (args[0] == "-c")
            {
                var input = File.ReadAllText(args[1]);
                if (input.Any(ch => ch > 127))
                    throw new InvalidOperationException("Only ASCII characters are supported.");

                using (var file = File.Open(args[1] + ".compressed", FileMode.Create, FileAccess.Write))
                using (var acw = new ArithmeticCodingWriter(file, freqs))
                {
                    while (input.Length > 0)
                    {
                        int i = 0;
                        while (i < elements.Length && !input.StartsWith(elements[i]))
                            i++;
                        if (i < elements.Length)
                        {
                            acw.WriteSymbol(i + 129);
                            input = input.Substring(elements[i].Length);
                        }
                        else
                        {
                            acw.WriteSymbol(input[0]);
                            input = input.Substring(1);
                        }
                    }
                    acw.WriteSymbol(128);
                }
            }
            else
            {
                using (var file = File.Open(args[1], FileMode.Open, FileAccess.Read))
                using (var acr = new ArithmeticCodingReader(file, freqs))
                using (var outputFile = File.Open(args[1] + ".decompressed.txt", FileMode.Create, FileAccess.Write))
                using (var outputWriter = new StreamWriter(outputFile))
                {
                    while (true)
                    {
                        int i = acr.ReadSymbol();
                        if (i == 128)
                            break;
                        outputWriter.Write(i < 128 ? ((char) i).ToString() : elements[i - 129]);
                    }
                }
            }

            Console.WriteLine("Done.");
        }
    }
}
\$\endgroup\$
6
\$\begingroup\$

Python - Star Transform Turned Huffman [ratio=55% (decimal), and 45.4% (base36)]

This started out as a star transformation algorithm, but morphed into a Huffman-style frequency based encoding.

I generated a frequency dictionary of lorem ipsum words (using the NLTK) from the samples, and then assigned them decimal values. Words are then substituted for their decimal values. There are some special cases for new lines and capital letters.

There are 3 different compression options: normal, strict, and stricter. Normal uses decimal encoding, strict uses hex encoding, and stricter uses base 36 encoding. Both strict and stricter will have problems if there are new words.

compress.py

#!/usr/bin/env python
import sys,re,lorem

strict = len(sys.argv) == 2 and sys.argv[1] == '-s'
stricter = len(sys.argv) == 2 and sys.argv[1] == '-ss'

text = sys.stdin.read()
dict = lorem.dictionary

splitter = re.compile(r'([a-zA-Z]+|\s+|[,\.]*)')
words = splitter.findall(text)
for w in words:
    if w.lower() in dict:
        code = int(dict[w.lower()])
        if strict:
            code = lorem.strict_code(code)
        elif stricter:
            code = lorem.base36encode(code)
        if w.istitle():
                code = '^%s' %(code)
        sys.stdout.write(str(code))
    elif w == '\n\n ':
        sys.stdout.write('~')
    else:
        sys.stdout.write(w)

decompress.py

#!/usr/bin/env python
import sys,re,lorem

strict = len(sys.argv) == 2 and sys.argv[1] == '-s'
stricter = len(sys.argv) == 2 and sys.argv[1] == '-ss'

text = sys.stdin.read()

# create the inverse of the dictionary
dict = dict((v,k) for k, v in lorem.dictionary.iteritems())

splitter = re.compile(r'(\s+|\^?[0-9a-zA-Z]+|[a-zA-Z]+|\^?\d+|[,\.~]?)')
words = splitter.findall(text)
for w in words:
    code = w
    upper = False
    if len(code) > 1 and code[0] == '^':
        code = code[1:]
        upper = True
    if strict:
        #print code, lorem.strict_str(code)
        code = lorem.strict_str(code)
    elif stricter:
        try:
            #print "\n'"+code+"'", lorem.base36decode(code)
            code = str(lorem.base36decode(code))
        except ValueError:
            pass
    if code in dict:
        sys.stdout.write(dict[code].title() if upper else dict[code])
    elif w == '~':
        sys.stdout.write('\n\n ')
    else:
        sys.stdout.write(w)

lorem.py - library file

dictionary ={'consul': '64', 'discere': '378', 'virtute': '78', 'salutatus': '430', 'appareat': '362', 'doctus': '452', 'definiebas': '285', 'labitur': '399', 'vel': '34', 'te': '7', 'audire': '447', 'libris': '232', 'delicatissimi': '290', 'consequat': '194', 'veri': '351', 'fierent': '307', 'solet': '166', 'aliquip': '359', 'vero': '173', 'torquatos': '346', 'urbanitas': '483', 'habeo': '309', 'clita': '369', 'ferri': '390', 'integre': '313', 'nemore': '46', 'aeterno': '183', 'partem': '103', 'nusquam': '467', 'cetero': '191', 'natum': '465', 'fabulas': '215', 'eleifend': '454', 'voluptatibus': '79', 'apeirian': '187', 'diam': '291', 'interpretaris': '314', 'essent': '304', 'nec': '35', 'mollis': '319', 'erroribus': '52', 'mea': '30', 'ludus': '235', 'mel': '31', 'sint': '112', 'error': '51', 'mei': '39', 'decore': '126', 'repudiandae': '161', 'imperdiet': '393', 'soluta': '113', 'saperet': '337', 'aliquam': '184', 'invidunt': '460', 'dicta': '85', 'viderer': '441', 'nulla': '99', 'takimata': '263', 'insolens': '312', 'dicunt': '294', 'tractatos': '266', 'vim': '36', 'vis': '18', 'causae': '368', 'modus': '408', 'iusto': '143', 'vix': '16', 'oporteat': '74', 'zzril': '80', 'assentior': '189', 'meliore': '241', 'liber': '402', 'molestiae': '318', 'efficiendi': '87', 'usu': '29', 'lucilius': '403', 'ocurreret': '100', 'indoctum': '396', 'solum': '478', 'luptatum': '236', 'legendos': '230', 'voluptatum': '271', 'democritum': '128', 'detracto': '376', 'officiis': '153', 'sententiae': '477', 'salutandi': '429', 'prompta': '332', 'dictas': '202', 'accusamus': '355', 'alia': '81', 'conclusionemque': '449', 'phaedrum': '328', 'reque': '60', 'exerci': '305', 'minimum': '463', 'antiopam': '186', 'nullam': '246', 'similique': '261', 'regione': '258', 'quot': '335', 'mnesarchum': '147', 'inimicus': '92', 'aeque': '274', 'animal': '121', 'quod': '424', 'vitae': '43', 'dissentias': '296', 'affert': '119', 'numquam': '414', 'abhorreant': '273', 'gloriatur': '308', 'mutat': '410', 'disputando': '379', 'conceptam': '193', 'sit': '40', 'honestatis': '311', 'iracundia': '461', 'maluisset': '240', 'dicant': '377', 'electram': '134', 'petentium': '156', 'propriae': '333', 'recusabo': '336', 'adversarium': '118', 'oblique': '72', 'possim': '254', 'elit': '209', 'euripidis': '385', 'nonumy': '151', 'possit': '472', 'iudico': '462', 'omnes': '249', 'ius': '28', 'nostro': '152', 'eum': '25', 'repudiare': '427', 'etiam': '384', 'omittam': '247', 'ornatus': '154', 'suavitate': '262', 'civibus': '192', 'comprehensam': '84', 'dicit': '50', 'nibh': '321', 'facilis': '306', 'patrioque': '155', 'laboramus': '316', 'nihil': '243', 'odio': '468', 'ipsum': '315', 'tollit': '61', 'scribentur': '432', 'docendi': '204', 'quaerendum': '106', 'diceret': '200', 'fastidii': '136', 'liberavisse': '317', 'ei': '11', 'ea': '3', 'recteque': '425', 'ex': '4', 'eu': '10', 'et': '8', 'molestie': '98', 'aliquid': '446', 'aliquyam': '276', 'mediocritatem': '405', 'efficiantur': '133', 'menandri': '406', 'dissentiet': '67', 'pericula': '251', 'tamquam': '481', 'hendrerit': '310', 'tritani': '436', 'cibo': '83', 'scriptorem': '260', 'disputationi': '295', 'euismod': '455', 'qui': '17', 'equidem': '135', 'quo': '15', 'saepe': '163', 'accusata': '180', 'tibique': '265', 'homero': '140', 'referrentur': '257', 'neglegentur': '148', 'bonorum': '448', 'principes': '158', 'enim': '211', 'appellantur': '122', 'volumus': '443', 'graeco': '90', 'graeci': '138', 'persecuti': '56', 'posidonium': '253', 'percipitur': '470', 'dolorum': '297', 'option': '250', 'quando': '256', 'veritus': '172', 'quas': '421', 'epicuri': '300', 'gubergren': '139', 'accumsan': '354', 'graece': '457', 'nominati': '150', 'splendide': '343', 'ponderum': '75', 'sonet': '77', 'instructior': '141', 'omnis': '415', 'intellegam': '93', 'habemus': '392', 'verear': '439', 'corrumpit': '284', 'pri': '14', 'vocent': '484', 'expetendis': '387', 'duis': '132', 'soleat': '342', 'ridens': '162', 'tale': '480', 'latine': '228', 'aperiam': '277', 'mazim': '69', 'ignota': '222', 'elitr': '210', 'scripta': '259', 'argumentum': '188', 'veniam': '350', 'perpetua': '104', 'expetenda': '386', 'esse': '213', 'erant': '383', 'philosophia': '416', 'constituam': '282', 'ceteros': '124', 'sale': '428', 'inani': '394', 'oratio': '47', 'adipiscing': '116', 'alienum': '445', 'errem': '68', 'dolor': '205', 'probo': '418', 'elaboraret': '208', 'laoreet': '401', 'blandit': '123', 'quaestio': '476', 'delenit': '287', 'nobis': '244', 'sadipscing': '110', 'platonem': '329', 'contentiones': '374', 'quem': '422', 'dico': '201', 'oportere': '102', 'dolore': '453', 'laudem': '229', 'reprehendunt': '426', 'invenire': '95', 'consequuntur': '450', 'vocibus': '177', 'his': '38', 'signiferumque': '111', 'utroque': '348', 'congue': '372', 'intellegat': '142', 'qualisque': '58', 'complectitur': '371', 'meis': '70', 'unum': '438', 'prima': '474', 'nisl': '149', 'accommodare': '178', 'tation': '435', 'ancillae': '185', 'suscipit': '345', 'sed': '33', 'sea': '32', 'incorrupte': '395', 'labore': '400', 'postulant': '473', 'temporibus': '482', 'nostrum': '245', 'nostrud': '413', 'posse': '471', 'partiendo': '469', 'debitis': '197', 'aliquando': '358', 'eirmod': '207', 'detraxit': '130', 'malorum': '96', 'verterem': '267', 'melius': '54', 'viris': '442', 'altera': '120', 'mandamus': '145', 'magna': '237', 'amet': '361', 'omnium': '101', 'summo': '167', 'tempor': '169', 'facer': '216', 'facilisis': '217', 'placerat': '57', 'maiestatis': '404', 'doming': '206', 'evertitur': '456', 'quodsi': '76', 'assum': '278', 'cu': '13', 'mentitum': '71', 'quis': '59', 'duo': '23', 'eros': '302', 'puto': '475', 'feugiat': '137', 'pro': '21', 'inciderint': '45', 'lobortis': '233', 'dolores': '86', 'consulatu': '283', 'vituperatoribus': '269', 'senserit': '433', 'atqui': '190', 'suas': '479', 'pertinax': '327', 'eligendi': '381', 'impedit': '224', 'corpora': '196', 'agam': '275', 'vulputate': '115', 'fuisset': '220', 'volutpat': '272', 'noster': '322', 'rationibus': '160', 'offendit': '323', 'semper': '340', 'erat': '212', 'prodesset': '419', 'accusam': '179', 'in': '0', 'debet': '375', 'id': '20', 'cotidieque': '65', 'minim': '55', 'movet': '464', 'sensibus': '341', 'paulo': '324', 'omittantur': '248', 'audiam': '365', 'commune': '370', 'vivendo': '270', 'commodo': '280', 'fabellas': '88', 'brute': '367', 'persius': '252', 'delicata': '289', 'iuvaret': '144', 'graecis': '391', 'appetere': '363', 'deleniti': '288', 'legere': '231', 'aperiri': '82', 'choro': '63', 'deseruisse': '129', 'utamur': '347', 'iisque': '53', 'inermis': '91', 'concludaturque': '281', 'scripserit': '339', 'theophrastus': '264', 'eruditi': '303', 'noluisse': '412', 'impetus': '459', 'vide': '440', 'hinc': '221', 'dissentiunt': '131', 'cum': '37', 'has': '19', 'percipit': '325', 'tantas': '168', 'eripuit': '301', 'sumo': '434', 'perfecto': '42', 'interesset': '397', 'primis': '255', 'copiosae': '451', 'kasd': '227', 'munere': '409', 'facilisi': '44', 'scaevola': '431', 'explicari': '214', 'omnesque': '73', 'vidisse': '174', 'velit': '349', 'facete': '388', 'iudicabit': '225', 'timeam': '170', 'augue': '279', 'eloquentiam': '382', 'tota': '62', 'est': '41', 'persequeris': '105', 'iriure': '398', 'per': '22', 'epicurei': '299', 'reprimique': '109', 'necessitatibus': '411', 'adipisci': '182', 'atomorum': '48', 'sapientem': '338', 'definitionem': '127', 'definitiones': '286', 'stet': '114', 'probatus': '417', 'moderatius': '97', 'rebum': '107', 'intellegebat': '94', 'justo': '226', 'simul': '164', 'modo': '407', 'autem': '366', 'falli': '389', 'putant': '159', 'vituperata': '268', 'delectus': '198', 'adolescens': '356', 'praesent': '331', 'putent': '334', 'feugait': '218', 'maiorum': '238', 'dolorem': '380', 'singulis': '165', 'vivendum': '176', 'ubique': '171', 'forensibus': '219', 'illum': '223', 'eam': '27', 'illud': '458', 'mediocrem': '146', 'voluptaria': '444', 'admodum': '117', 'postea': '157', 'deserunt': '66', 'adhuc': '181', 'wisi': '353', 'ut': '9', 'malis': '239', 'reformidans': '108', 'eius': '298', 'vidit': '175', 'ad': '1', 'mundi': '320', 'fugit': '89', 'an': '2', 'consetetur': '373', 'at': '5', 'pertinacia': '326', 'albucius': '357', 'constituto': '125', 'no': '6', 'quaeque': '420', 'ne': '12', 'nam': '26', 'mucius': '242', 'dignissim': '203', 'alterum': '360', 'convenire': '195', 'denique': '199', 'dicam': '292', 'quidam': '423', 'assueverit': '364', 'lorem': '234', 'suscipiantur': '344', 'dicat': '293', 'voluptua': '352', 'ullamcorper': '437', 'nominavi': '466', 'eos': '24', 'porro': '330', 'consectetuer': '49'}

# base 36 impl from wikipedia
# http://en.wikipedia.org/wiki/Base_36#Python_implementation
def base36encode(number, alphabet='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'):
    """Convert positive integer to a base36 string."""
    if not isinstance(number, (int, long)):
        raise TypeError('number must be an integer')

    # Special case for zero
    if number == 0:
        return alphabet[0]

    base36 = ''

    sign = ''
    if number < 0:
        sign = '-'
        number = - number

    while number != 0:
        number, i = divmod(number, len(alphabet))
        base36 = alphabet[i] + base36

    return sign + base36

def base36decode(number):
    return int(number, 36)

def strict_code(code):
    return hex(int(code))[2:]

def strict_str(code):
    try:
        return str(int(code,16))
    except ValueError:
        return code

process.py - creates the encoding dictionary

#!/usr/bin/env python

from nltk.probability import *
from nltk.tokenize import *
from sets import Set

txt = open('lorem', 'r').read()
tokens = list(WordTokenizer().tokenize(txt))
freq = FreqDist()
for w in tokens:
    freq.inc(w.lower())
tokens_sorted = sorted(freq, key=freq.get, reverse=True)

d = {}
star_count = 0
for i in tokens_sorted:
    d[i] = str(star_count)
    star_count += 1

print d

First test case compressed

^M 8 6B 4F 2O, 1F 7A M C. ^BB 2H 18 2 10, 25 1P AG 13 D. ^I 1G 92 1, 7 8R 3Q S. ^0 11 5M 9D 9J. ^M 2 2O B1.~^5 Z 4N 5H 1D, M 9F 19 1. ^5 2V 1G 3E E, AU 1Z E 3. ^5 7Q 22 2K H, T 4V AO 0, W 7 5K 3Y. ^9Z 2M G 8, T 7 3C 1A.~^1P 4P 3M 6 O, I 4O 4P 4G 4, 1H CJ 57 S 1. ^1R 1A P 3, B J 5R 4W 4Y. ^V 1 B6 AW 42, BQ 17 7B C X, 1J 2Q 18 0 G. ^7 4T 2U V. ^V 4 2D A3 3H.~^0 Z 17 6D 9G, 2 Q 51 3A, 0 77 6K BL R. ^6 16 31 M, Y 0 96 89. ^R 5 1Q 6D 58, C 49 2N Y. ^7 2B 3Y P. ^2R 17 2Y U 1, 2A 2E 7A W 3.~^4J 7O L C. ^6 T 8V 6W 7Y, 1 3W D4 P, 1B 1L 43 N 9. ^4 CK 7P 4E S, N 4 4T 7O. ^D 12 6X 4J CM, X 1F 9G 9. ^G C9 4X C, V 67 5U 2N 1. ^7 W AN 5H 37, 66 4W 3P P 4.~^V 6D 2L 78 6, 2R 6F 4 H. ^A 3W 2A 8D X. ^0 O 76 1D. ^CX 3S R 3, 2 16 3P L, 5 Y B7 5D. ^U 1 3U AI BY, 4 49 43 8Q X. ^1B 1S 24 X K, 1Q 6A 2L L 8.~^E 1 5V 2Z 9J. ^K S 6A AQ 7U, 2H 7K 7X 1 J. ^2H 75 1D Q 1. ^4T 78 3E B L, 51 2L B 11, 4K 5B 41 D S. ^0 5C 7H G, 1H 9J X 7.~^11 6L 46 A. ^5 U 9P BI 23, O 2U 6W 2. ^X 3 2D 4Q 3F, M 5L 3R 0, B5 B9 2 Z. ^60 3K 4 X, V K 9Q 8O 2Y. ^P 5 7S 2N 7X. ^G B 35 98, 8W 3V B 15.~^2 V 4S 95 5E, J 0 5R A3. ^P 0 1B 27. ^E BW AH 5, 1A 3Q Q 2. ^25 8P 1L T A, I 7Q 6X 5.~^Q 8 39 3G 55. ^42 4H T 1. ^1 11 24 AL 2C. ^9 P 8A DA 9N, E K 6C 8I, 3 G 1Y 2U 7J.~^4N 2P L A, 54 8T 3 E. ^93 9W 88 K E, C 83 1R 44 E, D7 17 4G Y D. ^13 D 7D AQ 63. ^V 2 C2 5J 3Y, 51 5G B G. ^3 16 5D 1D L. ^8G BO I 7.~^M 4 6A 16 7W, 3 E 2A 3M, J 2 5M 2S. ^8J B9 V 1. ^74 7K O D, 2 2G 5N 3H Y. ^1B 62 1M T 9, 1N 73 CB B G, X C 1E 7H. ^R 1 2J 9U, 49 AE A S, B 9R 5F 3A 13. ^Q 26 61 2, M A 50 3V BF.~^5 16 41 27 10. ^5X 1R 7K 5 G, A 15 1J CN 9S. ^11 6J 2K 7K D, 12 7M 4S 19 K. ^0 6P 6T 27 R, 1U 9C 8N 3 Z. ^N 0 5V CB A2, S 5H 2X 4.~^2Z 5U F 1. ^2 I CS 1T, 7L 1T J 8. ^7I 3F 7T W 1. ^R 8 9E 19. ^F 3T 3N 2, 2Q 2Y F 4. ^H 5 7Z 3Y, A 1O 57 A4 W, I 25 2L A.~^0 9B 9A G, X 5 72 2K 3N, 4 F 6U 22. ^9 4W AX T, W 1 2T 71 AB. ^E 85 60 6F 6. ^51 7F BX A H, M 4 7Z BN.~^A L 47 6E. ^8X 6S 5Y 2 12, 93 4C B Q. ^1 I 7N 1V 33, 1 13 36 2P 27. ^4 9U 97 10. ^L 0 5A 3W, M 9X 56 6. ^7 5I 75 Q.~^7M 2T 0 Q, AK 2W 4B U 8. ^7N 1I 92 12 8, 9S 2W F 4. ^V 7 5T 1I 64, 14 66 9L 6. ^O 2 4V 4S, 74 5C P 4.~^5 O 25 2Q, 15 62 1V 0, 3G 2X 10 9. ^9G 38 58 M 7, 11 B 84 BL 52. ^2D 41 F 1. ^K 7S 7P F.~^3 7Q 30 T. ^4 G 4F 89, Q 1E 1I D2 K. ^B Z 3S 7V. ^5 AY 23 Q, 4Q 23 6E T 2, E 8 A7 5J 82.~^9L 94 8 E. ^B 62 8K U. ^S 3 67 6I 1R, BS 26 L 7, B3 3E K H. ^72 3D 30 10 2, A 45 83 22 F.~^4N 6R 5 L, 12 D 65 3Z AA. ^K M 60 6C, 9 4V 88 3A N. ^D V 5W 4G. ^H 1 5I 52 79, S 4 34 C0. ^36 7X 30 L 9. ^P 3D 1V 5. ^Q 1E 70 1.~^6 12 1Q 3L, 5P 77 49 2 13. ^7R 2A 3E 5 W, 8 BH 5O 55 T, 8W 1B 0 N. ^DC 5V 9T 6 H, V 26 3V A. ^2 7O 2P 32 E. ^D 38 6W M.~^16 50 31 A 10, X 3 5Q DG 9F, A8 99 0 11. ^3I 7J B H, 5B D1 5S 6 P. ^E A 6U 2O, E 1J 62 5S 6. ^I 2 6N 35, 1W 28 9 U, J 34 8C A. ^Z 4D 37 7C 1, L 6 5K BZ 9M.~^7W 2Y Z 0. ^4M 4H U 5, 0 15 2V 9V 63, 2D 4G P 4. ^AH 2E F 3, 0 15 91 6O 1T, 3 N 2G 6Z. ^U K 1J 4K 46, 3 H BD DF AJ, 11 D D6 1H.

Sources in my github repo.

\$\endgroup\$
4
\$\begingroup\$

A simple but good JavaScript compressor (ratio=0.312)

Averaging the three test cases together, this program can reduce Lorem Ipsum text to 31.2% of its original size by converting each word to a base-36 number (demo page). I optimized my dictionary for the test cases, but the output from lipsum.com is not much less compressible if I also include its words in the dictionary.

Example output for test case 3

@U6r8f36A!@9a1va6XH)K456m2w10)SD2fc28v!@6125VC)8u1g19D)Q7s9n9c16!@F17886g64!@3o2g6fYD!##@117o8q%)BXal2c2v)(Z3nbw4l!@c6377eMA!@IE1c2523)IC1s4y8k)C156q8k4p!@HJ1y75)%265y14)324fVQ!##@C4g6f2tU)&133i1n!@1s3o1gT&!@279lNF)b6ar56CJ!@F2s4qY!@G4m4q18)Ac5biY!##@DO4b5b!@137y5iB!@L^3f4k!@Y1pcb2tD)IA1m6k!@9r7aawH1a)GYaz2o)^Z1q5g4t!##@3m7kaaFN!@(61bm3tN)4vbmDU!@5k6bcpR*!@7v2tSF)173a7t76H)18H1w42!@A3c7q49R)D1c2q2iN)C3h8oV!@PDbe2j)15K1zcb!##@881db3Y()7u51OC!@6q2458PA!@153a385xB!@4h2aB15!##@at1g1n(Y)4a4j%M)cf291u^12!@E5p2411!@5v2j18^)L6t6o7nD!@155v1q3wC)H1h93W!@akc7DN)12&2q98!@1637574d^!##@UB1j1i!@1t2q6x&O)^S335s2n)428h2lGI!@J^26717v!@5j8bGL)I&ca3z)*161i5x1f!@UK4s7k39)18998y8k%)O3y2eD!@27a8aiX(!##@E3h4kO!@1e3g7xM*!@a926EL)173d6163D!@C4m5nI!@C6e46T)3x2bWA!##@*271s7kT)3o1d7jHS!@%1a6z1m!@633e8z^U!@O4j918eC!@KZ1w1q)G16675z2i!##@Dc58174U)B8d9411)W2s61F!@H48bpc01a!@16*1pb1)N4o2jG!@601rJF)O(afam42!@3s2xIK!##@A4b2a3uR!@U*4m9y!@M&1ib890)3r6v5b13C!@898w2bW&!@1c4yd5A11)5h3ybyPK!##@M(2y1v2r!@%2aag7zZ)S8x5m2kE!@MD6020)L7t1nQ!@*452g7aX!##@171w8l77E)16&2c3z4r)Eap897rJ!@5y3766UQ)5dcdX^!@956j1m^17)9197bc%16)O43a7K!@956f14E)*265u36Y!@19D923gbb)BI5w4o)&81d38wZ!@6q1nA12!##@ZK1w1b)F18bo3v!@7u2814%!@14&23ab39)a53aE12)111s587hG!@(3x7j6e18)9e8l6jA19)P5p7pH!@O7c23C)U6ibgbcE)H1a3g9u6o!@az3s7717C)IGcy2p!##@I2h294d(!@T1oa1()Yajbt6oE!@HT3b70)289iGL!@4y6x2o18A!##@XH1t29)D146u2ab3!@bnc319^)J*a71l8p!@G153q23!@G151gae52)1t73NK!##@BYa33y!@17B2dcd)Pca3s&!@K4ibv85W)P726bbk%)OCb75z1n!@(133c9d41!##@UF1h23!@ad5010^)9p1f15A)K11988e!@8y3x8iI%)CY2u3d4i!@C8s2s7gJ)Z^23319c!@^4j6z6kM)&X267b6e)1k3a43IH!##@1g1lF10)(1d4d14!@&1o4aW!@IF3m2c3l)2mbz9bQ13!@9x6pCM)&d24w15)K181c4a2a!@O6xan46G)RH6s8c!##@1b9z(13)1q487zGI!@5e2j4dDM!@C1j4051T)b978MQ!@6h5h5mC16)B272x19!##@1a7d4aB!@8m2zR^)%622eL!@4v3917G)&X1n522l!@5c2t12%!@17723kE)%6n8j13)%Tav8r!@1t9f2c11(!@1aQ2scz9h)E1y9oZ!##@9j87Q18)1h999zAY)8n514rUD!@LDas8b48)1z4a7b10D!@1126ax1lB)A3k864r1a)67b9BJ!@FM23dg!@U403pG)7730HV!@&123c32!@FN2f6y!##@Q4570R)7d7fA13!@Acv4z561a)FL3wba39!@RB6cdd7i)G218g12!@2hbrBW)Y5w55avG)1v4614QA!


Code listing

HTML page
<textarea id=dict>
in
an
ad
ex
ea
at
no
te
ut
et
eu
ei
ne
quo
pri
cu
vix
qui
vis
has
pro
id
per
eum
eos
duo
nam
usu
ius
eam
vel
sed
sea
mel
mea
vim
nec
cum
sit
mei
his
est
perfecto
vitae
oratio
nemore
inciderint
facilisi
tota
tollit
reque
quis
qualisque
placerat
persecuti
minim
melius
iisque
erroribus
error
dicit
consectetuer
atomorum
zzril
voluptatibus
virtute
sonet
quodsi
ponderum
oporteat
omnesque
oblique
mentitum
meis
mazim
errem
dissentiet
deserunt
cotidieque
consul
choro
vulputate
stet
soluta
sint
signiferumque
sadipscing
reprimique
reformidans
rebum
quaerendum
persequeris
perpetua
partem
oportere
omnium
ocurreret
nulla
molestie
moderatius
malorum
invenire
intellegebat
intellegam
inimicus
inermis
graeco
fugit
fabellas
efficiendi
dolores
dicta
comprehensam
cibo
aperiri
alia
vocibus
vivendum
vidit
vidisse
vero
veritus
ubique
timeam
tempor
tantas
summo
solet
singulis
simul
saepe
ridens
repudiandae
rationibus
putant
principes
postea
petentium
patrioque
ornatus
officiis
nostro
nonumy
nominati
nisl
neglegentur
mnesarchum
mediocrem
mandamus
iuvaret
iusto
intellegat
instructior
homero
gubergren
graeci
feugiat
fastidii
equidem
electram
efficiantur
duis
dissentiunt
detraxit
deseruisse
democritum
definitionem
decore
constituto
ceteros
blandit
appellantur
animal
altera
affert
adversarium
admodum
adipiscing
volutpat
voluptatum
vivendo
vituperatoribus
vituperata
verterem
tractatos
tibique
theophrastus
takimata
suavitate
similique
scriptorem
scripta
regione
referrentur
quando
primis
possim
posidonium
persius
pericula
option
omnes
omittantur
omittam
nullam
nostrum
nobis
nihil
mucius
meliore
maluisset
malis
maiorum
magna
luptatum
ludus
lorem
lobortis
libris
legere
legendos
laudem
latine
kasd
justo
iudicabit
impedit
illum
ignota
hinc
fuisset
forensibus
feugait
facilisis
facer
fabulas
explicari
esse
erat
enim
elitr
elit
elaboraret
eirmod
doming
dolor
docendi
dignissim
dictas
dico
diceret
denique
delectus
debitis
corpora
convenire
consequat
conceptam
civibus
cetero
atqui
assentior
argumentum
apeirian
antiopam
ancillae
aliquam
aeterno
adipisci
adhuc
accusata
accusam
accommodare
wisi
voluptua
veri
veniam
velit
utroque
utamur
torquatos
suscipit
suscipiantur
splendide
soleat
sensibus
semper
scripserit
sapientem
saperet
recusabo
quot
putent
propriae
prompta
praesent
porro
platonem
phaedrum
pertinax
pertinacia
percipit
paulo
offendit
noster
nibh
mundi
mollis
molestiae
liberavisse
laboramus
ipsum
interpretaris
integre
insolens
honestatis
hendrerit
habeo
gloriatur
fierent
facilis
exerci
essent
eruditi
eros
eripuit
epicuri
epicurei
eius
dolorum
dissentias
disputationi
dicunt
dicat
dicam
diam
delicatissimi
delicata
deleniti
delenit
definitiones
definiebas
corrumpit
consulatu
constituam
concludaturque
commodo
augue
assum
aperiam
aliquyam
agam
aeque
abhorreant
voluptaria
volumus
viris
viderer
vide
verear
unum
ullamcorper
tritani
tation
sumo
senserit
scribentur
scaevola
salutatus
salutandi
sale
repudiare
reprehendunt
recteque
quod
quidam
quem
quas
quaeque
prodesset
probo
probatus
philosophia
omnis
numquam
nostrud
noluisse
necessitatibus
mutat
munere
modus
modo
menandri
mediocritatem
maiestatis
lucilius
liber
laoreet
labore
labitur
iriure
interesset
indoctum
incorrupte
inani
imperdiet
habemus
graecis
ferri
falli
facete
expetendis
expetenda
euripidis
etiam
erant
eloquentiam
eligendi
dolorem
disputando
discere
dicant
detracto
debet
contentiones
consetetur
congue
complectitur
commune
clita
causae
brute
autem
audiam
assueverit
appetere
appareat
amet
alterum
aliquip
aliquando
albucius
adolescens
accusamus
accumsan
vocent
urbanitas
temporibus
tamquam
tale
suas
solum
sententiae
quaestio
puto
prima
postulant
possit
posse
percipitur
partiendo
odio
nusquam
nominavi
natum
movet
minimum
iudico
iracundia
invidunt
impetus
illud
graece
evertitur
euismod
eleifend
dolore
doctus
copiosae
consequuntur
conclusionemque
bonorum
audire
aliquid
alienum
non
eget
ac
a
vestibulum
nunc
mauris
tincidunt
pellentesque
ante
donec
turpis
orci
massa
arcu
ultrices
luctus
neque
tortor
dui
metus
posuere
leo
ligula
libero
sem
nisi
quam
sapien
risus
mi
faucibus
purus
consectetur
malesuada
urna
tellus
lectus
felis
egestas
porta
varius
tristique
lacus
dictum
convallis
rutrum
morbi
rhoncus
aliquet
sodales
viverra
sollicitudin
tempus
suspendisse
lacinia
interdum
scelerisque
fusce
fringilla
sagittis
pretium
cursus
auctor
condimentum
ultricies
elementum
gravida
pulvinar
porttitor
pharetra
vivamus
integer
bibendum
vehicula
iaculis
fermentum
proin
ornare
mattis
cras
curabitur
aenean
quisque
phasellus
venenatis
maecenas
dapibus
curae
cubilia
torquent
taciti
sociosqu
nostra
litora
inceptos
himenaeos
conubia
class
aptent
platea
hac
habitasse
dictumst
senectus
netus
habitant
fames
everti
sociis
sanctus
ridiculus
penatibus
parturient
nonummy
natoque
nascetur
mus
montes
magnis
dis
utinam
ullum
harum
alii
potenti
populo
legimus
idque
periculis
novum
labores
deterruisset
enean
</textarea>

<textarea rows=25 cols=80 id=box></textarea>
<button id=comp>compress</button><button id=decomp>decompress</button>
Source code (uses jQuery 1.5.2)
var $box = $('#box'),
    dict = $('#dict').val().split(/\n/g).filter(function(v) {
        return v.length;
    }),
    CODE = {
        COMMA: 0,
        FULL_STOP: 1,
        SHIFT: 2,
        NEWLINE: 3,
        UNCOMP: 4,
        FIRST_WORD: 5
    },
    base36UpperAlphabet = ")!@#$%^&*(ABCDEFGHIJKLMNOPQRSTUVWXYZ";

function compress(orig) {
    function writeCode(n) {
        if(n < 36) {
            comped += base36UpperAlphabet[n];
        } else {
            comped += n.toString(36);
        }
    }

    function writeUncompressed(d) {
        comped += d;
        comped += '.';
    }

    function writeCurrentWord() {
        if(word) {
            // look up word in dictionary
            var wordIndex = dict.indexOf(word), shift = false;

            // try lowercasing first letter
            if(wordIndex < 0) {
                shift = true;
                wordIndex = dict.indexOf(word[0].toLowerCase() + word.slice(1));
            }

            if(wordIndex < 0) {
                writeCode(CODE.UNCOMP);
                writeUncompressed(word);
            } else {
                if(shift) writeCode(CODE.SHIFT);
                writeCode(wordIndex + CODE.FIRST_WORD);
            }
        }
        word = '';
    }

    var comped = '', word = '';
    for(var i = 0; i < orig.length; ++i) {
        var ch = orig[i];
        switch(ch) {
            case ' ': writeCurrentWord(); break;
            case ',': writeCurrentWord(); writeCode(CODE.COMMA); break;
            case '.': writeCurrentWord(); writeCode(CODE.FULL_STOP); break;
            case '\n': writeCurrentWord(); writeCode(CODE.NEWLINE); break;
            default: word += ch;
        }
    }

    writeCurrentWord();
    return comped;
}

function decompress(comped) {
    function readCode() {
        var c = comped[i++],
            n = base36UpperAlphabet.indexOf(c);
        if(n >= 0) return n;
        return parseInt(c + comped[i++], 36);
    }
    function readUncompressed() {
        var c, d = '';
        while((c = comped[i++]) != '.') d += c;
        return d;
    }

    var code, i = 0, shift = false, orig = '';
    while(i < comped.length) switch(code = readCode()) {
            case CODE.COMMA: orig += ','; break;
            case CODE.FULL_STOP: orig += '.'; break;
            case CODE.SHIFT: shift = true; break;
            case CODE.NEWLINE: orig += '\n'; break;
            case CODE.UNCOMP: orig += ' ' + readUncompressed(); break;
            default:
            var word = dict[code - CODE.FIRST_WORD];
            orig += ' ' + (shift ? word[0].toUpperCase() + word.slice(1) : word);
            shift = false;
    }

    return orig.slice(1);
}

$('#comp').click(function() {
    var orig = $box.val(), comped = compress(orig);
    $box.val(comped);
    alert('ratio=' + (comped.length / orig.length).toFixed(5));
});

$('#decomp').click(function() {
    $box.val(decompress($box.val()));
});
Command for generating a frequency-sorted dictionary
tr '[:upper:]' '[:lower:]' < lipsum.txt | tr -cs '[:lower:]' '\n' | sort | uniq -c | sort -rn | cut -c9- > lipsumwords.txt
\$\endgroup\$
  • \$\begingroup\$ Does your program use the "hashing" I described in my comment above? I haven't learned jQuery, and I'm still learning JavaScript. Can you explain how it works? \$\endgroup\$ – Mateen Ulhaq Apr 30 '11 at 7:17
  • \$\begingroup\$ @muntoo: I only actually used jQuery to access the text boxes and attach event handling code to the push buttons, and I did use some ES5 features, which are not available in older browsers, only to get this submission done more quickly. The program, as a "quick-and-dirty" compressor, is not optimized for speed; every word results in a linear search of the frequency-sorted dictionary stored in the first text box. \$\endgroup\$ – PleaseStand Apr 30 '11 at 7:25
  • 2
    \$\begingroup\$ You could save a lot using base-36 (or even base-255). \$\endgroup\$ – Ry- Apr 30 '11 at 17:12
  • \$\begingroup\$ @minitech: switched to base-36 for a giant improvement in compression ratio. \$\endgroup\$ – PleaseStand Apr 30 '11 at 20:10
3
\$\begingroup\$

JavaScript, ≈ 11%

I can't figure out how to decompress it yet, but I think it is possible. I'll edit it when I figure out how, but if anybody here does before me, please tell me how!

This one can compress to ≈ 45%, but when run recursively settles down at ≈ 11% for the one I tried.

function liCompress(text, s) {
    // Some variables used throughout the function
    var c, i, result = [];

    // First, we get the unique characters in the text.
    var uniqueCharacters = '';
    for(i = 0; i < text.length; i++) {
        c = text.charAt(i);
        if(uniqueCharacters.indexOf(c) === -1) uniqueCharacters += c;
    }

    // Add them to the string:
    result.push(uniqueCharacters.length);
    for(i = 0; i < uniqueCharacters.length; i++) result.push(uniqueCharacters.charCodeAt(i));

    // Now we convert the base-x string to base-256.
    var total = 0, exponent = 0;
    for(i = 0; i < text.length; i++) {
        c = text.charAt(i);
        var n = uniqueCharacters.indexOf(c);
        total += n * Math.pow(uniqueCharacters.length, i - exponent);

        if(total > 255) {
            result.push(total % 256);
            total = total === 256 ? 0 : 1;
            exponent = i + 1;
        }
    }

    // Return the string representation of the result.
    var r = String.fromCharCode.apply(String, result);
    if(!s) {
        var x = liCompress(r, true);
        return x.length < r.length ? liCompress(r) : r;
    }
    return r;
}
\$\endgroup\$
  • \$\begingroup\$ You should include a 4-byte header stating how many recursive steps it's taken. \$\endgroup\$ – Mateen Ulhaq May 2 '11 at 23:32
  • \$\begingroup\$ 4-byte? Maybe 1, only 6 recursive steps were needed in my test... \$\endgroup\$ – Ry- May 3 '11 at 1:11
  • \$\begingroup\$ Whatever. :) \$\endgroup\$ – Mateen Ulhaq May 3 '11 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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