自然语言处理领域的开发者在处理文本之前必须清洗数据。有时，这种工作是通过关键字替换来完成的，比如用“JavaScript”替换“Javascript”。其他时候，我们只需要知道文档中是否提到了“JavaScript”。对于大多数处理文本的数据科学项目来说，这种类型的数据清理任务是必须的。DataScienceStartswithCleaningData本文作者是Belong.co的数据科学家，需要从事自然语言处理工作，遇到了这个问题。当我开始在我的文档语料库上训练Word2Vec模型时，它开始将同义词分组在一起，并且“Javascripting”被分组为“JavaScript”的兄弟姐妹。为了解决这个问题，我写了一个正则表达式（Regex）来用标准化名称替换所有已知的同义词。Regex会将“Javascripting”替换为“JavaScript”，这解决了一个问题但又产生了另一个问题。有些人遇到问题会想，“没关系，我们有正则表达式。”现在问题变成了两个。上面的引述来自一个Stack-exchange问题，现在我想到了这个问题。事实证明，正则表达式很快-如果要搜索和替换的关键字数量超过一百个。但是当面对超过20k的关键词和300万文档的语料库时，事情就会变糟。当我测试我的代码时，我发现完全运行需要长达5天的时间。通常，我们针对这种情况的解决方案是并行计算。但面对文件中出现次数上百次的千万级关键词，并行性能提升有限，必须寻找更好的方法！幸运的是，我在StackOverflow上的问题引起了大家的注意。网友和公司同事VinayPandey、SureshLakshmanan等人提到了一个叫做Aho-Corasick算法的神奇工具，以及前缀树数据结构（TrieDataStructure）。但是网上还是缺乏相关资源。Aho-Corasick算法：https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithmTrie数据结构：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这么快？让我们尝试通过一个例子来理解这部分。假设我们有一个三词的句子我喜欢Python，和一个四词的语料库{Python,Java,J2ee,Ruby}。如果你在语料库中一次一个地取一个词并检查它是否出现在句子中，需要四次操作。“Python”在句子中吗？is'Java'insentence?...如果语料库有n个词，意味着它需要做n次循环操作，每个时间步的搜索是在句子中？这有点像正则表达式匹配（Regexmatch）的过程。还有一种方法与第一种相反。对于句子中的每个单词，检查它是否出现在语料库中。“我”在语料库中吗？语料库中的“like”是什么？语料库中的“python”是什么？如果句子有m个词，就意味着它需要做m次循环操作。此示例中所需的时间步长取决于句子中的单词数。而在语料库中做呢？使用字典查找会快得多。FlashText基于第二种方法，灵感来自Aho-Corasick算法和前缀树(Trie)数据结构。其工作原理如下：首先，从语料库中创建一个前缀树字典如下图所示：语料库的前缀树字典Start和EOT（EndOfTerm）分别表示空格、句号、new_line等词的边界.只有两侧带有边框的关键字才会匹配，这会阻止将apple匹配到pineapple。在下一步中，我们将按照我喜欢的Python方式获取输入字符串，并逐个字符地搜索它。第一步：Iin字典？NoStep2:likein字典？NoStep3：字典里有Python吗？YesPython出现在字典中。由于这是一个字符匹配过程，所以我们可以很容易地在到达l时跳过整个like，因为start并没有连接到l。这使得跳过丢失单词的过程非常快。FlashText算法只需要遍历输入字符串“IlikePython”的每一个字符即可。即使字典有数百万个关键词，也不会对运行时间产生任何影响。这就是FlashText算法的真正威力。我什么时候应该使用FlashText？简单的回答是：当关键字数>500时，当关键字数>500时，FlashText的搜索速度开始超过Regex。完整的答案是：Regex可以根据^、$、*、d等特殊字符关键字进行搜索，FlashText不支持这种搜索。所以如果要匹配部分词如“worddvec”，使用FlashText没有任何好处，但它非常擅长提取完整的词如“word2vec”。查找关键字的代码#pipinstallflashtextfromflashtext.keywordimportKeywordProcessorkeyword_processor=KeywordProcessor()keyword_processor.add_keyword('BigApple','NewYork')keyword_processor.add_keyword('BayArea')keywords_found=keyword_processor.extract_keywords('IloveBigAppleandBayArea.')keywords_found#['NewYork','BayArea']使用FlashText提取关键词的简单例子用于替换关键词的代码FlashText不仅可以提取句子中的关键词，还可以替换它。我们将此作为数据处理管道中的数据清理步骤。fromflashtext.keywordimportKeywordProcessorkeyword_processor=KeywordProcessor()keyword_processor.add_keyword('BigApple','NewYork')keyword_processor.add_keyword('NewDelhi','NCRregion')new_sentence=keyword_processor.replace_keywords('我爱大苹果和新德里。')new_sentence#'我爱纽约和NCR地区。'使用FlashText替换关键字的简单例子
