Write an URL compressor Today your goal is to invent URL compression. You must write two programs: a compressor and a decompressor.


The compressor will be called with one URL on stdin and its output will be read on stdout.
The decompressor will be called with the output of the compressor on stdin, and must produce the exact URL passed into the compressor to stdout.
The sum of the size in bytes of the compressor and decompressor source may be at most 1024 bytes.
Your answer must come with command line instructions to run your two programs. You're not allowed to pass in information of any kind through command line arguments - they should merely be to run the program.


The standard loopholes are not allowed. Additionally, your program is not allowed to keep and use any state of any kind between executions, not in files, environment variables, etc. Lastly, you may not use any built-in data compression routines if your language has them.

Scoring

I have taken all URLs found in the StackExchange dump of PPCG and collected them in one file, one URL per line. Your score will be the sum of the size of all compressed URLs in that file. Lowest score wins.



It is not guaranteed that your program is called with a valid URL. Your program must work for every input found in the test file, but doesn't have to work for any other input.

Your answer only has to work for the given URLs, and only has to optimize for those.
CJam 308954 268306 bytes

Compressor (511 bytes)

0000000: 22 2f 25 2d 30 31 32 33 35 61 65 0a 2e 34 37 38  "/%-01235ae..478
0000010: 39 62 63 66 67 69 6c 6d 70 73 74 75 0a 36 41 42  9bcfgilmpstu.6AB
0000020: 43 44 45 46 49 4a 4b 4c 4d 53 58 5f 64 68 6a 6b  CDEFIJKLMSX_dhjk
0000030: 6e 6f 72 76 77 78 79 7a 97 a0 a5 a6 22 0a 4e 2f  norvwxyz....".N/
0000040: 5f 3a 2b 32 35 36 63 2c 5e 61 2b 3a 47 3b 22 63  _:+256c,^a+:G;"c
0000050: 6f 7f 6d 73 74 6e 67 6f 6c 6f 72 64 65 7f 85 83  o.mstngolorde...
0000060: 66 67 87 86 88 81 61 8a 63 8b 6b 61 82 80 2f 2e  fg....a.c.ka../.
0000070: 8e 65 8f 8d 90 68 91 63 92 78 93 65 94 8c 95 65  .e...h.c.x.e...e
0000080: 72 6f 6e 84 67 77 69 9a 6b 9b 69 74 68 96 61 69  ron.gwi.k.ith.ai
0000090: 98 69 6e 65 74 6e a1 65 6e 64 69 25 32 a5 30 a6  .inetn.endi%2.0.
00000a0: a6 77 77 a8 77 6c 65 72 65 2e 99 ac 2f ad 9c 9f  .ww.wlere.../...
00000b0: 73 81 af 89 2e b1 9e b1 96 65 a4 70 b4 9c b5 72  s........e.p...r
00000c0: 69 a5 42 b7 70 b9 74 62 8f b6 61 bc ae 61 72 b2  i.B.p.tb..a..ar.
00000d0: 2f 61 74 6c 6f 61 6d 74 6d 68 c3 c4 6c 65 b0 75  /atloamtmh..le.u
00000e0: c6 71 c7 b3 c8 63 ba 73 ca 88 cb 72 6f 61 6e 69  .q...c.s...roani
00000f0: 9d cf 75 d0 bb 67 d1 65 73 75 73 d4 97 b3 d5 6a  ..u..g.esus....j
0000100: c2 63 d7 c1 77 d9 8f 70 68 db bb 70 dc 73 75 74  .c..w..ph..p.sut
0000110: de a4 df 61 e0 98 90 85 e2 69 e3 d3 83 e5 8d a9  ...a.....i......
0000120: 2e 61 dd 76 97 6f e9 8c ea eb 66 ec da 6a 73 ee  .a.v.o....f..js.
0000130: 66 ef 69 f0 64 f1 64 f2 aa 70 cd a2 2f 2e f5 f3  f.i.d.d..p../...
0000140: f6 e1 f6 e6 73 f9 ae 61 6c 75 6e bf 34 70 79 fe  ....s..alun.4py.
0000150: 9d 63 74 fc 00 b8 b8 75 72 03 8f a5 43 64 6f 06  .ct....ur...Cdo.
0000160: 63 d6 73 ed c8 a7 a7 b8 a6 a6 a5 69 73 72 c2 75  c.s........isr.u
0000170: 74 69 82 bd 2f 2e 11 a3 12 67 49 14 43 15 41 16  ti../....gI.C.A.
0000180: 16 a3 74 07 73 72 fc d2 0d 69 74 2e c5 63 68 61  ..t.sr...it..cha
0000190: 73 e8 3f 20 63 5c 22 3d be 1e 6f 03 69 aa a5 39  s.? c\"=..o.i..9
00001a0: 60 a5 6f 66 22 32 2f 31 32 39 2c 31 32 37 66 2b  `.of"2/129,127f+
00001b0: 33 33 2c 2b 3a 63 22 5c 22 3c 3e 5c 5e 60 7b 7d  33,+:c"\"&lt;&gt;\^`{}
00001c0: 22 2b 6c 5f 34 3d 27 73 3d 3a 4c 37 2b 3e 40 7b  "+l_4='s=:L7+&gt;@{
00001d0: 2f 5c 28 40 5c 2a 7d 2f 30 5c 7b 47 7b 31 24 23  /\(@\*}/0\{G{1$#
00001e0: 29 7d 23 5f 47 3d 3a 54 40 23 40 54 2c 2a 2b 34  )}#_G=:T@#@T,*+4
00001f0: 2a 2b 7d 2f 32 2a 4c 2b 32 35 36 62 3a 63 0a     *+}/2*L+256b:c.


Decompressor (510 bytes)

0000000: 22 2f 25 2d 30 31 32 33 35 61 65 0a 2e 34 37 38  "/%-01235ae..478
0000010: 39 62 63 66 67 69 6c 6d 70 73 74 75 0a 36 41 42  9bcfgilmpstu.6AB
0000020: 43 44 45 46 49 4a 4b 4c 4d 53 58 5f 64 68 6a 6b  CDEFIJKLMSX_dhjk
0000030: 6e 6f 72 76 77 78 79 7a 97 a0 a5 a6 22 0a 4e 2f  norvwxyz....".N/
0000040: 5f 3a 2b 32 35 36 63 2c 5e 61 2b 3a 47 3b 22 63  _:+256c,^a+:G;"c
0000050: 6f 7f 6d 73 74 6e 67 6f 6c 6f 72 64 65 7f 85 83  o.mstngolorde...
0000060: 66 67 87 86 88 81 61 8a 63 8b 6b 61 82 80 2f 2e  fg....a.c.ka../.
0000070: 8e 65 8f 8d 90 68 91 63 92 78 93 65 94 8c 95 65  .e...h.c.x.e...e
0000080: 72 6f 6e 84 67 77 69 9a 6b 9b 69 74 68 96 61 69  ron.gwi.k.ith.ai
0000090: 98 69 6e 65 74 6e a1 65 6e 64 69 25 32 a5 30 a6  .inetn.endi%2.0.
00000a0: a6 77 77 a8 77 6c 65 72 65 2e 99 ac 2f ad 9c 9f  .ww.wlere.../...
00000b0: 73 81 af 89 2e b1 9e b1 96 65 a4 70 b4 9c b5 72  s........e.p...r
00000c0: 69 a5 42 b7 70 b9 74 62 8f b6 61 bc ae 61 72 b2  i.B.p.tb..a..ar.
00000d0: 2f 61 74 6c 6f 61 6d 74 6d 68 c3 c4 6c 65 b0 75  /atloamtmh..le.u
00000e0: c6 71 c7 b3 c8 63 ba 73 ca 88 cb 72 6f 61 6e 69  .q...c.s...roani
00000f0: 9d cf 75 d0 bb 67 d1 65 73 75 73 d4 97 b3 d5 6a  ..u..g.esus....j
0000100: c2 63 d7 c1 77 d9 8f 70 68 db bb 70 dc 73 75 74  .c..w..ph..p.sut
0000110: de a4 df 61 e0 98 90 85 e2 69 e3 d3 83 e5 8d a9  ...a.....i......
0000120: 2e 61 dd 76 97 6f e9 8c ea eb 66 ec da 6a 73 ee  .a.v.o....f..js.
0000130: 66 ef 69 f0 64 f1 64 f2 aa 70 cd a2 2f 2e f5 f3  f.i.d.d..p../...
0000140: f6 e1 f6 e6 73 f9 ae 61 6c 75 6e bf 34 70 79 fe  ....s..alun.4py.
0000150: 9d 63 74 fc 00 b8 b8 75 72 03 8f a5 43 64 6f 06  .ct....ur...Cdo.
0000160: 63 d6 73 ed c8 a7 a7 b8 a6 a6 a5 69 73 72 c2 75  c.s........isr.u
0000170: 74 69 82 bd 2f 2e 11 a3 12 67 49 14 43 15 41 16  ti../....gI.C.A.
0000180: 16 a3 74 07 73 72 fc d2 0d 69 74 2e c5 63 68 61  ..t.sr...it..cha
0000190: 73 e8 3f 20 63 5c 22 3d be 1e 6f 03 69 aa a5 39  s.? c\"=..o.i..9
00001a0: 60 a5 6f 66 22 32 2f 5b 71 32 35 36 62 32 6d 64  `.of"2/[q256b2md
00001b0: 22 68 74 74 70 22 6f 27 73 2a 6f 22 3a 2f 2f 22  "http"o's*o"://"
00001c0: 6f 7b 34 6d 64 47 3d 5f 2c 40 5c 6d 64 40 3d 5c  o{4mdG=_,@\md@=\
00001d0: 7d 68 3b 5d 57 25 31 32 39 2c 31 32 37 66 2b 33  }h;]W%129,127f+3
00001e0: 33 2c 2b 3a 63 22 5c 22 3c 3e 5c 5e 60 7b 7d 22  3,+:c"\"&lt;&gt;\^`{}"
00001f0: 2b 57 25 7b 2f 5c 29 40 5c 2a 7d 2f 4e 0a        +W%{/\)@\*}/N.


Algorithm


Strip the &lt;scheme&gt;:// part from the URL.
Replace character pairs by unused code points in the 0 - 255 range. 

This uses a static dictionary which is included in the source code.
Use arithmetic encoding on the modified input string.

To comply with the source code size limit, this is done by splitting the 256 code points into 4 groups and pretending the groups and the code points in a fixed group have equal probabilities.
Append a bit indicating the scheme to the resulting integer.
Convert the integer into a string.


Test cases

Create the source code files.

$ xxd -p -r &gt; comp.cjam &lt;&lt;&lt; 222f252d303132333561650a2e3437383962636667696c6d707374750a36414243444546494a4b4c4d53585f64686a6b6e6f72767778797a97a0a5a6220a4e2f5f3a2b323536632c5e612b3a473b22636f7f6d73746e676f6c6f7264657f8583666787868881618a638b6b6182802f2e8e658f8d9068916392789365948c9565726f6e846777699a6b9b69746896616998696e65746ea1656e64692532a530a6a67777a8776c6572652e99ac2fad9c9f7381af892eb19eb19665a470b49cb57269a542b770b974628fb661bcae6172b22f61746c6f616d746d68c3c46c65b075c671c7b3c863ba73ca88cb726f616e699dcf75d0bb67d165737573d497b3d56ac263d7c177d98f7068dbbb70dc737574dea4df61e0989085e269e3d383e58da92e61dd76976fe98ceaeb66ecda6a73ee66ef69f064f164f2aa70cda22f2ef5f3f6e1f6e673f9ae616c756ebf347079fe9d6374fc00b8b87572038fa543646f0663d673edc8a7a7b8a6a6a5697372c275746982bd2f2e11a3126749144315411616a374077372fcd20d69742ec563686173e83f20635c223dbe1e6f0369aaa53960a56f6622322f3132392c313237662b33332c2b3a63225c223c3e5c5e607b7d222b6c5f343d27733d3a4c372b3e407b2f5c28405c2a7d2f305c7b477b312423297d235f473d3a54402340542c2a2b342a2b7d2f322a4c2b323536623a630a

$ xxd -p -r &gt; decomp.cjam &lt;&lt;&lt; 222f252d303132333561650a2e3437383962636667696c6d707374750a36414243444546494a4b4c4d53585f64686a6b6e6f72767778797a97a0a5a6220a4e2f5f3a2b323536632c5e612b3a473b22636f7f6d73746e676f6c6f7264657f8583666787868881618a638b6b6182802f2e8e658f8d9068916392789365948c9565726f6e846777699a6b9b69746896616998696e65746ea1656e64692532a530a6a67777a8776c6572652e99ac2fad9c9f7381af892eb19eb19665a470b49cb57269a542b770b974628fb661bcae6172b22f61746c6f616d746d68c3c46c65b075c671c7b3c863ba73ca88cb726f616e699dcf75d0bb67d165737573d497b3d56ac263d7c177d98f7068dbbb70dc737574dea4df61e0989085e269e3d383e58da92e61dd76976fe98ceaeb66ecda6a73ee66ef69f064f164f2aa70cda22f2ef5f3f6e1f6e673f9ae616c756ebf347079fe9d6374fc00b8b87572038fa543646f0663d673edc8a7a7b8a6a6a5697372c275746982bd2f2e11a3126749144315411616a374077372fcd20d69742ec563686173e83f20635c223dbe1e6f0369aaa53960a56f6622322f5b7132353662326d642268747470226f27732a6f223a2f2f226f7b346d64473d5f2c405c6d64403d5c7d683b5d57253132392c313237662b33332c2b3a63225c223c3e5c5e607b7d222b57257b2f5c29405c2a7d2f4e0a


Verify their integrity.

$ cksum comp.cjam decomp.cjam
2293013588 511 comp.cjam
1577103568 510 decomp.cjam


Download the CJam interpreter.

$ wget -q wget http://downloads.sourceforge.net/project/cjam/cjam-0.6.4/cjam-0.6.4.jar


Create an alias for running the interpreter.

$ alias cjam='java -jar cjam-0.6.4.jar'


Set encoding to ISO-8859-1 to store each character as a single byte.

$ LANG=en_US


Prepare the test file.

$ wget -q https://gist.githubusercontent.com/orlp/fd3411259469ade4c65d/raw/bb6b088c18c444d28729abc870d6076ca594a6de/urls.txt

$ echo &gt;&gt; urls.txt


For each line in the test file, feed the URL to the compressor, append the output to urls-comp.bin and feed it back to the decompressor. Save the combined output of all decompressions in urls-vrfy.txt. This will take a few minutes.

$ &gt;urls-comp.bin

$ for URL in $(&lt;urls.txt); do
&gt; echo $URL | cjam comp.cjam | tee -a urls-comp.bin | cjam decomp.cjam
&gt; done &gt; urls-vrfy.txt


Verify that all URLs were decoded appropriately.

$ cksum urls.txt urls-vrfy.txt
3445245739 588562 urls.txt
3445245739 588562 urls-vrfy.txt


Compute the score.

$ wc -c urls-comp.bin
268306 urls-comp.bin


How it works

Common

Push the string containing the first three character groups.

"/%-01235ae
.4789bcfgilmpstu
6ABCDEFIJKLMSX_dhjknorvwxyz����"


Split at linefeeds, flatten a copy of the resulting array and compute the symmetric difference of the resulting string and the string of all code points.

N/_:+256c,^


Append the result to the array which now contains all four character groups. Save the result in the variable G and discard it from the stack.

a+:G;


Push the array (let's call it A) containing all character pairs to be substituted.

"comstngolorde��fg����a�c�ka��/.�e���h�c�x�e���eron�gwi�k�ith�ai�inetn�endi%2�0��ww�wlere.��/���s���.����e�p���ri�B�p�tb��a��ar�/atloamtmh��le�u�qǳ�c�sʈ�roani��uлg�esusԗ��j�c��wُphۻp�sutޤ�a���i�Ӄit.�chas�? c\"=�oi��9`�of"
2/


Push the array [ 0 ... 128 ], add 127 to each element, append the array [ 0 ... 32 ], cast to Char and append the string "\"&lt;&gt;\^{}". The result is the string (let's call itS`) of all unused code points from 0 to 255.

129,127f+33,+:c"\"&lt;&gt;\^`{}"+


Compressor

...        " Generate G. Push A and S.                                        ";
l          " Read one line from STDIN.                                        ";
_4='s=     " Check if its 5th character is an 's'.                            ";
:L7+       " Save the result in L and add it to 7.                            ";
&gt;          " Discard that many characters from the input string.              ";
@{         " For each character pair in A:                                    ";
  /        "   Split the input string at its occurrences.                     ";
  \(@\     "   Unshift one character C from S.                                ";
  *        "   Join the split string, using C as separator.                   ";
}/         "                                                                  ";
0          " Push 0 (accumulator).                                            ";
\{         " For each character C in the input string:                        ";
  G{1$#)}# "   Retrieve the index of the group C belongs to.                  ";
  _G=:T    "   Store the group in T.                                          ";
  @#       "   Push the index of C in T.                                      ";
  @T,*+4*+ "   Multiply the accumulator by the length of T and add the index. ";
}/         "                                                                  ";
2*L+       " Multiply the accumulator by 2 and add L.                         ";
256b:c     " Convert the accumulator (BigInteger) into a byte string.         ";


Decompressor

...        " Generate G. Push A.                                              ";
[q         " Start an array and read the whole input.                         ";
256b       " Convert the byte string into an integer.                         ";
2md        " Push quotient and residue of the division by 2.                  ";
"http"o    " Print 'http'.                                                    ";
's*o       " If the residue is 1, print 's'.                                  ";
"://"o     " Print '://'.                                                     ";
{          " While the integer is non-zero:                                   ";
  4md      "   Push quotient and residue of the division by 4.                ";
  G=_,     "   Push the corresponding character group and its length.         ";
  @\md     "   Divide the integer by the length. Push quotient and residue.   ";
  @=\      "   Retrieve the char corresponding to the residue from the group. ";
}h         "                                                                  ";
]W%        " End and reverse array.                                           ";
           " Since the elements are Chars, this yields a string.              ";
...        " Push S.                                                          ";
\W%{       " For each character in S reversed:                                ";
  /        "     Split the string at its occurrences.                         ";
  \)@\     "     Pop one character pair P from A.                             ";
  *        "     Join the split string, using P as separator.                 ";
}/         "                                                                  ";
N          " Push a linefeed.                                                 ";


Remarks

Decompression will work correctly only for the http and https schemes. The reasons are twofold:


The http part is hardcoded.
The arithmetic encoding uses the fact that &lt;http|https&gt;:// cannot be followed by a third slash.

Since the integer 0 encodes any arbitrary run of slashes (character 0 of group 0), we would have to store the URL's length or the number of leading slashes to support, e.g., file:/// URLs.