用于在磁盘上有效存储整数对集的数据结构选项？

Question

我有一堆处理文档聚类的代码.一步涉及计算每个文档与给定语料库中的每个其他文档的相似性(对于"类似"的一些不重要的定义),并存储相似性以供以后使用.相似之处是不同的,我不关心具体的相似性是什么,我的分析的目的,只是它在什么桶.例如,如果文件15378和3278是52%相似,有序对(3278,15378)得到存储在[0.5,0.6]桶中.在初始分析之后,文档有时会在语料库中添加或删除,因此根据需要将相应的对添加到桶中或从桶中删除.

我正在研究存储这些ID对列表的策略.我们发现一个SQL数据库(这个项目的大多数其他数据都存在)对于我们的目的来说太慢而且磁盘空间太大,所以目前我们将每个存储桶存储为磁盘上的整数压缩列表(最初zlib压缩,但现在使用lz4代替速度).我喜欢这件事:

• 阅读和写作都非常快
• 语料库的事后添加是相当简单的添加(对于lz4比对zlib少一点,因为lz4没有内置的框架机制,但可行)
• 在写入和读取时,数据都可以流式传输,因此不需要一次性保存在内存中,考虑到我们的语料库大小,这将是令人望而却步的

有点糟糕的事情:

• 删除是一个巨大的痛苦,基本上涉及流式传输所有桶并写出新的,省略任何包含已被删除的文档的ID的对
• 我怀疑通过更专用的数据结构和/或压缩策略,我在速度和紧凑性方面仍然可以做得更好

那么:我应该关注哪种数据结构？我怀疑正确的答案是某种奇特的简洁数据结构,但这不是我所熟知的空间.此外,如果重要:所有文档ID都是无符号的32位整数,处理这些数据的当前代码是用C语言编写的,作为Python扩展,所以这可能是我们坚持的通用技术系列.

Answer 1

您正在尝试重新发明新时代 NoSQL 数据存储中已经存在的内容。有 2 名非常适合您的要求的候选人。

1. 雷迪斯。
2. 蒙古数据库

两者都支持字典、列表、队列等数据结构。追加、修改或删除等操作在两者中都可用，而且速度非常快。

它们的性能均由 RAM 中驻留的数据量驱动。由于大多数数据都是基于整数的，因此这应该不是问题。

我个人的建议是使用 Redis，具有良好的持久性配置（即数据应定期从 RAM 保存到磁盘）。

以下是 redis 数据结构的简介： http://redis.io/topics/data-types-intro

redis数据库是轻量级安装，客户端可用Python。