Rob*_*erc 45
如果内存是我们最大的考虑因素,那么我们根本不需要存储数字,只需要存储i和i + 1之间的差值.
现在,如果数字范围从200 0000 - 999 9999,那么有7,999,999个可能的电话号码.由于我们有100万个数字,如果我们假设它们是均匀分布的,我们在连续数n_i和n_i + 1之间的预期距离为E = n_i + 1 - n_i~8(3位).因此,对于32位int,我们可能存储多达10个连续偏移(〜400kb最佳总内存占用量),但是我们可能会遇到需要大于8的偏移的情况(也许我们有400个,或者1500？).在这种情况下,我们可以简单地保留int的前2位作为标题,告诉我们用什么帧大小来读取它存储的位.例如,我们可能使用:00 = 3x10,01 = 5x6,10 = 7x4,11 = 1*30.
Ste*_*sop 29
将它们写成ASCII,空格分隔.
使用您喜欢的压缩算法压缩生成的字符串.如果顺序不重要,首先对它们进行排序可能有助于压缩,让您更加紧密地重复.
哦,你想要有效的随机访问吗？那你应该说.
650*_*502 10
可能的解决方案是
Delta频率分布将高度倾斜.
我使用简单的类似BER的打包方法,使用7 + 3 + 3 + ...位编码进行增量实验; 编码功能是
def delta_write(x, b1, b2):
lim = 1 << (b1 - 1)
if x < lim:
bit_write(x, b1)
else:
bit_write(lim + (x & (lim - 1)), b1)
delta_write(x >> (b1 - 1), b2, b2)
(两个参数7和3是通过实验确定的)
通过这种方法,我获得了一百万个10位数字,前五个数字从千个随机前缀中选择,平均每个数字为8.83位(打包大小为1104188).
数字块上的霍夫曼编码可能会产生非常好的结果.如果数字是混合类型(例如一些美国,一些海外包括访问代码),则需要另外几位来指定它们是哪种类型(以及因此使用哪些块).
如果数字在一些小范围内 - 例如七位数 - 最紧凑的存储方式可能是将它们视为整数,对它们进行排序,并存储(霍夫曼编码的)值差异.例如,有7个数字的10 ^ 6个数字(10 ^ 7种可能性),你需要每个数字需要大约log2(10)〜= 3.3比特.
首先,我观察到它们从不以0开头,因为0在开始时用作转义字符.所以我可以简单地将电话号码视为整数.如果不是这种情况,我只需在数字前加一个"1",然后将其转换为整数.这不会显着影响编码效率(可能是几个字节的恒定开销).如果电话号码内的10位数字以外还有其他字符,则只能使用高于10的基数进行编码.但这会影响效率.
我按尺寸递增顺序排序.然后计算差异.然后使用protobuf序列化差异作为打包重复字段.
这种方法类似于RexKerr的方法,除了我使用protobuf的懒惰解决方案而不是霍夫曼编码器.可能有点大,因为protobuf整数编码是通用的,并没有考虑电话号码的概率分布.但是编码要容易得多,因为我只需要使用现有的protobuf序列化器.一旦超过UInt64的大小,这将会出现问题,即电话号码超过19位.文件格式仍然支持它,但大多数实现都不支持.
没有索引访问时间会非常糟糕,但它应该相当紧凑.
如果您查看北美编号计划的数据字段表示,您将得出结论,1 + NPA + NXX + xxxx 的美国电话号码可以存储在每个区号中每个电话号码字段少于22位的位置.添加区号和代表任何美国(加拿大)电话号码的数据可以轻松地适合32位.这是一个位字段表示 - 而不是int.
但是,你对此的思考不应该是以美国为中心的.当然,问题不仅仅在于将一百万个电话号码压缩到最少的位数.
美国电话号码可以短至3位数(内部PBX拨号方案)长达22位数(1 + NPA + NXX + xxxx + 11位内部PBX拨号方案).如果电话号码仅限于ITU指定的数字格式,则"+"最多可包含15位数加1位.
然后,您应该定义3位数和22位数(或ITU的15位数)之间的任何电话号码的可变位字段表示,每个位字段具有X位标题字段以指示字段的格式.
然后将这些位字段放入压缩位数组中.可能的是,位阵列可以用trie或其他方法索引.
这样做的效率取决于100万个电话号码的格式,您想要访问它们的速度,以及未来不同格式的数据结构对于更多电话号码的灵活性.它不只是计算"正确"答案恕我直言的位.