この記事はNikkei Advent Calendar 2021の10日目の記事です。

正規表現を使った文字列検索は検索対象の文書ファイルが大きく、正規表現のパターンが複雑であるほど実行時間がかかるというデメリットがあります。 その欠点を補う、文書に対してインデックスを作成する方法がありますが、データベースに保存されない文書に対してはあまり有効な解決方法とはいえません。 例えば、記事テキストから複数の企業名を取得して分析を行いたい場合はなるべくデータベースを使わず処理をしたいからです。

FlashTextは正規表現よりも高速に文字列を検索・置換可能なアルゴリズムです。 データベースやインデックスの準備が必要ないため、最小限の環境設定だけで簡単に使うことができます。

FlashTextはPython実装が GitHub で公開されており、pipでインストールして使うことができます。 ドキュメントでは英語での使用例しか載っていないため、日本語の文字列検索ができるか試します。

FlashTextの仕組み

アルゴリズムの詳細について、論文(Replace or Retrieve Keywords In Documents At Scale) が公開されています。

FlashTextはトライ(Trie)に基づいたアルゴリズムです。 トライ辞書は文字 (char) 単位でノードに登録していきます。 javaとj2eeを登録する場合、ルートからjまでは同じノードを共有し、それ以降の (j)ava と (j)2ee はそれぞれ別のノードとして登録します。

（Replace or Retrieve Keywords In Documents At Scale より）

探索・置換の際はこのトライ辞書を探索します。トライ辞書を探索した結果 eot (end of term) にたどり着けばその単語列を出力もしくは置換します。

FlashTextがインスパイアされたアルゴリズムとしてエイホ–コラシック法 が言及されていますが、仕組みが一部異なります。

エイホ–コラシック法では構築したトライ木においてノードのサフィックス(接尾)と一致するノードがあればリンクしておきます(failure link)。 これにより探索途中で続くノードがない場合でもルートに戻らず連続的に探索が可能になっています。

FlashTextの場合、探索中に続くノードがない時はトライ木のルートに戻ります。 そのため、入力の最初の位置からの最長一致が優先され、部分文字列は取得しません。探索は一方向です。

例えば、キーワードとして「ab」と「abc」が登録されていた場合、「abcd」から取得できるキーワードは「abc」だけです。 これにより計算時間を平均して $\mathcal{O}(N)$($N$は入力文書の文字数) まで高速化できています。

英語テキストで使う

理論的な話はここまでにして、実際に使って挙動を確かめます。

実行環境は以下の通りです。

• Python 3.8.0
• flashtext==2.7

KeywordProcessor を宣言し、キーワードを追加します。

from flashtext import KeywordProcessor

# initialize
processor = KeywordProcessor()

# add keyword one by one
processor.add_keyword("keyword")
processor.extract_keywords("I love keyword and keywords.")

>> ['keyword']

テキスト中の keyword を抽出できました。 置換に使いたい場合、 add_keyword で対象のキーワードと置換後のキーワードの2つ引数を渡します。

processor.add_keyword("newspaper", "Nikkei")

processor.replace_keywords("I read newspaper. Some keyword.")
>> 'I read Nikkei. Some keyword.'

キーワードをまとめて登録するために add_keywords_from_list や add_keywords_from_dict も用意されています。詳しくはドキュメントを参照してください。

日本語で使う

日本語を単語単位で抽出するにはFlashTextの仕組みをうまく使う必要があります。

# initialize
ja_processor = KeywordProcessor()
ja_processor.add_keywords_from_list(["日本経済新聞", "日経新聞", "日経", "Nikkei"])

ja_processor.extract_keywords("日本経済新聞は、常に言論報道機関としての日経の基盤になっています。")
>> ['日本経済新聞', '日経']

ja_processor.extract_keywords("日経新聞は日経を部分文字列として含みます。")
>> ['日経新聞', '日経']

冒頭で説明した通り、最長一致でキーワードを取得するため 日経新聞 からは 日経新聞 しか抽出されません。

# span_info で抽出位置を出力できる
ja_processor.extract_keywords(
   "日経は日経新聞の部分文字列です。日経産業新聞や日経MJといったメディアもあります。", 
   span_info=True
)
>> [('日経', 0, 2), ('日経新聞', 3, 7), ('日経', 16, 18)]

日経産業新聞 からは 日経 が取得されてしまいますが 日経MJ からは取得されません。

トライ辞書は単語境界(word_boundary)かどうかで単語の切れ目を判断します。 判断には単語境界では ない 文字条件である non_word_boundary を使っています。 デフォルトでは [A-Za-z0-9] 、英数字である限り探索する仕組みになっています。

日経MJ の場合 MJ が non_word_boundary に含まれているため 日経 ではなく、続く MJ も含めた文字列が一単語と判断されます。 そのため、 日経MJ からは 日経 が取得されません。

上記結果からわかる通り、non_word_boundary ではない文字についても、トライ辞書に登録されていればキーワード探索は可能です。

# スペースが開いていない単語は取得しない
ja_processor.extract_keywords(
   "Nikkei Financial and NikkeiFinancial and Nikkei/Style", 
   span_info=True
)
>> [('Nikkei', 0, 6), ('Nikkei', 41, 47)]

日本語のキーワードでなるべく厳密にキーワード抽出を行う方法について考えます。

まず、最長一致を利用して、なるべく長い単語（正式名称・類似語）もキーワードとして一緒に追加する方法が考えられます。

processor = KeywordProcessor()
processor.add_keywords_from_list(["コロナ", "ナウイ"])

processor.extract_keywords("新型コロナウイルスの感染状況", span_info=True)
>> [('コロナ', 2, 5)]
processor.extract_keywords("シンガタコロナウイルスの感染状況", span_info=True)
>> [('コロナ', 4, 7)]

# 最長一致するようキーワードを追加
processor.add_keyword("コロナウイルス")
processor.extract_keywords("新型コロナウイルスの感染状況", span_info=True)
>> [('コロナウイルス', 2, 9)]

processor.add_keyword("新型コロナウイルス")
processor.extract_keywords("新型コロナウイルスの感染状況", span_info=True)
>> [('新型コロナウイルス', 0, 9)]

辞書で渡せば複数の表記について集約もできます。

corona_processor = KeywordProcessor()
corona_processor.add_keywords_from_dict({"コロナ": ["新型コロナウイルス", "コロナウイルス", "コロナ"]})

corona_processor.extract_keywords("新型コロナウイルスの感染状況", span_info=True)
>> [('コロナ', 0, 9)]
corona_processor.extract_keywords("コロナの影響", span_info=True)
>> [('コロナ', 0, 3)]

非単語境界を日本語に対応させる方法もあります。 下の例ではnon_word_boundary にカタカナを追加することで「コロナウイルス」から「コロナ」を抽出しないようにしました。 （ちなみに non_word_boundary はset型のため、漢字ひらがなカタカナ全て追加するのは実用的でない気がします……）

processor = KeywordProcessor()
processor.add_keyword("コロナ")

# カタカナを 非単語境界 に追加
word_boundaries = processor.non_word_boundaries # set型
katakana = [chr(ord("\u30A1") + i) for i in range(ord("\u30FF") - ord("\u30A1"))]
word_boundaries.update(katakana)
processor.set_non_word_boundaries(word_boundaries)

processor.extract_keywords("新型コロナウイルスの感染状況", span_info=True)
>> []

processor.extract_keywords("新型コロナの感染状況", span_info=True)
>> [('コロナ', 2, 5)]

processor.extract_keywords("シンガタコロナの感染状況", span_info=True)
>> []

記事テキストから企業名を取得する

FlashTextを利用して、記事本文から企業名を抽出してみます。 正規表現との速度も比較します。

データ

企業名 2000

• 日経で管理しているデータベースから取得した紙面用の名称
• ノイズを減らすため3文字以上の企業名のみフィルター

記事 2000

• 2021年8月公開の日経電子版の記事から抜粋
• 合計文字数 1,239,493文字
• 1記事あたりの文字数平均 619文字
• 分かち書きなどの前処理なし

結果

FlashTextはデフォルトの設定で企業名リストをキーワードとして登録し、正規表現は | を使って単純に連結したパターンを設定しました。

実行時間は以下の画像の通りです。FlashTextは528msと1秒以下なのに対し、正規表現は2.1sかかってます。 今回はキリのいいデータ数で検証していますが、企業名を倍以上増やしてもFlashTextの速度は1秒以下のままでした。

出力結果の違いについても確認します。

今回、正規表現は | で繋げただけなため、最短一致・最長一致が考慮できていません。 例えば以下の例文の場合、パターンによって出力が変わるため、長い単語から繋げる必要があります。

ヤマハはヤマハ発動機との持ち合い解消を進め、売却で得た資金をもとに280億円を上限とする……

https://www.nikkei.com/article/DGXZQOUC116NR011082021000000/

yamaha_text = "ヤマハはヤマハ発動機との持ち合い解消を進め、売却で得た資金をもとに280億円を上限とする……"
re. findall("ヤマハ発動機|ヤマハ", yamaha_text)
>> ['ヤマハ', 'ヤマハ発動機']

re. findall("ヤマハ|ヤマハ発動機", yamaha_text)
>> ['ヤマハ', 'ヤマハ']

一方FlashTextは最長一致で取得するためキーワードを登録した順番は関係ありません。

keyword_processor.extract_keywords(yamaha_text)
>> ['ヤマハ', 'ヤマハ発動機']

デフォルトの設定でもかなり良い結果をえられましたが、デフォルトで大文字と小文字を区別しないため、一部誤って取得するケースがありました。

keyword_processor.extract_keywords("ｉＤｅＣｏ（個人型確定拠出年金）")
>> ['ＩＤＥＣ']

これは初期設定で KeywordProcessor(case_sensitive=True) を指定すると解消されます。

おわりに

高速でキーワード検索・抽出ができるFlashTextを紹介しました。

日本語でも問題なく使えるので、手軽に使えるツールとしてもっと広まればいいなと思っています。 ぜひ試してみてください。