c++ - Read-moSTLy 数据结构压缩和搜索源代码

Question

假设您有大量流行语言(Java、C、C++ 等)的源代码(如 50GB 以上)。

项目需求是:

• 压缩源代码以减少磁盘使用和磁盘 I/O

• 以无需解压整个文件即可从压缩源中提取特定源文件的方式对其进行索引

• 整个代码库的压缩时间不重要

• 搜索和检索时间(以及搜索和检索时的内存使用)很重要

此 SO 答案包含潜在答案:What are the lesser known but useful data structures?

但是，这只是潜力列表 - 我不知道这些结构实际上如何根据上面列出的要求进行评估。

问题:根据上述要求，哪些数据结构(及其实现)会表现良好？

Answer 1

用于搜索的主要数据结构是 inverted list .幸运的是，您不需要自己实现它。 Lucene是一种广泛使用的搜索工具，可在内部使用倒排列表。

使用 Lucene，您可以创建具有多个字段 的文档。我们的想法是，其中一些字段可以使用标准关键字类型查询搜索。

我已经实现了一个源代码搜索实用程序，现在我将在以下段落中对其进行简要描述。整个源代码本身存储为一个名为“代码”的不可索引字段(您可以修改源代码以存储压缩版本)。

对于检索部分，请注意您要用于搜索的关键字可以是函数、类、包或变量的名称。它们也可以是评论中的文字等等。在我的实现中，我使用 Java 注释语法树 (AST) 提取了这些信息。通过使用适当的解析器构建 AST，您也可以对其他语言执行相同的操作。

另一种可能性是示例查询 (QBE) 范例，您可以在其中使用一小段代码从您的索引代码库中搜索大致相似的片段。这对于检测源代码重用和剽窃特别有帮助，这是我开发该工具的主要目的。

项目页面为here .我称之为 YASOCS(又一个源代码搜索器)。

搜索速度非常快，因为它使用倒排列表。您也可以使用 Luke (一个开源的 Lucene 索引可视化工具)自己“查看”索引并使用界面执行测试查询。