こんにちは。 DSOC R&D グループの高橋寛治です。
Pythonの辞書オブジェクトは取り扱いやすいため、単語とIDの変換テーブルを作ったり、複合語の結合のためにデータ構造を工夫して簡易なトライ木を構築したりと、自分でコーディングすることがあるかと思います。
上記の場合は、ライブラリDAWGを使うことで省メモリかつ高速に、さらにできることが増えるかもしれません。 今回はそんな便利なライブラリの紹介をします。
辞書ライクなライブラリDAWG
DAWGはDirected Acyclic Word Graphのそれぞれの頭文字をとったものです。 日本語だと有向無閉路単語グラフでしょうか。
英語のWikipediaのページに少し詳しい説明があります。 トライ木に比べて、頂点の数がかなり少なくなるデータ構造であることが特徴のようです。
利用者側としては、省メモリかつ高速に辞書引きや共通接頭辞検索ができるライブラリであるということを押さえておくといいかと思います。
共通接頭辞検索とは、共通の接頭辞を持つキーを見つける検索のことです。 かな漢字変換システムにおける、かなと漢字の対応表を見つける箇所での利用がわかりやすい例です。 「きょういく」というかなを漢字に変換する場合を考えます。候補は「き」「きょ」「きょう」「きょうい」「きょういく」となり、それぞれに対応する漢字があります。 「きょう」で候補を定めたとすると、次は「いく」に対して「い」「いく」に対応する漢字をまた引きます。 このように共通の接頭辞に対して候補を高速に引くことがき、なおかつ省メモリで保持することができます。
DAWGのPython実装の公式ドキュメントはこちらです。
インストールは pip install DAWG で完了します。
公式ドキュメントのUsageに書いているDAWGクラスを簡単に紹介します。
dawg.DAWG: ユニコード文字のキーを保持し、検索が可能ですdawg.CompletionDAWG:dawg.DAWGのサブクラスであり、共通接頭辞検索などが可能ですdawg.BytesDAWG:dawg.CompletionDAWGのサブクラスであり、ユニコード文字のキーに対してbytesオブジェクトのリストを対応させますdawg.RecordDAWG:dawg.BytesDAWGのサブクラスであり、 Pythonのstructでパッキングされたデータをユニコード文字のキーに対応させます
dawg.IntCompletionDAWG:dawg.CompletionDAWGのサブクラスであり、ユニコード文字のキーに対して、数値を対応付けます
dawg.IntDAWG:dawg.DAWGのサブクラスであり、ユニコード文字のキーに対して、数値を対応づけます
複合語処理での利用
私はこのライブラリをルールベースでの形態素列の結合による複合語処理によく利用しますので、その実装方法を紹介します。
ある形態素列を入力し、複合語として結合可能かを先頭から判定します。 例えば「ルールベース」をMeCab IPADicで解析すると「ルール」と「ベース」に分割されます。 これを辞書で「ルールベース」は一語と認定します。
[1]: import dawg [2]: completion_dawg = dawg.CompletionDAWG(["ルール", "ルールベース"]) [3]: sentence = ["ルール", "ベース", "の", "解析"] [4]: completion_dawg.prefixes("".join(sentence)) : ['ルール', 'ルールベース']
分かち書きされた文を文字列に戻し、DAWGライブラリで共通接頭辞検索(メソッド prefixes)を行うと、「ルール」と「ルールベース」という単語が見つかります。
最長一致で候補を決定する方式であれば「ルールベース」を採用します(コード内では文字数最大のリストの添え字を取得)。
その後は、「の解析」に対して同様に共通接頭辞検索を行います。
[5]: import numpy as np [6]: common_prefixes = ['ルール', 'ルールベース'] [7]: np.argmax(list(map(len, common_prefixes))) : 1 [8]: def get_skip_index(surface, sentence): ...: for i in range(1, len(sentence)): ...: if surface == "".join(sentence[:i]): ...: return i ...: raise Exception(f"No such string '{ surface }' in the sentence.") [9]: get_skip_index("ルールベース", sentence) : 2
変数 sentence 中の2単語を結合すればよいことがわかります。
あとは、合致した分だけスキップしながら文末まで走査すれば、最長一致の単語列を取得することができます。
結合する単語は、新しく単語クラスを作ったり、文字列でそのままくっつけたりと、用途により変更すると良いでしょう。
便利なライブラリを使う
今回は、日頃使っている便利な辞書・共通接頭辞検索が可能な省メモリなライブラリを簡単に紹介しました。
アルゴリズムを実装することは楽しいですが、テストが書かれ効率の良い実装をされているライブラリを使っておくと、実運用向けの実装への移行が楽かと思います。
▼本連載のほかの記事はこちら
buildersbox.corp-sansan.com
執筆者プロフィール
高橋寛治 Sansan株式会社 DSOC (Data Strategy & Operation Center) R&Dグループ研究員
阿南工業高等専門学校卒業後に、長岡技術科学大学に編入学。同大学大学院電気電子情報工学専攻修了。在学中は、自然言語処理の研究に取り組み、解析ツールの開発や機械翻訳に関連する研究を行う。大学院を卒業後、2017年にSansan株式会社に入社。キーワード抽出など自然言語処理を生かした研究開発に取り組む。
