覺得正則表達式太慢？這裏有一個提速100倍的方案
“當遇到一個文本處理問題時，如果你在第一時間想到了正則表達式，那麼恭喜你，你的問題從一個變成了倆！“
如果你曾參與過文本數據分析，正則表達式（Regex）對你來說一定不陌生。詞庫索引、關鍵詞替換……正則表達式的強大功能使其成爲了文本處理的必備工具。然而， 在處理大文本的情境下，正則表達式的低效率卻常常讓人抓耳撓腮。今天，文摘菌將爲你介紹一款比正則表達式快數百倍的Python庫——FlashText。
本文福利：私信回覆【PDF】可獲取Python電子書一套
讓人抓狂的數據清洗工作
即便是最簡單的文本分析，我們在進入正式分析之前也需要對文本作出數據清洗。清洗的工作往往涉及到搜索和替換關鍵詞。例如，查詢文本中是否出現““Python”這一關鍵詞，或是將所有“python“都替換成”“Python”。如果僅有數百個被搜索和被替換的關鍵詞，正則表達式處理起來會很快。但在自然語言處理任務中，有數萬關鍵詞的語料庫和數百萬的文檔早已是家常便飯。這種情況下，運行正則表達式的時間就往往要以“天“來作計數單位了。
嚇哭了的文摘菌
當然了，你會覺得並行運算能夠解決這一問題，但實際上這一方案卻收效甚微。有沒有其他辦法呢？
FlashText的創造者當年也面臨了同樣的問題，在經過了一番搜尋而無所獲後，他決定自己來編寫一個新算法。
在瞭解FlashText的實現原理之前，讓我們先來看看FlashText和正則表達式在搜索任務中的性能對比圖。
我們可以看到，當關鍵詞數量上升時，Regex所花費的時間幾乎呈線性增長，然而FlashText卻幾乎沒受什麼影響。
開心的文摘菌
再來看一張執行詞語替換任務的對比圖
同樣的，在詞語數量增加時，FlashText的運行時間卻幾乎不受影響。
所以，什麼是FlashText呢？
FlashText是GitHub上的一個開源Python庫，正如之前所提到的，它在提取關鍵字和替換關鍵字任務上有着極高的性能。
在使用FlashText時，你首先要給它一個關鍵詞列表。這份列表將用於在內部建立一個單詞查找樹的字典（Trie dictionary）。然後你將一個字符串傳遞給它，並告訴它是要執行替換還是搜索。
對於替換，它將用替換關鍵字創建一個新字符串。對於搜索，它將返回字符串中找到的關鍵字列表。這些任務都只需要遍歷字符串一遍。
FlashText爲什麼這麼快？
舉個例子吧。我們有一個句子，它由三個單詞組成——I like Python，並且假設我們有一個四個單詞組成的語料庫{Python, Java, J2ee, Ruby}。
如果我們從語料庫中拿出每個單詞，並且檢查它是否出現在句子中，這需要我們遍歷字符串四次。
如果語料庫裏有n個詞，它將需要n個循環。並且每個搜索步驟（is
還有與第一種方法相反的另一種方法L對於句子中的每個單詞，檢查它是否存在於語料庫中。
如果這個句子有m個詞，它就有m個循環。在這種情況下，所花費的時間只取決於句子中的單詞數。這個步驟（ is
FlashText算法是基於第二種方法的，該靈感來自於Aho-Corasick算法和單詞查找樹數據結構（Trie data structure）。
它的工作方式是：
首先根據語料庫創建一個單詞查找樹字典（Trie data structure）。如下圖：
start和EOT（End Of Term）表示單詞邊界，可以是空格，句號或換行符。關鍵字只有在它的兩邊有單詞邊界時才能被匹配。這樣可以防止apple和pineapple的匹配。
接下來，我們將輸入一個字符串I like Python，並且一個字符一個字符搜索他、它。
因爲該算法是一個字符接一個字符匹配，在搜索
FlashText算法只檢查輸入字符串“I like Python”中的每個字符。即便我們的字典有一百萬個關鍵字，這對它的運行幾乎沒有影響。這正是FlashText算法的能力所在。
所以你什麼時候應用FlashText？
簡要回答：當關鍵詞數量>500時
對於搜索而言，大約超過500個關鍵詞後FlashText開始優於正則表達式。
補充：正則表達式可以搜索基於特殊字符爲關鍵字，如^,$,*,\d,.但FlashText是不支持的。
所以如果你想匹配部分的單詞（如“word\dvec”）是不行的，但它能很好地提取完整的單詞（如“word2vec”）。
最後，奉上FlashText的基本功能調用代碼！試一試，是不是比正則表達式快了很多呢？
代碼：用FlashText查找關鍵字
代碼：用FlashText替換關鍵字
怎麼樣？學會了嗎？是不是比正則快？
查看原文 >>
