NLP | 分析ノート

2019-05-122021-09-21

標準化レーベンシュタイン距離は距離関数なのか

以前の記事で、標準化レーベンシュタイン距離(標準化編集距離)というのを紹介し、
自分も使っていたのですが挙動に少し違和感があったので確認しました。

レーベンシュタイン距離はその名の通り、距離関数なのですが、
これを標準化してしまうとどうも距離関数っぽくない動きをしてるように思えたのです。

念の為、距離関数というもの自体の定義をおさらいしておきましょう。

集合$X$に対して、$d:X\times X \rightarrow \mathbb{R}$ が距離関数であるとは、
$x,y,z \in X$に対して次の条件が成り立つ時に言います。
1. $d(x,y) \geq 0$ (非負性)
2. $d(x, y) = 0 \Leftrightarrow x = y$ （同一律）
3. $d(x, y) = d(y, x)$ (対象律)
4. $d(x, z) \leq d(x, y) + d(y, z)$ (三角不等式)

この条件のうち、 1. 2. 3. は特に問題ないのですが、
標準化レーベンシュタイン距離については、4. の三角不等式がちょっと怪しかったです。
で、反例を探してみたところ簡単に見つかりました。
$ld(*,*)$をレーベンシュタイン距離、$nld(*,*)$を標準化レーベンシュタイン距離とし、
x = ‘ab’, y= ‘aba’, z = ‘ba’ とおきます、
すると、
$ld(x, z) = 2$ なので、$nld(x, z) = 1$ ですが、
$ld(x, y) = ld(y, z) = 1$ なので、$nld(x, y) = nld(y, z) = \frac13$ です。

そのため、 $nld(x, z) > nld(x, y) + nld(y, z) = \frac23$ となり、
三角不等式を満たしません。

標準化レーベンシュタイン距離は標準化レーベンシュタインという名前の距離関数と考えるのは誤りで、
レーベンシュタイン距離という距離関数を標準化したもの(その結果距離関数ではなくなってしまったもの)と、
考える必要があります。

現状これで激しく困ったということはないのですが、
一部のライブラリにある、自分で作った距離関数を引数に渡せるようなものには、
標準化レーベンシュタイン距離は突っ込まない方が安全そうです。

2019-05-072019-05-05

標準化レーベンシュタイン距離

以前の記事で、レーベンシュタイン距離を計算できるライブラリを紹介しました。
参考:pythonで編集距離(レーベンシュタイン距離)を求める

どちらかというと、ライブラリよりもアルゴリズム側の説明の続きなのですが、
標準化されたレーベンシュタイン距離(normalized Levenshtein distance)というものも提案されています。
これは、二つの文字列のレーベンシュタイン距離を、文字数が多い方の文字数で割った値として定義されます。
固有名詞の名寄せなどでレーベンシュタイン距離を使う場合、
こちらを使った方がうまく行くことが多いようです(個人的な経験から。)

以前紹介した、 python-Levenshtein に
実装されているんじゃないかと期待してしばらく調べていたのですが、どうやらこれは実装されてないようです。
特にLevenshtein.ratio という関数に期待したのですがこれは全然違いました。

ということで自分で実装しましょう。


import Levenshtein


def normalized_distance(text0, text1):
    dist = Levenshtein.distance(text0, text1)
    max_len = max(len(text0), len(text1))
    return dist / max_len

関数名は normalized_levenshtein_distance にしたかったが流石に長すぎるので少し短縮。
ただ、これでも長いですね。(pep8的につらい)

これによって、例えば通常のレーベンシュタイン距離では、
“バニラ” と “アイス”　の組み合わせも “チョコレート” と “チョコレートアイス” もどちらも距離は3でしたが、
標準化した距離を使うことで、
前者は距離1、後者は 1/3(=0.333…)と算出されるようになり、前者の方が離れてると見なせます。

使ってみた結果がこちら。


print(Levenshtein.distance("アイス", "バニラ"))  # 3
print(Levenshtein.distance("チョコレートアイス", "チョコレート"))  # 3
print(normalized_distance("アイス", "バニラ"))  # 1.0
print(normalized_distance("チョコレートアイス", "チョコレート"))  # 0.3333333333333333

2019-02-252019-02-23

pythonで編集距離(レーベンシュタイン距離)を求める

ごく稀にですが、文字列同士の編集距離を求める必要が発生するのでその時のメモです。

編集距離(レーベンシュタイン距離)とは、二つの文字列がどの程度異なっているかを表す距離の一種です。
Wikipediaにも解説があります。

一方の文字列に対して、1文字の挿入、削除、置換を最低何回施せばもう一方の文字列に等しくなるかで定まります。

pythonでこれを求めるときは、python-Levenshtein というライブラリが使えます。

インストール


pip install python-Levenshtein

使い方


>>> import Levenshtein
>>> text1 = 'Levenshtein'
>>> text2 = 'Lenvinsten'
>>> Levenshtein.distance(text1, text2)
4

2019-01-262019-01-26

MeCab.Tagger()はかなり遅いという話

昔、形態素解析にかかる時間を短縮するために調べた内容のメモです。

以前の記事で、mecab-python3 の使い方を書いたとき、tagger = MeCab.Tagger() という処理を関数の外側で行なっていました。

実は初めてmecab-python３を使った頃、僕は次のように書いてました。


def mecab_tokenizer(text):
    # 関数の中で、MeCab.Tagger()を呼び出す。これが遅い
    tagger = MeCab.Tagger()
    parsed_text = tagger.parse(text)
    parsed_lines = parsed_text.split("\n")[:-2]
    surfaces = [l.split('\t')[0] for l in parsed_lines]
    features = [l.split('\t')[1] for l in parsed_lines]
    bases = [f.split(',')[6] for f in features]
    # ここに、必要な品詞の単語だけ選抜する処理を入れることもある
    result = [b if b != '*' else s for s, b in zip(surfaces, bases)]
    return result

1個や2個のテキストを処理する分にはこの書き方で問題なかったのですが、
数十万件のテキストを処理するとこの関数がとても遅いという問題があり、調査をしていました。

結果わかったことは、タイトルの通り、MeCab.Tagger()が遅いということです。
jupyter でコードの前に %timeit とつけると時間を測れるのでやってみます。


%timeit tagger=MeCab.Tagger()
```
結果:
217 µs ± 6.17 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
```

ちなみに、形態素解析自体(parse)の実行時間はこちら


# 100文字のテキストを事前に用意しておきます
print(len(text))
```
100
```
%timeit parsed_text = tagger.parse(text)
```
結果:
26.9 µs ± 151 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
```

テキストがもっと長くなると話も変わるのですが、100文字くらいのテキストであれば、
parseにかかる時間よりも、Taggerのオブジェクトを作るのにかかる時間の方が8くらいかかっています。

対象のテキスト数(=関数が呼び出される回数)が数十万〜数百万件になってくると、
体感スピードがかなり違うので、
tagger = MeCab.Tagger()
は関数の中ではなく、事前に行うようにしておきます。

名前空間を汚染したりすることが気になる場合は、 class化するなどの対応をとりましょう。
また、形態素解析するテキストの数が少ない場合はあまり気にしなくても大丈夫です。

完全に余談ですが、この記事を書くために私物のMacで時間を計測したとき、職場のMacよりはるかに速いので感動しました。
職場の端末だとMeCab.Tagger()に 1.2ms (6倍!)かかります。
端末が5年物とそこそこ古いだけでなく、辞書指定などの問題もあるかもしれません。

2019-01-202019-01-19

mecab-python3をつかってみる

前回の記事でインストールした mecab-python3 の使い方を書いておきます。
MeCabについてはWikiがあるのですが、このライブラリについては詳細なマニュアルはなく、
リポジトリの test.py を読むようにとそっけなく書いてあります。

ただ、実際のところつかのは非常に簡単です。
次の例のようにMeCab.Tagger() と parse を呼び出すだけで結果を得られます。


>>> import MeCab
>>> text = 'すもももももももものうち'
>>> tagger = MeCab.Tagger()
>>> print(tagger.parse(text))
すもも	名詞,一般,*,*,*,*,すもも,スモモ,スモモ
も	助詞,係助詞,*,*,*,*,も,モ,モ
もも	名詞,一般,*,*,*,*,もも,モモ,モモ
も	助詞,係助詞,*,*,*,*,も,モ,モ
もも	名詞,一般,*,*,*,*,もも,モモ,モモ
の	助詞,連体化,*,*,*,*,の,ノ,ノ
うち	名詞,非自立,副詞可能,*,*,*,うち,ウチ,ウチ
EOS

各行の出力結果は次の形です。

表層形\t品詞,品詞細分類1,品詞細分類2,品詞細分類3,活用型,活用形,原形,読み,発音

注意点としては、 parseした戻り値は一つのテキストなので非常に使いにくいことです。

多くの場合、必要なのは原型の列です。
そこでプログラムでこのテキストから原形の情報を取り出すことになります。
僕はいつも下記のような関数を作って実行しています。


tagger = MeCab.Tagger()


def mecab_tokenizer(text):
    parsed_text = tagger.parse(text)
    parsed_lines = parsed_text.split("\n")[:-2]
    surfaces = [l.split('\t')[0] for l in parsed_lines]
    features = [l.split('\t')[1] for l in parsed_lines]
    bases = [f.split(',')[6] for f in features]
    # ここに、必要な品詞の単語だけ選抜する処理を入れることもある
    result = [b if b != '*' else s for s, b in zip(surfaces, bases)]
    return result