darts-cloneを使って最長一致法で分かち書きしてみる

ホクソエムサポーターの白井です。

呪術廻戦をみて喜久福が食べたくなりました *1。

今回は形態素解析について深堀りしてみます。

日本語の自然言語処理において、形態素解析は必ずといっていいほど通る道です。 形態素解析を必要としないSentencePieceのような深層学習向けのtokenizerも出現していますが、品詞単位で分割する形態素解析が重要であることは変わりありません。

そんなこんなで、『実践・自然言語処理シリーズ2　形態素解析の理論と実装』 (以降「形態素解析本」と表記)を読んでいます。 リンク先の目次を見て分かるとおり、基礎の部分から実装まで説明されている本です。

今回は4章で紹介されている darts-clone を使って、精度は粗いが高速で分かち書きができる最長一致法で、どれぐらい分かち書きが可能かを検証します。

事前知識・辞書引き

辞書を使って分かち書きする場合、単語の検索時間が課題となります。 単語を検索するのではなく、部分文字列から辞書に含まれる単語を探索するためです。

すべての開始位置と終了位置を探索し、辞書に含まれるかどうか判定する場合、計算時間がO(n²)かかります。 (実際はハッシュ値を計算するのに文字列長に依存したコストがかかるため、O(n³)です)

一般的に、効率的な単語の探索には 共通接頭辞検索 (Common Prefix Search) による辞書引きが用いられます。 これは文字列を前から探索し、前方の部分文字列と一致する単語を探す方法です。

共通接頭辞検索には トライ (Trie) と呼ばれるデータ構造を用います。 トライは木構造で、文字を1つのノードとし、遷移することで文字列を表現します。

Booyabazooka (based on PNG image by Deco). Modifications by Superm401., Public domain, via Wikimedia Commons

ダブル配列 はトライの実装方法のひとつであり、darts や darts-clone はその実装ライブラリです。 ダブル配列についての詳しい説明は形態素解析本や darts-cloneに記載の参考文献 を参照してください。

darts-cloneを使ってみる

実際にdarts-cloneを動かしてみます。

単語辞書を準備し、darts-clone形式で構築することを目指します。

単語辞書

辞書はmecab用の辞書であるIPA辞書を使います。 Mecabのページからダウンロードし、インストールします。

デフォルトの文字コードは enc-jp ですが、今回は扱いやすいようにutf-8 に変換します。 darts-cloneで辞書を作成するだけであれば、品詞などの情報が不要なので、単語だけ切り取り、ソートしておきます。

$ iconv -f EUC-JP /path/to/mecab-ipadic/Noun.csv|cut -d"," -f1 |LC_ALL=C sort|uniq > /output/path/Noun.csv

iconvを使って文字コードを変換していますが、configureで文字コードを再構築することもできるようです。(文字コード変更)

また、日本語をソートする場合、sortの前に LC_ALL=C のオプションが必要なので注意しましょう。正しくソートされていないと辞書を構築する際エラーになります。

ちなみに複数ファイルをまとめる場合、awkを使ってiconvをかませました。

$ ls Noun.* | awk '{print "iconv -f EUC-JP " $1}'|sh |cut -d"," -f1 |LC_ALL=C sort|uniq >> /output/path/Noun_all.csv

darts-clone

darts-clone を git clone しインストールします。configure ファイルがないので、autoreconf で configure ファイルを作成します。 このとき、autoreconf automake パッケージをあらかじめインストールしておく必要があります。

Mac OSで試しているため、brew でインストールしていますが、それぞれのOSに合わせて darts-clone をインストールしてください。

$ brew install autoreconf automake
$ autoreconf -i
$ ./configure
$ make

辞書をdarts-clone形式に変換

darts-cloneには、単語一覧をDoubleArrayFile に変換するプログラム mkdarts が付属しているので、それを用います。

$ ./src/mkdarts /path/to/Noun.csv /path/to/ipadic_dict/Noun.dic

keys: 58793
total: 511631
Making double-array: 100% |*******************************************|
size: 275968
total_size: 1103872

名詞だけを変換し、Noun.dic を構築しました。

実際に動くか確認しましょう。 darts を実行すると共通接頭辞検索がインタラクティブに実行できます。

$ ./src/darts /path/to/ipadic_dict/Noun.dic

もも
もも: found, num = 1 3822:6
すもも
すもも: found, num = 2 1996:3 2072:9
ほげ
ほげ: not found

出力ではマッチした要素の個数 (num = 1) と、単語keyに対応するvalueと文字長 (3822:6) が返ってきます。 文字長が単語の長さと一致しないのはバイト文字で表されているためです。 日本語で使う文字の1文字はだいたい3バイトなので、「もも」の結果にある文字長6は2文字 (＝もも)にマッチしたという意味になります。

(もちろん3バイトではない文字もあります。UTF-8の文字コード表 - 備忘帳 - オレンジ工房などで一覧で見られるので参考にしてください。)

共通接頭辞の検索では、複数の単語と一致する場合もあります。 例えば、下の実行結果をみると「すもも」の場合、「す」と「すもも」の2つにマッチしているのがわかります。

$ ./src/darts /path/to/ipadic_dict/Noun.dic

す
す: found, num = 1 1996:3
すも
すも: found, num = 1 1996:3
すもも
すもも: found, num = 2 1996:3 2072:9

最長一致法の実装

darts-cloneを使って、最長一致で分かち書きするプログラムを実装します。 最長一致法は最初の文字から共通接頭辞検索し、一番 長く 一致した単語を採用する、ルールベースの分かち書きです。

「すもももももももものうち」の場合、以下のように実行します。

$ ./src/darts Noun.dic
すもももももももものうち 
すもももももももものうち: found, num = 2 1996:3 2072:9
# 「す」「すもも」 → 「すもも」
もももももものうち
もももももものうち: found, num = 1 3822:6
# 「もも」 → 「もも」
もももものうち
# 
# 中略
# 
のうち
のうち: not found
# 一致単語なし → 「の」
うち
うち: found, num = 1 358:6
# 「うち」→ 「うち」

ここで注意したいのは以下の2点です。

• 「す」「すもも」の2つと一致する場合、長い「すもも」を1単語する
• 「のうち」のように一致する単語がない場合、一番最初の1文字である「の」を1単語とする

結果「すもも/もも/もも/もも/の/うち」と分割できました。 名詞辞書だけの場合、「も」1文字ではなく「もも(桃)」で分割されていますね。

この例だと最長一致法では全然うまくいかないように見えますが、「スモモも桃も桃のうち」のようにカタカナ・漢字を混ぜると正しく分割されそうなことは感覚的にわかるかと思います。

実際、形態素解析本には以下のように述べられています。

単純なアルゴリズムにもかかわらず，90%以上の分割精度が得られるため，大規模なテキスト集合から大ざっぱな単語頻度を高速に求める処理に向いています.

実践・自然言語処理シリーズ2　形態素解析の理論と実装 P76

では、どれぐらいの精度で分割可能なのか確かめてみます。

python実装

ここからはdarts-cloneのpythonバインディングを利用し、pythonで実装します。 darts-clone-pythonはSudachiPyにも使われているdarts-cloneのpythonバインディングです。

形態素解析本のC++実装とSudachiPyの実装を参考にしつつ実装します。

Python 3.8 で動作確認しています。 darts-clone-pythonは v0.9.0 です。

import sys
import dartsclone


class DartsDict:
    def __init__(self, filename):
        self.trie = self.load_darts(filename)

    @staticmethod
    def load_darts(filename):
        darts = dartsclone.DoubleArray()
        darts.open(filename)
        return darts

    def longest_match(self, line: str):
        line_b = line.encode("utf-8")
        begin_str = 0
        begin = 0
        end = len(line_b)
        while begin < end:
            longest_length = 0
            key = line_b[begin:]
            result = self.trie.common_prefix_search(key, length=len(key))
            for (word_id, length) in result:
                longest_length = max(longest_length, length)

            if longest_length == 0:
                # 一致する単語がなかった場合
                longest_length = len(line[begin_str].encode("utf-8"))

            word = line_b[begin:begin+longest_length].decode()
            yield word

            begin += longest_length
            begin_str += len(word)


def sample():
    darts = DartsDict("/path/to/ipadic_dict/Noun.dic")
    for w in darts.longest_match("すもももももももものうち"):
        print(w)
    print("EOS")


def main(dic_file, text_file):
    darts = DartsDict(dic_file)
    with open(text_file, "r")as f:
        for line in f:
            words = []
            for w in darts.longest_match(line.strip()):
                words.append(w)
            print(" ".join(words))


if __name__ == '__main__':
    args = sys.argv[1:]
    if len(args) < 2:
        print("Usage: python main.py dic_file text_file")
    else:
        main(args[0], args[1])

検証

実装したところで、最長一致法でどこまで正確に分かち書きできるのか検証していきます。

今回は livedoor ニュースコーパス のテキストを使ってmecabの分かち書きと比較していきます。

データ

livedoor ニュースコーパスからダウンロードできるデータ ldcc-20140209.tar.gz の記事から、トピックごとそれぞれ1つずつ、合計9つの文書を使います。

具体的にはディレクトリごとsortして一番上のテキストデータを使いました。 ただし、1~2行目のURL・日付は取り除いてます。

辞書はipadic (mecab-ipadic-2.7.0-20070801) のcsvを使って4種類作成しました。 名詞・動詞を選んだのは単語数が多く、重要度が高いと予想したためです。

名前	説明	単語数
Noun	名詞・一般 (Noun.csv) だけ	58,793
NounAll	全ての名詞 (Noun*.csvで指定)	197,489
Verb	動詞 (Verb.csv)だけ	101,751
NounVerb	NounAll + Verb	296,935

mecabのIPA辞書を使った -Owakati の出力結果を正解データとし、正解データと一致したかどうかで評価します。 MevAL の 単語境界判定のエラー分析 をベースに評価コードを作成しました。

def eval_line(gold, pred):
    gold_cnt, pred_cnt = 0, 0
    idx = 0
    tp, fp, fn = 0, 0, 0
    for g in gold:
        gold_cnt += len(g)
        if g == pred[idx]:
            # print("true ", g, pred[idx])
            tp += 1
            pred_cnt += len(pred[idx])
            idx += 1
        else:
            if gold_cnt < pred_cnt + len(pred[idx]):
                fn += 1
                # print("fn  ", g, pred[idx])
            else:
                tmp = []
                while gold_cnt > pred_cnt:
                    tmp.append(pred[idx])
                    pred_cnt += len(pred[idx])
                    idx += 1
                    fp += 1
                # print("fp  ", g, " ".join(tmp))
    return tp, fp, fn

結果と考察

文書ごとのF値は以下の表のとおりです。 基本的に単語数が多いほどF値は高い結家となりました。

	Noun	NounAll	Verb	NounVerb	行数
dokujo-tsushin-4778030.txt	0.593	0.725	0.556	0.766	25
it-life-hack-6292880.txt	0.567	0.680	0.449	0.725	32
kaden-channel-5774093.txt	0.659	0.807	0.574	0.849	19
livedoor-homme-4568088.txt	0.693	0.847	0.565	0.878	18
movie-enter-5840081.txt	0.612	0.702	0.642	0.788	23
peachy-4289213.txt	0.638	0.765	0.534	0.795	16
smax-6507397.txt	0.485	0.536	0.425	0.555	79
sports-watch-4597641.txt	0.614	0.780	0.562	0.841	10
topic-news-5903225.txt	0.517	0.607	0.463	0.658	58

一番F値が良いのNounVerbのprecisionとrecallをみてみるとprecisionが低いことがわかります。 FalsePositive(正解にはない境界があると予測)、つまり正解より細かく分割している数が多いということです。

	precision	recall	F1
dokujo-tsushin-4778030.txt	0.683	0.872	0.766
it-life-hack-6292880.txt	0.585	0.954	0.725
kaden-channel-5774093.txt	0.770	0.946	0.849
livedoor-homme-4568088.txt	0.802	0.970	0.878
movie-enter-5840081.txt	0.695	0.909	0.788
peachy-4289213.txt	0.704	0.912	0.795
smax-6507397.txt	0.398	0.919	0.555
sports-watch-4597641.txt	0.765	0.934	0.841
topic-news-5903225.txt	0.507	0.937	0.658

具体的に分割結果をみてみます。

まず、以下のように名詞、特に漢字が多い文においてはほぼ同じ分割になりました。

今月 8 日 、 都内 ホテル で は 、 総合 格闘 家 ・ 吉田 秀彦 の 引退 試合 興行 「 ASTRA 」 の 開催 が 発表 さ れ た 。

今月 8 日 、 都内 ホテル で は 、 総合 格闘 家 ・ 吉田 秀彦 の 引退 試合 興行 「 A S T R A 」 の 開催 が 発表 され た 。 上がmecab、下がNounVerbの分割 sports-watch-4597641.txt

一方、辞書の問題として、「Twitter」や「TV」のような英単語が「T w i t t e r」「T V」と1文字ごと分割されてしまう課題があります。 これは英単語を辞書に登録することで解消されるはずです。

画面 下 に は Facebook 、 Twitter 、 SHARE （ Facebook 、 Twitter 、 メール 、 SMS ） で の 共有 、

画面 下 に は F a c e b o o k 、 T w i t t e r 、 S H A R E （ F a c e b o o k 、 T w i t t e r 、 メール 、 S M S ） で の 共有 、 上がmecab、下がNounVerbの分割 smax-6507397.txt

しかしながら、「すももも〜」と同様、ひらがなの多い部分については最長一致というルール上、mecabと同じ結果を出力することができないです。

その 過半数 は 毎年 5 , 000 円 程度 かかる 更新 費用 や その 手続き について 不満 を 持っ て いる 。(中略)性能 面 で 劣る の で は という 不安 から 導入 を 控え て いる という 状況 に ある 。

そ の 過半数 は 毎年 5 , 0 0 0 円 程度 かかる 更新 費用 や そ の 手続き につい て 不満 を 持っ てい る 。(中略)性能 面 で 劣る の で はと いう 不安 から 導入 を 控え てい る とい う 状況 に ある 。 上がmecab、下がNounVerbの分割 it-life-hack-6292880.txt

上の例ではNounVerbが「持っている」「控えている」について、「持っ/てい/る」「控え/てい/る」と左に最長であるように分割されます。 ですが、正しい分割は以下のように「て/いる」であり、「いる」が動詞であるように分割したい部分です。

持っ    動詞,自立,*,*,五段・タ行,連用タ接続,持つ,モッ,モッ
て      助詞,接続助詞,*,*,*,*,て,テ,テ
いる    動詞,非自立,*,*,一段,基本形,いる,イル,イル

おわりに

最長一致法を実装しながら、ダブル配列ライブラリdarts-cloneの使い方を解説しました。

ナイーブな最長一致法は高速かつ、ある程度は使える実装ですが、分割には課題点もあります。

mecabの実装のように、最適化アルゴリズムを使うべきだというお気持ちがちょっと分かった気がします。

また、今回は細かい部分は割愛して darts.open(filename) で辞書を読み込みましたが、形態素解析本では全部をメモリに載せず メモリマップトファイル (pythonでは mmap) を使って最適化する実装が提案されています。

実際、IPA辞書の全単語でdarts-cloneの辞書を構築してメモリに乗せようとするとsegmatation faultします……。 この記事はあくまで「使ってみた」系記事ですので、ご了承ください。

参考資料

mecabとdarts関連

• mecab https://taku910.github.io/mecab/
• darts http://chasen.org/~taku/software/darts/
• Applying Conditional Random Fields to Japanese Morphological Analysis (paper)
• 実践・自然言語処理シリーズ 第2巻 形態素解析の理論と実装

おまけ資料：SudachiPyで最長一致法

前述のように、SudachiPyはdarts-cloneで辞書引きしているので、実装されたクラスをうまく活用すれば最長一致法での分かち書きが実装できます。

具体的には BinaryDictionary クラスで辞書の設定をしているので、そこから単語辞書 (DoubleArrayLexiconのインスタンス)だけを抜き出して使います。

ちなみにDoubleArrayLexiconでは mmap を使った辞書の読み込みを行ってます。

from pathlib import Path
from sudachipy.dictionarylib.binarydictionary import BinaryDictionary

# 辞書のパス
system_dic = (Path(import_module('sudachidict_core').__file__).parent / 'resources' / 'system.dic') 

dict_ = BinaryDictionary.from_system_dictionary(system_dic)
lexicon = dict_.lexicon


def longest_match(line: str):
  line_b = line.encode("utf-8")
  begin_str = 0
  begin = 0
  end = len(line_b)
  while begin < end:
    longest_length = 0
    longest_word_id = None
    for (word_id, length) in lexicon.lookup(line_b, begin):
      if longest_length < length:
        longest_length = length
        longest_word_id = word_id


    if longest_length==0:
      # print(line[begin_str])
      longest_length = len(line[begin_str].encode("utf-8"))

    word = line_b[begin:longest_length].decode()
    yield word

    begin = longest_length
    begin_str += len(word)

SudachiPyは v0.4.9 で確認しています。

SudachiPyの辞書であるSudachiDict の語彙数が多いため、結構正確に分割できると思います。 当たり前ですがSudachiPyより高速です。

実践・自然言語処理シリーズ2　形態素解析の理論と実装

*1:宮城にしかないと思っていたのですが、ググったら関東にも店舗を出店しているみたいで、正直驚いています。