見出し語化の高速化 - TorasenLab@はてな

nltkのWordNetLemmatizerを力ずくで高速化した。

環境

コード

# -*- coding: utf-8 -*-

from collections import defaultdict
import nltk
from nltk.corpus import wordnet as _wordnet


_STEMMER = nltk.PorterStemmer().stem
_LEMMATIZATION_POS_PRIORITY = (_wordnet.NOUN, _wordnet.VERB,
                               _wordnet.ADJ, _wordnet.ADV)
_POS_LIST = (_wordnet.ADJ, _wordnet.ADV, _wordnet.NOUN, _wordnet.VERB)


def stem_form(form):
    return _STEMMER(form)


def _detect_pos(form):
    form = form.replace(' ', '_')
    synsets = _wordnet.synsets(form)
    if not synsets:
        return None
    pos = None
    stem = stem_form(form)
    for synset in synsets:
        if stem_form(synset.name[:-5]) == stem:
            pos = synset.pos
            break
    if pos is None:
        pos = synsets[0].pos
    if pos == _wordnet.ADJ_SAT:
        pos = _wordnet.ADJ
    return pos


def lemmatize_with_wordnet(form, pos=None):
    if pos is None:
        pos = _detect_pos(form)
        if not pos:
            return form
    assert(pos in _POS_LIST)
    return nltk.WordNetLemmatizer().lemmatize(form, pos=pos)


def _lemmatize_form_with_wordnet(form, pos_set):
    assert(pos_set)
    if len(pos_set) == 1:
        target_pos = pos_set.copy().pop()
    else:
        target_pos = _detect_pos(form)
        if not target_pos or target_pos not in pos_set:
            for pos in _LEMMATIZATION_POS_PRIORITY:
                if pos in pos_set:
                    target_pos = pos
                    break
    assert(target_pos in _POS_LIST)
    return nltk.WordNetLemmatizer().lemmatize(form, pos=target_pos)


def _construct_inflected_form_to_lemma_dictionary():
    all_inflected_forms = defaultdict(set)
    for pos, excepted_forms in _wordnet._exception_map.iteritems():
        if pos == _wordnet.ADJ_SAT:
            continue
        for excepted_form in excepted_forms:
            all_inflected_forms[excepted_form].add(pos)

    for pos in _POS_LIST:
        substitutions = _wordnet.MORPHOLOGICAL_SUBSTITUTIONS[pos]
        for lemma in _wordnet.all_lemma_names(pos=pos):
            lemma = lemma.replace('_', ' ')
            all_inflected_forms[lemma].add(pos)

            form = lemma
            if pos == _wordnet.NOUN and form.endswith('ful'):
                suffix = 'ful'
                form = form[:-3]  # len('ful')
            else:
                suffix = ''
            for new_suffix, old_suffix in substitutions:
                if form.endswith(old_suffix) or old_suffix == '':
                    if old_suffix == '':
                        inflected_form = form + new_suffix
                    else:
                        inflected_form = form[:-len(old_suffix)] + new_suffix
                    inflected_form += suffix
                    all_inflected_forms[inflected_form].add(pos)
    inflected_form_to_lemma = {}
    for inflected_form, pos_set in all_inflected_forms.iteritems():
        lemma = _lemmatize_form_with_wordnet(inflected_form, pos_set)
        inflected_form_to_lemma[inflected_form] = lemma.replace('_', ' ')
    return inflected_form_to_lemma


_INFLECTED_FORM_TO_LEMMA = _construct_inflected_form_to_lemma_dictionary()


def lemmatize_with_dict(form):
    try:
        return _INFLECTED_FORM_TO_LEMMA[form.lower().replace(' ', '_')]
    except KeyError:
        pass
    return form.lower()


def _test():
    test_forms = ('media', 'playing', 'player', 'possesses', 'sung', 'became',
                  'begun', 'fallen', 'men', 'buses', 'initial', 'initialization')
    print 'original\tstemming\twordnet_lemmatizer\tlemmatize_with_dict'
    for form in test_forms:
        print ('{0}\t{1}\t{2}\t{3}').format(form,
                                            stem_form(form),
                                            lemmatize_with_wordnet(form),
                                            lemmatize_with_dict(form))


if __name__ == '__main__':
    _test()

'''
original        stemming   wordnet_lemmatizer   lemmatize_with_dict
media           media      medium               medium
playing         play       playing              playing
player          player     player               player
possesses       possess    posse                possess
sung            sung       sung                 sung
became          becam      become               become
begun           begun      begin                begin
fallen          fallen     fall                 fall
men             men        man                  man
buses           buse       bus                  bus
initial         initi      initial              initial
initialization  initi      initialization       initialization
'''

nltkのWordNetLemmatizerの動作は、入力語句に対して以下の手順で見出し語化を行っているようです。

入力語句が例外リストに載っていないかどうかチェックする。載っていれば別途処理する。
末尾置換ルールを用いて入力語句の末尾を置換する。
辞書の見出し語に語句が存在しているかどうかをチェックする。
末尾置換ルールが無くなるまで手順2.と3.を繰り返す。

手順1.の例外リストとは、主に不規則変化(sing-sang-sungなど)を解決するための手順のようです。
手順2.と手順3.では、あらかじめ用意された末尾置換ルールを使用します。
例えば入力語句が名詞であり、xesで終わっている場合、末尾からxesを取り除き、代わりにxを追加する。その後、置換した単語が辞書の見出し語にあるかどうかをチェックする。例えば入力語句がboxesであるとき、末尾のxesをxに置換しboxとし、その後boxが辞書の見出し語にあるかどうかチェックする。

ソースコードを読む限り、nltkのWordNetLemmatizerは本家WordNetのC言語実装と同様の手順で見出し語化を行っているらしい。

末尾の置換、検索、を繰り返しているので実行速度が遅い。
そこで、これら例外リストと置換ルールを使用して、WordNetLemmatizerが処理できる語句をすべて生成する。
それらWordNetLemmatizerが処理できる語句をキーとし、それらの見出し語を値とする辞書(_INFLECTED_FORM_TO_LEMMA)を作成した。
{'boxes': 'box', 'box': 'box', ..., 'media': 'medium', 'medium': 'medium', ...}のような活用形がキーであり、見出し語が値である辞書。

実行速度テスト

http://americannationalcorpus.org/OANC/index.htmlから抽出した16,814,123個の英単語(296,528種類)に対して、見出し語化にかかる時間を測った。

nltkのWordNetLemmatizerによる見出し語化(lemmatize_with_wordnet)では3583秒(およそ1時間)、
nltkのWordNetLemmatizerによる見出し語化(lemmatize_with_wordnet)の入出力をキャッシュした場合では80秒、
今回作成した作成した辞書を使用した見出し語化(lemmatize_with_dict)では20秒、

となった。結局入出力をキャッシュした場合と大差無い結果になった。
しかし、入出力をキャッシュする場合、WordNetに登録されていない単語や固有名詞などが入力されるたび、キャッシュのサイズが大きくなる。
その点、今回作成した辞書のサイズは固定されているので、メモリ消費量の増加などを気にしなくて良い。
今回作成した辞書にも問題点がある。今回作成した辞書では、入力語句から出力が一意に決まるが、通常は一意には決まらない。例えば、betterの見出し語はwellかgoodかは品詞を用いない限り決めにくい。