hOOt - 全文搜索引擎

Mehdi Gholam

4.92/5 (155投票s)

2011年7月12日

CPOL

17分钟阅读

1322361

23160

最小的全文本搜索引擎（lucene 替代品），从头开始使用倒排 MGRB 位图索引构建，存储高度紧凑，支持数据库和文档模式运行

引言

简介

hOOt 是一个极其小巧且快速的嵌入式 .NET 全文搜索引擎，使用倒排 WAH 位图索引从头构建。大多数人都熟悉 Apache 的 Lucene.net 项目，它是 Java 原始版本的移植。很多人过去曾抱怨为什么 lucene 的 .NET 版本没有得到维护，并且存在许多原始版本的非官方移植。为了规避这个问题，我创建了这个项目，它完成了相同的工作，但更小、更简单、更快。hOOt 是我即将推出的 RaptorDB 文档存储数据库 的一部分，并且非常成功，因此我决定暂时将其作为一个独立实体发布。

hOOt 使用以下文章

WAH 压缩位数组，在此处找到 (WAHBitArray.aspx)
mini Log4net 替代品，在此处找到 (https://codeproject.org.cn/KB/miscctrl/minilog4net.aspx)
来自 RaptorDB 的 MurMur2 哈希索引和存储文件，在此处找到 (RaptorDB.aspx)
fastJSON 序列化器，在此处找到 (https://codeproject.org.cn/KB/IP/fastJSON.aspx)
Eyal Post 的无 COM 的 IFilter，在此处找到 (https://codeproject.org.cn/KB/cs/IFilter.aspx) 用于示例应用程序

根据用户对该项目的响应和反馈，我将把 hOOt 升级和增强到与 lucene.net 完全兼容的功能，所以请支持我。

为什么叫 'hOOt'？

这个名字来源于著名的 Google 搜索页脚，当时我在寻找猫头鹰的标志（gooooogle ~ hOOOOOOOt）。

什么是全文搜索？

全文搜索是指在文本块中搜索单词的过程。全文索引器/搜索器有两个方面：

存在性：意味着找到存储在许多文本块中的单词（例如，'bob' 存在于存储的 PDF 文档中）。
相关性：意味着返回的文本块是通过一个排序系统传递的，该系统将最相关的排在前面。

第一部分很简单，第二部分很难，并且在使用的排名公式上存在很大争议。hOOt 在此版本中仅实现第一部分，因为我们大多数人在应用程序中使用和需要存在性比相关性更多，尤其是对于数据库应用程序。

为什么要另一个全文索引器？

我一直对 Google 的搜索方式以及 lucene 的索引技术及其内部算法着迷，但它们太难理解了。任何使用过 lucene.net 的人都会证明它是一段复杂且晦涩的代码。虽然有些人正在尝试创建更 .NET 优化的版本，但事实是，用现有的代码库很难做到。令我惊讶的是，没有人从头开始重写它。 hOOt 比 lucene.net 更简单、更小、更快。

创建 hOOt 的原因之一是为 RaptorDB - 文档存储版本 - 的字符串列实现全文搜索。希望更多人能够使用和扩展 hOOt 而不是 lucene.net，因为它更容易理解和更改。

特点

hOOt 在构建时考虑了以下特点：

极快的运行速度（参见性能测试部分）
代码体积极其小巧。
使用 WAH 压缩位数组存储信息。
多线程实现，意味着您可以在索引时进行查询。
体积小巧，仅 38kb DLL（lucene.net 约为 300kb）。
高度优化的存储，通常比 lucene.net 小约 60%（索引中的内容越多，差异越大）。
查询字符串按空格分隔，并使用 AND 运算符（例如，所有单词都必须存在）。
查询中支持通配符（*、?）。
OR 操作是默认的（类似于 lucene）。
AND 操作需要 (+) 前缀（类似于 lucene）。
NOT 操作需要 (-) 前缀（类似于 lucene）。

限制

此版本存在以下限制：

文档模式下的文件路径限制为 255 字节或 UTF8 等效字符。
目前不支持精确字符串匹配（例如，“爱丽丝梦游仙境”）。
~~目前不支持通配符（*、?）。~~
~~查询中目前不支持 OR 操作（例如，bob OR alice）。~~
~~查询中目前不支持 NOT 操作（例如，bob NOT alice）。~~
查询中目前不支持括号。
目前不支持排名和相关性。
目前不支持搜索用户定义的文档字段。

性能测试

测试在我的笔记本电脑上进行，规格如下：AMD K625 1.5Ghz，4Gb Ram DDRII，Windows 7 Home Premium 64位，Win Index 3.9。
hOOt 生成大量日志信息，您可以使用这些信息了解引擎内部情况。使用示例应用程序，我对大约 4600 个文件（约 5.8Gb 数据）进行了抓取，这些文件格式各不相同。以下是使用 grep 对输出文件进行分析的结果（请注意，该应用程序是在 .NET 4 下编译并以 64 位运行的，并且安装了 64 位 IFilters）

文档数量	4,490
总时间	约 22 分钟
索引文件大小	29 MB
文本总大小	632,827,458 个字符
hOOt 总索引时间	56767.2471 毫秒 ~ 56.7 秒
hOOt 写入文档信息总时间（fastJSON 序列化）	110632.3282 毫秒 ~ 110 秒
hOOt 中的总单词数	~290,000

正如您所见，索引引擎速度极快，在 57 秒内处理了 632MB 的文本。与总共 22 分钟的差异是由于 IFilter 提取时间。在查询方面，对于上述文档数量，所有查询在引擎端执行时间约为 1 毫秒，正如您在示例图片中看到的，搜索“microsoft”返回了 208 项，耗时 0.151 秒，这再次是由于文档反序列化时间。

相比之下，lucene.net 的结果如下：

索引文件大小	70.5 MB
总时间	约 28 分钟

性能测试 v1.2

使用更好的单词提取器，索引大小减少了约 19% 至 24MB。

使用示例应用程序

上图是基于 hOOt 构建的桌面搜索应用程序。要使用该应用程序，请执行以下操作：

在（1）组框中设置索引存储目录，这将存储所有索引信息。
在（2）组框中选择一个要抓取内容的文件夹。
在（3）组框中，您可以执行以下操作：
1. 加载 hOOt：这将加载 hOOt，以便您可以查询现有索引。
2. 开始索引：这将加载 hOOt 并开始索引您指定的目录。
3. 停止索引：在开始索引后，此选项将变为可用，以便您可以停止该过程。
4. 计数单词：这将显示 hOOt 词典中的单词数量。
5. 保存索引：这将把内存中的任何内容保存到磁盘。
6. 释放内存：这将调用 hOOt 上的内部释放内存方法（这只会释放位图存储，而不会释放缓存）。
您可以在（4）组框中搜索内容，标签将显示计数和所花费的时间。
1. 双击列表框中的文件路径即可打开文件。

这只是一个展示 hOOt 功能的演示，虽然它本身就能工作，但对于实际应用程序来说，它还需要一些额外的功能。为了有效使用此示例，请提前安装以下 IFilter 处理程序：

Foxit PDF 过滤器，在此处找到 (http://www.foxitsoftware.com/) [切勿使用 Adobe，因为它非常慢]。
Microsoft Office 2010 IFilter，在此处找到 (http://www.microsoft.com/download/en/details.aspx?displaylang=en&id=17062)

v1.5 的更改

从 1.5 版本开始，查询遵循 lucene 风格，需要前缀，并增加了对通配符的支持，如下所示：

用于 AND 操作的前缀（+）字符

+microsoft +testing 

Search for "microsoft" and "testing" and all words must exist

用于 NOT 操作的前缀（-）：

 microsoft -testing

Search for "microsoft" excluding "testing"

默认是 OR 操作

 microsft testing

Search for "microsoft" or "testing" and any word can exist

对于通配符，使用（*、?），就像旧式 DOS 搜索一样，所有结果将被 OR 一起处理。

 m?cro*
 
Search for "macro" or "micro" or "microsoft" or "microphone" or ...

示例应用程序背后的代码

示例应用程序背后的代码很容易理解，它使用 BackgroundWorker 类来执行索引，并提供进度事件供 UI 显示已完成的文件。

private void backgroundWorker1_DoWork(object sender, DoWorkEventArgs e)
{
	string[] files = e.Argument as string[];
	BackgroundWorker wrk = sender as BackgroundWorker;
	int i = 0;
	foreach (string fn in files)
	{
		if (wrk.CancellationPending)
		{
			e.Cancel = true;
			break;
		}
		backgroundWorker1.ReportProgress(1, fn);
		try
		{
			TextReader tf = new EPocalipse.IFilter.FilterReader(fn);
			string s = "";
			if (tf != null)
				s = tf.ReadToEnd();

			h.Index(new Document(fn, s), true);
		}
		catch { }
		i++;
		if (i > 300)
		{
			i = 0;
			h.Save();
		}
	}
	h.Save();
        h.OptimizeIndex();
}

在您的代码中使用 hOOt

使用 hOOt 简单直接。

// specify the index folder to store information and the file name for the index files
Hoot hoot = new Hoot("d:\\IndexFolder" , "documents"); 

hoot.FreeMemory(false); // will free bitmap memory

// database mode of operation
hoot.Index(10, "some string from a database"); // index the contents of rec# 10 

// document indexing mode of operation
hoot.Index(new Document("d:\\filename.ext",string_from_file));  

// optimize the bitmap index size
hoot.OptimizeIndex();

您可以继承 Document 对象，并存储应用程序需要的任何额外信息作为属性（lucene 使用字典值，这在编译时不利，并且在运行时需要进行拼写等检查）。

public class myDoc : Hoot.Document
{
	public string Extension {get;set;}
	// any other properties you need
}

因为 hOOt 使用 fastJSON 来存储您创建的文档，所以它会以一流对象的方式将您保存的内容返回给您。

v1.2 中的新增功能

foreach(string filename in hoot.FindDocumentNames("microsoft"))
{
   // a faster way to get just the filename instead of a Document object
}

工作原理

hOOt 在以下 2 种模式下运行：

数据库模式：您要索引数据库中的列，并自行提供数据库中的行号。
文档模式：您提供一个文档文件给 hOOt，该文件将被序列化并存储，并为其生成文档编号。

hOOt 有 2 个主要部分，如下所示：

索引器引擎：负责更新和处理生成的索引。
查询引擎：负责解析查询文本并生成执行计划。

为了优化内存使用，索引器可以在以下 2 个阶段释放内存：

压缩内存中的位图索引并释放位数组存储。
完全卸载缓存的单词位图索引。

在大多数情况下，您将使用第一阶段，但如果您要索引数亿个文档，那么第二阶段将是必要的。

一些统计数据...

快速在互联网上搜索，可以找到以下关于英语的统计数据：

英语大约有 250,000 个单词，其中约 175,000 个在 W使用（牛津英语词典）。
英语单词的最大长度为 28 个字符。

在通过 IFilters 提取的单词后，很容易看出一些文档格式存在问题，因为有些句子没有空格，单词粘在一起。此外，对于编程文档，CamelCase 单词很普遍。

因此，从 1.2 版本开始，hOOt 中的单词提取器将执行以下操作：

CamelCase 单词会被拆分。
长度大于 60 个字符的单词将被忽略
长度小于 2 个字符的单词将被忽略

索引引擎

索引引擎负责以下工作：

将单词加载到内存中。
按需加载位图索引数据。
从输入文本中提取单词统计信息。
更新单词位图索引。
释放内存和位图缓存。
将单词写入磁盘。
将位图索引写入磁盘。

查询引擎

查询引擎将执行以下操作：

将输入的搜索字符串解析为单词
提取搜索字符串中所有使用的单词的位图索引
执行位图算术逻辑
将结果与已删除文档位图的 NOT 进行 AND 操作，以过滤掉已删除的文档。
枚举结果位图
- 在数据库模式下，为您提供记录号列表
- 在文档模式下，查找文档编号，并为您提供来自文档存储的文档列表。

什么是倒排索引？

倒排索引是一种特殊索引，它存储单词到位图的转换数据。在普通索引中，您会存储某个文档中包含哪些单词，而倒排索引则相反，给定一个单词 'x'，它存储了哪些文档包含这个单词。

例如，如果您有以下内容：

文档编号 1：“to be or not to be, that is the question ...”
文档编号 2：“Romeo! Romeo! where art thou Romeo! ...”

使用 GenerateWordFreq 方法解析后将生成以下内容：

单词：{"to" count=2, doc#=1 }，{"be" count=2, doc#=1}，{"or" count=1, doc#=1} ...
单词：{"romeo" count=3, doc#=2}，{"where" count=1, doc#=2} ...

并且将更新以下单词位图（1 表示该单词存在于文档编号的索引位置，0 表示不存在）

to : 1000000...
be : 1000000...
or : 1000000...
romeo : 0100000...
where : 0100000...

位图索引的力量

要了解位图索引的力量，请看以下图表。

xxxhOOt/execution_plan.png

如您所见，对于查询字符串“alice in wonderland”（不含引号），hOOt 将执行以下操作：

过滤器解析器提取单词“alice”、“in”、“wonderland”。
查找与这些单词关联的位图索引。
执行查询算术逻辑，在这种情况下是逻辑 AND 操作，以生成结果位图索引。

结果位图是文档的基于索引的记录号。例如，如果结果是 0001100...，那么文档 4, 5...（从索引号 1 开始）包含所有单词“alice”、“in”、“wonderland”。
这与 lucene 索引方案形成鲜明对比，后者将记录号字面存储，尽管是优化过的表示法。hOOt 提供了巨大的索引大小空间节省，尤其是使用了 WAH 压缩，并且作为一个额外的优点，性能也极其快速。

生成的文件

在索引目录中会生成以下文件：

filename.WORDS：存储从输入文本中提取的单词。
filename.DOCS：存储文档信息。
filename.BITMAP：存储所存储单词的位图信息。
filename.DELETED：存储已删除文档的索引。
filename.REC：存储文档编号的数据文件偏移量。
filename.IDX：存储文档文件名与文档编号之间的映射。
log.txt：存储日志调试和错误消息。

文件格式：*.WORDS

单词以以下格式存储在磁盘上：
xxxhOOt/words_file.png

位图索引偏移量将指向 *.bitmap 文件中的一个记录。

文件格式：*.DOCS

文档以 JSON 格式存储在磁盘上的以下结构中：
xxxhOOt/docs_file.png

此格式直接来自 RaptorDB 并在那里使用，hOOt 中的唯一修改是 MaxKeyLength 设置为 1。另外，由于记录的长度可变，*.RECS 文件将记录号映射到此文件中的偏移量以进行数据检索。

文件格式：*.BITMAP

位图索引以以下格式存储在磁盘上：
xxxhOOt/bitmap_file.png

位图行长度可变，如果新数据适合磁盘上的记录大小，则会被重用。如果不行，将创建另一个记录。因此，可能需要定期进行索引压缩以删除之前更新留下的未使用记录。

文件格式：*.DELETED

已删除索引文件只是代表已删除文件的 int 值系列，没有特殊格式。

文件格式：*.REC

Rec 文件是写入磁盘的 long 值系列，没有特殊格式。这些值将记录号映射到 DOCS 存储文件中的偏移量。

文件格式：*.IDX

IDX 文件是 MurMur2 哈希字典，用于将文档文件名映射到文档编号。这在文档模式下使用。

附录 v2.0

终于有时间更新 hOOt 了，大部分更新都来自于 RaptorDB 的回传，主要是为了提高稳定性、修复 bug 和改进性能，例如锁和多线程问题。

位图文件格式已更改，以支持索引偏移量，并且存储文件已更新以支持已删除项，因此之前的文件在此版本中将无法使用。

hOOt 现在支持文档的增量索引，并将在索引之前检查文件是否存在。您现在可以 RemoveDocument(filename)，文件将从索引结果中删除。

文件信息（如日期和大小）现在存储在存储文件中，因此将来可以检查已更改的文件并索引已更新的文档。

附录 v3.3.7

终于找到时间为 hOOt 添加一些内容，并发布了期间在 RaptorDB 中进行的许多更改。其中大部分是 bug 修复。值得注意的新增功能是能够继承您自己的类 Document 并添加属性，因此您现在可以这样做：

    /// <summary>
    /// Sample doc override
    /// </summary>
    public class myDoc : Document
    {
        public myDoc(FileInfo fileinfo, string text) : base(fileinfo, text)
        {
            now = DateTime.Now;
        }

        // other data I want to save
        public DateTime now;
    }

此外，单词提取部分已被提取到自己的类中，因此将来您可以更轻松地更改分词器。

附录 v4.0.7

从这个版本开始，这里的代码（大部分）与 RaptorDB 中的代码同步。此外，索引现在使用 MGRB 位图结构，该结构使用的内存（大约三分之一）更少。索引文件不是向后兼容的，因此您应该删除它们并重新构建。

版本记录

历史

初始发布 v1.0：2011 年 7 月 12 日
更新 v1.1：2011 年 7 月 16 日
- 调整了参数，索引大小减少了 46%（现在不到 lucene 的一半）
- 性能提升，位图索引保存速度提升 5 倍
- 修复了示例 UI 的 bug
- 修复了位数组大小调整的 bug
- 内部线程安全
- 代码重构
- 实现了 OptimizeIndex()
更新 v1.2：2011 年 7 月 21 日
- FindDocumentFileNames() 用于更快的仅字符串返回
- 更好的单词提取器 ~ 索引减小 19%
  - 分割 CamelCase 复合词
  - 忽略长度 >60 个字符和 <2 个字符的字符串
- 更新了统计部分
更新 v1.3：2011 年 7 月 23 日
- 修复了位数组算术的 bug
- 修复了 UI 列表框闪烁问题
更新 v1.4：2011 年 7 月 26 日
- 将 WAHBitarray 替换为 v2
- 位图保存速度提升约 9 倍
- ** 索引必须从前一个版本重建 **
更新 v1.5：2011 年 8 月 7 日
- 感谢 **Dave Dolan** 提供的查询评估逻辑
- 增加了对通配符（*、?）的支持
- 增加了对 AND (+)、NOT (-) 查询的支持
更新 v2.0：2012 年 12 月 24 日
- 在项目中更新并嵌入了 fastjson v2.0.11
- 回传了 RaptorDB 的代码
- 线程安全锁更新
- 修复了日志记录器线程问题
- 重构了源代码
- 修复了示例窗体的 Tab 顺序（感谢 **Sergey Kryukov**）
- 增加了增量索引功能
- 存储文档文件信息以供将来检查
更新 v2.1：2013 年 5 月 24 日
- 升级到 fastJSON v2.0.15
- 修复了最后一个单词丢失最后一个字符的 bug
更新 v2.2：2013 年 6 月 15 日
- WAHBitArray bug 修复
- 代码与 RaptorDB 同步
更新 v2.2.1：2013 年 6 月 22 日
- WAHBitArray bug 修复
更新 v3.3.7：2016 年 8 月 5 日
- 与 RaptorDB v3.3.7 同步代码
- 将 FindDocuments() 更改为泛型
- 修复了继承 Document 以添加自定义属性的功能
- 修复了 64 位系统上注册表读取 IFilter 的问题
- 搜索修复“microsoft -oracle +google -app*”
- 将 tokenizer 提取到自己的类中，并进行更好的单词解析
- 添加了带有自动增量的构建版本
- 日志消息多样化
- 日志级别实现
更新 v3.3.8：2016 年 8 月 12 日
- 修复了搜索词的 bug
- 分词器能够分割 a.b.c 单词和数字
更新 v4.0.7：2019 年 2 月 25 日
- 与 RaptorDB v4.0.7 同步
- 现在使用 MGRB 位图索引而不是 WAH，以获得更好的内存使用
- * 索引文件存在破坏性更改，请删除并重新索引 *