轉自：2017-12-14?文摘菌??大數據文摘

作者：Vikash Singh

編譯：肖依月、吳雙、錢天培

“當遇到一個文本處理問題時，如果你在第一時間想到了正則表達式，那么恭喜你，你的問題從一個變成了倆！“

如果你曾參與過文本數據分析，正則表達式（Regex）對你來說一定不陌生。詞庫索引、關鍵詞替換……正則表達式的強大功能使其成為了文本處理的必備工具。然而， 在處理大文本的情境下，正則表達式的低效率卻常常讓人抓耳撓腮。今天，文摘菌將為你介紹一款比正則表達式快數百倍的Python庫——FlashText。

讓人抓狂的數據清洗工作

即便是最簡單的文本分析，我們在進入正式分析之前也需要對文本作出數據清洗。清洗的工作往往涉及到搜索和替換關鍵詞。例如，查詢文本中是否出現““Python”這一關鍵詞，或是將所有“python“都替換成”“Python”。如果僅有數百個被搜索和被替換的關鍵詞，正則表達式處理起來會很快。但在自然語言處理任務中，有數萬關鍵詞的語料庫和數百萬的文檔早已是家常便飯。這種情況下，運行正則表達式的時間就往往要以“天“來作計數單位了。

當然了，你會覺得并行運算能夠解決這一問題，但實際上這一方案卻收效甚微。有沒有其他辦法呢？

FlashText的創(chuàng)造者當年也面臨了同樣的問題，在經過了一番搜尋而無所獲后，他決定自己來編寫一個新算法。

在了解FlashText的實現原理之前，讓我們先來看看FlashText和正則表達式在搜索任務中的性能對比圖。

我們可以看到，當關鍵詞數量上升時，Regex所花費的時間幾乎呈線性增長，然而FlashText卻幾乎沒受什么影響。

再來看一張執(zhí)行詞語替換任務的對比圖

同樣的，在詞語數量增加時，FlashText的運行時間卻幾乎不受影響。

所以，什么是FlashText呢？

FlashText是GitHub上的一個開源Python庫，正如之前所提到的，它在提取關鍵字和替換關鍵字任務上有著極高的性能。

在使用FlashText時，你首先要給它一個關鍵詞列表。這份列表將用于在內部建立一個單詞查找樹的字典（Trie dictionary）。然后你將一個字符串傳遞給它，并告訴它是要執(zhí)行替換還是搜索。

對于替換，它將用替換關鍵字創(chuàng)建一個新字符串。對于搜索，它將返回字符串中找到的關鍵字列表。這些任務都只需要遍歷字符串一遍。

FlashText為什么這么快？

舉個例子吧。我們有一個句子，它由三個單詞組成——I like Python，并且假設我們有一個四個單詞組成的語料庫{Python, Java, J2ee, Ruby}。

如果我們從語料庫中拿出每個單詞，并且檢查它是否出現在句子中，這需要我們遍歷字符串四次。

如果語料庫里有n個詞，它將需要n個循環(huán)。并且每個搜索步驟（is in sentence?）將花費自己的時間，這就是正則匹配（Regex match）的機制。

還有與第一種方法相反的另一種方法L對于句子中的每個單詞，檢查它是否存在于語料庫中。

如果這個句子有m個詞，它就有m個循環(huán)。在這種情況下，所花費的時間只取決于句子中的單詞數。這個步驟（ is in corpus? ）可以使用字典查找快速創(chuàng)建。

FlashText算法是基于第二種方法的，該靈感來自于Aho-Corasick算法和單詞查找樹數據結構（Trie data structure）。

它的工作方式是：

首先根據語料庫創(chuàng)建一個單詞查找樹字典（Trie data structure）。如下圖：

start和EOT（End Of Term）表示單詞邊界，可以是空格，句號或換行符。關鍵字只有在它的兩邊有單詞邊界時才能被匹配。這樣可以防止apple和pineapple的匹配。

接下來，我們將輸入一個字符串I like Python，并且一個字符一個字符搜索他、它。

因為該算法是一個字符接一個字符匹配，在搜索I時，我們可以很容易地跳過like在，因為I沒有接在后面。這一機制讓我們可以很快跳過詞庫中不存在的詞。

FlashText算法只檢查輸入字符串“I like Python”中的每個字符。即便我們的字典有一百萬個關鍵字，這對它的運行幾乎沒有影響。這正是FlashText算法的能力所在。

所以你什么時候應用FlashText？

簡要回答：當關鍵詞數量>500時

對于搜索而言，大約超過500個關鍵詞后FlashText開始優(yōu)于正則表達式。

補充：正則表達式可以搜索基于特殊字符為關鍵字，如^,$,*,\d,.但FlashText是不支持的。

所以如果你想匹配部分的單詞（如“word\dvec”）是不行的，但它能很好地提取完整的單詞（如“word2vec”）。

最后，奉上FlashText的基本功能調用代碼！試一試，是不是比正則表達式快了很多呢？

代碼：用FlashText查找關鍵字

代碼：用FlashText替換關鍵字

原文鏈接：https://medium.freecodecamp.org/regex-was-taking-5-days-flashtext-does-it-in-15-minutes-55f04411025f