~matubara/ChangeLog / 2005-08 →移動しました

■ 頻出文字列発見問題 [algorithm][string][net]

<http://chasen.org/~taku/blog/archives/2005/01/post_780.html>
一定以上の頻度のエントリだけの接尾辞配列を生成するアルゴリズム。
という論文があるらしい。

http://chasen.aist-nara.ac.jp/~yuuta-t/papers/nl158.pdf

■ LCPにもとづく接尾辞配列上でのアルファベット統合 [segmentation]

接尾辞配列上での隣接要素のLCPは配列で記憶できる。
任意区間のLCPは、区間内の隣接LCPの最小値。
- 統合文字列がLCPの直後にある場合、そのような区間のうち極大な区間をまるごと移動。
-- どこへ？ … 2分探索？
-- 移動した後、即座に整合性維持？ ← 移動されたものが再び移動される可能性があるから
- 統合文字列がLCPの中にある場合、そのような区間のうち極大な区間の整合性維持。
-- LCPの長さを減らす。
-- こういう整合性維持はどのタイミングでやるべきか微妙。

■ Simple Linear Work Suffix Array Construction (Juha Kärkkäinen, Peter Sanders) [algorithm][segmentation]

線形時間で接尾辞配列を作る”シンプルな”アルゴリズム。
シンプルな、というのが重要。
いままで見かけたアルゴリズムは、複雑で、すぐには理解できなかった。
このアルゴリズムは1時間読んで理解できた。
このアルゴリズムに少し付け加えると、LCPも線形時間でできるらしい。
via 武田先生＠梅村研の博士論文

■ 高橋正子 『計算論 計算可能性とラムダ計算』 [book][net]

<http://www.amazon.co.jp/exec/obidos/ASIN/4764901846/>

■ Gentoo Live CD Installer [gentoo][net]

<http://mirror.gentoo.gr.jp/experimental/x86/livecd/x86/>
GTKとかコンソールのダイアログ形式でインストール作業が出来る。
いまはまだα版なので、reiserfs が使えないなど不十分な点もあるようだが。

■ TopPage - Debian GNU/Linux スレッドテンプレ [debian][net]

<http://debian.fam.cx/index.php?TopPage>
aptのエラーのFAQとか。

■ Michael Sipser『計算理論の基礎』 [book][net]

<http://www.amazon.co.jp/exec/obidos/ASIN/4320029488/>

■ 長谷川 浩司『線型代数』 [book][net]

<http://www.amazon.co.jp/exec/obidos/ASIN/4535783713/>
雑誌、数学セミナーでの紹介。
授業での解説にまわされがちなことを記した注が充実しているとのこと。

■ 書体関係 Wiki - X でのフォント設定 [net][linux][font][ui]

■ font.properties -> fontconfig.properties [font][ui][linux][java]

JDK1.4 までは、font.properties [2005-07-07] で設定していた日本語フォントの設定は、
1.5 では fontconfig.properties に移ったらしい。
fontconfig.RedHad.xxx.properties.src などという、ディストリビューション専用のサンプルがあるので、それを元に改変する。
なお、srcは外さなければならない。（それではまった）

■ Gentoo 半死 → 修復 [linux]

emerge -e system
を実行しておいたら、中途半端なところでエラーが出ていた。
起動し直すと、カーネルは立ち上がるが、"initがない"などと表示され、その先に進めない。

原因は、/usr のファイルシステムを読み取りのみでマウントしながらアップデートを仕掛けたため。
/ に属する /lib, /sbin, /etc, /bin などの一部が消えていた。
/usr 以下も怪しかった。

インストールしなおさずに、消えた（あるいは壊れた）ファイルを復元するため、
別パーティションに stage1 のファイルを展開し、
emerge -e system
のところまでインストール手順を実行した。

できたパーティションから、先ほどの消えたディレクトリをコピー。
すると一応立ち上がるようになったので、
起動時のエラーを見て
jfsutils, portmap
などの emerge しなおす。

そもそも /usr を読み取り専用でマウントしていたのはなぜか？
起動時にfsckが働かなかったから？
普段でも、ときどきシステム停止時の umount がうまくいかないことがある。
大抵は NFS でサーバーからマウントしているやつで、
無視しても問題ないのだが。