Lorem Ipsum Compressor 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.
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) &gt; 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 &lt; 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.