todo:log

todo:log

todo


(2003/05/23 05:38:42 PDT) ここにこっそりShiroさんへの質問を書いてみよう. SICP読書会のMLから,インタビュー へのリンクがあって見てみたのですが, Lispとの出会いのところで出てきた「Cで書くLispの本」って何という本ですか? まぁ超シンプルなLispインタプリタなら本を見なくても書けると思いますけど, やっぱ教師あり学習の方が…(笑)

(2003/05/07 08:46:33 PDT) 最近ちょっとプログラムから遠ざかっていて少し寂しい感じ. ネタですが,こんな本出ないですかねぇ….(ネタ元はこちら→ http://www.ilbbs.com/oracovers/ )


(2003/03/17 03:45:14 PST) 各ドキュメントに名前を付ける機構が欲しいと思った. …というのも,某コーパスにはドキュメント名(番号)が連番で振られているわけではない. つまり,内部のドキュメント番号と実際のドキュメント名の整合性が取れていないことが 問題だと考えたわけである. htmlとかだとタイトルが連番なわけもないし. とりあえず,そのドキュメント一覧を取得するにはドキュメント名に付随している情報を利用するとよい. 某コーパスは<ACCN>, </ACCN>で区切られている.これを利用する.

 (use suffix)
 (define (show-all-titles suf)
   (for-each (lambda (x)
               (format (current-output-port)
                       "~a\n"
                       (suffix-substring suf x (+ x 30))))
             (suffix-search-keyword suf "<ACCN>")))
 >(show-all-titles suf)
 <ACCN>gakkai-0000000001</ACCN>
 <ACCN>gakkai-0000000002</ACCN>
 <ACCN>gakkai-0000000003</ACCN>
 <ACCN>gakkai-0000000004</ACCN>
 <ACCN>gakkai-0000000005</ACCN>
 <ACCN>gakkai-0000000007</ACCN>
 <ACCN>gakkai-0000000008</ACCN>
 …(略)

これは全ドキュメント名を表示するだけだが,これを元にドキュメント名を抜き出せばよい. ドキュメント5の次は7になっている. 内部的には,ドキュメント番号は0から連番として数えるから,gakkai-000..07は5番目のドキュメント. この機構はsuffix.scmに組み込むのが多分本筋な気がするので,持たせることにしよう.

(2003/03/17 06:48:02 PST) 少し早めの帰宅. 文字列が定数時間アクセスじゃないとわかっていながら,利便性のために 実際の文字列はstringのまま持たせていた. でもやっぱり2分探索するときだって定数時間アクセスじゃないとやっぱりツライ.

そもそも利便性って何?と言うと,2分探索時の文字列比較や,部分文字列の取り出しかなぁ. Suffix array生成後も文字列をu32vectorで持たせると,一時的な部分文字列の取り出しが 頻発してオブジェクト生成しまくりかなぁ,と思ったので結局文字列はstringのまま 運用していた. でも実際復元するときはsuffix-substring位であることに気付く. それならいっそのことSuffix array生成後も文字列をu32vectorで運用した方がいいだろう. Suffix array生成部にてu32vectorに変換した文字列比較も実装しているし.

やっぱり速度が気になったので,やってみようっと.

(2003/03/17 11:48:39 PST) ぷほ.どうしようもないバグ発見. 辞書順で一番最後に出現する検索文字列を比較する際,検索文字列の末尾にアンカーとして 比較結果が必ず大となる文字を入れておく必要がある. u32vectorで使う以上,2^32 - 1のアンカーを付けておくべきだが, 何を勘違いしたのか,2^16 - 1のアンカーしか付けていなかった("\uFFFF"ってやつ). とりあえず,直しておいた.もう少しでアップ.


(2003/03/15 03:47:00 PST) 色々ソースを直した.

研究室でcvs使ってるのに$Id:$を埋め込んでいないことに気付く. そんなわけでv 1.1.2.7になった. Suffix array構築の際だけ文字へのアクセスを定数時間にするために string->u32vectorを導入する. 実行したら無茶苦茶速くなったが,とうとう懸念されていたメモリ使用量が明るみに.

Multikey Quicksortを破壊ソートで実装していたが,バグが全然取れない. とりあえず時間もないので,リストで持たせていたソート前Suffix arrayを vectorに変更し,破壊ソート. vectorに対する破壊ソートは0.6.7で実現されたがuvectorにはまだ未対応らしい. それは置いといて,問題なのは…, Multikey Quicksortを結局使わず,ただのQuicksortにしてしまったこと. 破壊ソートでメモリ効率は非常に良くなったが,計算が遅くなった. まぁstring-ref時代と比べれば全然マシ.

時間が出来たらMultikeyの破壊ソート版を動かせるようにしよう. とりあえず某コーパス1万件のSuffix arrayがちゃんと作れた. (define suf (suffix-create corpus "</REC>")) で,きちんとドキュメントの区切りもわかっているので, (suffix-number-of-documents suf) ==> 10000 と出てくれる.えがった.


(2003/03/10 08:49:50 PST) 大きいデータを扱う場合,GCは少々考えもの.

(以下,自分のプログラムの設計が悪いことを棚に上げているという前提を置いて読んで下さい)

某コーパスから日本語ドキュメント1万件を取り出し,Suffix arrayを構築させようとした. 現バージョンではソート前のsuffixをリストで持たせている. ちなみに1万件の日本語ドキュメントは約360万文字で6.5MB. ということは,約360万のセルを持つリストが出来上がってしまう. しかも内部ではキューを使ってセルを追加しまくっているので, とんでもない数のセルを生成してしまっている. 約360万のセルを1パスするだけでも異様な時間がかかっているのは, セルの生成やらGC発動やらが原因であろう.

本当にまじめに書かないとまずいな….


(2003/03/09 11:48:47 PST) 効率が悪いと分かっていながら,まだ改善していないのが, 一番クリティカルな部分であるSuffix arrayの生成部. 最速なのはSuffix Array の効率的な構築法であるが, 代入の嵐であることと,企業の人の論文なので特許が絡んでいると思い, 実装の簡単なMultikey Quicksortを用いている.

…が,シンプルな実装(sort!を使っていた時代)からあまり変更を加えないように作ったせいか, 大量のunsigned intをリストで持ち,とんでもないメモリと計算の効率の悪さが露呈している.

一番計算の大変なところなので,もっと真面目に作る必要がある.

でも比較対照が全部分文字列.C側から可変長文字はどのように見えるんだろう…. とりあえず,前者スタートになりそうだ.


(2003/03/07 04:11:53 PST) Suffix array操作用モジュールが一応動くようになったので暫定的に公開してみた. まだファイルI/O周りがbuggyだと思うが,統計関係は一応まともに動いている. 検索エンジンに組み込んでも文句は言って来なかった (検索エンジンから派生したモジュールなので当然と言えば当然だが…)

ところで,事後承諾で申し訳ないのですが,ソース公開に当たって 何かやっておかなければならないこととかあるのでしょうか? (ちなみに今は一応暫定公開)


金谷の謎日記(2002年9月12日)にも書いたのですが, string-pointerの仕様がどうしてこうなったのか,理解に苦しんでおります.

Cでは,文字列ポインタは文字列の始点が変動するのに対し, string-pointer-set!, string-pointer-next!, string-pointer-prev! のそれぞれの動作は,始点は0のままで終点が変動するようです.

せめて始点を変動させる手続きがあれば納得はいくのですが, どうしてかなぁ…,と悩んでおります.2002/09/12 01:23:59 PDT

なるほど.了解しました. Suffix Arrayを生成する際に,substringが文字列をコピーしていたら恐ろしいことになると思い, string-pointerを使おうと思っていたのですが,なるほどコピーしないなら問題ないですね. 丁寧な解説ありがとうございました.todo 2002/09/12 06:15:16 PDT

More ...