tem*_*def 16 language-agnostic compression algorithm graph data-structures
我正在开展一个侧面项目,现在涉及编码维基百科页面之间的所有链接.我已将此信息写入磁盘,但编码此图结构所需的内存使用量非常荒谬 - 有数百万个节点和数千万个链接.虽然这种结构确实适合记忆,但我不知道如果有十亿个链接或十亿页,我会怎么做.
我的问题是 - 有没有一种方法可以无损压缩一个太大的图形以适应内存,以便它适合内存？如果没有,是否有一个好的有损算法,对于某些"结构"的定义,不会从原始图中丢失太多的结构？
链接图和社交图等图表都经过深入研究,它们通常具有统计属性,可实现高效的压缩表示.
例如,这些属性之一是对于输出边缘,邻接列表的差分编码具有低功率分布,即存在许多非常小的值和非常少的大值,因此大多数通用代码工作得很好.特别是在这种设置中,zeta代码类是可证明是最优的,并且在本文中,作者压缩了每个链接大约3比特的小网络爬行的链接图.
他们的代码(用于Java,Python和C++)在他们的网页中可以作为图形压缩框架使用,因此您应该能够在不需要太多编码的情况下进行实验.
这个算法有点陈旧(2005)并且在该领域已经有了发展,但我现在没有指向论文的指针,这些改进无论如何都不重要,我认为没有任何可用且经过测试的代码实现它们.