按比例替换或检索文档中的关键词

来源：arXiv

作者：Vikash Singh

编辑：智察（ID：Infi-inspection）

文章字数：2553 预计阅读用时：3分钟

摘要

本文我们介绍了一种可以在已给文本中替换或寻找关键词的算法FlashText。FlashText可以搜索或替换一份文档中的关键词。这个算法的时间复杂度不依赖于搜索或替换的词汇数量。对于大小为N（字符）的文档和M关键词集，时间复杂度为。由于正则表达式的时间复杂度为，所以这个算法向比于Regex（见图1&2）更快。由于它也不与子字符串相匹配，所以它也不同于Aho Corasick算法。

FlashText只是被设计用来匹配完整单词（两边都有边界字符的单词）。对于一个输入集，该算法不会将它匹配到“I like Pineapple”。最初设计这个算法是为了进行最长匹配。对于输入集在句子“I like Machine learning”进行查询，他只会对最长的匹配，即对“Machine learning”进行匹配。在开放的MIT许可下，我们已经将这个算法的python实现作为开源代码放在GitHub上。

项目数据结构和算法（cs.DS）

关键词信息检索，关键词搜索，正则化，关键词替换，FlashText

1、 简介

在信息检索领域中，关键词搜索和替换是一个长期问题。通常我们是想发现文本中的特殊关键词或使用标准化的名字来替换关键词。

例如：

关键词搜索：我们有一个软件工程的摘要（D）和一个20K的编程技能列表corpus=。我们想要在摘要中发现这20K的列表中哪些在摘要中（corpus∩D）。

关键词替换：另一个常用惯例是当我们使用像corpus=一样的同义词语料库时我们也想使用标准名字代替摘要中的同义词。

我们通常使用正则表达式来解决这些问题。虽然正则化在数量为上百数量级以内是工作情况良好，但在数量上千的情况下来说就会非常慢。当词汇的数量级为上万，而文件的数量为数百万时，运行时间将达到几天。如图1所示，Regex在10K词汇文档中找到15K关键词所花费的时间应该有0.165秒。鉴于FlashText只花费0.002秒，所以对于15K的词汇量FlashText比Regex快82倍。

随着词汇量的提升，Regex所花费的时间会线性上升。而FlashText所花费的时间是一个常数，本文我们会讨论基于搜索和替换的Regex并将其与FlashText相比较。我们也会详细介绍FlashText算法及其工作原理并共享用于对FlashText进行基于Regex的基准测试的代码。（其在本文是用来生成图片）。

1.1、 针对关键词搜索的Regex

Regex是一种在模式匹配中非常通用和有效的工具。我们可以搜索像‘\d’的模式（其可以与任何四位数相匹配），或是在文本文档中像‘2017’这样的关键词，使用示例python代码（代码1）来搜索已给字符串中关键词“2017”或任何四位数。

代码1：在Regex中使用简单Python代码来搜索已给字符串中的2017和任意四位数。

图1：比较Regex和FlashText发现不同词汇量（x轴）所花费的时间（y轴）

这里‘\b’是用来表示词边界，并将23114不会返回2311作为一组匹配。在Regex（‘\b’）中词边界是通过特殊字符比如‘space’，‘period’，‘new line’等等来进行匹配。

1.2、 针对关键词替换的Regex

我们也可以使用Regex工具来使用标准词汇替换匹配词汇。示例Python代码（代码2）用于使用javascript替换java script。

代码2：在Regex中的使用示例Python代码用于使用javascript替换javascript

图2：比较Regex和FlashText替换不同词汇量（x轴）所花费的时间（y轴）

2、 FLASHTEXT

FlashText是一个基于Trie词典数据结构并受Aho Corasick算法启发的算法。其工作原理是：首先将所有相关关键词作为输入。使用这些关键词构建了一个trie词典(如图3所示)。

图3：包含两个关键字的Trie词典，J2ee和java都映射到标准词汇java。

Start和eot是两个像Regex中定义的那样，用于定义词边界的特殊符号。这个trie词典既可以用来搜索也可以用于替换字符串中的关键词。

2.1、 FlashText中的搜索

对于一个输入字符串（文档），我们逐字符迭代它。当文档word中的字符序列匹配到word中的trie词典（Start和eot均代表词边界），我们将它认定为完整匹配。我们将对应于匹配词汇的标准化词汇添加到已发现的关键词列表中。

输入字符串：My project is written inJ2ee

关键词发现：Java

图4：匹配到字符序列的输入字符串显示成绿色，没有匹配到的显示成红色

2.2、 FlashText中的替换

对于一个输入字符串（文档），我们逐字符迭代它。我们构造一个空的反馈字符串，当文档word中的字符序列无法匹配到trie词典时我们在反馈字符串中复制原始词。所以反馈字符串是输入字符串的复制，只有匹配的词被替换。

输入字符串：My project is written inJ2ee

关键词发现：Java

替换字符串：My project is written in java

图5：输入字符串匹配的字符序列被替换为标准化的名称。

2.3、 FlashText算法

FlashText有三个主要部分，我们将分别讨论每一部分。

1.构造trie词典

2. 搜索关键词

3. 替换关键词

2.3.1、 构造trie词典

为了构造trie词典，我们从一个指向一个empty_dictionary的root节点开始。此节点用作所有词的起始点。我们通过将第一个字符插入到root节点来将一个词插入到词典中并将其指向空词典。词中的下一个字符，会作为这个词典中的一个键，并也指向一个空词典。这个过程会被重复，直到我们到达词中的最后一个字符为止。如果词典中已经存在字符，我们将移到子词典和词中下一个字符中。当达到词的末尾我们会插入一个特殊的键_keyword_来表示词汇的结尾（eot），并将标准化的名称存储在这个键上。

输入

关键词，是输入字符是输入关键词。

标准化名称对应关键词。

方法

代码3:用于FlashText初始化并向词典中添加关键词的Python代码。

输出构造出与图3相像的词典。

2.3.2、 关键词搜索

只要将关键词都添加到trie词典中，我们就可以在一个输入字符串中发现关键词。

输入

字符串其中每一个都是一个输入字符，是输入字符串。

方法

代码4：为得到出现在词典中的输入字符串中的关键词而编写的Python代码

输出类似于在图4的字符串x中发现的标准化名称列表

2.3.3、 替换关键词

我们可以用相同的trie词典来使用标准化名称替换出现在输入字符串中的关键词。

输入

字符串其中每一个都是一个输入字符，是输入字符串

方法

代码5：在输入字符串中使用词典中的标准化名称替换关键词的Python代码

输出在字符串x中带有替换后的标准化名称的新字符串，如图5所示。

3、 对FlashText和Regex进行基准测试

如图1图2所示，FlashText比Regex快得多，现在我们对二者进行基准比较。

3.1、 搜索关键词

我们使用Python代码来对关键词搜索功能进行基准测试。首先我们会随机生成10K随机长度的词的语料库，随后从列表中选择1K的词汇组合生成一个文档。

代码6：使用Python代码来对FlashText和Regex的关键词搜索功能进行基准测试。GitHub要点链接

关键词搜索功能基准测试的GitHub要点链接。

（https://gist.github.com/vi3k6i5/604eefd92866d081cfa19f862224e4a0）

3.2、 关键词替换

对关键词替换功能进行基准测试的代码

代码7：对FlashText和Regex关键词替换进行基准测试的Python代码

Github Gist Link对关键词替换进行基准测试的代码。

（https://gist.github.com/vi3k6i5/dc3335ee46ab9f650b19885e8ade6c7a）

4、 总结

就像我们看到的一样，FlashText更快也更适合于关键词搜索/替换。当关键词完整的时候它要比Regex更快。算法的复杂性随文本长度呈线性变化。当关键字的数量很大时，这样做特别有用，因为所有的关键字都可以在输入字符串的一次传递中同时匹配。

（完）

转载声明

End.