歡迎光臨
每天分享高質量文章

正則運算式太慢?這裡有一個提速100倍的方案(附代碼)


授權轉載自大資料文摘 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 in sentence?)將花費自己的時間,這就是正則匹配(Regex match)的機制。

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

如果這個句子有m個詞,它就有m個迴圈。在這種情況下,所花費的時間只取決於句子中的單詞數。這個步驟( is in corpus? )可以使用字典查找快速創建。

FlashText演算法是基於第二種方法的,該靈感來自於Aho-Corasick演算法和單詞查找樹資料結構(Trie data structure)。

它的工作方式是:

首先根據語料庫創建一個單詞查找樹字典(Trie data structure)。如下圖:

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

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

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

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

近期精彩活動(直接點擊查看):

福利 · 閱讀 | 免費申請讀大資料新書 第21期

END

投稿和反饋請發郵件至hzzy@hzbook.com。轉載大資料公眾號文章,請向原文作者申請授權,否則產生的任何版權糾紛與大資料無關。

大資料

為大家提供與大資料相關的最新技術和資訊。

長按指紋 > 識別圖中二維碼 > 添加關註

近期精彩文章(直接點擊查看):

華為內部狂轉好文,大資料,看這一篇就夠了!

讀完這100篇論文,你也是大資料高手!

如何建立資料分析的思維框架

百度內部培訓資料PPT:資料分析的道與術

論大資料的十大局限

打包帶走!史上最全的大資料分析和製作工具

資料揭秘:中國姓氏排行榜

程式猿分析了42萬字歌詞後,終於搞清楚民謠歌手唱什麼了

計算機告訴你,唐朝詩人之間的關係到底是什麼樣的?

資料分析:微信紅包金額分配的秘密

2000萬人口的大北京,上下班原來是這樣的(附超炫蝌蚪圖)

大資料等IT職業技能圖譜【全套17張,第2版】

不要跟賭場說謊,它真的比你老婆還瞭解你

如果看了這篇文章你還不懂傅里葉變換,那就過來掐死我吧

不做無效的營銷,從不做無效的用戶畫像開始

更多精彩文章,請在公眾號後臺點擊“歷史文章”查看,謝謝。

赞(0)

分享創造快樂