SuffixArrayの説明に便利な単語を探す

SuffixArrayやその周辺領域での解説では、説明のための文字列としてabracadabraやmississippiといった単語が使われることが多いです。唐突ですが、別の単語を使ってみたくなったので、NLTKに付属のテキストから、使えそうな単語を探す指標をいくつか考えました。

使えそうな単語の条件として、最終的に考慮に入れたものを以下に示します。

単語長は長いほうが良い
単語を構成するアルファベットの種類は少ないほうが良い
長すぎる単語はNG
連長圧縮が効かないもののほうが面白い

使用したテキストはnltk.book.text[1-4,6-9]です。text5はチャットの履歴で、擬音語が含まれ過ぎているのでやめました。

指標A

条件1と2を愚直に表現したモデルです。値が大きい方が良いです。

value = len(word) / len(set(word))

結果

2.75 mississippi
2.20 abracadabra

13.00 _____________
6.50 oooohoohohooo
5.00 aaaaaaaaah
4.50 aaaaaaaah
4.00 ....
4.00 ....
4.00 mooooooo
4.00 rrrr
4.00 oooo
4.00 oooooooh

感想

単語っぽくない文字列が含まれているのは仕方ないとして、ooooとooooooohが同じレベルになっているのは納得いかないですね。

指標B

アルファベットの種類数をそのまま使うのはイマイチな感じがするので、単語内で同じアルファベットがたくさん使われている場合に値が大きくなるようなモデルを考えました。値が大きいほうが良いです。

value = sum(math.exp(word.count(c)) for c in set(word))

結果

168.63 abracadabra
119.30 mississippi

442413.39 _____________
22046.55 oooohoohohooo
8105.80 aaaaaaaaah
2989.11 auuuuuuuugh
2983.68 aaaaaaaah
1112.94 camaaaaaargue
1099.35 mooooooo
1099.35 oooooooh
460.04 trockenbeerenauslesen
439.82 jalaalwalikraam

感想

指標Aよりは納得できる感じになりました。ただ、単語っぽくないものがたくさん含まれているのはイマイチですね。

指標C

指標Bの別バージョンです。0次経験エントロピーを使いました。0次経験エントロピーは0になることがあるので分子に持ってきて、値が小さいほど良いということにしました。0次経験エントロピーが同じ値の場合には、文字数が多いほうが嬉しいので、値を文字数で割っています。また、0次経験エントロピーが0になる場合 (aやaaaa) は文字数で割っても評価値が同じになるのですが、それは嬉しくないので、評価値に 1 / len(word) を足してみました (1は適当に持ってきた係数なので改善の余地はあります) 。

h = sum(word.count(c)/len(word)*math.log(len(word)/word.count(c), 2) for c in set(word))
value = (h + 1) / len(word)

結果

0.26 mississippi
0.28 abracadabra

0.08 _____________
0.14 oooohoohohooo
0.15 aaaaaaaaah
0.17 aaaaaaaah
0.19 mooooooo
0.19 oooooooh
0.19 marketing-communications
0.20 trockenbeerenauslesen
0.20 macmillan\/mcgraw-hill
0.21 bridgestone\/firestone

感想

指標Bと似た感じですね。ただ、指数関数を使っていない分、値が扱いやすい範囲にあるのは指標Bよりも嬉しいです。

指標D

指標Cを元にして条件3と4を組み込んだモデルです。

条件3に関してですが、文字数は短すぎても長すぎても扱いにくく、10文字前後だと説明するときに嬉しいので、次のような関数を探しました。

定義域は [0, ∞) の整数 (実数でも良い)
引数が10前後のときに最大となる単峰性の関数である
0除算について考えるのは嫌なので、値域は (0, ∞) か (0, Constant]

今回は $\mu=10$ のポアソン分布を関数として使ってみました。「引数が10前後のときに最大」が言えるのかはよく知らないので、ご存知の方はコメントかTwitterで教えてください。

また、4の条件を組み込むために、同じアルファベットが連続している部分を省略してみました。ついでに記号も省いてみました。

from scipy.stats import poisson

def compress(word):
    ret = ''
    for c in word:
        if c.isalpha() and (len(ret) == 0 or c != ret[-1]):
            ret += c
    return ret

h = sum(word.count(c)/len(word)*math.log(len(word)/word.count(c), 2) for c in set(word))
value = (h + 1) / poisson.pmf(len(compress(word)), 10)

結果

25.07 mississippi
26.73 abracadabra

19.75 oooohoohohooo
22.56 tete-a-tete
22.75 sereneness
24.28 sleeplessness
24.28 mississippies
24.35 bedeadened
24.42 selflessness
24.42 rokovoko
24.45 senseless
24.45 reference

感想

これは良さそうです！上位の単語の評価値がmississippiやabracadabraと近いこともポイントですね。