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.");
}
}
}
