次の月 / 最新

~matubara/ChangeLog / 2005-07移動しました

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

2008 : 01 02 03 04 05 06 07 08 09 10 11 12
2007 : 01 02 03 04 05 06 07 08 09 10 11 12
2006 : 01 02 03 04 05 06 07 08 09 10 11 12
2005 : 01 02 03 04 05 06 07 08 09 10 11 12

2005-07-30 Sat

CSJコーパス入手 [segmentation]

CSJ(the Corpus of Spontaneous Japanese)のコーパスが入った
DVD-ROM 18枚組を北岡先生からお借りした。

書き起こし文と関連ツールが1枚目に、
XMLによるタグづけデータが2枚目に入っていた。

CD-ROMなどのイメージファイルの作成法 [linux]

/dev/cdrom から読み取れるデータをファイル hoge.iso に格納。

# dd if=/dev/cdrom of=hoge.iso

デバイスから読み取る代わりに、hoge.isoから読み取る。
# mount -t iso9660 -o loop hoge.iso /mnt/cdrom

2005-07-28 Thu

頻度計算のための接尾辞配列ライブラリ [programming]

固定長ngramの頻度
- 接尾辞配列を文字列形式で表示 [2005-07-21](接尾辞の接頭辞を表示)
頻度が高く、長い文字列から順に表示
- Longest Common Prefixにもとづいたクラス分けのうちの最長文字列

2005-07-25 Mon

ベストのbigram連結から、Nベスト連結へ [segmentation]

1回連結するたびにSAを更新するのは無駄。
どうせならいくつかのbigramについて連結してから更新したほうが効率的。
ということで、とりあえず、もっとも高い頻度から50%以内の頻度を持つbigramを1ステップで連結するようにした。
同時に、bigram連結のチェック、カウントのときに、
いちいち Bigramインスタンスを作るのを止めてみた。
カウントミスが起きていなければいいが。

2005-07-24 Sun

C で assertion [programming]

#include <stdio.h>
#include <assert.h>
int main(int argc, char *argv[])
{
  assert(argc>1);
  printf("%s\n", argv[1]);
  return 0;
}
と書くと、引数なしで実行したとき
a.out: test.c:6: main: Assertion `argc>1' failed.
と表示されて終了する。
#define NDEBUG
を先にやっておくと、assertマクロは空になる。

CSS Dencitie [markup][net]

<http://www6.plala.or.jp/go_west/nextcss/>
CSSの仕様、ブラウザの実装などを網羅的に解説。
中級者入門という、まとまった記事もある。

2005-07-21 Thu

接尾辞配列を文字列形式で閲覧する [segmentation][algorithm][programming]

接尾辞の先頭 n 文字を表示する効率的な方法。

素朴な方法1:
接尾辞配列の各エントリについて、元ファイルでの該当位置から
n 文字を、ランダムアクセスで読み取り、出力。
問題は、合計で ファイルサイズ * n のデータを読み取る必要があり、
読み取り時間のために実行時間がかかること。

素朴な方法2:
最初に元ファイルをメモリにすべて読み込んでおく。
問題は、メモリ使用量と、最初のオーバーヘッド(応答性が悪い)。

ということで中間をとる方法:
各エントリの接尾辞を、要求があるたびに読み取り、2分木に追加する。
ただし、既に2分木にあるデータだけで足りるならば、読み取らない。
(2つのとなりあうノードをつなげて見ればよい)
ノード中のすべての文字が n 回参照されたら、ノードを解放。路の圧縮。
メモり使用量とオーバーヘッドも抑えられ、
合計読み取り回数は最小限。

で効率的かと思ったが、各文字について参照カウンタが必要なため、
結構メモリを消費するかも。

Stray Penguin - Linux Memo (パーミション) [linux][net]

<http://www.asahi-net.or.jp/~aa4t-nngk/perm.html>

Referrer (Inside): [2005-07-28-1]

2005-07-18 Mon

perlによる大規模データの取り扱い [perl][net]

<http://www.lr.pi.titech.ac.jp/~abekawa/perl/perl_bigdata.html>
大規模データのハッシュをファイル化するとか。
メモリに乗せきれない量のデータを扱う。

やはり Perl はメモり喰いな言語。 [net][perl]

<http://www.drk7.jp/MT/archives/000803.html>
「100MByte 程度のデータが Perl 内部では 1GByte 程度もメモリを喰う」

クラスタリングとしての見方 [segmentation]

区間集合のクラスタリング
- 区間(領域):全体文字列上の区間。接頭辞と接尾辞も含意。

2005-07-15 Fri

GNU Emacsマニュアル 国際化文字集合の使い方 [linux][emacs][net]

<http://www.bookshelf.jp/texi/emacs-man/21-3/jp/emacs_21.html#SEC224>
<http://mibai.tec.u-ryukyu.ac.jp/cgi-bin/info2www?(emacs-ja)Defining%20Fontsets>
Emacsで文字集合ごとにフォントを使い分ける設定。
.Xdefaultsに

Emacs.Fontset-0: -*-*-medium-r-normal--12-*-*-*-*-*-fontset-standard,\
         ascii:-b&h-lucidatypewriter-medium-r-normal-*-12-*-*-*-*-*-iso8859-*,\
         japanese-*:-shinonome-gothic-medium-r-normal--12-*-*-jisx*-0
Emacs.font: -*-*-medium-r-normal--12-*-*-*-*-*-fontset-standard

projects/segment/segnaive/Segment.java [segmentation][java][net]

エントロピーの計算が間違っていたのを修正。
頻度^-1 から、頻度 / 文字列長(頻度の合計値)へ。
これにより、エントロピーは単調増加になった。

2005-07-14 Thu

projects/segment/segnaive/Segment.java [segmentation][java]

前のデバッグで、とんでもないバグを誘発しているのに気づいた。
2単語よりあとじゃあなくて、2単語よりあとか前だ!
計算し終わってから気づくとは…

Tiger (Java 5.0) Generics, auto (un)boxing and new For loop [java][net]

<http://technology.amis.nl/blog/index.php?p=197>
上記2つはjava boxingより。
boxing … 'int' <-> 'Integer' が、文脈(要求されている型)によって適切に選択される。
例えば、2項演算では int に。Mapのキーでは Integer。

2005-07-12 Tue

バグ修正 [segmentation]

- 同じ単語が連続する場合のカウントミス(オーバーラップしたものをカウントしてはいけない)

現在の実行速度:
300kB では3時間程度
600kB では8時間程度
メモリ使用量は、大体 10MB くらいに収まっている。

HPROF, A Heap/CPU Profiling Tool in J2SE 5.0 [java][net]

<http://java.sun.com/developer/technicalArticles/Programming/HPROF.html>
Sun による、JDK付属プロファイラの説明。

Javaプログラムのクラス別実行時間測定 [java][net][howto]

<http://www005.upp.so-net.ne.jp/khayashi/profiling.html>
プロファイラの呼び出しの仕方。
JDK1.2頃はこんな感じ。
$ java -Xrunhprof:cpu=times,heap=all,file=test.prof Segment
いまはこう。
$ java -agentlib:hprof=cpu=times,heap=all,file=test.prof Segment

StringBuilder [java][string][net]

<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/StringBuilder.html>
StringBuffer の代替。
1スレッドでしか使わない場合はこっちの方がいいらしい。

Segment.java のメモリ使用量 [segmentation][java]

大きなデータを食わせたら、すぐにヒープが足りない、といわれる。

SuffixArray の中で持つ「元の配列」に、連結の履歴を全て保った単語が書かれている。
同じ単語の情報は重複するので、辞書へのポインタにすべき。

→ bigramに置き換えるときに、Bigram インスタンスを1つ1つ生成していたので、
単にリファレンスを入れておくだけにした。
内部状態は全て final なので、共有しても問題ない。

また、JavaVM への割り当てメモリを増やすには↓で起動
$ java -Xms20M -Xmx800M Segment ...
なお、初期メモリ(-Xmsで指定する方)はあまり大きくできないらしい。

projects/segment/segnaive/Segment.java [segmentation][java]

Perlの配列は、連結リストとしても使える。
それは便利なんだけど。
ふと考えてみると、どちらも単位時間でできるとは思えない。
いままであまり考えていなかったが、「挿入・削除」「インデックスアクセス」のどちらが
とっても遅いということがない以上、両方が少々遅いのでは?

ということで、Java に移行した。
ひさしぶりなので、クラスをいっぱい作った。

いま考えているアルゴリズムを、もっとも素朴な方法で実装した。
- 接尾辞配列の先頭2単語ずつをみて
- 頻度が最大のbigramを見つけ
- それを1単語にくっつけた文字列を作成し
- 改めて接尾辞配列を作る
- この繰り返しを、エントロピーが落ち着くまで続ける。

fstabの設定 from Gentoo インストール記 [filesystem][linux][net]

<http://bd.tank.jp/gentoo/install6.html>
xfs fsck 自動で発見。
JFS は reiserfs と違って、起動時の fsck を自動的にやってくれないなあ…
と思っていたら、違ったらしい。
fstab を適当に書いていたせい。
正しくは

/dev/ROOT    /    xfs   noatime    0 0
^マウント元             ^オプション  ^ 0=自動的にfsckしない(する場合、/ は 1、他は2)
             ^マウント先           ^ dump(バックアップ)が必要かどうか

2005-07-10 Sun

ssh-agent [linux]

ssh の毎回のパスワード認証を省略する。
まず、パスワードでなくパスフレーズ認証に切替える。

パスフレーズ作成
$ ssh-keygen -t dsa
公開鍵をログインしたい先(SERVER)に登録
$ cat .ssh/id_dsa.pub | ssh SERVER "bash -Cc 'cat >> .ssh/authorized_keys'"

普段の使い方は以下の通り。
アプリケーション起動と同時にキャッシュするプロセス起動(終了も連動)
$ ssh-agent xterm
パスフレーズ入力(アプリごとに一回は必要)
$ ssh-add

2005-07-09 Sat

subversion [programming][linux]

最初に、データベースを置く場所を指定する。
$ svnadmin create ~/repos/

データベースへの登録
$ svn import ./project/project-name file:///$HOME/repos/ -m "initial import"
over SSH
$ svn import ./project/project-name svn+ssh://hostname/$HOME/repos

データベースからの(カレントディレクトリへの)取り出し
$ svn checkout project-name

更新をデータベースに反映
$ svn commit -m "fixed XXX"

データベースに登録されているファイルのリスト
$ svn list file:///$HOME/repos/

同じく、更新ログ
$ svn log

Subversionの基礎練習 [programming][linux][net]

<http://www.hyuki.com/techinfo/svninit.html>
現在、僕がやっているバックアップは
「日付つきでディレクトリごとコピー」だけ。
将来変更したあとでその変更をキャンセルできるように、
ある時点での状態をそのままとっておく。
いまのところこれで必要充分ではあるが、もっと高機能なバージョン管理もあってもいい。
- 一部を共有して分岐したものを作る
- どういう状態でのスナップショットか、他のスナップショットとの違いはどこかがわかる
とか。

2005-07-08 Fri

LVMを語らせていただけませんか? [filesystem][lvm][linux][net]

<http://pc5.2ch.net/test/read.cgi/linux/1024122484/>

LVMのスナップショット [filesystem][lvm][linux][net]

<http://www.atmarkit.co.jp/flinux/rensai/root06/root06b.html>
バックアップだが、実行時点ではポインタのコピーしか行わず、
あとで変更が起きたとき、変更された部分に関してコピーを行う。
容量を無駄遣いしない点と、バックアップのためにシステムを止める必要がない点が良い。

kernel再構築でトラブル [kernel][filesystem][linux]

プロセッサを指定するカーネルのオプションを
"Generic 64bit x86" → "AMD Athlon 64bit "
に変更。(オプションの名前は正確ではない)
しかし、これと同時に
"Synmetric M.. Processors"
のような、マルチプロセッサ用のオプションをオフにしなかったため、
Xが起動しないとか、モジュールの読み込みに失敗するとか、いろいろな問題が出た。

関連して、LVMによる問題も。
やむを得ず、電源遮断を何度かやったあとの復帰で、
手動によるfsckが必要になる。(jfsの場合のみ?)
何度も繰り返すうちに、「ファイルが回復できない」とか怖いことをいわれた。
そのあいだはカーネル構築しかしていないので、壊れたとしたらその辺。
念のためソースを展開し直して、きれいな状態からビルドしなおした。
fsckを自動的にする、というのは是非必要。

changelog2mediawiki [linux][chalow][perl]

ChangeLog での日誌がたまったし、Wikiへ転載できるように、変換スクリプトを書いた。
ChangeLogにはキーワードを付けてあるので、それを指定して抜き出す。

Wikiで日誌を付けるのは少々面倒なので、今後はChangeLogメインになるが、移行期間ということで。

#! /usr/bin/perl -w
use strict;

my @keys = qw|segmentation|;
my %keywords;
@keywords{ @keys } = map 1, @keys;
my $regexp_section_head = '^([\d-]+)';
my $output_section_head = sub { "== $_[0] ==" };
my $regexp_subsect_head = '^\t\*(.+):';
my $output_subsect_head = sub { "=== $_[0] ===" };
my $regexp_keyword = '('. join('|',@keys) .')';
my $regexp_begin_src = '\[src\]';
my $regexp_end_src = '\[/src\]';

my $showing = 0;
my $insrc = 0;
while ( $_ = <> ) {
  if ( m/$regexp_section_head/ ) {
    print $output_subsect_head->($1)."\n";
    $showing = 0;
  } elsif ( m/$regexp_subsect_head/ ) {
    my $subsect = $1;
    if ( $subsect =~ m/$regexp_keyword/ ) {
      print $output_subsect_head->($subsect)."\n";
      $showing = 1;
    } else {
      $showing = 0;
    }
  } elsif ( m/^(.+)$/) {
    my $text = $1;
    if ( $insrc ) {
      if ( $text =~ m/$regexp_end_src/ ) {
        $text = "$`\n$'";
        $insrc = 0;
      }
      print " $text\n";
    } elsif ($text =~ m/$regexp_begin_src/) {
      $insrc = 1;
    } elsif ( $showing ) {
      $text =~ s/^\s+-/\*/;
      print "$text\n";
    }
  }
}

2005-07-07 Thu

Mostly-Unsupervised Statistical Segmentation of Japanese [segmentation]

\bibitem{ando}
{Rie Kubota Ando, Lillian Lee}, 
``Mostly-Unsupervised Statistical Segmentation of Japanese:
Applications to Kanji'',
漢字列→単語の分割の手法。
頻度の高いN-gram部分を分けないようにし、頻度が落ちるところで分ける。
漢字しか対象にしていないものの、考え方が近い気がする。

Using Suffix Arrays to Compute Term Frequency and Document Frequency for All Substrings in a Corpus [segmentation][algorithm]

\bibitem{yamamoto}
{Mikio Yamamoto, Kenneth W. Church}, 
``Using Suffix Arrays to Compute Term Frequency
and Document Frequency for All Substrings in a Corpus'',
2001.
すべての部分文字列の単語頻度を一気に計算する、というもの。
まさしくいまやりたいことなので、必読。
途中まで読んだ感じでは、Longest Common Prefix という、
Prefix Listででてきた「共有部分の長さ」を持つことと、
部分文字列をクラス分けするというのがポイントっぽい。
クラス分けというのがまだよく分らないが。
ちゃんと読まねば。

Gentoo Linux Documentation -- Power Management Guide [gentoo][linux][net]

<http://www.gentoo.org/doc/en/power-management-guide.xml>
CPU、ディスプレイ、ハードディスクの電力消費を抑えるための方法。
特定のハードウェアに依存して書かれているので、そのまま適用はできないが、参考にはなる。

font.properties.ja [net][java][linux]

<http://fukuoka.cool.ne.jp/dream_theater/jusa/font.properties.ja.html>
Java の awt で日本語を表示するために必要な設定。
ファイルの場所は、$JAVA_HOME/jre/lib
この他、JAVA_FONTS という環境変数で ttf ファイルへのパスを通すとか、
font.properties.ja と同じディレクトリに、フォントへのシンボリックリンクを張っておく必要があることも。

Referrer (Inside): [2005-08-02-2]

2005-07-06 Wed

HOWTO Auto mount filesystems (AUTOFS) [gentoo][linux][net]

<http://gentoo-wiki.com/HOWTO_Auto_mount_filesystems_(AUTOFS)>
Gentoo の場合、USEフラグ amd も一応有効にする。(あまり使われていないみたいだけど)
autofs は、「アクセスされたときにマウントする」ので、一見動いてないように見える。
しかし、アクセスしてみると、ちゃんとアクセスできる。
タイムアウトも指定できるので、取り外し可能なデバイスのマウントに便利。
ただし、CD-ROMのディレクトリを見ようとすると Segmentation Fault になるのが謎。
(下層ディレクトリや、ファイルへのアクセスはできる)

nfs のマウントも同様にできるはずだが、何かうまくいかない。

HOWTO PowerNow! [gentoo][linux][net]

<http://gentoo-wiki.com/HOWTO_PowerNow!>
AMD Athlon XP でサポートされているらしいCPUの電力消費を抑える機能。
↓こんな感じでカーネルオプションを設定。

 [*] Power Management support
 CPU Frequency scaling  --->
 [*] CPU Frequency scaling
< >   /proc/cpufreq interface (deprecated)                                                 
 Default CPUFreq governor (performance)  --->                                         
 ---   'performance' governor                                                               
 <*>   'powersave' governor                                                                 
 <*>   'userspace' governor for userspace frequency scaling                                 
 [ ]     /proc/sys/cpu/ interface (2.4. / OLD)                                               
 <*>   CPU frequency table helpers                                                           
 ---   CPUFreq processor drivers                                                             
 <*> AMD Opteron/Athlon64 PowerNow!
とくに、CPUFreq processor drivers から自分の環境に合ったものを選ぶのが重要。

2005-07-05 Tue

頻度計算のもうひとつの問題 [segmentation]

aaaa のようなシークェンスを含む文字列で、単語 aa の頻度を接尾辞配列上で調べるとする。
接尾辞配列をつかって調べると、その箇所で 3 回と数えてしまう。
しかし、単語分割における頻度としては、せいぜい2回(まんなかの2つしかとれなければ、1回)である。

案:
- 接尾辞配列による頻度計算のときに、前のエントリと対象文字列上で単語長以上離れていないものはカウントしない。
- 接尾辞配列を、文字単位ではなく単語単位とし、適宜更新する。
- 接尾辞配列を使わずに頻度計算を行う。接尾辞配列は、頻出シークェンスの発見にのみ使う。

インクリメンタルな頻度計算に問題 [segmentation]

包含されたときに頻度を減らす、としていたが、
既に別の単語に包含されていたものを改めて包含するときに、重複して減らすことになる。
例:
b が bc に包含されている状態で、ab が生成されたとする。
abの頻度分だけ、b の頻度を減らすと、
abc
というシークェンスが対象文字列にあった場合、まんなかの b は
ab にも bc にも属しているとみなされることになる。

ほかにも問題。
a+b, b+c, a+bc の順で単語が生成されたとする。

projects/segment/ex-seg.pl (produce_new_words($$)) [segmentation]

「頻度の高い単語から分岐」を、とりあえず採用。
辞書のエントリに、頻度と接尾辞配列へのリンクをつけた。

新単語発見 [segmentation]

「頻度の高い単語から分岐させて、新単語を作る」:
- もっとも頻度の高い単語を選ぶ
- それに続く単語の中でもっとも頻度の高い単語を選ぶ
- 両者をつなげたものを新単語とする

「頻度の高いbigramを新単語とする」…すべてのbigramの頻度を計算:
- n文字 bigram の頻度計算…接尾辞の先頭n文字による接尾辞配列の分割

頻度計算 [segmentation]

よく考えたら、頻度は辞書更新に対して、インクリメンタルに計算できるような。
- 最初は普通に数える。(接尾辞配列の先頭1文字だけを見れば良い)
- 単語 A と単語 B と、新規単語 AB が与えられたとする。
- 新規単語 AB の頻度 = f[AB]を計算。(接尾辞配列上での2分探索で開始位置)
- f[A] と f[B] を f[AB] だけ減らす。

projects/segment/ex-seg.pl [segmentation]

頻度計算の案:
- 辞書を単語長別に区分し、それぞれ辞書式順序でソート
- 接尾辞配列には「共通範囲」の付加情報を付ける
- n 文字の単語の先頭から順に、接尾辞配列の接尾辞の先頭 n 文字を見て
  それが単語と一致していたら、共通範囲がn以上である限り、カウントしつづける。
  単語より前だったら、接尾辞配列を読み進める。単語よりあとだったら、辞書を読み進める。
  共通範囲がn未満になったら、次の単語に対して同様の手順。

2005-07-04 Mon

chalow [net][linux]

<http://nais.to/~yto/tools/chalow/>
Y's memo経由で知り、始めてみた。
emacs で編集モードが標準組み込まれている。
HTML に変換するときカテゴリ分けが階層型でなく多重型。

Sen [segmentation]

Java版形態素解析ライブラリ。

projects/segment/ex-seg.pl (get_freq($$$$)) [segmentation]

頻度計算に接尾辞配列をどう使っていいかが分からない。
接尾辞配列を使うと、多数の単語の頻度を高速に計算できる気がするんだけど…

案:
- 辞書を辞書式順序でソート
- 辞書の先頭と接尾辞配列の先頭から順に、一致をみる

辞書に構造を持たせる:

a => { '' => {}, b => {b =>{} }, c => {} },
b => { '' => {} }
<=> (a, abb, ac, b)
接尾辞配列に付加情報:
prefix list の効率的実装に類似した、「次のエントリと何文字目までが同じか」の情報

2005-07-03 Sun

cperl-mode [emacs][linux]

emacs の新しい方の Perl 編集モード。
古い方の perl-mode と比べ、Perl 5.x の文法に対応している感じ。

単語分割第一弾 [segmentation]

接尾時配列を使った単語分割プログラムを作りはじめた。
アルゴリズムは以下の通り。
- 分割は辞書に登録されている単語との最長一致で行う
- 辞書は初期状態で、各文字が登録されている
- 頻繁に現れる”2単語の連なり”を辞書に登録する、という作業を繰り返す
- 分割における各単語の使用頻度の平均が極小値になったらやめる
考え中。
- 単語の使用頻度は極小にたどりつくのか?
- 使用頻度はインクリメンタルに求められるか?……たぶん

2008 : 01 02 03 04 05 06 07 08 09 10 11 12
2007 : 01 02 03 04 05 06 07 08 09 10 11 12
2006 : 01 02 03 04 05 06 07 08 09 10 11 12
2005 : 01 02 03 04 05 06 07 08 09 10 11 12

最終更新時間: 2009-02-01 00:57

Powered by chalow
inserted by FC2 system