当遇到“文本搜索”这个词时,“人们通常会想到大量的文本，这些文本的索引方式使得当用户输入一个或多个搜索词时，可以快速查找到它们. 这是一个典型的问题 计算机科学家，有许多解决办法.

但如果是相反的情况呢? 如果事先可用于索引的是一组搜索短语呢, 只有在运行时才会显示大量文本以供搜索? 这些问题正是本单词查找树数据结构教程试图解决的问题.

应用程序

此场景的实际应用程序是将许多医学论文与医疗条件列表进行匹配，并找出哪些论文讨论了哪些条件. 另一个例子是遍历大量的司法判例并提取它们所引用的法律.

直接的方法

最基本的方法是遍历搜索短语, 然后在文本中搜索每个短语, 一个接一个. 这种方法不能很好地扩展. 在另一个字符串中搜索字符串比较复杂 O(n). 重复这个过程 m 搜索短语会导致糟糕的结果 O(m * n).

直接方法的(可能唯一的)优点是它易于实现, 如下面的c#代码片段所示:

String[] search_phrases =文件.ReadAllLines(“条款.txt”);
字符串text_body =文件.ReadAllText(“身体.txt”);

Int count = 0;
foreach (search_phrases中的字符串短语)
    如果(text_body.IndexOf (phrase) >= 0)
        + +计数;

在我的开发机器上运行此代码 [1] 对照测试样本 [2], 我得到了1小时14分钟的运行时间——远远超过了你喝杯咖啡所需的时间, 站起来伸展一下身体, 或者其他开发者用来逃避工作的借口.

一个更好的方法——Trie

可以通过几种方式增强前面的场景. 例如，搜索过程可以在多个处理器/内核上进行分区和并行化. 但是，通过这种方法减少的运行时间(假设4个处理器/核心的完全分割，总运行时间为20分钟)并不能证明增加编码/调试的复杂性是合理的.

最好的解决方案是只遍历文本主体一次. 这要求在一个可以线性横向的结构中对搜索短语进行索引, 与正文平行, 一次, 达到最终的复杂性 O(n).

特别适合此场景的数据结构是 单词查找树. 当涉及到搜索问题时，这种通用的数据结构通常被忽视，也不像其他与树相关的结构那样出名.

Toptal之前的教程 很好地介绍了它们的结构和使用方式. 简而言之, 树是一种特殊的树, 能够以这样一种方式存储值序列，即跟踪从根到任何节点的路径产生该序列的有效子集.

So, 如果我们能把所有的搜索词组组合成一个树, 每个节点包含一个单词, 我们将把短语放在一个结构中，简单地从词根向下追溯, 通过任何路径, 产生一个有效的搜索短语.

单词查找树的优点是它显著地缩短了搜索时间. 为了便于本教程的理解，让我们想象一个二叉树. 遍历二叉树的复杂度为 O (log2n)，因为每个节点分成两个分支，将剩余的遍历分成两半. 因此，三叉树的遍历复杂度为 O (log3n). 在一个尝试中, 然而, 子节点的数量由它所表示的序列决定, 在可读/有意义的文本的情况下, 孩子的数量通常很高.

文本搜索算法

作为一个简单的例子，让我们假设以下搜索短语:

• “同一家族”
• “不同的家庭”
• “独立存在”
• “联盟成员”

记住，我们事先知道我们的搜索短语. 那么，我们从建立一个索引开始，以一个单词查找树的形式:

稍后，我们软件的用户向它提供一个包含以下文本的文件:

欧洲语言是同一家族的成员. 他们的独立存在是一个神话.

剩下的很简单. 我们的算法将有两个指示器(指针), 如果你愿意的话), 一个从根开始, 或者是树结构中的“开始”节点, 另一个在正文的第一个单词. 这两个指标一个字一个字地同步前进. 文本指示符只是向前移动, 而单词查找树指示符则按深度遍历该单词查找树, 跟随一系列匹配的单词.

单词查找树指示器在两种情况下返回开始:当它到达分支的末端时, 这意味着找到了一个搜索短语, 或者遇到不匹配的单词, 这样的话就找不到匹配的了.

文本指示符移动的一个例外是当找到部分匹配时.e. 在一系列匹配之后，在分支结束之前遇到一个不匹配. 在这种情况下，文本指示符不会向前移动, 因为最后一个词可能是一个新分支的开始.

让我们将这个算法应用到我们的单词查找树数据结构示例中，看看它是如何运行的:

如我们所见，系统成功地找到了两个匹配的短语， “同一家族” 和 “独立存在”.

现实的例子

最近的一个项目, 我遇到了这样一个问题:一个客户有大量与她的工作领域相关的文章和博士论文, 并且生成了她自己的短语列表，这些短语代表与同一工作领域相关的特定头衔和规则.

她的困境是这样的:给定她的短语列表, 她是如何把文章/论文和那些短语联系起来的? 最终目标是能够随机选择一组短语，并立即有一个提到这些特定短语的文章/论文列表.

如前所述, 有两个部分可以解决这个问题:将短语索引到一个单词查找树中, 而实际的搜索. 下面几节提供了c#中的一个简单实现. 请注意文件处理, 编码问题, 在这些代码片段中不处理文本清理和类似的问题, 因为它们超出了本文的范围.

索引

索引操作只是逐个遍历短语，并将它们插入到树中, 每个节点/级别一个单词. 节点用下面的类表示:

类节点
{
    int PhraseId = -1;
    Dictionary 孩子们 = new Dictionary();

    public Node() {}
    公共节点(int id)
    {
        PhraseId = id;
    }
}

每个短语由一个ID表示, 哪个可以像增量数一样简单, 并传递给以下索引函数(变量root是单词查找树的实际根):

void addPhrase(ref Node root, String phrase, int phraseId)
{
    //一个指针遍历树而不损坏
    //原始引用
    Node = root;

    //将短语分成单词
    String[] words = phrase.Split ();

    //从根节点开始遍历
    for (int i = 0; i < words.Length; ++i)
    {
        //如果当前单词不作为子单词存在
        //添加到当前节点
        如果(节点.孩子们.ContainsKey(words[i]) == false)
            节点.孩子们.Add(words[i]， new Node());

        //移动遍历指针到当前单词
        节点=节点.孩子们[字[我]];

        //如果当前单词是最后一个，用
        //短语Id
        If (i == words.长度- 1)
            节点.PhraseId = PhraseId;
    }
}

搜索

搜索过程是上面教程中讨论的单词查找树算法的直接实现:

无效findPhrases(ref Node root, String textBody)
{
    //一个指针遍历树而不损坏
    //原始引用
    Node = root;

    //找到的id列表
    List foundPhrases = new List();

    //将文本主体分解为单词
    String[] words = textBody.Split ();

    //从树的根开始遍历
    //文本主体中的单词
    for (int i = 0; i < words.长度。)
    {
        //如果当前节点有当前字作为子节点
        //将节点和单词指针都向前移动
        如果(节点.孩子们.ContainsKey(话说[我]))
        {
            //将指针向前移动
            节点=节点.孩子们[字[我]];

            //向前移动单词指针
            ++i;
        }
        其他的
        {
            //当前节点没有current
            //在它的子字符

            //如果有一个短语Id，则前面的
            //与短语匹配的单词序列，将Id添加到
            //查找列表
            如果(节点.PhraseId != -1)
                foundPhrases.Add(节点.PhraseId);


            If (节点 == root)
            {
                //如果单词查找树指针已经在根，则自增
                //单词指针
                ++i;
            }
            其他的
            {
                //如果不是，则将words指针保留在当前单词处
                //返回指向根节点的树指针
                节点=根;
            }
                
        }
    }

    //剩下一个case, word指针到达结束
    //循环结束，但单词查找树指针指向
    //一个短语Id
    如果(节点.PhraseId != -1)
        foundPhrases.Add(节点.PhraseId);
}

表演。

这里提供的代码是从实际项目中提取出来的，并且为了本文的目的而进行了简化. 在同一台机器上再次运行此代码 [1] 而且是针对相同的测试样本 [2] 导致运行时间为2.构建单词查找树的时间是5秒，0秒.3秒搜索时间. 休息时间到此为止吧?

变化

重要的是要认识到，本教程中描述的算法在某些边缘情况下可能会失败, 因此，在设计时已经考虑了预定义的搜索项.

例如, 如果一个搜索词的开头与另一个搜索词的某些部分相同, 如:

• “分享 和朋友们一起享受吧!”
• “我有两张票 分享 与某人”

文本主体包含一个短语，导致单词查找树指针从错误的路径开始, 如:

我有两张票可以和朋友们一起分享.

那么算法将无法匹配任何项, 因为在文本指示符已经通过文本主体中匹配项的开头之前，单词查找树指示符不会返回到开始节点.

在实现算法之前，考虑应用程序是否可能出现这种边缘情况是很重要的. 如果是这样的话, 该算法可以使用额外的单词查找树指标进行修改，以在任何给定时间跟踪所有匹配, 而不是一次只抽一根火柴.

结论

Text search is a deep field in computer science; a field rich with problems 和 solutions alike. 我必须处理的这种数据(23MB的文本在现实生活中相当于一吨的书)可能看起来很罕见，或者是一个专门的问题, 但是从事语言学研究的开发人员, 存档, 或任何其他类型的数据操作, 在常规的基础上遇到大量的数据.

正如上面的单词查找树数据结构教程所示, 为手头的问题仔细选择正确的算法是非常重要的. 在这种特殊情况下，单词查找树方法将运行时间缩短了惊人的99.93%，从一个多小时缩短到不到3秒.

这绝不是唯一有效的方法，但它足够简单，而且有效. 我希望你觉得这个算法很有趣, 祝你在编程过程中好运.

---

[1] 本次试验使用的机器规格如下:

• 英特尔i7 4700HQ
• 16 gb的RAM

测试是在Windows 8上进行的.1使用 .净4.5.1和Kubuntu 14.04使用最新版本的mono和结果非常相似.

[2] 测试样本由280K个搜索短语组成，总大小为23.5MB，文本主体为1.5MB.