Article space character count
I just wrote a script to go through my local copy of the Wikipedia article space and count characters. Looking at my results, I believe I've found some encoding issues with my import scripts, which I need to look into and then do the count all over again. But this should give you a rough idea. Using the huffman codings given on this data yields data 64.4% of the size of the original data (35.6% compression).
Optimizations to shorten the maximum length of the huffman code would have a negligible effect on compression and would increase performance. For instance, the maximum length of a huffman code can be shortened to 16 and still yield 35.2% compression. A full 16 bit lookup table can then be stored in just 64K of ram.
(I think this is right, but I'm not 100% sure)
Counts
editHere's the list, in the format "ASCII code: character count".
Article namespace, March 2004.
Unsorted
edit0 : 3 1 : 1 2 : 0 3 : 3 4 : 0 5 : 0 6 : 0 7 : 0 8 : 0 9 : 121638 10 : 10336138 11 : 13 12 : 2 13 : 228803 14 : 1 15 : 1 16 : 1 17 : 1 18 : 1 19 : 11 20 : 20 21 : 5 22 : 1 23 : 1 24 : 3 25 : 15 26 : 1 27 : 1 28 : 40 29 : 2 30 : 3 31 : 1 32 : 119829446 33 : 137708 34 : 2216362 35 : 1310211 36 : 222481 37 : 1090747 38 : 1591497 39 : 10214159 40 : 2407761 41 : 2409341 42 : 2698119 43 : 59665 44 : 7883141 45 : 3301218 46 : 9098636 47 : 2732753 48 : 4602799 49 : 5789151 50 : 3934118 51 : 2368626 52 : 2220609 53 : 2187065 54 : 1924199 55 : 1800029 56 : 2323314 57 : 3265593 58 : 2118962 59 : 1830948 60 : 2590955 61 : 3733347 62 : 2594550 63 : 85086 64 : 3285 65 : 3130604 66 : 1960997 67 : 3705133 68 : 1764943 69 : 1791063 70 : 1465971 71 : 1354346 72 : 1530187 73 : 2268672 74 : 917739 75 : 691982 76 : 1525687 77 : 2178000 78 : 1394622 79 : 948660 80 : 1928187 81 : 133362 82 : 1938469 83 : 3621048 84 : 3404655 85 : 1118940 86 : 544900 87 : 1223036 88 : 122354 89 : 284716 90 : 144907 91 : 21544392 92 : 1316127 93 : 21545092 94 : 19285 95 : 445853 96 : 1690 97 : 51224950 98 : 8131546 99 : 18442785 100: 21674710 101: 69874916 102: 12479232 103: 11877498 104: 25360619 105: 44301737 106: 631820 107: 3888111 108: 25720096 109: 15398150 110: 42740036 111: 43898365 112: 12371595 113: 581608 114: 39975788 115: 37391289 116: 48307684 117: 16335346 118: 6030293 119: 8363216 120: 1440822 121: 9548861 122: 901854 123: 499864 124: 4691438 125: 499687 126: 15809 127: 1 128: 134 129: 17 130: 31 131: 33 132: 230 133: 1107 134: 95 135: 33 136: 6 137: 16 138: 539 139: 8 140: 25 141: 18 142: 155 143: 0 144: 2 145: 1788 146: 16009 147: 6419 148: 7315 149: 342 150: 7266 151: 6096 152: 5 153: 65 154: 1025 155: 18 156: 187 157: 1 158: 391 159: 8 160: 793 161: 247 162: 84 163: 4321 164: 243 165: 180 166: 34 167: 603 168: 68 169: 228 170: 82 171: 283 172: 164 173: 251 174: 623 175: 51 176: 8118 177: 284 178: 7458 179: 580 180: 757 181: 351 182: 45 183: 3903 184: 38 185: 148 186: 595 187: 276 188: 124 189: 725 190: 91 191: 131 192: 205 193: 1837 194: 145 195: 190 196: 658 197: 1559 198: 493 199: 450 200: 98 201: 7880 202: 62 203: 78 204: 33 205: 357 206: 724 207: 62 208: 118 209: 485 210: 51 211: 838 212: 95 213: 58 214: 2516 215: 1622 216: 627 217: 33 218: 267 219: 43 220: 902 221: 35 222: 322 223: 3128 224: 5474 225: 32513 226: 4768 227: 7893 228: 21063 229: 4572 230: 3354 231: 9627 232: 16777 233: 104245 234: 3364 235: 6875 236: 1807 237: 20737 238: 1720 239: 1633 240: 1721 241: 5568 242: 1027 243: 23457 244: 5815 245: 810 246: 25716 247: 56 248: 5171 249: 923 250: 7106 251: 1237 252: 23134 253: 1143 254: 551 255: 174
Sorted
editSame list, sorted, 0 counts are changed to 1.
1: 1 1: 2 1: 4 1: 5 1: 6 1: 7 1: 8 1: 14 1: 15 1: 16 1: 17 1: 18 1: 22 1: 23 1: 26 1: 27 1: 31 1: 127 1: 143 1: 157 2: 12 2: 29 2: 144 3: 0 3: 3 3: 24 3: 30 5: 21 5: 152 6: 136 8: 139 8: 159 11: 19 13: 11 15: 25 16: 137 17: 129 18: 141 18: 155 20: 20 25: 140 31: 130 33: 131 33: 135 33: 204 33: 217 34: 166 35: 221 38: 184 40: 28 43: 219 45: 182 51: 175 51: 210 56: 247 58: 213 62: 202 62: 207 65: 153 68: 168 78: 203 82: 170 84: 162 91: 190 95: 134 95: 212 98: 200 118: 208 124: 188 131: 191 134: 128 145: 194 148: 185 155: 142 164: 172 174: 255 180: 165 187: 156 190: 195 205: 192 228: 169 230: 132 243: 164 247: 161 251: 173 267: 218 276: 187 283: 171 284: 177 322: 222 342: 149 351: 181 357: 205 391: 158 450: 199 485: 209 493: 198 539: 138 551: 254 580: 179 595: 186 603: 167 623: 174 627: 216 658: 196 724: 206 725: 189 757: 180 793: 160 810: 245 838: 211 902: 220 923: 249 1025: 154 1027: 242 1107: 133 1143: 253 1237: 251 1559: 197 1622: 215 1633: 239 1690: 96 1720: 238 1721: 240 1788: 145 1807: 236 1837: 193 2516: 214 3128: 223 3285: 64 3354: 230 3364: 234 3903: 183 4321: 163 4572: 229 4768: 226 5171: 248 5474: 224 5568: 241 5815: 244 6096: 151 6419: 147 6875: 235 7106: 250 7266: 150 7315: 148 7458: 178 7880: 201 7893: 227 8118: 176 9627: 231 15809: 126 16009: 146 16777: 232 19285: 94 20737: 237 21063: 228 23134: 252 23457: 243 25716: 246 32513: 225 59665: 43 85086: 63 104245: 233 121638: 9 122354: 88 133362: 81 137708: 33 144907: 90 222481: 36 228803: 13 284716: 89 445853: 95 499687: 125 499864: 123 544900: 86 581608: 113 631820: 106 691982: 75 901854: 122 917739: 74 948660: 79 1090747: 37 1118940: 85 1223036: 87 1310211: 35 1316127: 92 1354346: 71 1394622: 78 1440822: 120 1465971: 70 1525687: 76 1530187: 72 1591497: 38 1764943: 68 1791063: 69 1800029: 55 1830948: 59 1924199: 54 1928187: 80 1938469: 82 1960997: 66 2118962: 58 2178000: 77 2187065: 53 2216362: 34 2220609: 52 2268672: 73 2323314: 56 2368626: 51 2407761: 40 2409341: 41 2590955: 60 2594550: 62 2698119: 42 2732753: 47 3130604: 65 3265593: 57 3301218: 45 3404655: 84 3621048: 83 3705133: 67 3733347: 61 3888111: 107 3934118: 50 4602799: 48 4691438: 124 5789151: 49 6030293: 118 7883141: 44 8131546: 98 8363216: 119 9098636: 46 9548861: 121 10214159: 39 10336138: 10 11877498: 103 12371595: 112 12479232: 102 15398150: 109 16335346: 117 18442785: 99 21544392: 91 21545092: 93 21674710: 100 25360619: 104 25720096: 108 37391289: 115 39975788: 114 42740036: 110 43898365: 111 44301737: 105 48307684: 116 51224950: 97 69874916: 101 119829446: 32
Tree
editand finally, the tree, expressed two different ways
Internal nodes, with counts
edit0: 1.0,1.1 2 1: 1.2,1.3 2 2: 1.4,1.5 2 3: 1.6,1.7 2 4: 1.8,1.9 2 5: 1.10,1.11 2 6: 1.12,1.13 2 7: 1.14,1.15 2 8: 1.16,1.17 2 9: 1.18,1.19 2 10: 1.20,1.21 4 11: 1.22,0.0 4 12: 0.1,0.2 4 13: 0.3,0.4 4 14: 0.5,0.6 4 15: 0.7,0.8 4 16: 1.23,0.9 5 17: 1.24,1.25 6 18: 1.26,0.10 7 19: 0.11,0.12 8 20: 0.13,0.14 8 21: 1.27,0.15 9 22: 1.28,0.16 10 23: 1.29,0.17 12 24: 1.30,0.18 15 25: 1.31,0.19 16 26: 0.20,0.21 17 27: 1.32,0.22 21 28: 1.33,0.23 25 29: 1.34,0.24 30 30: 1.35,0.25 32 31: 1.36,0.26 34 32: 1.37,1.38 36 33: 1.39,0.27 41 34: 1.40,0.28 50 35: 1.41,0.29 61 36: 1.42,0.30 65 37: 1.43,1.44 66 38: 1.45,1.46 67 39: 1.47,0.31 69 40: 1.48,0.32 74 41: 1.49,0.33 81 42: 1.50,1.51 88 43: 1.52,0.34 101 44: 1.53,1.54 107 45: 1.55,0.35 119 46: 1.56,1.57 124 47: 1.58,0.36 130 48: 0.37,0.38 133 49: 1.59,0.39 137 50: 1.60,0.40 152 51: 1.61,0.41 163 52: 1.62,0.42 172 53: 1.63,1.64 186 54: 1.65,1.66 193 55: 0.43,0.44 208 56: 1.67,0.45 237 57: 1.68,0.46 248 58: 1.69,0.47 261 59: 1.70,0.48 267 60: 1.71,0.49 282 61: 1.72,0.50 300 62: 1.73,0.51 318 63: 1.74,0.52 336 64: 1.75,1.76 354 65: 1.77,0.53 373 66: 1.78,0.54 383 67: 1.79,0.55 413 68: 1.80,1.81 458 69: 1.82,0.56 480 70: 1.83,0.57 495 71: 1.84,0.58 512 72: 1.85,0.59 534 73: 1.86,0.60 558 74: 1.87,1.88 567 75: 0.61,0.62 618 76: 1.89,0.63 658 77: 1.90,1.91 693 78: 1.92,0.64 711 79: 0.65,0.66 756 80: 1.93,0.67 804 81: 1.94,0.68 908 82: 1.95,0.69 965 83: 1.96,0.70 988 84: 0.71,0.72 1046 85: 1.97,1.98 1090 86: 0.73,0.74 1125 87: 1.99,1.100 1175 88: 1.101,0.75 1221 89: 1.102,1.103 1250 90: 1.104,0.76 1316 91: 0.77,0.78 1404 92: 1.105,1.106 1449 93: 1.107,0.79 1513 94: 1.108,0.80 1597 95: 1.109,1.110 1648 96: 1.111,0.81 1810 97: 1.112,0.82 1888 98: 1.113,0.83 2013 99: 1.114,0.84 2073 100: 1.115,0.85 2197 101: 1.116,0.86 2268 102: 0.87,0.88 2396 103: 1.117,0.89 2487 104: 0.90,0.91 2720 105: 0.92,0.93 2962 106: 1.118,0.94 3156 107: 1.119,1.120 3255 108: 1.121,0.95 3338 109: 1.122,1.123 3441 110: 1.124,1.125 3595 111: 1.126,0.96 3647 112: 0.97,0.98 3901 113: 0.99,0.100 4270 114: 0.101,0.102 4664 115: 1.127,0.103 5003 116: 0.104,0.105 5682 117: 1.128,0.106 6284 118: 1.129,0.107 6540 119: 1.130,0.108 6692 120: 1.131,0.109 6805 121: 0.110,0.111 7242 122: 1.132,0.112 7804 123: 1.133,0.113 8591 124: 1.134,0.114 9236 125: 1.135,0.115 9771 126: 1.136,1.137 10645 127: 1.138,0.116 11250 128: 1.139,1.140 11911 129: 1.141,0.117 12703 130: 0.118,0.119 13232 131: 1.142,0.120 13680 132: 1.143,0.121 14348 133: 1.144,1.145 14581 134: 1.146,0.122 15262 135: 1.147,1.148 15773 136: 1.149,0.123 16709 137: 1.150,0.124 18863 138: 0.125,0.126 20416 139: 0.127,0.128 23161 140: 0.129,0.130 25935 141: 0.131,0.132 28028 142: 0.133,0.134 29843 143: 1.151,0.135 31582 144: 1.152,0.136 32718 145: 1.153,0.137 35640 146: 1.154,0.138 39701 147: 1.155,1.156 41800 148: 1.157,0.139 46295 149: 1.158,1.159 49173 150: 0.140,0.141 53963 151: 0.142,0.143 61425 152: 1.160,0.144 65231 153: 0.145,0.146 75341 154: 0.147,0.148 88095 155: 0.149,0.150 103136 156: 1.161,0.151 121090 157: 0.152,0.153 140572 158: 1.162,0.154 173181 159: 1.163,0.155 207381 160: 1.164,0.156 242728 161: 1.165,1.166 255716 162: 1.167,0.157 278280 163: 1.168,0.158 318088 164: 1.169,0.159 429862 165: 1.170,0.160 471531 166: 0.161,0.162 533996 167: 1.171,0.163 602804 168: 1.172,0.164 875715 169: 1.173,0.165 971218 170: 1.174,0.166 1033860 171: 1.175,1.176 1126508 172: 1.177,0.167 1234624 173: 1.178,0.168 1567697 174: 1.179,1.180 1819593 175: 1.181,0.169 1919878 176: 1.182,0.170 2124607 177: 1.183,0.171 2245448 178: 1.184,0.172 2457660 179: 1.185,1.186 2626338 180: 1.187,1.188 2748968 181: 1.189,1.190 2906793 182: 1.191,1.192 3055874 183: 1.193,0.173 3159194 184: 1.194,1.195 3556006 185: 1.196,0.174 3619622 186: 1.197,0.175 3750826 187: 1.198,1.199 3852386 188: 1.200,1.201 3899466 189: 1.202,0.176 4243569 190: 1.203,1.204 4365065 191: 1.205,1.206 4436971 192: 1.207,0.177 4514120 193: 1.208,1.209 4691940 194: 1.210,1.211 4817102 195: 1.212,0.178 5048615 196: 1.213,0.179 5220888 197: 1.214,1.215 5430872 198: 0.180,0.181 5655761 199: 1.216,0.182 6186478 200: 1.217,0.183 6424787 201: 1.218,1.219 6705873 202: 0.184,0.185 7175628 203: 1.220,1.221 7326181 204: 1.222,0.186 7484173 205: 1.223,0.187 7740497 206: 1.224,0.188 7833584 207: 0.189,0.190 8608634 208: 0.191,0.192 8951091 209: 1.225,1.226 9294237 210: 0.193,0.194 9509042 211: 0.195,0.196 10269503 212: 0.197,0.198 11086633 213: 1.227,1.228 11819444 214: 0.199,0.200 12611265 215: 0.201,0.202 13881501 216: 0.203,0.204 14810354 217: 0.205,0.206 15574081 218: 1.229,1.230 16014687 219: 1.231,0.207 16971850 220: 1.232,0.208 18049727 221: 0.209,0.210 18803279 222: 1.233,1.234 19763020 223: 1.235,0.211 20605641 224: 0.212,0.213 22906077 225: 1.236,1.237 24249093 226: 1.238,0.214 25090497 227: 0.215,0.216 28691855 228: 1.239,0.217 30972231 229: 1.240,0.218 32350033 230: 0.219,0.220 35021577 231: 1.241,0.221 37246064 232: 0.222,0.223 40368661 233: 1.242,1.243 43089484 234: 1.244,0.224 44580787 235: 0.225,0.226 49339590 236: 1.245,1.246 51080715 237: 0.227,0.228 59664086 238: 0.229,0.230 67371610 239: 1.247,0.231 74637353 240: 1.248,0.232 80344449 241: 1.249,0.233 85829520 242: 1.250,1.251 88200102 243: 1.252,0.234 92888471 244: 0.235,0.236 100420305 245: 1.253,0.237 110889036 246: 1.254,0.238 137246526 247: 0.239,0.240 154981802 248: 0.241,0.242 174029622 249: 0.243,0.244 193308776 250: 1.255,0.245 230718482 251: 0.246,0.247 292228328 252: 0.248,0.249 367338398 253: 0.250,0.251 522946810 254: 0.252,0.253 890285208
Binary encodings
edit0000: 110 00010: 91 00011: 93 0010: 111 0011: 105 0100: 116 01010: 100 01011000: 42 01011001: 47 010110100: 71 010110101: 78 010110110: 120 010110111: 70 0101110: 49 0101111: 118 011000: 103 011001: 112 011010: 102 01101100: 65 011011010: 76 011011011: 72 01101110: 57 011011110: 38 0110111110: 75 01101111110: 95 011011111110: 36 0110111111110: 233 011011111111100: 243 011011111111101: 246 01101111111111000: 147 011011111111110010: 223 0110111111111100110: 197 01101111111111001110: 160 011011111111110011110: 158 0110111111111100111110: 192 011011111111110011111100: 175 0110111111111100111111010: 140 01101111111111001111110110: 11 011011111111110011111101110: 136 0110111111111100111111011110: 3 0110111111111100111111011111: 24 011011111111110011111110: 210 011011111111110011111111: 247 011011111111110100: 64 0110111111111101010: 215 0110111111111101011: 239 011011111111110110: 230 0110111111111101110: 96 01101111111111011110: 245 01101111111111011111: 211 01101111111111100: 235 011011111111111010: 234 0110111111111110110: 238 0110111111111110111: 240 01101111111111110: 250 0110111111111111100: 145 0110111111111111101: 236 0110111111111111110: 193 01101111111111111110: 220 011011111111111111110: 199 0110111111111111111110: 169 0110111111111111111111: 132 01110: 104 01111: 108 100: 32 1010: 97 10110000: 45 10110001: 84 101100100: 68 101100101: 69 101100110: 55 1011001110: 122 1011001111: 74 10110100: 83 10110101: 67 10110110: 61 101101110: 59 1011011110: 79 10110111110: 125 101101111110: 13 1011011111110: 9 10110111111110: 43 10110111111111000: 150 10110111111111001: 148 10110111111111010: 178 101101111111110110: 183 10110111111111011100: 249 101101111111110111010: 209 1011011111111101110110: 164 10110111111111011101110: 208 101101111111110111011110: 213 1011011111111101110111110: 130 10110111111111011101111110: 25 101101111111110111011111110: 139 1011011111111101110111111110: 30 10110111111111011101111111110: 12 10110111111111011101111111111: 29 10110111111111011110: 154 101101111111110111110: 198 1011011111111101111110: 161 10110111111111011111110: 188 101101111111110111111110: 202 101101111111110111111111: 207 1011011111111110: 126 10110111111111110: 201 10110111111111111: 227 101110: 109 10111100: 107 101111010: 54 101111011: 80 10111110: 50 101111110: 82 101111111: 66 1100: 101 110100: 117 1101010: 44 1101011: 98 1101100: 119 110110100: 58 1101101010: 37 11011010110: 123 1101101011100: 88 1101101011101: 81 1101101011110: 33 110110101111100: 225 1101101011111010: 146 11011010111110110: 176 110110101111101110: 163 11011010111110111100: 242 1101101011111011110100: 173 11011010111110111101010: 191 110110101111101111010110: 153 1101101011111011110101110: 131 11011010111110111101011110: 137 110110101111101111010111110: 159 11011010111110111101011111100: 144 110110101111101111010111111010: 1 110110101111101111010111111011: 2 110110101111101111010111111100: 4 110110101111101111010111111101: 5 110110101111101111010111111110: 6 110110101111101111010111111111: 7 1101101011111011110110: 218 11011010111110111101110: 128 1101101011111011110111100: 135 1101101011111011110111101: 204 1101101011111011110111110: 217 1101101011111011110111111: 166 11011010111110111110: 133 110110101111101111110: 138 110110101111101111111: 254 1101101011111100: 232 11011010111111010: 231 110110101111110110: 229 11011010111111011100: 253 1101101011111101110100: 187 11011010111111011101010: 194 110110101111110111010110: 168 1101101011111101110101110: 221 11011010111111011101011110: 129 110110101111110111010111110000: 8 110110101111110111010111110001: 14 110110101111110111010111110010: 15 110110101111110111010111110011: 16 110110101111110111010111110100: 17 110110101111110111010111110101: 18 110110101111110111010111110110: 22 110110101111110111010111110111: 23 1101101011111101110101111110: 21 110110101111110111010111111100: 26 110110101111110111010111111101: 27 110110101111110111010111111110: 31 110110101111110111010111111111: 127 1101101011111101110110: 171 1101101011111101110111: 177 110110101111110111100: 179 110110101111110111101: 186 110110101111110111110: 167 11011010111111011111100: 185 110110101111110111111010: 203 1101101011111101111110110: 184 11011010111111011111101110: 141 11011010111111011111101111: 155 11011010111111011111110: 142 110110101111110111111110: 170 1101101011111101111111110: 28 11011010111111011111111110: 20 110110101111110111111111110: 19 1101101011111101111111111110: 152 11011010111111011111111111110: 0 110110101111110111111111111110: 143 110110101111110111111111111111: 157 1101101011111110: 94 110110101111111100: 226 1101101011111111010: 214 11011010111111110110: 251 110110101111111101110: 174 110110101111111101111: 216 110110101111111110: 248 110110101111111111: 224 110110110: 77 110110111: 53 1101110: 46 110111100: 34 110111101: 52 110111110: 73 1101111110: 85 11011111110: 86 11011111111: 113 11100: 115 111010: 99 11101100: 48 11101101: 124 111011100: 56 111011101: 51 111011110: 40 111011111: 41 11110: 114 1111100: 121 1111101: 39 1111110: 10 111111100: 60 1111111010: 87 11111110110: 106 111111101110: 89 1111111011110: 90 11111110111110: 63 1111111011111100: 237 1111111011111101: 228 1111111011111110: 252 111111101111111100: 241 111111101111111101000: 196 1111111011111111010010: 222 11111110111111110100110: 172 111111101111111101001110: 162 1111111011111111010011110: 219 1111111011111111010011111: 182 1111111011111111010100: 149 1111111011111111010101: 181 1111111011111111010110: 205 11111110111111110101110: 255 11111110111111110101111: 165 111111101111111101100: 206 111111101111111101101: 189 111111101111111101110: 180 11111110111111110111100: 156 111111101111111101111010: 190 111111101111111101111011: 134 11111110111111110111110: 195 111111101111111101111110: 212 111111101111111101111111: 200 111111101111111110: 244 111111101111111111: 151 111111110: 62 1111111110: 35 1111111111: 92