RegExの100倍速のFlashTextを使ってデータ分析を行う

データ分析に関しては、**FlashText**は検索や置換を行うためのより高速で信頼性の高いツールです。

*本ブログは英語版からの翻訳です。オリジナルは[こちら](https://www.alibabacloud.com/blog/why-you-should-use-flashtext-instead-of-regex-for-data-analysis_593727)からご確認いただけます。一部機械翻訳を使用しております。翻訳の間違いがありましたら、ご指摘いただけると幸いです。*

テキストやデータの分析を行ったことがある方は、すでに正規表現 (RegEx) に精通しているかもしれません。RegExは、テキスト編集を実行するために必要なツールとして進化してきました。もしあなたがまだテキスト処理の処理に RegEx を使っているのであれば、対処すべき問題があるかもしれません。それはなぜでしょうか？大きなサイズのテキストの場合、RegExの効率が低いためにデータ分析に許容できないほどの時間がかかってしまうことがあるからです。

この記事では、RegExの100倍の速度でデータ解析を行うことができる[Python](https://www.alibabacloud.com/blog/how-to-write-a-headless-web-scraping-bot-in-python_594829?spm=a2c65.11461447.0.0.61739943rkkVz0)ライブラリ「FlashText」を利用する方法をご紹介します。

#RegEx と FlashText の比較
分析を進める前に、最も単純なテキストであっても、ソースデータをきれいにする必要があります。これには、多くの場合、キーワードの検索と置換が含まれます。例えば、コーパス内で "Python" というキーワードを検索したり、"python" をすべて "Python" に置き換えたりします。

RegEx は、数百個のキーワードを検索して置換する必要がある場合には理想的なツールです。しかし、これらの作業の多くは自然言語処理（NLP）を伴います。このような操作に何万回と出くわすこともあるでしょう。このような要件を満たすために RegEx を使用すると、数日かかることになります。

もちろん、プロセスを並列化することでこの問題を解決できると考えるかもしれませんが、実際にはこの解決策では大きな違いはありません。

この問題に対処する他の方法はないのでしょうか？

FlashTextの開発者も、当時同じ問題に直面していました。いくつかの研究をしても結果が出なかったため、彼は新しいアルゴリズムを書くことにしました。

その裏にあるアルゴリズムを理解する前に、検索におけるFlashTextと検索における正規表現の速度を示す比較表を見てみましょう。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/647921/e1a9c99b-705a-a1fc-e5fa-82d2496e3e2d.png)

上の図を見ると、キーワード数の増加に伴って RegEx の処理時間がほぼ直線的に増加していることがわかります。しかし、一方で、キーワードの増加は FlashText には影響しません。

次に、キーワード置換に関する別のチャートを見てみましょう。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/647921/f05b950d-b6c0-d404-99d7-67d0bb17e551.png)

同様に、キーワードの数が増えても、FlashTextの処理時間はほとんど変わりません。

#データクレンジングをより賢く、より速くする方法 - FlashText
FlashTextはその名の通り、キーワードの検索・置換を最速で実行する方法の一つです。これはGitHubにあるオープンソースのPythonライブラリです。

FlashTextを使用する際には、まずキーワードのリストを提供することから始めます。FlashText はこのリストを使って内部の Trie 辞書を構築します。次に、検索するか置換するかに応じてテキストの文字列を送ります。

置換を行う場合は、置換キーワードを含む新しい文字列を作成します。検索を実行するには、文字列内のキーワードのリストを返します。これらのタスクは、文字列を一度だけ繰り返し処理します。

#なぜFlashTextは速いのか？
FlashTextの速さの理由を真に理解するために、例を考えてみましょう。「I like Python」という3つの単語からなる文章を考えてみましょう。4つの単語{Python, Java, J2ee, Ruby}からなるコーパスがあるとします。

コーパス内のすべての単語を選択して、それが文の中に現れるかどうかを確認すると、文字列を4回反復する必要があります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/647921/3205c70c-4f99-3bd3-1917-24825817fe6e.png)

コーパスに含まれるn個の単語に対して、数回の反復が必要です。そして、各ステップ（文の中にある？これがRegExマッチングのロジックです。
また、最初の方法と矛盾する別の方法もあります。それは、文中の各単語について、それがコーパスに存在するかどうかを確認することです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/647921/ea8304ea-311c-f684-5407-01f1f094348f.png)

文中のm個の単語に対して、あなたはm回のサイクルを持っています。この状況では、費やした時間は文中の単語数にのみ依存します。辞書を使ってこのステップを素早く実行することができます。

FlashTextアルゴリズムは、第2の方法を使用しています。さらに、Aho-CorasickアルゴリズムとTrieデータ構造は、そのアルゴリズムにインスピレーションを与えています。

#FlashTextの仕組み
まず、コーパスからTrieデータ構造を作成します。以下のグラフのようになります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/647921/ee20c11d-5f0f-f551-f92d-d76fd3052954.png)

StartとEOT（End of Term）は単語の境界を示します。スペース、コンマ、行の戻り値のいずれかです。両側に境界がある場合はキーワードと一致できます。これにより、パイナップルのリンゴの一致などのケースを防ぐことができます。

「I like Python」という文字列を使って、一文字ずつ検索してみましょう。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/647921/a837de4c-87ed-00ef-9112-f84ac9fa3094.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/647921/d3125fa8-f8f3-23d8-7ed6-35bda70847dd.png)

このアルゴリズムは文字単位で検索するので、1を検索するときには、lが.の直後ではないので、簡単に飛び越えられます。この仕組みにより、存在しない単語をすべてスキップすることができます。

FlashTextアルゴリズムは、"I like Python "という文字列の中のすべての文字を検査します。辞書に100万個のキーワードが含まれていても、実際には動作には影響しません。

#FlashTextを使うのはいつ？
キーワードの数が500を超えるときにFlashTextを使用することをお勧めします。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/647921/e3a72c8f-dcc3-2ff8-7a89-2b2d985059f6.png)

検索の面では、キーワード数が500以上の場合、RegExよりもFlashTextの方がパフォーマンスが高いです。

さらに、RegExは"^, $, *, d "のような特殊文字を検索できますが、FlashTextはそれらをサポートしていません。

部分的な単語（例えば "worddvec"）にはマッチしませんが、完全な単語（"word2vec"）にはマッチします。

FlashTextの基本的な使い方を見てみましょう。試してみてください。RegExよりもはるかに高速であることがわかるでしょう。

以下は、FlashTextを使うのに役立つコードです。
コード：FlashTextを使ってキーワードを検索します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/647921/075cb1ea-d82d-8219-59e2-b22e0c92098c.png)

コード：FlashTextを使ってキーワードを検索します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/647921/15e4489c-6806-998e-2bd9-2758aaa2e289.png)


#結論
この記事を読むことで、RegEx と比較して FlashText の方が優れたツールであるという事実に納得していただければ幸いです。また、特に、RegEx と FlashText のパフォーマンスを表示するグラフを示しました。

*アリババクラウドは日本に２つのデータセンターを有し、世界で60を超えるアベラビリティーゾーンを有するアジア太平洋地域No.1(2019ガートナー)のクラウドインフラ事業者です。
アリババクラウドの詳細は、こちらからご覧ください。
[アリババクラウドジャパン公式ページ](https://www.alibabacloud.com/ja)*