Puzzle 16: Zip me up, Buttercup

[damber]

OK, after a short break we're back to bring you more puzzle-liscious programming challenges, this time in the form of a compression algorithm.

We've all used a compression tool at some point or another, and most probably used a library within our applications to do much of the same. In many cases we probably don't even realise we're using a compression feature.. such as viewing this site, if your browser supports it most of the textual content will be transferred in gzip format.

So what we want to do here is to think about how these algorithms work and write a new handcoded solution from scratch - whilst we don't expect the entry to perform at the same level as existing algorithms, that's not really the challenge - we're looking to stretch those braincells to write something that will compress an input string and decompress to the original exactly - the higher the compression, obviously the better, but just compressing with a noticeable size reduction will be a success.

The rules....

Using the string below, reduce the size of the text in a single transportable file. Then inflate that same file to reproduce the original string exactly (e.g. lossless compression).

You may not use any compression utility, library, etc - this must be your own work.
You may not copy verbatim some existing algorithm to do this either (and changing a function name does not count for being different ).
You may use the concepts from other compression tools or file formats though
Compressed size in bytes is important and will be the primary metric for judging the winners
Speed of compression will also be considered, but is of lesser importance

Provide your results (with code) in the following format:

Input Size: xxxx Bytes
Input MD5 hash: ......
Compressed size: xxx Bytes
Compression time: xxx ms (or sec, mins, hrs, etc)
Decompressed Size: xxx Bytes
Decompressed MD5 Hash: ......


The Input:

textLine number Off | Show | Select all

1. Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Curabitur porttitor scelerisque pede. Mauris rutrum tortor non lacus. Duis volutpat, dui sit amet rhoncus posuere, felis odio tristique neque, a fringilla risus magna et mauris. Duis eu purus et diam suscipit vulputate. Nam faucibus leo nec sapien. Integer vitae ante. Donec non est. Vestibulum condimentum, felis ut hendrerit malesuada, lectus tellus faucibus est, a dictum nulla diam ac dolor. Donec pede. Mauris id nisl. Vivamus sit amet elit. Pellentesque in odio sed nibh vestibulum aliquet. Sed erat mauris, tempor sed, molestie iaculis, pulvinar quis, turpis. Sed rutrum tellus at arcu. Duis lectus lorem, rutrum eget, consectetuer vitae, tempor eu, risus. In hac habitasse platea dictumst. Ut neque. Aenean sem nisi, hendrerit non, lacinia eu, gravida eget, magna.
2.  
3.  
4.  
5. Pellentesque pellentesque tristique neque. Duis varius. Nunc venenatis, libero at molestie porttitor, tortor mauris volutpat purus, vel sollicitudin orci orci nec metus. Suspendisse ut ipsum at ipsum vehicula luctus. Sed gravida felis eu lectus. Proin fringilla felis. Duis ornare ultricies eros. Nullam a leo pretium nunc pharetra tempor. Etiam vitae tortor ac leo adipiscing bibendum. Integer facilisis. Aenean varius purus eget odio. Nulla laoreet. Aliquam auctor blandit nibh. Mauris augue. Sed egestas purus in justo. Duis id quam.
6.  
7.  
8.  
9. Maecenas at nibh. Donec imperdiet vehicula sem. Praesent et lacus ac elit interdum sollicitudin. Donec id nibh. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Nullam semper, felis vehicula gravida consequat, neque nisl dictum massa, eu sodales dui sem id augue. Sed sit amet purus. Quisque consectetuer elit et ipsum rutrum iaculis. Morbi placerat, leo ac consectetuer porttitor, nisl odio tempus mi, nec volutpat est dolor vel enim. Duis faucibus gravida urna. Curabitur eget felis non nisi pretium pharetra. Fusce tincidunt eros eu purus. Maecenas dolor. Maecenas libero nulla, hendrerit quis, dignissim in, lacinia eget, est. Curabitur pharetra ante vel quam ultrices dignissim.
10.  
11. ================================================================================================================
12. <?php
13. /**
14.  * Class Minify  
15.  * @package Minify
16.  */
17.  
18. /**
19.  * Minify_Source
20.  */
21. require_once 'Minify/Source.php';
22.  
23. /**
24.  * Minify - Combines, minifies, and caches JavaScript and CSS files on demand.
25.  *
26.  * See README for usage instructions (for now).
27.  *
28.  * This library was inspired by {@link mailto:flashkot@mail.ru jscsscomp by Maxim Martynyuk}
29.  * and by the article {@link http://www.hunlock.com/blogs/Supercharged_Javascript "Supercharged JavaScript" by Patrick Hunlock}.
30.  *
31.  * Requires PHP 5.1.0.
32.  * Tested on PHP 5.1.6.
33.  *
34.  * @package Minify
35.  * @author Ryan Grove <ryan@wonko.com>
36.  * @author Stephen Clay <steve@mrclay.org>
37.  * @copyright 2008 Ryan Grove, Stephen Clay. All rights reserved.
38.  * @license http://opensource.org/licenses/bsd-license.php  New BSD License
39.  * @link http://code.google.com/p/minify/
40.  */
41. class Minify {
42.  
43.     const TYPE_CSS = 'text/css';
44.     const TYPE_HTML = 'text/html';
45.     // there is some debate over the ideal JS Content-Type, but this is the
46.     // Apache default and what Yahoo! uses..
47.     const TYPE_JS = 'application/x-javascript';
48.    
49.     /**
50.      * How many hours behind are the file modification times of uploaded files?
51.      *
52.      * If you upload files from Windows to a non-Windows server, Windows may report
53.      * incorrect mtimes for the files. Immediately after modifying and uploading a
54.      * file, use the touch command to update the mtime on the server. If the mtime
55.      * jumps ahead by a number of hours, set this variable to that number. If the mtime
56.      * moves back, this should not be needed.
57.      *
58.      * @var int $uploaderHoursBehind
59.      */
60.     public static $uploaderHoursBehind = 0;
61.    
62.     /**
63.      * Specify a cache object (with identical interface as Minify_Cache_File) or
64.      * a path to use with Minify_Cache_File.
65.      *
66.      * If not called, Minify will not use a cache and, for each 200 response, will
67.      * need to recombine files, minify and encode the output.
68.      *
69.      * @param mixed $cache object with identical interface as Minify_Cache_File or
70.      * a directory path. (default = '')
71.      *
72.      * @param bool $fileLocking (default = true) This only applies if the first
73.      * parameter is a string.
74.      *
75.      * @return null
76.      */
77.     public static function setCache($cache = '', $fileLocking = true)
78.     {
79.         if (is_string($cache)) {
80.             require_once 'Minify/Cache/File.php';
81.             self::$_cache = new Minify_Cache_File($cache, $fileLocking);
82.         } else {
83.             self::$_cache = $cache;
84.         }
85.     }
86.    
87.     /**
88.      * Serve a request for a minified file.
89.      *
90.      * Here are the available options and defaults in the base controller:
91.      *
92.      * 'isPublic' : send "public" instead of "private" in Cache-Control
93.      * headers, allowing shared caches to cache the output. (default true)
94.      *
95.      * 'quiet' : set to true to have serve() return an array rather than sending
96.      * any headers/output (default false)
97.      *
98.      * 'encodeOutput' : to disable content encoding, set this to false (default true)
99.      *
100.      * 'encodeMethod' : generally you should let this be determined by
101.      * HTTP_Encoder (leave null), but you can force a particular encoding
102.      * to be returned, by setting this to 'gzip', 'deflate', or '' (no encoding)
103.      *
104.      * 'encodeLevel' : level of encoding compression (0 to 9, default 9)
105.      *
106.      * 'contentTypeCharset' : appended to the Content-Type header sent. Set to a falsey
107.      * value to remove. (default 'UTF-8')  
108.      *
109.      * 'maxAge' : set this to the number of seconds the client should use its cache
110.      * before revalidating with the server. This sets Cache-Control: max-age and the
111.      * Expires header. Unlike the old 'setExpires' setting, this setting will NOT
112.      * prevent conditional GETs. Note this has nothing to do with server-side caching.
113.      *
114.      * 'rewriteCssUris' : If true, serve() will automatically set the 'currentDir'
115.      * minifier option to enable URI rewriting in CSS files (default true)
116.      *
117.      * 'debug' : set to true to minify all sources with the 'Lines' controller, which
118.      * eases the debugging of combined files. This also prevents 304 responses.
119.      * @see Minify_Lines::minify()
120.      *
121.      * 'minifiers' : to override Minify's default choice of minifier function for
122.      * a particular content-type, specify your callback under the key of the
123.      * content-type:
124.      * <code>
125.      * // call customCssMinifier($css) for all CSS minification
126.      * $options['minifiers'][Minify::TYPE_CSS] = 'customCssMinifier';
127.      *
128.      * // don't minify Javascript at all
129.      * $options['minifiers'][Minify::TYPE_JS] = '';
130.      * </code>
131.      *
132.      * 'minifierOptions' : to send options to the minifier function, specify your options
133.      * under the key of the content-type. E.g. To send the CSS minifier an option:
134.      * <code>
135.      * // give CSS minifier array('optionName' => 'optionValue') as 2nd argument
136.      * $options['minifierOptions'][Minify::TYPE_CSS]['optionName'] = 'optionValue';
137.      * </code>
138.      *
139.      * 'contentType' : (optional) this is only needed if your file extension is not
140.      * js/css/html. The given content-type will be sent regardless of source file
141.      * extension, so this should not be used in a Groups config with other
142.      * Javascript/CSS files.
143.      *
144.      * Any controller options are documented in that controller's setupSources() method.
145.      *
146.      * @param mixed instance of subclass of Minify_Controller_Base or string name of
147.      * controller. E.g. 'Files'
148.      *
149.      * @param array $options controller/serve options
150.      *
151.      * @return mixed null, or, if the 'quiet' option is set to true, an array
152.      * with keys "success" (bool), "statusCode" (int), "content" (string), and
153.      * "headers" (array).
154.      */
155.     public static function serve($controller, $options = array()) {
156.         if (is_string($controller)) {
157.             // make $controller into object
158.             $class = 'Minify_Controller_' . $controller;
159.             if (! class_exists($class, false)) {
160.                 require_once "Minify/Controller/"
161.                     . str_replace('_', '/', $controller) . ".php";    
162.             }
163.             $controller = new $class();
164.         }
165.        
166.         // set up controller sources and mix remaining options with
167.         // controller defaults
168.         $options = $controller->setupSources($options);
169.         $options = $controller->analyzeSources($options);
170.         self::$_options = $controller->mixInDefaultOptions($options);
171.        
172.         // check request validity
173.         if (! $controller->sources) {
174.             // invalid request!
175.             if (! self::$_options['quiet']) {
176.                 header(self::$_options['badRequestHeader']);
177.                 echo self::$_options['badRequestHeader'];
178.                 return;
179.             } else {
180.                 list(,$statusCode) = explode(' ', self::$_options['badRequestHeader']);
181.                 return array(
182.                     'success' => false
183.                     ,'statusCode' => (int)$statusCode
184.                     ,'content' => ''
185.                     ,'headers' => array()
186.                 );
187.             }
188.         }
189.        
190.         self::$_controller = $controller;
191.        
192.         if (self::$_options['debug']) {
193.             self::_setupDebug($controller->sources);
194.             self::$_options['maxAge'] = 0;
195.         }
196.        
197.         // check client cache
198.         require_once 'HTTP/ConditionalGet.php';
199.         $cgOptions = array(
200.             'lastModifiedTime' => self::$_options['lastModifiedTime']
201.             ,'isPublic' => self::$_options['isPublic']
202.         );
203.         if (self::$_options['maxAge'] > 0) {
204.             $cgOptions['maxAge'] = self::$_options['maxAge'];
205.         }
206.         $cg = new HTTP_ConditionalGet($cgOptions);
207.         if ($cg->cacheIsValid) {
208.             // client's cache is valid
209.             if (! self::$_options['quiet']) {
210.                 $cg->sendHeaders();
211.                 return;
212.             } else {
213.                 return array(
214.                     'success' => true
215.                     ,'statusCode' => 304
216.                     ,'content' => ''
217.                     ,'headers' => $cg->getHeaders()
218.                 );
219.             }
220.         } else {
221.             // client will need output
222.             $headers = $cg->getHeaders();
223.             unset($cg);
224.         }
225.        
226.         // determine encoding
227.         if (self::$_options['encodeOutput']) {
228.             if (self::$_options['encodeMethod'] !== null) {
229.                 // controller specifically requested this
230.                 $contentEncoding = self::$_options['encodeMethod'];
231.             } else {
232.                 // sniff request header
233.                 require_once 'HTTP/Encoder.php';
234.                 // depending on what the client accepts, $contentEncoding may be
235.                 // 'x-gzip' while our internal encodeMethod is 'gzip'. Calling
236.                 // getAcceptedEncoding() with false leaves out compress as an option.
237.                 list(self::$_options['encodeMethod'], $contentEncoding) = HTTP_Encoder::getAcceptedEncoding(false);
238.             }
239.         } else {
240.             self::$_options['encodeMethod'] = ''; // identity (no encoding)
241.         }
242.        
243.         if (self::$_options['contentType'] === self::TYPE_CSS
244.             && self::$_options['rewriteCssUris']) {
245.             reset($controller->sources);
246.             while (list($key, $source) = each($controller->sources)) {
247.                 if ($source->filepath
248.                     && !isset($source->minifyOptions['currentDir'])
249.                     && !isset($source->minifyOptions['prependRelativePath'])
250.                 ) {
251.                     $source->minifyOptions['currentDir'] = dirname($source->filepath);
252.                 }
253.             }
254.         }
255.        
256.         // check server cache
257.         if (null !== self::$_cache) {
258.             // using cache
259.             // the goal is to use only the cache methods to sniff the length and
260.             // output the content, as they do not require ever loading the file into
261.             // memory.
262.             $cacheId = 'minify_' . self::_getCacheId();
263.             $encodingExtension = self::$_options['encodeMethod']
264.                 ? ('deflate' === self::$_options['encodeMethod']
265.                     ? '.zd'
266.                     : '.zg')
267.                 : '';
268.             $fullCacheId = $cacheId . $encodingExtension;
269.             // check cache for valid entry
270.             $cacheIsReady = self::$_cache->isValid($fullCacheId, self::$_options['lastModifiedTime']);
271.             if ($cacheIsReady) {
272.                 $cacheContentLength = self::$_cache->getSize($fullCacheId);    
273.             } else {
274.                 // generate & cache content
275.                 $content = self::_combineMinify();
276.                 self::$_cache->store($cacheId, $content);
277.                 self::$_cache->store($cacheId . '.zd', gzdeflate($content, self::$_options['encodeLevel']));
278.                 self::$_cache->store($cacheId . '.zg', gzencode($content, self::$_options['encodeLevel']));
279.             }
280.         } else {
281.             // no cache
282.             $cacheIsReady = false;
283.             $content = self::_combineMinify();
284.         }
285.         if (! $cacheIsReady && self::$_options['encodeMethod']) {
286.             // still need to encode
287.             $content = ('deflate' === self::$_options['encodeMethod'])
288.                 ? gzdeflate($content, self::$_options['encodeLevel'])
289.                 : gzencode($content, self::$_options['encodeLevel']);
290.         }
291.        
292.         // add headers
293.         $headers['Content-Length'] = $cacheIsReady
294.             ? $cacheContentLength
295.             : strlen($content);
296.         $headers['Content-Type'] = self::$_options['contentTypeCharset']
297.             ? self::$_options['contentType'] . '; charset=' . self::$_options['contentTypeCharset']
298.             : self::$_options['contentType'];
299.         if (self::$_options['encodeMethod'] !== '') {
300.             $headers['Content-Encoding'] = $contentEncoding;
301.             $headers['Vary'] = 'Accept-Encoding';
302.         }
303.  
304.         if (! self::$_options['quiet']) {
305.             // output headers & content
306.             foreach ($headers as $name => $val) {
307.                 header($name . ': ' . $val);
308.             }
309.             if ($cacheIsReady) {
310.                 self::$_cache->display($fullCacheId);
311.             } else {
312.                 echo $content;
313.             }
314.         } else {
315.             return array(
316.                 'success' => true
317.                 ,'statusCode' => 200
318.                 ,'content' => $cacheIsReady
319.                     ? self::$_cache->fetch($fullCacheId)
320.                     : $content
321.                 ,'headers' => $headers                
322.             );
323.         }
324.     }
325.    
326.     /**
327.      * Return combined minified content for a set of sources
328.      *
329.      * No internal caching will be used and the content will not be HTTP encoded.
330.      *
331.      * @param array $sources array of filepaths and/or Minify_Source objects
332.      *
333.      * @return string
334.      */
335.     public static function combine($sources)
336.     {
337.         $cache = self::$_cache;
338.         self::$_cache = null;
339.         $out = self::serve('Files', array(
340.             'files' => (array)$sources
341.             ,'quiet' => true
342.             ,'encodeMethod' => ''
343.             ,'lastModifiedTime' => 0
344.         ));
345.         self::$_cache = $cache;
346.         return $out['content'];
347.     }
348.    
349.     /**
350.      * On IIS, create $_SERVER['DOCUMENT_ROOT']
351.      *
352.      * @param bool $unsetPathInfo (default false) if true, $_SERVER['PATH_INFO']
353.      * will be unset (it is inconsistent with Apache's setting)
354.      *
355.      * @return null
356.      */
357.     public static function setDocRoot($unsetPathInfo = false)
358.     {
359.         if (isset($_SERVER['SERVER_SOFTWARE'])
360.             && 0 === strpos($_SERVER['SERVER_SOFTWARE'], 'Microsoft-IIS/')
361.         ) {
362.             $_SERVER['DOCUMENT_ROOT'] = substr(
363.                 $_SERVER['PATH_TRANSLATED']
364.                 ,0
365.                 ,strlen($_SERVER['PATH_TRANSLATED']) - strlen($_SERVER['SCRIPT_NAME'])
366.             );
367.             if ($unsetPathInfo) {
368.                 unset($_SERVER['PATH_INFO']);
369.             }
370.         }
371.     }
372.    
373.     /**
374.      * @var mixed Minify_Cache_* object or null (i.e. no server cache is used)
375.      */
376.     private static $_cache = null;
377.    
378.     /**
379.      * @var Minify_Controller active controller for current request
380.      */
381.     protected static $_controller = null;
382.    
383.     /**
384.      * @var array options for current request
385.      */
386.     protected static $_options = null;
387.    
388.     /**
389.      * Set up sources to use Minify_Lines
390.      *
391.      * @param array $sources Minify_Source instances
392.      *
393.      * @return null
394.      */
395.     protected static function _setupDebug($sources)
396.     {
397.         foreach ($sources as $source) {
398.             $source->minifier = array('Minify_Lines', 'minify');
399.             $id = $source->getId();
400.             $source->minifyOptions = array(
401.                 'id' => (is_file($id) ? basename($id) : $id)
402.             );
403.         }
404.     }
405.    
406.     /**
407.      * Combines sources and minifies the result.
408.      *
409.      * @return string
410.      */
411.     protected static function _combineMinify() {
412.         $type = self::$_options['contentType']; // ease readability
413.        
414.         // when combining scripts, make sure all statements separated
415.         $implodeSeparator = ($type === self::TYPE_JS)
416.             ? ';'
417.             : '';
418.         // allow the user to pass a particular array of options to each
419.         // minifier (designated by type). source objects may still override
420.         // these
421.         $defaultOptions = isset(self::$_options['minifierOptions'][$type])
422.             ? self::$_options['minifierOptions'][$type]
423.             : array();
424.         // if minifier not set, default is no minification. source objects
425.         // may still override this
426.         $defaultMinifier = isset(self::$_options['minifiers'][$type])
427.             ? self::$_options['minifiers'][$type]
428.             : false;
429.        
430.         if (Minify_Source::haveNoMinifyPrefs(self::$_controller->sources)) {
431.             // all source have same options/minifier, better performance
432.             // to combine, then minify once
433.             foreach (self::$_controller->sources as $source) {
434.                 $pieces[] = $source->getContent();
435.             }
436.             $content = implode($implodeSeparator, $pieces);
437.             if ($defaultMinifier) {
438.                 self::$_controller->loadMinifier($defaultMinifier);
439.                 $content = call_user_func($defaultMinifier, $content, $defaultOptions);    
440.             }
441.         } else {
442.             // minify each source with its own options and minifier, then combine
443.             foreach (self::$_controller->sources as $source) {
444.                 // allow the source to override our minifier and options
445.                 $minifier = (null !== $source->minifier)
446.                     ? $source->minifier
447.                     : $defaultMinifier;
448.                 $options = (null !== $source->minifyOptions)
449.                     ? array_merge($defaultOptions, $source->minifyOptions)
450.                     : $defaultOptions;
451.                 if ($defaultMinifier) {
452.                     self::$_controller->loadMinifier($minifier);
453.                     // get source content and minify it
454.                     $pieces[] = call_user_func($minifier, $source->getContent(), $options);    
455.                 } else {
456.                     $pieces[] = $source->getContent();    
457.                 }
458.             }
459.             $content = implode($implodeSeparator, $pieces);
460.         }
461.        
462.         // do any post-processing (esp. for editing build URIs)
463.         if (self::$_options['postprocessorRequire']) {
464.             require_once self::$_options['postprocessorRequire'];
465.         }
466.         if (self::$_options['postprocessor']) {
467.             $content = call_user_func(self::$_options['postprocessor'], $content, $type);
468.         }
469.         return $content;
470.     }
471.    
472.     /**
473.      * Make a unique cache id for for this request.
474.      *
475.      * Any settings that could affect output are taken into consideration  
476.      *
477.      * @return string
478.      */
479.     protected static function _getCacheId() {
480.         return md5(serialize(array(
481.             Minify_Source::getDigest(self::$_controller->sources)
482.             ,self::$_options['minifiers']
483.             ,self::$_options['minifierOptions']
484.             ,self::$_options['postprocessor']
485.         )));
486.     }    
487. }
488. ================================================================================================================
489.  
490. Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Curabitur porttitor scelerisque pede. Mauris rutrum tortor non lacus. Duis volutpat, dui sit amet rhoncus posuere, felis odio tristique neque, a fringilla risus magna et mauris. Duis eu purus et diam suscipit vulputate. Nam faucibus leo nec sapien. Integer vitae ante. Donec non est. Vestibulum condimentum, felis ut hendrerit malesuada, lectus tellus faucibus est, a dictum nulla diam ac dolor. Donec pede. Mauris id nisl. Vivamus sit amet elit. Pellentesque in odio sed nibh vestibulum aliquet. Sed erat mauris, tempor sed, molestie iaculis, pulvinar quis, turpis. Sed rutrum tellus at arcu. Duis lectus lorem, rutrum eget, consectetuer vitae, tempor eu, risus. In hac habitasse platea dictumst. Ut neque. Aenean sem nisi, hendrerit non, lacinia eu, gravida eget, magna.
491.  
492.  
493.  
494. Pellentesque pellentesque tristique neque. Duis varius. Nunc venenatis, libero at molestie porttitor, tortor mauris volutpat purus, vel sollicitudin orci orci nec metus. Suspendisse ut ipsum at ipsum vehicula luctus. Sed gravida felis eu lectus. Proin fringilla felis. Duis ornare ultricies eros. Nullam a leo pretium nunc pharetra tempor. Etiam vitae tortor ac leo adipiscing bibendum. Integer facilisis. Aenean varius purus eget odio. Nulla laoreet. Aliquam auctor blandit nibh. Mauris augue. Sed egestas purus in justo. Duis id quam.
495.  
496.  
497.  
498. Maecenas at nibh. Donec imperdiet vehicula sem. Praesent et lacus ac elit interdum sollicitudin. Donec id nibh. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Nullam semper, felis vehicula gravida consequat, neque nisl dictum massa, eu sodales dui sem id augue. Sed sit amet purus. Quisque consectetuer elit et ipsum rutrum iaculis. Morbi placerat, leo ac consectetuer porttitor, nisl odio tempus mi, nec volutpat est dolor vel enim. Duis faucibus gravida urna. Curabitur eget felis non nisi pretium pharetra. Fusce tincidunt eros eu purus. Maecenas dolor. Maecenas libero nulla, hendrerit quis, dignissim in, lacinia eget, est. Curabitur pharetra ante vel quam ultrices dignissim.
499.  
500.  
501.  

Code is hidden, SHOW

We're going to leave this one open for two weeks so that everyone has chance to have a go.

Also attached as file (suggest using the file for actual test in case the text above is slightly corrupted by the posting process (e.g. removal of whitespace etc)

[tisodotsk]

My first result (2 algorithms, in PHP):

textLine number Off | Hide | Select all

1. Input Size: 23444 Bytes
2. Input MD5 hash: 9caae65c46aea68c7c5630456d4007cf
3. ---------------------------------------------------------------------
4. Compressed size: 21099 Bytes
5. Compression time: 19.9990272522 ms
6. Decompressed Size: 23444 Bytes
7. Decompressed MD5 Hash: 9caae65c46aea68c7c5630456d4007cf
8. ---------------------------------------------------------------------
9. Compressed size: 14992 Bytes
10. Compression time: 2.31652522087 s
11. Decompressed Size: 23444 Bytes
12. Decompressed MD5 Hash: 9caae65c46aea68c7c5630456d4007cf
13. ---------------------------------------------------------------------

[damber]

congrats tisodtsk in being the only response! - this challenge seems to have been pretty hard to solve.

As this is a programming puzzle, could you post the code that you used to generate those results ?

[tisodotsk]

damber: of course, here it is:

PHPLine number Off | Show | Select all

1. <?php
2. //Puzzle 16: Zip me up, Buttercup
3. //via Topic3086: Puzzle 16:  Zip me up, Buttercup
4. //------------------------------------------------------------------------------
5. define('NL', "\r\n");
6. $file='text.txt';
7.  
8. //1. method:--------------------------------------------------------------------
9. $delimiter='~';//hardcoded
10. $content=file_get_contents($file);
11. $orig=strlen($content);
12. header('Content-type: text/plain; encoding: utf-8');
13. echo 'Input Size: '.$orig.' Bytes
14. Input MD5 hash: '.md5($content).NL;
15. //------------------------------------------------------------------------------
16. echo '---------------------------------------------------------------------'.NL;
17. //compression:
18. $ms=microtime(TRUE);
19. $content=preg_compress_string($content, $delimiter);
20. $me=microtime(TRUE);
21. echo 'Compressed size: '.strlen($content).' Bytes
22. Compression time: '.(1000*($me-$ms)).' ms'.NL;
23. //decompression:
24. $content=preg_uncompress_string($content, $delimiter);
25. echo 'Decompressed Size: '.strlen($content).' Bytes
26. Decompressed MD5 Hash: '.md5($content).NL;
27. //------------------------------------------------------------------------------
28. function preg_compress_string($string, $delimiter)
29. {
30.     $chars=count_chars($string, 1);
31.     if(isset($chars[47])){unset($chars[47]);}// exception /
32.     arsort($chars);
33.     foreach($chars as $key => $val){
34.         if($val <= 4){break;}
35.         $pattern='/(['.chr($key).']){5,}/';
36.         preg_match_all($pattern, $string, $matches);
37.         arsort($matches[0]);
38.         $output=array_unique($matches[0]);
39.         if(count($output) !== 0){
40.             foreach($output as $val){
41.                 $string=str_replace($val, $delimiter.$val{0}.strlen($val).$delimiter, $string);
42.             }
43.         }
44.     }
45.     return $string;
46. }
47. function preg_uncompress_string($string, $delimiter)
48. {
49.     $pattern='/('.$delimiter.'.{1}(\d+)'.$delimiter.')/';
50.     preg_match_all($pattern, $string, $matches);
51.     $output=array_unique($matches[0]);
52.     if(count($output) !== 0){
53.         foreach($output as $key => $val){$string=str_replace($val, str_repeat($val{1}, $matches[2][$key]), $string);}
54.     }
55.     return $string;
56. }
57.  
58. //2. method:--------------------------------------------------------------------
59. echo '---------------------------------------------------------------------'.NL;
60. //compression:
61. $ms=microtime(TRUE);
62. $used=count_chars($content, 1);
63. $unused=array_keys(count_chars($content, 2));
64. $delimiter=chr(array_pop($unused));
65. $start=0;
66. $length=5;
67. $end=strlen($content)-2*$length;
68. $strings=$counts=$saves=array();
69. $last_string='';
70. while($start <= $end){
71.     $start2=1;
72.     $length2=$length;
73.     $last_string=$substr=substr($content, $start, $length2);
74.     $last_count=substr_count($content, $substr);
75.     if($last_count > 1){
76.         $total=0;
77.         while(FALSE !== $pos=strpos($content, $substr, $start+$length2)){
78.             $start2=$length2-$length+1;
79.             $count=substr_count($content, $substr);
80.             if($total > $count*$length2){break(1);}
81.             $last_string=$substr;
82.             $last_count=$count;
83.             $total=$count*$length2;
84.             $substr=substr($content, $start, ++$length2);
85.         }
86.         $strings[]=$last_string;
87.         $saves[]=$last_count*$length2;
88.     }
89.     $start+=$start2;
90. }
91. arsort($saves);//todo: more efective sorting
92. foreach($saves as $key => $val){
93.     if(count($unused) < 1){break;}
94.     if(FALSE === strpos($content, $strings[$key])){continue;}
95.     $shortcut=array_pop($unused);
96.     $shortcuts[chr($shortcut)]=$strings[$key];
97.     $content=str_replace($strings[$key], chr($shortcut), $content);
98. }
99. $content=$delimiter.serialize($shortcuts).$delimiter.$content;
100. $me=microtime(TRUE);
101. echo 'Compressed size: '.strlen($content).' Bytes
102. Compression time: '.(($me-$ms)).' s'.NL;
103. //decompression:
104. $delimiter=$content{0};
105. $serialized=substr($content, 1, ($pos=strpos($content, $delimiter, 1))-1);
106. $shortcuts=unserialize($serialized);
107. $search=array_keys($shortcuts);
108. $replace=array_values($shortcuts);
109. $content=substr($content, $pos+1);
110. $content=str_replace($search, $replace, $content);
111. echo 'Decompressed Size: '.strlen($content).' Bytes
112. Decompressed MD5 Hash: '.md5($content).NL;
113. echo '---------------------------------------------------------------------'.NL;
114. ?>
115.  

Code is hidden, SHOW

[damber]

Nice work tisodotsk, thanks for posting your code

I was a little surprised no-one else attempted it, especially as an example approach was included with the input data

Therefore I think we can safely declare you the winner