我有一个SQLite数据库，里面充满了大量的URL，它占用了巨大的磁盘空间，并且访问它会导致许多磁盘寻道并变得很慢。 平均URL路径长度为97个字节（主机名重复很多，因此我将它们移到了外键表中）。 有没有好的方法可以压缩它们？ 大多数压缩算法在处理大型文档时效果良好，而不是平均不到100个字节的“文档”，但即使20％的减少也非常有用。 有哪些压缩算法可以使用？ 不必非得是标准算法。
如何压缩小字符串
11
- taw
1
1FemtoZip适用于压缩大量小型文档。https://github.com/gtoubassi/femtozip - bossturbo
7个回答
11
使用压缩算法，但使用共享字典。
我之前做过类似的事情，我使用了LZC/LZW算法，就像Unix compress命令使用的那样。
要想获得短字符串的良好压缩效果的诀窍是使用由标准样本URL组成的字典进行压缩。
您应该可以轻松获得20%的压缩率。
编辑：LZC是LZW的一种变体。因为只需要静态字典，所以您只需要LZW。当字典/表满时，LZC添加了重置字典/表的支持。
- ewalshe
1
我之前将压缩和哈希表结合起来，将URL转换为32位ID，这比字符串占用更少的空间。您也不需要URL表 - 您只需存储ID而不是外键即可。 - Pete Kirkham
5
我尝试使用以下策略进行操作。它使用了共享词典的方法，但绕过了Python zlib无法访问词典本身的方式。
首先，通过将大量训练字符串传递给压缩器和解压器来初始化预先训练的压缩器和解压器。然后丢弃输出字符串。
然后，使用经过训练的压缩器的副本来压缩每个小字符串，并使用解压器的副本对它们进行解压缩。
以下是Python代码（对于丑陋的测试，我表示抱歉）：
首先，通过将大量训练字符串传递给压缩器和解压器来初始化预先训练的压缩器和解压器。然后丢弃输出字符串。
然后，使用经过训练的压缩器的副本来压缩每个小字符串，并使用解压器的副本对它们进行解压缩。
以下是Python代码（对于丑陋的测试，我表示抱歉）：
import zlib
class Trained_short_string_compressor(object):
def __init__(self,
training_set,
bits = -zlib.MAX_WBITS,
compression = zlib.Z_DEFAULT_COMPRESSION,
scheme = zlib.DEFLATED):
# Use a negative number of bits, so the checksum is not included.
compressor = zlib.compressobj(compression,scheme,bits)
decompressor = zlib.decompressobj(bits)
junk_offset = 0
for line in training_set:
junk_offset += len(line)
# run the training line through the compressor and decompressor
junk_offset -= len(decompressor.decompress(compressor.compress(line)))
# use Z_SYNC_FLUSH. A full flush seems to detrain the compressor, and
# not flushing wastes space.
junk_offset -= len(decompressor.decompress(compressor.flush(zlib.Z_SYNC_FLUSH)))
self.junk_offset = junk_offset
self.compressor = compressor
self.decompressor = decompressor
def compress(self,s):
compressor = self.compressor.copy()
return compressor.compress(s)+compressor.flush()
def decompress(self,s):
decompressor = self.decompressor.copy()
return (decompressor.decompress(s)+decompressor.flush())[self.junk_offset:]
测试后，我使用压缩技术成功压缩了一万个长度在50到300字符之间的Unicode字符串，并且节省了30%以上的空间。压缩和解压缩这些字符串大约需要6秒钟（相比于使用简单的zlib压缩/解压缩的2秒钟）。然而，简单的zlib压缩只节省了5%，而不是30%。
def test_compress_small_strings():
lines =[l for l in gzip.open(fname)]
compressor=Trained_short_string_compressor(lines[:500])
import time
t = time.time()
s = 0.0
sc = 0.
for i in range(10000):
line = lines[1000+i] # use an offset, so you don't cheat and compress the training set
cl = compressor.compress(line)
ucl = compressor.decompress(cl)
s += len(line)
sc+=len(cl)
assert line == ucl
print 'compressed',i,'small strings in',time.time()-t,'with a ratio of',s0/s
print 'now, compare it ot a naive compression '
t = time.time()
for i in range(10000):
line = lines[1000+i]
cr = zlib.compressobj(zlib.Z_DEFAULT_COMPRESSION,zlib.DEFLATED,-zlib.MAX_WBITS)
cl=cr.compress(line)+cr.flush()
ucl = zlib.decompress(cl,-zlib.MAX_WBITS)
sc += len(cl)
assert line == ucl
print 'naive zlib compressed',i,'small strings in',time.time()-t, 'with a ratio of ',sc/s
请注意，如果您删除它，则不会保留该内容。如果您需要保持内容，请记住训练集。
- wisty
4
您是否考虑过使用静态的哈夫曼编码？
您可以使用现有的URL列表计算所有字节在URL中出现的频率，并根据此计算Huffmann编码。然后，您可以将该代码集存储一次，并使用它对所有URL进行编码。我认为这应该能够提供不错的压缩效果。
- bendin
4
你的URL格式是什么？
如果任何URL共享一个或多个域名，并且您已经足够了解大约20亿个域名，可以为域名创建一个池。如果您有共享的相对路径，也可以将它们放入池中。
对于数据库中的每个URL，请将每个URL分成三个部分：方案和域，例如http://mydomain.com，实际URL /my/path/，然后是剩余的mypage.html?id=4（如果您有查询字符串参数）。
这样，您应该将每个域名和相对路径的开销减少到仅约8字节。如果您想要查找URL的某些部分，则应更好且快速。
注意：仅“http”方案字符串本身就占用4个字节，您将在每个域条目上节省超出此范围的任何内容。如果每个URL都以“http://www.”开头，您将每次节省“：//www。”7个字节。
尝试一下如何拆分和结构化URL，我敢打赌这是您发现压缩的地方。现在，剩余的字符串不是常见的域名或相对路径，您能做些什么呢？
压缩URL
一般用途的压缩方法是从算术编码中派生出来的。信息论之父Shannon在60年代写了一篇关于此的论文。我一直在研究压缩，而我始终发现，通用目的的压缩永远无法解决实际问题。
您很幸运，因为URL具有结构，您应该利用这种结构更好地存储您的URL。
如果您想应用压缩算法（我认为主题应更改以反映URL压缩，因为它是特定于域的），则必须检查数据的熵。因为它会告诉您存储的产量。 URL是ASCII字符，不在ASCII范围0x20-0x7E内的任何字符都不会出现，并且忽略大小写，您只剩下63个不同的状态。 !"#%&'()*+,-./0123456789:;<=>?@abcdefghijklmnopqrstuvwxyz{|}~ 包括空格。
您可以创建剩余字符的频率表并执行算术编码。您知道最多需要6位，这意味着对于数据库中的每个字符，您现在浪费了2位，如果您只是将事物移动到正确位置并使用查找表，则可以获得20％的压缩率。就像那样 ;)
由于数据非常特定，因此仅使用通用方法进行压缩并不是一个好主意。最好结构化信息并将其拆分为更有效存储的数据块。您对域名了解很多，请利用这些知识来压缩数据。
- John Leidegren
2
正如我所说，我已经只存储路径（http://host.com/部分是外键），而且URL区分大小写，所以这样做行不通。每8位保存1位是一种明显的优化方式，我只是想知道是否有更好的方法。 - taw
根据RFC规定，URL应该是不区分大小写的，如果您需要区分大小写，请自行处理。从频率分析中构建静态表以进行算术编码是一个很好的开始。您需要在位级别上工作，如果可以的话，分解路径。在数据库中寻找模式。 - John Leidegren
2
摘要：
大规模搜索引擎和网络爬虫的常见问题是如何处理大量遇到的URL。传统的搜索引擎和网络爬虫使用硬盘存储URL而不进行任何压缩。这导致性能缓慢且需要更多的空间。本文描述了一种简单的URL压缩算法，可以实现高效的压缩和解压缩。该压缩算法基于增量编码方案提取共享公共前缀的URL和AVL树以获得高效的搜索速度。我们的结果表明，可以实现50％的大小减小。
-- Kasom Koht-arsa计算机工程系。
- Lukas Šalkauskas
2
论文中提出的解决方案似乎无法扩展到URL不适合内存的情况，即使使用非常高的压缩率也不行。此外，他们的数据（平均每个完整URL 55字节）与我的非常不同（仅路径部分的平均97字节）。 - taw
我之所以说这个是因为它可能会给你带来一些好的想法。 - Lukas Šalkauskas
0
这是 97 字节，还是 97 个 8 位 ASCII 字符，或者是 97 个 16 位 Unicode 字符？
假设您的所有 URL 都符合 http://www.w3.org/Addressing/URL/url-spec.txt 的规定，则应该只有 ASCII 字符。
如果是 97 个 16 位 Unicode 字符，只需存储每个字符的低字节即可自动节省 50% 的空间。
如果是 97 个 8 位字符，则注意到只需要 7 位。可以将每次传入 7 位到您的位流中并将该位流存储到数据库中；使用一些旧的 7 位传输协议；或想出自己的特别方法，将每第 8 个字符的位存储在前 7 个字符的高位中。
- Ants
0
如何使用URL表？
通常您是进行“范围扫描”还是仅进行唯一ID查找？
如果您不会像WHERE url like "/xxxx/question/%"这样做。您可以使用哈希索引而不是在varchar()上使用B树索引来减少磁盘寻道次数。
- Dennis Cheung
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接