file - 文件格式需要倒排索引

Question

我一直在研究反向索引，它索引文档集合，将每个术语与信息一起存储，并将其引用存储在发布文件中（文档 ID、位置等）。

目前我将它存储为 .txt 文件格式，需要为与该 .txt 文件相关的每个查询进行字符串匹配，这需要更多时间并且更复杂。

现在我想将该信息存储在像链表样式数据结构这样的文件中。对于这种情况，这是否可能......（而且我正在使用 PHP 语言进行索引）。

任何帮助将不胜感激，谢谢。

Answer 1

倒排索引的要点是允许对任何给定术语的出现列表（发布列表）进行极快的访问。如果您想使用简单、现成的数据结构来实现它，那么您可能做的最好的事情就是

• 使用哈希存储从术语到发布列表的映射
• 将每个发布列表存储为一个连续的排序整数块（例如ArrayList，在 Java 或std::vectorC++ 中）。不要使用链表，因为这会浪费大量空间用于指针

一个更合适（和更复杂）的实现将考虑到：

• 帖子列表可能会变得非常大，因此您必须将其分成多个块，每个块都存储为一个连续的块
• 帖子列表可以而且应该被压缩

这些技术的详细描述可在经典书籍管理千兆字节中找到。