性能利器,Python Flashtext 实现查找或替换文本中关键词

通常,我们使用Python 在文本中进行关键词查找或替换时,会使用 re 模块以正则的形式实现。在文本数量、文本内容、关键词数量较小时,该方法能

性能利器,Python Flashtext 实现查找或替换文本中关键词

通常,我们使用Python 在文本中进行关键词查找或替换时,会使用 re 模块以正则的形式实现。在文本数量、文本内容、关键词数量较小时,该方法能够满足我们程序的功能、性能需要。但当在大规模的文本或者对大量关键词语料查找或者替换,re 实现方案的性能将成为瓶颈,本文我们将介绍一种新的关键词搜索和替换的算法:Flashtext 算法,它是一个高效的字符搜索和替换算法。

有多高效呢?如下,是通过随机生方式生成10000个单词组成的文本,我们分别在该文本中查找由 0, 500, 1000, 5000, 10000, 50000, 100000, 200000, 400000 个关键词组成的关键词库,我们来感受一下两者的性能差异:

性能利器,Python Flashtext 实现查找或替换文本中关键词

我们发现随着关键词查询数量的增加,Flashtext 与 re 的时间消耗存在百倍乃至千倍以上的差异 。

为何存在这么大的差异呢?Flashtext 算法的时间复杂度不依赖于查找或替换的字符的数量。如,对于一个文档有 N 个字符,和一个有 M 个词的关键词库,那么时间复杂度就是 O(N) 。而正则匹配的时间复杂度是 O(M * N) 。这也是两者在性能上的差异随着关键词数量增多而拉大的原因。

因此,在一些大数据下的内容检索和替换,我们更倾向于选择 Flashtext 算法 ,比如,自然语言处理领域中数据清洗是一项必须的操作。经常涉及使用标准的关键词替换一些非标准的词,如,将Javascript替换成JavaScript。或者我们需要判断文本中是否存在JavaScript 关键词等等。

接下来,就让我们了解一下,如何使用Flashtext 实现关键词的查找和替换。


FlashText

Flashtext 算法主要分为三部分,我们接下来将对每一部分进行单独分析:

  1. 构建 Trie 字典
  2. 关键词搜索
  3. 关键词替换

构建 Trie 字典 (这部分不理解不影响我们使用Flashtext

Flashtext 是一种基于 Trie 字典数据结构和 Aho Corasick 的算法。它的工作方式是,首先它将所有相关的关键词作为输入,使用这些关键词建立一个 trie 字典。

为了构建 trie 字典,Flashtext 创建一个空的节点指向空字典。这个节点被用作所有关键词的起点。我们在字典中插入一个关键词。这个关键词中的下一个字符在本字典中作为关键词,并且这个指针需要再次指向一个空字典。这个过程不断重复,直到我们达到单词中的最后一个字符。当我们到达单词的末尾时,我们插入一个特殊的字符(eot)来表示词尾,如下:

性能利器,Python Flashtext 实现查找或替换文本中关键词

starteot 是两个特殊的字符,用来定义关键词的边界,因此,也可知 Flashtext 只匹配完整的单词,这个 trie 字典就是我们后面要用来搜索和替换的数据结构。

我们举一个简单的例子,假设我们有一个包含3个单词的句子 “I like Python”,和一个有4个关键词的语料库 corpus = [Python,Java,J2ee,Ruby]。

Flashtext 算法将对于句子中的每一个单词,检查其是否在语料库中出现,如下:

性能利器,Python Flashtext 实现查找或替换文本中关键词

如果句子 N 个单词,意味着需要做 N 次的循环操作。在这个例子中所需的时间步取决于句子中的单词数。

如上,因为将文本中的每个字符串进行匹配,由于这是一个字符匹配过程,因为 start 并没有和 l 相连,因此可以快速的跳过的I、like的匹配,这使得跳过缺失单词的过程变得非常快。

因此,FlashText 算法不受 corpus 中关键词数量的影响。


使用 Flashtext 进行搜索

我们对输入文本中的字符进行逐个遍历,当我们在文档中的字符 word 匹配到字典中的 <start>word<eot> 时,则认为这是一个完整匹配。我们将匹配到的字符序列所对应的标准关键词进行输出,具体如下:

性能利器,Python Flashtext 实现查找或替换文本中关键词

代码示例如下:

性能利器,Python Flashtext 实现查找或替换文本中关键词


使用 Flashtext 进行替换

Flashtext 对输入文本中的字符进行逐个遍历,Flashtext 先创建一个空的字符串,当字符序列中的 word 无法在 Trie 字典中找到匹配时,那么Flashtext 就简单的原始字符复制到返回字符串中。但当Flashtext 可以从 Trie 字典中找到匹配时,那么Flashtext 将把匹配到的字符的标准字符复制到返回字符串中。因此,返回字符串是输入字符串的一个副本,唯一的不同是替换了匹配到的字符序列,具体如下:

性能利器,Python Flashtext 实现查找或替换文本中关键词

代码示例如下:

性能利器,Python Flashtext 实现查找或替换文本中关键词


性能比对

在本文开始,我们首先介绍了使用 re模块与 flashtext 模块在不同数量的关键词语料库下,两者的耗时情况差异,具体性能比对实现的源码如下:

性能利器,Python Flashtext 实现查找或替换文本中关键词

性能利器,Python Flashtext 实现查找或替换文本中关键词

输出结果:

性能利器,Python Flashtext 实现查找或替换文本中关键词


Flashtext 常用方法及参数说明

add_keyword

添加关键词。

语法

性能利器,Python Flashtext 实现查找或替换文本中关键词

参数

  • keyword:检索的词。
  • clean_name:显示或要被替换为的词(默认keywords本身),如果匹配到keyword,则会返回clean_name。

示例

性能利器,Python Flashtext 实现查找或替换文本中关键词


add_keywords_from_dict

添加多个关键词。

语法

性能利器,Python Flashtext 实现查找或替换文本中关键词

参数

  • keyword_dict:其中 key 类似于clean_name,value类似于keyword ,如果匹配到value,则会返回key。

示例

性能利器,Python Flashtext 实现查找或替换文本中关键词


add_keywords_from_list

添加多个关键词。

语法

性能利器,Python Flashtext 实现查找或替换文本中关键词

参数

  • keyword_list:要添加的关键词列表

示例

性能利器,Python Flashtext 实现查找或替换文本中关键词


remove_keyword

删除关键词。

语法

性能利器,Python Flashtext 实现查找或替换文本中关键词

参数

  • keyword:删除的关键词。

示例

性能利器,Python Flashtext 实现查找或替换文本中关键词


remove_keywords_from_list

删除多个关键词。

语法

性能利器,Python Flashtext 实现查找或替换文本中关键词

参数

  • keyword_list:要删除的关键词列表

示例

性能利器,Python Flashtext 实现查找或替换文本中关键词


remove_keywords_from_dict

删除多个关键词。

语法

性能利器,Python Flashtext 实现查找或替换文本中关键词

参数

  • keyword_list:其中 key 类似于clean_name,value类似于keyword 。

示例

性能利器,Python Flashtext 实现查找或替换文本中关键词


免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/43127.html

(0)
上一篇 2024-04-18 19:26
下一篇 2024-04-19 12:00

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信