大海捞针：一个漂亮的大规模文本搜索算法教程

本文概述

• 应用领域
• 直接进场
• 更好的方法-Trie
• 文字搜寻算法
• 真实的例子
• 变化
• 总结

当遇到术语”文本搜索”时, 通常会想到大量的文本, 这些文本的索引方式使用户在输入一个或多个搜索词时可以快速查找它们。对于计算机科学家来说, 这是一个经典的问题, 存在许多解决方案。

但是相反的情况呢？如果预先可以建立索引的是一组搜索词组, 并且只有在运行时才显示大量文本进行搜索, 该怎么办？这些问题是本Trie数据结构教程试图解决的问题。

应用领域

这种情况的实际应用是将许多医学论文与一系列医学状况进行匹配, 并找出哪些医学论文讨论了哪些疾病。另一个例子是遍历大量司法判例并提取其所引用的法律。

直接进场

最基本的方法是遍历搜索短语, 并逐个单词地搜索文本。这种方法无法很好地扩展。在另一个内部搜索字符串的复杂度为O(n)。对m个搜索短语重复该操作会导致可怕的O(m * n)。

易于实现的直接方法的(可能)唯一优点, 如以下C＃片段所示：

String[] search_phrases = File.ReadAllLines ("terms.txt");
String text_body = File.ReadAllText("body.txt");

int count = 0;
foreach (String phrase in search_phrases)
    if (text_body.IndexOf (phrase) >= 0)
        ++count;

在开发计算机[1]上针对测试样本[2]运行此代码, 我的运行时间为1小时14分钟-远远超出了你需要喝杯咖啡, 起身伸展运动或其他任何借口的时间开发人员用来跳过工作。

更好的方法-Trie

可以通过两种方式增强以前的方案。例如, 搜索过程可以在多个处理器/内核上进行分区和并行化。但是, 通过这种方法实现的运行时间减少(假设在4个处理器/内核上进行完美划分, 则总运行时间为20分钟)并不能证明增加编码/调试的复杂性是合理的。

最好的解决方案是仅遍历文本主体一次的解决方案。这就要求将搜索短语索引为一种结构, 该结构可以与文本主体平行地线性地横向横切, 从而获得最终复杂度O(n)。

特里就是这种情况特别适合的数据结构。当涉及到搜索问题时, 通常会忽略这种通用的数据结构, 而不像其他与树相关的结构那样著名。

托普塔尔(srcmini)的上一本关于尝试的教程, 很好地介绍了它们的结构和使用方式。简而言之, 特里树是一棵特殊的树, 它能够以如下方式存储值的序列：从根到任何节点的路径跟踪都会产生该序列的有效子集。

因此, 如果我们可以将所有搜索短语组合成一个树, 每个节点都包含一个单词, 那么我们将把这些短语布置在一个结构中, 该结构只需从根向下通过任何路径向下跟踪就可以生成一个有效的搜索短语。

特里的优点是可以大大减少搜索时间。为了简化本教程的学习, 让我们想象一下一个二叉树。遍历二叉树的复杂度为O(log2n), 因为每个节点都分支为两个, 从而将剩余遍历减半。这样, 三叉树的遍历复杂度为O(log3n)。但是, 在特里树中, 子节点的数目由其表示的顺序决定, 在可读/有意义的文本的情况下, 子节点的数目通常很高。

文字搜寻算法

举一个简单的例子, 假设以下搜索词：

• “同一个家庭”
• “异族”
• “分开存在”
• “联盟成员”

请记住, 我们事先知道我们的搜索短语。因此, 我们首先以特里形式创建索引：

后来, 我们的软件的用户向其提供了一个包含以下文本的文件：

欧洲语言是同一家族的成员。他们分开存在是一个神话。

其余的很简单。我们的算法将有两个指示符(如果需要, 可以指向指针), 一个指示符从trie结构的根或”开始”节点开始, 另一个指示符在文本正文中的第一个单词处。这两个指标逐字一起移动。文本指示器仅向前移动, 而特里指示器则沿着匹配单词的轨迹深度遍历特里。

trie指示器在两种情况下返回开始：当它到达分支的末尾时, 这意味着找到了搜索短语, 或者当它遇到不匹配的单词时, 在这种情况下, 没有找到匹配项。

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

让我们将此算法应用于我们的trie数据结构示例, 看看它如何进行：

如我们所见, 系统成功找到了两个匹配的短语”同一个家庭”和”分别存在”。

真实的例子

对于一个最近的项目, 我面临以下问题：一个客户拥有大量与其工作领域相关的文章和博士学位论文, 并生成了自己的短语列表, 这些短语表示与该领域相同的特定标题和规则。工作。

她的困境是：给定短语列表, 她如何将文章/主题链接到这些短语？最终目标是能够随机选择一组短语, 并立即准备一列提及这些特定短语的文章/主题, 以备取用。

如前所述, 解决此问题有两个部分：将短语索引成特里索引和实际搜索。以下各节提供了C＃的简单实现。请注意, 这些代码段未处理文件处理, 编码问题, 文本清理和类似问题, 因为它们不在本文讨论范围之内。

索引编制

索引操作只是简单地一遍遍短语, 然后将它们插入到trie中, 每个节点/级别一个单词。节点用以下类表示：

class Node
{
    int PhraseId = -1;
    Dictionary<String, Node> Children = new Dictionary<String, Node>();

    public Node() { }
    public Node(int id)
    {
        PhraseId = id;
    }
}

每个短语都由一个ID表示, 该ID可以像一个递增数字一样简单, 并传递给以下索引函数(可变根是trie的实际根)：

void addPhrase(ref Node root, String phrase, int phraseId)
{
    // a pointer to traverse the trie without damaging
    // the original reference
    Node node = root;

    // break phrase into words
    String[] words = phrase.Split ();

    // start traversal at root
    for (int i = 0; i < words.Length; ++i)
    {
        // if the current word does not exist as a child
        // to current node, add it
        if (node.Children.ContainsKey(words[i]) == false)
            node.Children.Add(words[i], new Node());

        // move traversal pointer to current word
        node = node.Children[words[i]];

        // if current word is the last one, mark it with
        // phrase Id
        if (i == words.Length - 1)
            node.PhraseId = phraseId;
    }
}

正在搜寻

搜索过程是上面教程中讨论的trie算法的直接实现：

void findPhrases(ref Node root, String textBody)
{
    // a pointer to traverse the trie without damaging
    // the original reference
    Node node = root;

    // a list of found ids
    List<int> foundPhrases = new List<int>();

    // break text body into words
    String[] words = textBody.Split ();

    // starting traversal at trie root and first
    // word in text body
    for (int i = 0; i < words.Length;)
    {
        // if current node has current word as a child
        // move both node and words pointer forward
        if (node.Children.ContainsKey(words[i]))
        {
            // move trie pointer forward
            node = node.Children[words[i]];

            // move words pointer forward
            ++i;
        }
        else
        {
            // current node does not have current
            // word in its children

            // if there is a phrase Id, then the previous
            // sequence of words matched a phrase, add Id to
            // found list
            if (node.PhraseId != -1)
                foundPhrases.Add(node.PhraseId);


            if (node == root)
            {
                // if trie pointer is already at root, increment
                // words pointer
                ++i;
            }
            else
            {
                // if not, leave words pointer at current word
                // and return trie pointer to root
                node = root;
            }
                
        }
    }

    // one case remains, word pointer as reached the end
    // and the loop is over but the trie pointer is pointing to
    // a phrase Id
    if (node.PhraseId != -1)
        foundPhrases.Add(node.PhraseId);
}

性能

此处提供的代码是从实际项目中提取的, 并且出于本文档的目的已被简化。在同一台机器[1]上并在同一测试样本[2]上再次运行此代码, 导致构建Trie的运行时间为2.5秒, 而搜索为0.3秒。这么多的休息时间, 是吗？

变化

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

例如, 如果一个搜索词的开头与另一个搜索词的某个部分相同, 则如下所示：

• “与朋友分享和享受”
• “我有两张票可以和某人分享”

并且文本正文中包含一个短语, 该短语使trie指针从错误的路径开始, 例如：

我有两张票可以和朋友分享和享受。

那么该算法将无法匹配任何术语, 因为在文本指示器已通过文本主体中匹配术语的开始之前, 特里指示符不会返回到起始节点。

在实施算法之前, 请考虑一下这种边缘情况是否对你的应用程序很重要。如果是这样, 则可以使用附加的trie指示符对算法进行修改, 以在任何给定时间跟踪所有匹配, 而不是一次仅跟踪一个匹配。

总结

文本搜索是计算机科学的一个深层领域。一个充满问题和解决方案的领域。我必须处理的数据类型(23MB的文本是现实生活中的大量书籍)可能看起来很少见, 也可能是一个特殊的问题, 但是从事语言学研究, 归档或任何其他类型的数据处理的开发人员定期查看大量数据。

从上面的trie数据结构教程中可以明显看出, 针对当前问题精心选择正确的算法非常重要。在这种情况下, 特里方法将运行时间从一个多小时减少到不到3秒, 减少了99.93％。

这绝不是唯一有效的方法, 但它足够简单, 并且行得通。我希望你发现此算法很有趣, 并祝你在编码工作中一切顺利。

[1]用于此测试的机器具有以下规格：

• 英特尔i7 4700HQ
• 16GB RAM

使用.NET 4.5.1在Windows 8.1上以及在最新版本的mono上的Kubuntu 14.04上进行了测试, 结果非常相似。

[2]测试样本包含280K个搜索短语, 总大小为23.5MB, 文本正文为1.5MB。