SKK 辞書を操作するスクリプトを作成しつつ配列の勉強
SKK 辞書の共有(2012.07.04)
Mac 上の Vim と Emacs、Win 上の Vim と Emacs で SKKを使っていて、最終的に skk-jisyo ひとつで運用できるようにするため、S 辞書使ってなるべくユーザ辞書に登録して育成をしている。
今まではほとんどの時間 Mac 上の Emacs を使っていたのだけど、最近になって Win 上の Vim を使う時間が長くなってきて、ユーザ辞書の同期について悩むようになった。だって実質的に 4 種類存在することになるんだもの。
同じマシンで Emacs と Vim 用の辞書を共有すれば良いと思うかもしれないけど、Emacs は立ち上げっぱなし、Vim は起動・終了を繰り返すという使い方なので、共有することができない(SKK を使っている人なら説明しなくてもわかると思うが)。
ということで、起動時間の一番長い Carbon Emacs の辞書に合わせるのが良いと思い、sort してから diff をとってみたものの、なんだかひとすじ縄ではいかなそう。読みに対する登録語が同じでも、出現頻度の順番が入れ替っているので diff では別物と見做されて結果に出てきてしまう。例えば下記のようなもの。
なr /慣/成/馴/鳴/ なr /慣/馴/成/鳴/
このような(実質的には同じものなのに差分として出てきてしまう)ものが 4000 行とかあるので、これを元にして同期するのは難しい。最終的には手動登録になっても良いので、各辞書の本当の差分のみを抽出したいのだ。気付くと irb を立ち上げて readlines() をしていた。少しばかり試行錯誤して方針が見えてきた所で、ファイルにスクリプトとして記述していった。
SKK 辞書を良く見てみると、アノテーションのような付加情報がついていた。これらをすべて欠落することなく比較するのは大変だし、自分の欲しいものとは関係がないので gsub で削除していった。目的に合わせて情報を削除することも必要。
方針としては各辞書の「読み・漢字」のペアを二次元配列にし、差分を取って出力するというもの。「どちらの辞書に存在して、どちらの辞書に存在していない」という情報は必要なく、単純に「重複していないユニークな単語集」を得られれば良い。あとはそれを見ながら手動で登録していけば良いのだから。
ユーザ辞書は現在 16536 行あって、SKK のメニューで候補数を表示させると 20632 となっている。自分の作成したスクリプトの結果は 20638 となっていた。6 語重複があるのかもしれないね。何が重複してるのかと思って
cat skk-jisyo | sort | uniq -c | sort -r | head -330
としてみると 322 語も重複していた。三重のものはなくて二重のものだけだったけど、どうしてこうなった？異常終了した時にクリーンに更新されなかったとか？まぁ、これはあとで修正しよう。おやおや？作成した二次元配列を uniq してみると、length が 19886 になってしまった。いったいどういうことだろう? これもあとで考えよう。
二次元配列は差分を取れないのか...。これはこの前作った重複確認スクリプトと似たような感じで、空の配列を用意して片方に存在していなければ用意した配列に追加するという方法でいくしかないのかな。
うお〜、要素数が 20000 あると結果が出てくるまで時間がかかる。PentiumM の 800MHz で 11分23秒。それほど頻繁にやる作業でもないのでいいか。速度を求めるなら Python で作り直すけど、これまで書いてきたように、サクッとプロトタイプを作って方針を考えることができるので Ruby は気に入ってるの。慣れてるってのもあるけどさ。
Windows 上では下記のように -Ku オプションを付けるのを忘れないように。
ruby -Ku diffskkdic.rb jisyo1 jisyo2
SKK 辞書の共有の続き(2012.07.05)
6 語違った件。ちょっとわかった。
すうがく /數學/数学/ すうがく /数学/
というようなエントリーがあったので、この場合は自分の作ったスクリプトだと別物として認識されてしまうけれども、実際は「数学」が重複しちゃってるわけ。このようなものが他に 5 箇所あるということ。たまたま見付けたけど、どうやって探そうかな。
行頭の単語(つまり「読み」)が重複しているものをピックアップするスクリプトを書いて出力してみたら、300近くも下記のようなものが出てきてしまった。あれれ？
「わるi /悪/」と「わるi /悪/惡/」 「あg /上/挙/掲/」と「あg /上/挙/掲/擧/」
手作業で地道に直していくかなぁ。ちなみに処理時間は 44 秒。今時の CPU なら 10 秒くらいで処理しちゃうのかな？
手動での修正が終った。15959 行になった。約 580 行の削除(というか統合)だった。目が痛い。この段階で再度調べてみたけど、やっぱり語数の 6 個が合わない(-_-;)。
昨日 SKK 16536 行 20632 自作 16536 行 20638
今日 SKK 15959 行 19870 自作 15959 行 19876
思い当たるものと言えば
cat skk-jisyo | sort | head -10 #, #じ, #ねん, /, @, today
の 6 個くらいだろうか。上記は SKK 上で特別なものとして認識しており、候補数として計算されていないとか？なのかな？
辞書を目視でずらずら見ていたら、かなり勉強になった。アノテーションって邪魔なんだけど、「使う」と「遣う」の違いが書いてあったりして変換という意味ではなく、ほんまもんの辞書として使えそうなりよ。
SKK 辞書の共有の続きの続き(2012.07.06)
Ruby で作ったスクリプトを Python で実装した。写経のような感じで、内部的な記述(つまりアルゴリズム)はほぼ一緒になっている。癖というか、どうしても Python から書きはじめることができず、Ruby → Python の順になってしまう。自分にとって Ruby の方が手軽なんだな。
処理速度は Python の方が速いということを承知してはいるものの、今回もかなりの差が出てしまったので気落ちしてしまう。逆に言えば Python を使えば iBook でもまだまだ実用で使えるということになるのだが...。
CPU Python Ruby 差 処理内容
--------------------------------------------------------
PentiumM 52s 561s 10.7倍 辞書の差分を調べる
800MHz 16s 44s 2.9倍 読みの重複を調べる
--------------------------------------------------------
PentiumM 26s 286s 11.0倍 辞書の差分を調べる
2000MHz 6s 17s 2.8倍 読みの重複を調べる
--------------------------------------------------------
PowerPCG3 211s 2773s 13.1倍 辞書の差分を調べる
600MHz 59s 239s 4.0倍 読みの重複を調べる
--------------------------------------------------------
Windows と Mac で 処理速度が CPU 速度と比例していないのはメモリ容量が少ないからかな？(800MHz と 600MHz は 1.3 倍だけど、実際には 4 倍も違っている)。今時 384 MB なんて携帯電話に負けてる。
SKK 辞書の共有の続きの三乗(2012.07.09)
Ring Server から skktools をダウンロードしてビルドしてみる。いつも通りに ./configure & make をするのだが、skkdic-expr2 が作成されていない。GLIB2 が必要とのことなので、まずは glib をインストールする。過去の記録によると 2.4.8 まではインストールができていたので、今回もこのバージョンにする。
GLIB2 をインストールし終えてから再度 ./configure & make すると、無事に skkdic-expr2 をビルドすることができた。expr との違いは(良く見ていないけど) DB を使わなくなったことかな？ヘッダに gdb とかが無くなってるから。
それはさておき、早速動かしてみる。自分の欲しい表示形式では無いものの、差分を求めるという目的は同じ。めちゃくちゃ速かった。Python で 62 秒かかったところ、1 秒で終了してしまった。どんなアルゴリズムになっているのだろう？
読み込ませるファイルは UTF-8 のものだったけど、問題なく処理されたみたい。出力の詳細までは確認していないけど、Python で出したものと同じ結果になっている。
いや、それにしても速い。これなら skk-jiyo と SKK-JISYO.S の差分や、npiii.l との差分も気楽に取れる。
skkdic-expr2 SKK-JISYO.S - skk-jisyo > Small-User.dic cat Small-User.dic | wc -l ;=> 1053 skkdic-count Small-User.dic ;=> 3139 candidates
S 辞書は 6763 candidates だったので、約半分はユーザ辞書に重複して登録されたことになる。これなら S 辞書を読み込まないようにしてもいいかなぁ。
問題は北極三號。1.6 MB もあって読み込みにものすごく時間がかかっているのだ。
skkdic-expr2 npiii.l - skk-jisyo > NP3-User.dic cat NP3-User.dic | wc -l ;=> 54949 skkdic-count NP3-User.dic ;=> 72568 candidates
npiii.l 辞書は 83063 candidates なので、約 1 万語はユーザ辞書と重複してることになるのかな。これは差分を取ったものを参照させるようにした方がいいね。
SKK 辞書に関する...(2012.07.10)
ツイートをしながら自分で気が付いたのだけど、二つの辞書の差分を求めるのに、今までは「ひとつの辞書(A)を基準にして、別の辞書(B)からひとつずつ要素を取り出してきて、その要素が辞書 A に含まれているかどうかを確認して、含まれていなければ diff_array に格納する」という方法を取っていた。
しかし、この方法だと辞書 A に含まれており、かつ、辞書 B に重複して含まれているものが diff_array に追加されない。なぜなら、辞書 A に含まれているので、diff_array に追加する処理が実行されないから。具体的には下記のような感じ。
def homu(arr1, arr2): diff_array = [] for x in arr1: if x in arr2: pass else: diff_array.append(x) homu(B, A) A = [["あい","愛"],["あい","哀"],["ふくだ","福田"]] B = [["あい","愛"],["あい","哀"],["ふくだ","福田"], ["ふくだ","福田"],["あい","愛"]] B - A = [ ["ふくだ","福田"] ] 結果 B - A = [["ふくだ","福田"],["あい","愛"]] 欲しい結果
欲しい結果を得るためにはどうすれば良いのかなぁと考えていたのだけど、単純に配列から引いていったらどうだろう？と思った。
def homu2(arr1, arr2): diff_array = [] for x in arr1: if x in arr2: arr2.remove(x) else: diff_array.append(x)
これで欲しい結果を得ることができた。remove 処理を加えただけなのだが。
最初は if 文を付けていなかったのだけど、arr2 に要素が含まれていないとエラーになってしまったので if 文を付けて、ついでなので else 文で arr2 に存在していない(しなくなった)ものを追加させるようにした。その結果、ほとんど同じようなコードになってしまった。
辞書が変わっているので前回のベンチマークと単純に比べることは出来ないけれど、下記のような感じになった。
要素数 A: 20637、B: 19918
変更前 50.7s
変更後 9.8s
5 倍ほど速くなった。しかも一度に両方の辞書に対して差分を得ることができてしまった。処理内容はかえって増えているにもかかわらず速くなったのはどうしてだろう？気付かないミスをしてるのかも。
あ〜、配列からどんどんと remove で要素を削除していくので、if で比較するのに要する時間が短かくなっていくわけだ。全数を調べるので最初の for は仕方ない。しかし、次の if にかかる時間はその要素数に比例するのだから、要素数が減れば時間も短かくなっていくのは理屈に合っている。
ここで arr1 と arr2 の 要素数をそれぞれ 10 とする。当初のスクリプトでは arr1 から要素を 1 つ取ってきては arr2 の要素と比較するので、(100 億回の比較が行なわれることになる。)100 回ね。誰も指摘してくれないので自分で修正しちゃうけど。100 億回ってどんなスーパーコンピュータだよって感じ。
ペケ10 x 10 x 10 x 10 x 10 x 10 x 10 x 10 x 10 x 10 = 10^10
10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 = 100
修正したスクリプトでは、仮に運良くすべてが配列に含まれているとすれば、比較すべき要素がどんどんと減っていくので、(363 万回で済むわけだ。)55 回ね。
ペケ10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 10!
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 55
辞書の要素数を見てみれば、それぞれ 20000 もある。階乗と冪乗を計算するのが恐しくなるけど、その差はあきらかだ。たぶんね。n^2 と n(n+1)/2 でした。
Ruby の delete は適合する要素を全て削除しちゃうのか。これはマズイ。とりあえずこの状態で試してみたけど処理速度は変わらなかった。どうしてかな？配列から削除されていってないとか？破壊的操作が必要なのかも。
先に delete の置き換えをしよう。index と delete_at で実現できそうだけど、そのまま list.delete_at(index(x)) とやってはエラーになってしまった。ワンクッション置いて、homu = list.index(x), list.delete_at(homu) で出来た。
結果は下記のようになった。括弧内は以前の記録(調べる辞書は異なっている)なのだが、Ruby は遅いとは言え大夫速くなった。Python が 5 倍に対して Ruby は 15 倍だ。
Python 11.0s ( 52s)
Ruby 38.2s (561s)
調べる辞書を逆転させると、また違った結果になった。Python は速くなって Ruby は遅くなった。まぁ Python の方は誤差みたいなものだけど、Ruby の方はどうしてかな？
Python 10.0s
Ruby 53.1s
出力される結果を見ればわかるのだけど、arr2 から削除される単語が少ないと時間がかかるみたい。つまり、include? の処理が軽減されないので時間がかかるわけだね。
それでも以前よりも 10 倍速くなったのだから、常用できるレベルになった。
追記。 iBook 上で実験してみた。Python は以前の 7 倍、Ruby は 11 倍速くなった。46 分かかっていたのが 4 分になったのだからこれは大きいぞ！
A - B B - A
Python 27.53s 30.61s ( 211s)
Ruby 179.18s 248.81s (2773s)
SKK 辞書に関する......(2012.07.11)
前回は階乗と冪乗なんて間違いをしてしまった。単なる二乗と数列の和だった。要素数が 10 個で 100 億回とか、どんだけ〜。約 20000 同士の比較回数なら 20000 x 20000 = 400000000 回で 4 億回だね。あとは 20000 * (20000 + 1) / 2 = 200010000 回で 2 億回と。
う〜ん、でも最高に良い状態(要素がすべてある)で 2 倍しか違わないのに、実際は 10 倍とかになってる。どうしてだろう？すべてを検査してるわけでは無いのかな？
include? や if x in arr: は配列の中をどのように走査しているのだろう？ハッシュ値を使っているわけではないので、頭(左)から順番に評価していってるのかな？だとしたら、なるべく早い段階で true になって次の処理に移れた方が良いのではないだろうか？
自分の比較したい配列はほとんど同じもので、差分がちょこっとある程度。だから比較する前に配列自体をソートしておけば、若干速くなるかもしれない。
ということで、二次元配列を作成する関数の最後に homuarr.sort! で並べ変えるようにしてみた。Ruby の場合は破壊的メソッドの sort! を使う。Python の方は homuarr.sort() もしくは sorted(homuarr) を使えば良さそう。違いはわからん。ソート自体の処理はほとんど負担になっていないようで一瞬で終わる。
A - B B - A
Python 26.19 30.82
(27.53) (30.61)
Ruby 140.39 236.98
(179.18) (248.81)
ちなみに A と B の関係は、要素数 A > B。動作は iBook で。
Python の方はもともと最適化されているのか、sort の使い方を間違っているのかわからないけれど有意差はみられなかった。Ruby の方は明らかに速くなっている。今回は配列を sort するコストをかけてでもやっておいた方がいい例になった。
