選自FreeCoderCamp
作者：Vikash Singh
參與：李澤南、劉曉坤
數據清理是很多機器學習任務上我們遇到的首要問題。本文介紹的 FastText 是一個開源 Python 庫，可用於快速進行大規模語料庫的文本搜索與替換。該項目的作者表示，使用正則表達式（Regex）需要 5 天的任務在新的方法中只需要 15 分鐘即可完成。
項目鏈接：https://github.com/vi3k6i5/flashtext
自然語言處理領域的開發者在處理文本之前必須對數據進行清理。有些時候，此類工作是由關鍵詞替換完成的，就像吧「Java」替換成「Java」。另一些時候，我們只需要知道文檔中是否提到了「Java」。
這類數據清理任務是大多數處理文本的數據科學項目必須要做的。
數據科學從清理數據開始
本文作者是 Belong.co 的一名數據科學家，需要從事有關自然語言處理的工作，於是遇到了這個問題。當我在自己的文檔語料庫中開始訓練 Word2Vec 模型時，它開始將同義詞歸爲同類項，「Javaing」被歸類爲「Java」的同類項。
爲了解決這個問題，我寫了一個正則表達式（Regex），用標準化命名來替換所有已知的同義詞。Regex 會將「Javaing」替換爲「Java」，這解決了一個問題，卻又帶來了另一個問題。
有些人遇到問題時會想：「沒關係，我們有正則表達式。」現在問題變成了兩個。
上文所述引自 Stack-exchange question，現在讓我遇到了。
事實證明，正則表達式的速度很快——如果要搜索和替換的關鍵詞數量是一百多個的話。但是面對超過 20k 個關鍵詞，300 萬個文件的語料庫，事情就會變得很糟。當我測試我的代碼時，我發現完全運行需要 5 天之久。
通常，面對這種情況我們的解決方案是並行運算。但在面對上千萬個文件中成百上千出現頻次的關鍵詞，並行的性能提升有限，我們必須找到更好的方法！
幸好，在 Stack Overflow 上我的疑問獲得了大家的關注，網友們和公司同事 Vinay Pandey、Suresh Lakshmanan 等人提到了一個名叫 Aho-Corasick 算法的神奇工具，以及前綴樹數據結構（Trie Data Structure）。然而目前網絡上還缺乏相關資源。
Aho-Corasick 算法：https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
Trie Data Structure：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 爲什麼那麼快？
我們用一個例子來嘗試和理解這一部分。假設我們有一個包含三個單詞的句子 I like Python，和一個有四個單詞的語料庫 {Python，Java，J2ee，Ruby}。
如果每次取出語料庫中的一個單詞，並檢查其在句子中是否出現，這需要四次操作。
is'Python'insentence?
is'Java'insentence?
...
如果語料庫有 n 個單詞，意味着需要做 n 次的循環操作，並且每一個時間步的搜索都是 is in sentence ? 這有點像正則表示式相配（Regex match）中的過程。
還有另一種和第一種相反的方法。對於句子中的每一個單詞，檢查其是否在語料庫中出現。
is'I'incorpus?
is'like'incorpus?
is'python'incorpus?
如果句子 m 個單詞，意味着需要做 m 次的循環操作。在這個例子中所需的時間步取決於句子中的單詞數。而使用字典查詢進行 is in corpus ? 會快得多。
FlashText 基於第二種方法，由 Aho-Corasick 算法和前綴樹（Trie）數據結構所啓發。
它的工作方式爲：
首先由語料庫創建一個如下圖所示的前綴樹字典：
語料庫的前綴樹字典
Start 和 EOT（End Of Term，期末）表示單詞的邊界比如 space、period 和 new_line。只有兩側都有邊界的關鍵詞才能得到匹配，這可以防止把 apple 匹配到 pineapple。
下一步我們將取輸入字符串爲 I like Python，並按字符逐個對齊進行搜索。
Step1: isI indictionary? No
Step2: islike indictionary? No
Step3: isPythonindictionary? Yes
Python 出現在字典中。
由於這是一個字符匹配過程，我們可以輕易地在進行到 l 的時候跳過整個 like ，因爲 start 並沒有和 l 相連。這使得跳過缺失單詞的過程變得非常快。
FlashText 算法只需要遍歷輸入字符串『I like Python』的每一個字符。即使字典有上百萬個關鍵詞，對運行時間也沒有任何影響。這是 FlashText 算法的真正威力。
什麼時候需要使用 FlashText？
簡單的回答是：當關鍵詞數量>500 的時候
當關鍵詞數量>500 的時候，FlashText 的搜索速度開始超過 Regex
完整的回答是：Regex 可以搜索基於特殊字符比如^、$、*、d 等的關鍵詞，而 FlashText 不支持這種搜索。
所以如果想要匹配部分單詞比如『worddvec』，使用 FlashText 並沒有好處，但其非常善於提取完整的單詞比如『word2vec』。
用於尋找關鍵詞的代碼
# pip install flashtext
fromflashtext.keyword importKeywordProcessor
keyword_processor = KeywordProcessor()
keyword_processor.add_keyword('Big Apple', 'New York')
keyword_processor.add_keyword('Bay Area')
keywords_found = keyword_processor.extract_keywords('I love Big Apple and Bay Area.')
keywords_found
# ['New York', 'Bay Area']
使用 FlashText 提取關鍵詞的簡單例子
用於替換關鍵詞的代碼
FlashText 不僅可以提取句子中的關鍵詞還可以對其進行替換。我們將此作爲數據處理管道的數據清理步驟。
fromflashtext.keyword importKeywordProcessor
keyword_processor = KeywordProcessor()
keyword_processor.add_keyword('Big Apple', 'New York')
keyword_processor.add_keyword('New Delhi', 'NCR region')
new_sentence = keyword_processor.replace_keywords('I love Big Apple and new delhi.')
new_sentence
# 'I love New York and NCR region.'
使用 FlashText 替換關鍵詞的簡單例子
原文鏈接：https://medium.freecodecamp.org/regex-was-taking-5-days-flashtext-does-it-in-15-minutes-55f04411025f
本文爲機器之心編譯，轉載請聯繫本公衆號獲得授權。
責任編輯：