内容简介：用Python只花十五分钟完成正则表达式五天任务量
自然语言处理领域的开发者在处理文本之前必须对数据进行清理。有些时候，此类工作是由关键词替换完成的，就像吧「Javascript」替换成「JavaScript」。另一些时候，我们只需要知道文档中是否提到了「JavaScript」。
这类数据清理任务是大多数处理文本的数据科学项目必须要做的。
数据科学从清理数据开始
本文作者是 Belong.co 的一名数据科学家，需要从事有关自然语言处理的工作，于是遇到了这个问题。当我在自己的文档语料库中开始训练 Word2Vec 模型时，它开始将同义词归为同类项，「Javascripting」被归类为「JavaScript」的同类项。
为了解决这个问题，我写了一个正则表达式（Regex），用标准化命名来替换所有已知的同义词。Regex 会将「Javascripting」替换为「JavaScript」，这解决了一个问题，却又带来了另一个问题。
有些人遇到问题时会想：「没关系，我们有正则表达式。」现在问题变成了两个。
上文所述引自 Stack-exchange question，现在让我遇到了。
事实证明，正则表达式的速度很快——如果要搜索和替换的关键词数量是一百多个的话。但是面对超过 20k 个关键词，300 万个文件的语料库，事情就会变得很糟。当我测试我的代码时，我发现完全运行需要 5 天之久。
通常，面对这种情况我们的解决方案是并行运算。但在面对上千万个文件中成百上千出现频次的关键词，并行的性能提升有限，我们必须找到更好的方法！
幸好，在 Stack Overflow 上我的疑问获得了大家的关注，网友们和公司同事 Vinay Pandey、Suresh Lakshmanan 等人提到了一个名叫 Aho-Corasick 算法的神奇工具，以及前缀树数据结构（Trie Data Structure）。然而目前网络上还缺乏相关资源。
-
Aho-Corasick 算法：https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
-
Trie Data Structure：https://en.wikipedia.org/wiki/Trie
所以我开始自己动手，FlashText 诞生了。
在介绍 FlashText 的结构和工作原理之前，先看看它的搜索性能表现：
下面的红线是 FlashText 的搜索耗时
如上图所示，Regex 算法和 FlashText 搜索同一篇文档的耗时相差很大。随着关键词数量的增加，Regex 的耗时呈线性增长，而对于 FlashText 来说并没有影响。
FlashText 可以把 5 天的工作缩短到 15 分钟！
这是 FlashText 替换的速度：
同样，下面的红线是 FlashText 的替换速度。
所以，FlashText 是什么？
FlashText 是我在 GitHub 上开源的一个 Python 库，它能高效地提取和替换关键词。
使用 FlashText 时，首先你需要发送一系列关键词，这个列表将被用于在内部建立一个前缀树字典。随后你需要传递一个字符串，告诉它你需要执行替换还是搜索。
在替换时，它会创建一个新字符串来替换关键词。在搜索时，它会返回一个关键词列表。这一切都将在输入字符串上进行。
有的用户是这样评价FastText的：
Radim Řehůřek 是著名 Python 库 Gensim 的作者
FlashText 为什么那么快？
我们用一个例子来尝试和理解这一部分。假设我们有一个包含三个单词的句子 I like Python，和一个有四个单词的语料库 {Python，Java，J2ee，Ruby}。
如果每次取出语料库中的一个单词，并检查其在句子中是否出现，这需要四次操作。
is 'Python' in sentence? is 'Java' in sentence?...
如果语料库有 n 个单词，意味着需要做 n 次的循环操作，并且每一个时间步的搜索都是 isin sentence ? 这有点像正则表示式相配（Regex match）中的过程。
还有另一种和第一种相反的方法。对于句子中的每一个单词，检查其是否在语料库中出现。
is 'I' in corpus?is 'like' in corpus?is 'python' in corpus?
如果句子 m 个单词，意味着需要做 m 次的循环操作。在这个例子中所需的时间步取决于句子中的单词数。而使用字典查询进行 isin corpus ? 会快得多。
FlashText 基于第二种方法，由 Aho-Corasick 算法和前缀树（Trie）数据结构所启发。
它的工作方式为：
首先由语料库创建一个如下图所示的前缀树字典：
语料库的前缀树字典
Start 和 EOT（End Of Term，期末）表示单词的边界比如 space、period 和 new_line。只有两侧都有边界的关键词才能得到匹配，这可以防止把 apple 匹配到 pineapple。
下一步我们将取输入字符串为 I like Python，并按字符逐个对齐进行搜索。
Step 1: is Iin dictionary? NoStep 2: is likein dictionary? NoStep 3: is Pythonin dictionary? Yes
Python出现在字典中。
由于这是一个字符匹配过程，我们可以轻易地在进行到l 的时候跳过整个like，因为 start 并没有和 l 相连。这使得跳过缺失单词的过程变得非常快。
FlashText 算法只需要遍历输入字符串『I like Python』的每一个字符。即使字典有上百万个关键词，对运行时间也没有任何影响。这是 FlashText 算法的真正威力。
什么时候需要使用 FlashText？
简单的回答是：当关键词数量>500 的时候
当关键词数量>500 的时候，FlashText 的搜索速度开始超过 Regex
完整的回答是：Regex 可以搜索基于特殊字符比如^、$、*、d 等的关键词，而 FlashText 不支持这种搜索。
所以如果想要匹配部分单词比如『worddvec』，使用 FlashText 并没有好处，但其非常善于提取完整的单词比如『word2vec』。
用于寻找关键词的代码
# pip install flashtextfrom flashtext.keyword import KeywordProcessorkeyword_processor = KeywordProcessor()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']
使用 FlashText 提取关键词的简单例子
用于替换关键词的代码
FlashText 不仅可以提取句子中的关键词还可以对其进行替换。我们将此作为数据处理管道的数据清理步骤。
from flashtext.keyword import KeywordProcessorkeyword_processor = KeywordProcessor()keyword_processor.add_keyword('Big Apple', 'New York')keyword_processor.add_keyword('New Delhi', 'NCR region')new_sentence = keyword_processor.replace_keywords('I love Big Apple and new delhi.')new_sentence# 'I love New York and NCR region.'
使用 FlashText 替换关键词的简单例子
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Hacking Growth
Sean Ellis、Morgan Brown / Crown Business / 2017-4-25 / USD 29.00
The definitive playbook by the pioneers of Growth Hacking, one of the hottest business methodologies in Silicon Valley and beyond. It seems hard to believe today, but there was a time when Airbnb w......一起来看看 《Hacking Growth》 这本书的介绍吧!
