作者都是各自领域经过审查的专家,并撰写他们有经验的主题. 我们所有的内容都经过同行评审,并由同一领域的Toptal专家验证.
当遇到“文本搜索”这个词时,“人们通常会想到大量的文本,这些文本的索引方式使得当用户输入一个或多个搜索词时,可以快速查找到它们. 这是一个典型的问题 计算机科学家,有许多解决办法.
但如果是相反的情况呢? 如果事先可用于索引的是一组搜索短语呢, 只有在运行时才会显示大量文本以供搜索? 这些问题正是本单词查找树数据结构教程试图解决的问题.
此场景的实际应用程序是将许多医学论文与医疗条件列表进行匹配,并找出哪些论文讨论了哪些条件. 另一个例子是遍历大量的司法判例并提取它们所引用的法律.
最基本的方法是遍历搜索短语, 然后在文本中搜索每个短语, 一个接一个. 这种方法不能很好地扩展. 在另一个字符串中搜索字符串比较复杂 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分钟的运行时间——远远超过了你喝杯咖啡所需的时间, 站起来伸展一下身体, 或者其他开发者用来逃避工作的借口.
可以通过几种方式增强前面的场景. 例如,搜索过程可以在多个处理器/内核上进行分区和并行化. 但是,通过这种方法减少的运行时间(假设4个处理器/核心的完全分割,总运行时间为20分钟)并不能证明增加编码/调试的复杂性是合理的.
最好的解决方案是只遍历文本主体一次. 这要求在一个可以线性横向的结构中对搜索短语进行索引, 与正文平行, 一次, 达到最终的复杂性 O(n).
特别适合此场景的数据结构是 单词查找树. 当涉及到搜索问题时,这种通用的数据结构通常被忽视,也不像其他与树相关的结构那样出名.
Toptal之前的教程 很好地介绍了它们的结构和使用方式. 简而言之, 树是一种特殊的树, 能够以这样一种方式存储值序列,即跟踪从根到任何节点的路径产生该序列的有效子集.
So, 如果我们能把所有的搜索词组组合成一个树, 每个节点包含一个单词, 我们将把短语放在一个结构中,简单地从词根向下追溯, 通过任何路径, 产生一个有效的搜索短语.
单词查找树的优点是它显著地缩短了搜索时间. 为了便于本教程的理解,让我们想象一个二叉树. 遍历二叉树的复杂度为 O (log2n),因为每个节点分成两个分支,将剩余的遍历分成两半. 因此,三叉树的遍历复杂度为 O (log3n). 在一个尝试中, 然而, 子节点的数量由它所表示的序列决定, 在可读/有意义的文本的情况下, 孩子的数量通常很高.
作为一个简单的例子,让我们假设以下搜索短语:
记住,我们事先知道我们的搜索短语. 那么,我们从建立一个索引开始,以一个单词查找树的形式:
稍后,我们软件的用户向它提供一个包含以下文本的文件:
欧洲语言是同一家族的成员. 他们的独立存在是一个神话.
剩下的很简单. 我们的算法将有两个指示器(指针), 如果你愿意的话), 一个从根开始, 或者是树结构中的“开始”节点, 另一个在正文的第一个单词. 这两个指标一个字一个字地同步前进. 文本指示符只是向前移动, 而单词查找树指示符则按深度遍历该单词查找树, 跟随一系列匹配的单词.
单词查找树指示器在两种情况下返回开始:当它到达分支的末端时, 这意味着找到了一个搜索短语, 或者遇到不匹配的单词, 这样的话就找不到匹配的了.
文本指示符移动的一个例外是当找到部分匹配时.e. 在一系列匹配之后,在分支结束之前遇到一个不匹配. 在这种情况下,文本指示符不会向前移动, 因为最后一个词可能是一个新分支的开始.
让我们将这个算法应用到我们的单词查找树数据结构示例中,看看它是如何运行的:
一步 | 特里结构指标 | 文本指示器 | 匹配? | 单词查找树行动 | 文本操作 |
---|---|---|---|---|---|
0 | 开始 | 的 | - | 搬到 开始 | 转到下一个 |
1 | 开始 | 欧洲 | - | 搬到 开始 | 转到下一个 |
2 | 开始 | 语言 | - | 搬到 开始 | 转到下一个 |
3 | 开始 | 是 | - | 搬到 开始 | 转到下一个 |
4 | 开始 | 成员 | 成员 | 搬到 成员 | 转到下一个 |
5 | 成员 | of | of | 搬到 of | 转到下一个 |
6 | of | 的 | 的 | 搬到 的 | 转到下一个 |
7 | 的 | 相同 | - | 搬到 开始 | - |
8 | 开始 | 相同 | 相同 | 搬到 相同 | 转到下一个 |
9 | 相同 | 家庭 | 家庭 | 搬到 开始 | 转到下一个 |
10 | 开始 | 他们的 | - | 搬到 开始 | 转到下一个 |
11 | 开始 | 单独的 | 单独的 | 搬到 单独的 | 转到下一个 |
12 | 单独的 | 存在 | 存在 | 搬到 开始 | 转到下一个 |
13 | 开始 | is | - | 搬到 开始 | 转到下一个 |
14 | 开始 | a | - | 搬到 开始 | 转到下一个 |
15 | 开始 | 神话 | - | 搬到 开始 | 转到下一个 |
如我们所见,系统成功地找到了两个匹配的短语, “同一家族” 和 “独立存在”.
最近的一个项目, 我遇到了这样一个问题:一个客户有大量与她的工作领域相关的文章和博士论文, 并且生成了她自己的短语列表,这些短语代表与同一工作领域相关的特定头衔和规则.
她的困境是这样的:给定她的短语列表, 她是如何把文章/论文和那些短语联系起来的? 最终目标是能够随机选择一组短语,并立即有一个提到这些特定短语的文章/论文列表.
如前所述, 有两个部分可以解决这个问题:将短语索引到一个单词查找树中, 而实际的搜索. 下面几节提供了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秒.
这绝不是唯一有效的方法,但它足够简单,而且有效. 我希望你觉得这个算法很有趣, 祝你在编程过程中好运.
测试是在Windows 8上进行的.1使用 .净4.5.1和Kubuntu 14.04使用最新版本的mono和结果非常相似.
世界级的文章,每周发一次.
世界级的文章,每周发一次.