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)

CountsEdit

Here's the list, in the format "ASCII code: character count".

Article namespace, March 2004.

UnsortedEdit

0  : 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

SortedEdit

Same 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

TreeEdit

and finally, the tree, expressed two different ways

Internal nodes, with countsEdit

0: 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 encodingsEdit

0000: 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