10

我正在开发一些与 IDE 非常相似的东西，它将处理数以万计的非常大的（文本）文件，并且我正在调查该主题的最新技术。

例如，Intellij 对标准（非正则表达式）表达式的搜索算法非常直接。他们如何做到这一点？他们只是在内存中保留所有可搜索文件的某种后缀树吗？他们是否只是将文件内容的很大一部分保留在内存中，所以他们只是在内存中执行几乎完全的标准 KMP 以避免任何磁盘 IO？

谢谢

4

3 回答 3

12

目前，IntelliJ IDEA 对项目中的文件进行索引，并记住哪些 3-grams（3 个字母或数字的序列）出现在哪些文件中。搜索时，它也将查询拆分为 3-gram，从包含所有这些 trigram 的索引中获取文件，与这些集合相交，并在每个文件中使用相对简单的文本搜索来检查它们是否真的包含整个搜索细绳。

于 2016-09-05T06:03:57.360 回答
1

你可以看看Apache Lucene。这是一个完全用java编写的文本搜索引擎库。它可能对您的使用来说有点太重了，但是由于它是开源的，您可以看看它是如何工作的。

它具有一个演示，可引导您构建索引并搜索库源代码，这听起来非常像您想要做的。

另外，看看Boyer-Moore 字符串搜索算法。这显然通常用于提供 ctrl+f 样式文档搜索的应用程序。它涉及对搜索词进行预处理，以便它可以运行尽可能少的比较。

于 2016-09-04T21:08:14.163 回答
1

正如 js441 指出的那样，Apache Lucene 是一个不错的选择，但前提是您要进行基于术语的搜索，类似于 google 的工作方式。如果您需要搜索跨术语 Lucene 的任意字符串，则不会帮助您。

在后一种情况下，您是对的，您必须构建某种后缀树。构建后缀树后可以做的一个巧妙的技巧是将其写入文件并将其映射到内存空间。这样，您不会浪费内存将整个树保存在 RAM 中，但您会自动缓存树的频繁访问部分。mmap 的缺点是初始搜索可能有点慢。如果您的文件经常更改，这也不会。

为了帮助搜索刚刚编辑过的文件，您可以保留两个索引，一个用于大量文件，另一个仅用于最近编辑的文件。因此，当您进行搜索时，您将在两个索引中进行搜索。您应该定期使用新文件的内容重建永久索引并替换旧的。

以下是 Lucene 何时好以及后缀树何时好的一些示例：

假设您有一个包含以下内容的文档：

一只敏捷的棕色狗跳过了懒惰的狐狸。

Lucene 适合以下搜索：

  • 快的
  • 快速棕色
  • q*

  • q* b

    通过一些技巧，您可以使以下搜索正常工作：

  • '*ick *拥有'

    这种类型的搜索会运行得很慢

  • 'q*ick 棕色 d*g'

    而且这种类型的搜索永远找不到任何东西

  • “ick brown d”

    当您将文档视为词袋时，Lucene 也很好。所以你可以轻松地进行这样的搜索

  • 快狐

    无论中间是什么，它都会为您找到所有包含单词 quick 和 fox 的文档。

    另一方面，后缀树可以很好地搜索文档中子字符串的精确匹配，即使您的搜索跨越了术语并且在术语中间开始和结束。

    此处描述了构建大型数组后缀树的非常好的算法（Warnign paywalled）。

于 2016-09-04T21:16:00.777 回答