flashtext：大规模数据清洗的利器

flashText介绍

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

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

安装：

pip install flashtext

正则表达式和Flashtext效率测试

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

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

import re

compiled_regex = re.compile(r'\b2017\b|\b\d{4}\b')
compiled_regex.findall('In 2017 2311 is my birthday.')

# output
['2017', '2311']

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

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

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

import re

re.sub(r"\bjava script\b", 'javascript', 'java script is awesome.')

# output
javascript is awesome.

正则表达式在一个 10k 的词库中查找 15k 个关键词的时间差不多是 0.165 秒。但是对于 Flashtext 而言只需要 0.002 秒。因此，在这个问题上 Flashtext 的速度大约比正则表达式快 82 倍。

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

Flashtext

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

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

利用 Flashtext 进行搜索

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

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

利用 Flashtext 进行替换

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

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

函数解读

新增与关键词查询

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

• 构建 Trie 字典 KeywordProcessor
• 新增关键词 add_keyword
• 关键词抽取 extract_keywords

from flashtext import KeywordProcessor

keyword_processor=KeywordProcessor(case_sensitive=False)
keyword_processor.add_keyword(one_kw,)
keywords_found=keyword_processor.extract_keywords(one_str,span_info=True)
>>> ('健康', 6, 8)

其中：

• case_sensitive，是否对大小写敏感
• span_info，是否要返回位置信息

当然，新增关键词还有很多招数:

匹配词归类

add_keyword(word,key) word就会被归类到key，就像{'key':'word'} ，所以匹配到word,会直接显示key

keyword_processor.add_keyword('Taj Mahal', {1:1,2:2})
keyword_processor.add_keyword('Delhi', ('Location', 'Delhi'))
keyword_processor.add_keyword('Delhi', ['Location', 'Delhi'])

与字典一样的新增方式

keyword_processor['apple']='fruits'

可以与字典一样的新增，而与add_keyword(word,key) 一样的效果

批量新增 —— 字典和列表

keyword_dict={
            "fruit": ["apple", "banana","orange","watermelon"], 
            "ball": ["tennis", "basketball","football"]
             }
keyword_processor.add_keywords_from_dict(keyword_dict)         # 可以添加dict
keyword_processor.add_keywords_from_list(["fruit", "banana"])  # 可以添加list

add_keywords_from_dict与add_keyword(word,key) 一样，如果匹配到values，则会返回key

查询与检索

一般用的是：extract_keywords还可以使用replace_keywords

keywords_found=keyword_processor.extract_keywords(one_str,span_info=True)

extract_keywords返回的是匹配到的关键词，而replace_keywords是直接返回一整个句子，相当于关键词定位 + 替换：

# 加载
kw_list=['健康','美味']
keyword_processor=KeywordProcessor()
for kl in kw_list:
    keyword_processor.add_keyword(kl)
keyword_processor.add_keyword('健康','建康')
# 查询
text="这个菜，真是健康又美味，很健康"
new_sentence=keyword_processor.replace_keywords(text)   # 替换式查询
print(new_sentence)
new_sentence=keyword_processor.extract_keywords(text)   # 关键词检索
print(new_sentence)

>>> 这个菜，真是建康又美味，很建康
>>> ['建康', '美味', '建康']

删除关键词

'''
移除关键词
'''
keyword_processor.remove_keyword('banana')
keyword_processor.remove_keywords_from_dict({"food": ["bread"]})
keyword_processor.remove_keywords_from_list(["basketball"])

KeywordProcessor的一些属性

KeywordProcessor是trie树，可以：

len(keyword_processor)  # 关键词长度
'LOVE' in keyword_processor  # 判断关键词Love是否在词表中
keyword_processor.get_keyword('apple') # 与dict一样，看apple的key是啥
keyword_processor.get_all_keywords() # 所有的字符，一次性遍历出来

设置或添加字符作为单词字符的一部分,即：改变原有的关键词

'''设置或添加字符作为单词字符的一部分,即：改变原有的关键词'''
from flashtext import KeywordProcessor

keyword_processor=KeywordProcessor()
keyword_processor.add_keyword('Apple')
before_kw=keyword_processor.extract_keywords('I love Apple/And orange.')
keyword_processor.add_non_word_boundary('/')
after_kw=keyword_processor.extract_keywords('I love Apple/And orange.')
print('before_kw: ',before_kw)
print( 'after_kw: ',after_kw)

结果
before_kw: ['Apple']
after_kw: []

使用案例

关键字提取

>>> from flashtext import KeywordProcessor
>>> keyword_processor = KeywordProcessor()
>>> # keyword_processor.add_keyword(<unclean name>, <standardised name>)
>>> keyword_processor.add_keyword('Big Apple', 'New York')
>>> keyword_processor.add_keyword('Bay Area')
>>> keywords_found = keyword_processor.extract_keywords('I love Big Apple and Bay Area.')
>>> keywords_found
>>> # ['New York', 'Bay Area']

区分大小写字母

>>> from flashtext import KeywordProcessor
>>> keyword_processor = KeywordProcessor(case_sensitive=True)
>>> keyword_processor.add_keyword('Big Apple', 'New York')
>>> keyword_processor.add_keyword('Bay Area')
>>> keywords_found = keyword_processor.extract_keywords('I love big Apple and Bay Area.')
>>> keywords_found
>>> # ['Bay Area']

关键字不清晰

>>> from flashtext import KeywordProcessor
>>> keyword_processor = KeywordProcessor()
>>> keyword_processor.add_keyword('Big Apple')
>>> keyword_processor.add_keyword('Bay Area')
>>> keywords_found = keyword_processor.extract_keywords('I love big Apple and Bay Area.')
>>> keywords_found
>>> # ['Big Apple', 'Bay Area']

同时添加多个关键词

>>> from flashtext import KeywordProcessor
>>> keyword_processor = KeywordProcessor()
>>> keyword_dict = {
>>>     "java": ["java_2e", "java programing"],
>>>     "product management": ["PM", "product manager"]
>>> }
>>> # {'clean_name': ['list of unclean names']}
>>> keyword_processor.add_keywords_from_dict(keyword_dict)
>>> # Or add keywords from a list:
>>> keyword_processor.add_keywords_from_list(["java", "python"])
>>> keyword_processor.extract_keywords('I am a product manager for a java_2e platform')
>>> # output ['product management', 'java']

删除关键字

>>> from flashtext import KeywordProcessor
>>> keyword_processor = KeywordProcessor()
>>> keyword_dict = {
>>>     "java": ["java_2e", "java programing"],
>>>     "product management": ["PM", "product manager"]
>>> }
>>> keyword_processor.add_keywords_from_dict(keyword_dict)
>>> print(keyword_processor.extract_keywords('I am a product manager for a java_2e platform'))
>>> # output ['product management', 'java']
>>> keyword_processor.remove_keyword('java_2e')
>>> # you can also remove keywords from a list/ dictionary
>>> keyword_processor.remove_keywords_from_dict({"product management": ["PM"]})
>>> keyword_processor.remove_keywords_from_list(["java programing"])
>>> keyword_processor.extract_keywords('I am a product manager for a java_2e platform')
>>> # output ['product management']

关键词匹配与pyahocorasick进行对比

import ahocorasick

def build_actree(wordlist):
    '''
        AC自动机进行关键词匹配
        构造AC trie
    '''
    actree = ahocorasick.Automaton()         # 初始化trie树
    for index, word in enumerate(wordlist):
        actree.add_word(word, (index, word))     # 向trie树中添加单词
    actree.make_automaton()    # 将trie树转化为Aho-Corasick自动机
    #self.actree = actree
    return actree

def ac_detect(actree,text):
    '''
        AC自动机进行关键词匹配
        文本匹配
    '''
    region_wds = []
    for w1 in actree.iter(text):
        if len(w1) > 0:
            region_wds.append(w1[1][1])
    return region_wds

wordlist = ['健康','减肥']
text = '今天你减肥了吗，今天你健康了吗，减肥 = 健康！'
actree = build_actree(wordlist)
ac_detect(actree,text)

>>> CPU times: user 10 µs, sys: 3 µs, total: 13 µs
>>> Wall time: 17.4 µs
>>> ['减肥', '健康', '减肥', '健康']

与flashtext进行对比：

from flashtext import KeywordProcessor

def build_actree(wordlist):
    '''
        AC自动机进行关键词匹配
        构造AC trie
    '''
    actree = KeywordProcessor()
    for index, word in enumerate(wordlist):
        actree.add_keyword(word)     # 向trie树中添加单词
    #self.actree = actree
    return actree

def ac_detect(actree,text,span_info = True):
    '''
        AC自动机进行关键词匹配
        文本匹配
    '''
    region_wds = []
    for w1 in actree.extract_keywords(text,span_info = span_info):
        if len(w1) > 0:
            region_wds.append(w1[0])
    return region_wds

wordlist = ['健康','减肥']
text = '今天你减肥了吗，今天你健康了吗，减肥 = 健康！'
actree = build_actree(wordlist)
ac_detect(actree,text)

>>> CPU times: user 41 µs, sys: 0 ns, total: 41 µs
>>> Wall time: 47.2 µs
>>> ['减肥', '健康', '减肥', '健康']

感觉，速度好像还是pyahocorasick 更快

flashtext github：https://github.com/vi3k6i5/flashtext

pypi：https://pypi.org/project/flashtext/

官方文档：https://flashtext.readthedocs.io/en/latest/

pyahocorasick github：https://github.com/WojciechMula/pyahocorasick/