6

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

我正在研究存储这些 ID 对列表的策略。我们发现一个 SQL 数据库（该项目的大多数其他数据都存放在该数据库中）对于我们的目的而言太慢且磁盘空间太大，因此目前我们将每个存储桶存储为磁盘上的压缩整数列表（最初是 zlib 压缩的，但现在使用 lz4 代替速度）。我喜欢这个的事情：

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

很烂的事情：

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

那么：我应该查看哪些类型的数据结构？我怀疑正确的答案是某种奇异的简洁数据结构，但这不是我非常了解的空间。此外，如果重要的话：所有文档 ID 都是无符号的 32 位整数，并且处理此数据的当前代码是用 C 编写的，作为 Python 扩展，所以如果可能的话，这可能是我们将坚持使用的通用技术系列。

4

3 回答 3

1

为什么不只存储一个包含自上次重写以来已删除的内容的表？

该表可能与您的主存储桶具有相同的结构，可能带有用于快速成员资格检查的布隆过滤器。

您可以在不删除项目的情况下重新写入主存储桶数据，无论是当您打算重写它以进行其他修改时，或者当已删除项目：存储桶大小的比率超过某个阈值时。

该方案可以通过将每个已删除的对与每个存储桶一起存储，或者为所有已删除的文档存储一个表来工作：我不确定哪个更适合您的要求。

保留一个表，除非您知道它影响了多少个存储桶，否则很难知道何时可以删除一个项目，而无需在删除表变得太大时重新写入所有存储桶。这可以工作，但它有点停止世界。

您还必须对您流式传输的每一对进行两次检查（即，对于(3278, 15378)，您将检查其中一个3278或15378已被删除，而不仅仅是检查对是否(3278, 15378)已被删除。

相反，每个已删除对的每桶表的构建时间会更长，但检查速度会稍微快一些，并且在重写桶时更容易崩溃。

于 2013-05-08T15:22:35.860 回答
1

每个桶使用一个哈希表或 B-tree 怎么样？

磁盘哈希表是标准的。也许 BerkeleyDB 库（库存 python 可用）对你有用；但请注意，由于它们带有事务，它们可能会很慢，并且可能需要一些调整。有很多选择：gdbm、tdb，你都应该试一试。只要确保你检查了 API 并用适当的大小初始化它们。有些不会自动调整大小，如果你给它们提供太多数据，它们的性能就会下降很多。

无论如何，如果你有很多变化，你可能想要使用更底层的东西，没有事务。

一对 int 是 long - 大多数数据库应该接受 long 作为键；事实上，许多人会接受任意字节序列作为键。

于 2013-05-08T15:11:28.500 回答
-1

您正在尝试重新发明新时代 NoSQL 数据存储中已经存在的内容。有 2 个非常好的候选人可以满足您的要求。

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

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

它们两者的性能都取决于可驻留在 RAM 中的数据量。由于您的大部分数据都是基于整数的，因此这应该不是问题。

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

这里简要介绍一下 redis 数据结构： http ://redis.io/topics/data-types-intro

redis 数据库是一个轻量级的安装，客户端可以在 Python 中使用。

于 2013-05-07T19:01:07.477 回答