Flashtext:大规模数据清洗的利器

在这篇文章中,我们将介绍一种新的关键字搜索和替换的算法:Flashtext 算法。Flashtext 算法是一个高效的字符搜索和替换算法。该算法的时间复杂度不依赖于搜索或替换的字符的数量。比如,对于一个文档有 N 个字符,和一个有 M 个词的关键词库,那么时间复杂度就是 O(N) 。这个算法比我们一般的正则匹配法快很多,因为正则匹配的时间复杂度是 O(M * N)。这个算法和 Aho Corasick 算法也有一点不同,因为它不匹配子字符串。

Flashtext 算法被设计为只匹配完整的单词。比如,我们输入一个单词 ,那么这个算法就不会去匹配 “I like Pineapple” 中的 apple。这个算法也被设计为首先匹配最长字符串。在举个例子,比如我们有这样一个数据集 ,一个文档 “I like Machine Learning”,那么我们的算法只会去匹配 “Machine Learning” ,因为这是最长匹配。

这个算法我们已经在 Github 上面实现了,用的是 Python 语言。

1. 介绍

在信息检索领域,关键字搜索和替代都是很常见的问题。我们经常想要在一个特定的文本中搜索特定的关键词,或者在文本中替代一个特定的关键词。

例如:

关键字搜索:假设我们有一个软件工程师的简历 (D),我们拥有一个 20k 的编程技巧词库corpus =。我们想要从这个词库 corpus 中哪些词在这个简历中出现了,即corpus ∩ D。

关键字替换:另一个常用的用例是当我们有一个同义词的语料库(不同的拼写表示的是同一个单词),比如corpus =,在软件工程师的简历中我们需要使用标准化的词,所有我们需要用一个标准化的词来替换不同简历中的同义词。

为了去解决上述这些问题,正则表达式是最常用的一个技术。虽然正则表达式可以很好的解决这个问题,但是当我们的数据量增大时,这个速度就会非常慢了。如果我们的文档达到百万级别时,那么这个运行时间将达到几天的量级。比如下面的图1,正则表达式在一个 10k 的词库中查找 15k 个关键词的时间差不多是 0.165 秒。但是对于 Flashtext 而言只需要 0.002 秒。因此,在这个问题上 Flashtext 的速度大约比正则表达式快 82 倍。

随着我们需要处理的字符越来越多,正则表达式的处理速度几乎都是线性增加的。然而,Flashtext 几乎是一个常量。在本文中,我们将着重讨论正则表达式与 Flashtext 之间的性能区别。我们还将详细的描述 Flashtext 算法及其工作原理,和一些基准测试。

1.1 用于关键字搜索的正则表达式

正则表达式是一种非常灵活和有用的模式匹配方式。比如我们在文本中搜索一个匹配 “\d”,它表示任何 4 位数字匹配,如 2017。我们利用 Python 代码可以实现这样一个功能,如下:

图1

这里 ‘\b’ 用来表示单词边界,它会去匹配特殊字符,如 'space','period','new line' 等。

1.2 用于关键字替换的正则表达式

我们也可以使用正则表达式来制作一个标准化术语的替换脚本,比如我们可以编写一个 Python 脚本来用 “javascript” 替换 “java script”。如下:

图2

2. Flashtext

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

图3:具有 2 个关键字的 Trie 字典,j2ee 和 java 都被映射到标准化的术语 java

start和eot是两个特殊的字符,用来定义词的边界,这和我们上面提到的正则表达式是一样的。这个 trie 字典就是我们后面要用来搜索和替换的数据结构。

2.1 利用 Flashtext 进行搜索

对于输入字符串(文档),我们对字符进行逐个遍历。当我们在文档中的字符序列 word 匹配到字典中的 word 时(start 和 eot 分别是字符序列的开始标签和结束标签),我们认为这是一个完整匹配了。我们将匹配到的字符序列所对应的标准关键字进行输出,具体如下:

图4:对于输入字符串,匹配到的字符序列显示为绿色,没有匹配到的字符序列显示为红色

2.2 利用 Flashtext 进行替换

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

图5:将输入字符串中的匹配字符进行标准替换

2.3 Flashtext 算法

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

构建 Trie 字典;

关键字搜索;

关键字替换;

2.3.1 构建 Trie 字典

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

输入

关键词 w = c1c2c3...cn,其中 ci 表示一个输入字符。标准词我们用 s 来表示。

代码:用于 Flashtext 的初始化并向字典添加关键字

输出

上述程序将会创建一个字典,如图3所示。

2.3.2 关键字搜索

一旦我们将所有的词都添加到 trie 字典中,我们就可以在输入字符串中找到关键字。

输入

字符串 x = a1a2...an,其中 ai 是输入字符串 x 中的第 i 个字符。

代码:Python 代码用来获取字典中的输入字符串中的关键字。

输出

返回一个列表,输出字符串 x 中找到的所有标准化之后的字,如图 4 所示。

2.3.3 关键字替换

我们使用相同的字典用标准化的字来替换输入字符串中的关键字。

输入

输入字符串 x = a1a2...an,其中 ai 表示第 i 个字符。

代码:Python 代码用于从输入字符串中用标准词替换。

输出

在字符串 x 中找到需要替换的词,然后用标准词进行替换输出,如图 5 所示。

3. Flashtext 和正则表达式的基准测试

正如在图 1 和图 2 中所展示的,Flashtext 比正则表达式的处理速度要快很多。现在我们来做一些基准测试来更加说明这个问题。

3.1 关键字搜索

我们利用 Python 代码来实现这个关键字搜索的基准测试。首先,我们会随机创建一个 10K 的语料库。然后,我们将从单词列表中选择 1K 的词用来创建一个新的文档。

我们将从语料库中选择 k 个词,其中 k ∈ 。我们将使用正则表达式和 Flashtext 分别对这个文档中的关键词进行搜索,然后对比分析。具体 Python 代码如下:

3.2 关键词替换

下面的代码是用来做关键词替换的 Python 代码。

3.3 结论

正如我们在上面看到的对比结果,Flashtext 在关键字搜索和替换上面比正则表达式都快很多。特别是在处理大规模数据的时候,这个优势会更加的显示被体现出来。

4. Flashtext 使用文档

4.1 安装

4.2 使用例子4.2.1 关键字提取

4.2.2 关键字替换

4.2.3 区分大小写字母

4.2.4 关键字不清晰

4.2.5 同时添加多个关键词

4.2.6 删除关键字

有时候我们会将一些特殊符号作为字符边界,比如 空格,\ 等等。为了重新设定字边界,我们需要添加一些符号告诉算法,这是单词字符的一部分。

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20171211B0L1QI00?refer=cp_1026

扫码关注云+社区