知識星球
授權轉載自大資料文摘 ID：BigDataDigest
“當遇到一個文字處理問題時，如果你在第一時間想到了正則運算式，那麼恭喜你，你的問題從一個變成了倆！“
如果你曾參與過文字資料分析，正則運算式（Regex）對你來說一定不陌生。詞庫索引、關鍵詞替換……正則運算式的強大功能使其成為了文字處理的必備工具。然而， 在處理大文字的情境下，正則運算式的低效率卻常常讓人抓耳撓腮。今天，文摘菌將為你介紹一款比正則運算式快數百倍的Python庫——FlashText。
01 讓人抓狂的資料清洗工作
即便是最簡單的文字分析，我們在進入正式分析之前也需要對文字作出資料清洗。清洗的工作往往涉及到搜尋和替換關鍵詞。例如，查詢文字中是否出現““Python”這一關鍵詞，或是將所有“python“都替換成”“Python”。如果僅有數百個被搜尋和被替換的關鍵詞，正則運算式處理起來會很快。但在自然語言處理任務中，有數萬關鍵詞的語料庫和數百萬的檔案早已是家常便飯。這種情況下，執行正則運算式的時間就往往要以“天“來作計數單位了。
嚇哭了的文摘菌
當然了，你會覺得並行運算能夠解決這一問題，但實際上這一方案卻收效甚微。有沒有其他辦法呢？
FlashText的創造者當年也面臨了同樣的問題，在經過了一番搜尋而無所獲後，他決定自己來編寫一個新演演算法。
在瞭解FlashText的實現原理之前，讓我們先來看看FlashText和正則運算式在搜尋任務中的效能對比圖。
我們可以看到，當關鍵詞數量上升時，Regex所花費的時間幾乎呈線性增長，然而FlashText卻幾乎沒受什麼影響。
開心的文摘菌
再來看一張執行詞語替換任務的對比圖
同樣的，在詞語數量增加時，FlashText的執行時間卻幾乎不受影響。
02 所以，什麼是FlashText呢？
FlashText是GitHub上的一個開源Python庫，正如之前所提到的，它在提取關鍵字和替換關鍵字任務上有著極高的效能。
在使用FlashText時，你首先要給它一個關鍵詞串列。這份串列將用於在內部建立一個單詞查詢樹的字典（Trie dictionary）。然後你將一個字串傳遞給它，並告訴它是要執行替換還是搜尋。
對於替換，它將用替換關鍵字建立一個新字串。對於搜尋，它將傳回字串中找到的關鍵字串列。這些任務都只需要遍歷字串一遍。
03 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演演算法的能力所在。
04 所以你什麼時候應用FlashText？
簡要回答：當關鍵詞數量>500時
對於搜尋而言，大約超過500個關鍵詞後FlashText開始優於正則運算式。
補充：正則運算式可以搜尋基於特殊字元為關鍵字，如^,$,*,\d,.但FlashText是不支援的。
所以如果你想匹配部分的單詞（如“word\dvec”）是不行的，但它能很好地提取完整的單詞（如“word2vec”）。
最後，奉上FlashText的基本功能呼叫程式碼！試一試，是不是比正則運算式快了很多呢？
程式碼：用FlashText查詢關鍵字
程式碼：用FlashText替換關鍵字
原文連結：https://medium.freecodecamp.org/regex-was-taking-5-days-flashtext-does-it-in-15-minutes-55f04411025f
近期精彩活動（直接點選檢視）：
投稿和反饋請發郵件至hzzy@hzbook.com。轉載大資料公眾號文章，請向原文作者申請授權，否則產生的任何版權糾紛與大資料無關。
為大家提供與大資料相關的最新技術和資訊。
近期精彩文章（直接點選檢視）：
更多精彩文章，請在公眾號後臺點選“歷史文章”檢視，謝謝。
