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

■ Container クラスのスクリーンショットを録る [java][vis]

ある Container vv に表示されている内容を format 形式で filename というファイルに書き出す。

public void writeImage(Container vv, String format, String filename) throws IOException
{
        // capture: create a BufferedImage
        BufferedImage bi = new BufferedImage(vv.getSize().width, vv.getSize().height, BufferedImage.TYPE_INT_BGR);
        // create the Graphics2D object that paints to it
        Graphics2D g = bi.createGraphics();
        vv.paintAll(g);

        g.setColor(Color.BLACK);
        g.drawString("Suffix Tree for '" + getBodyString() + "'", 20, 20);

        //  and save out the BufferedImage
        ImageIO.write(bi, format, new File(filename));
}

vv.paintALL(g);

を

vv.paintComponents(g);

と書くと、Container vv に含まれているコンポーネントを描画し、vv 自身を描画しない。

■ 佐藤 克己 Yoshiki SATO [java][vis][chalow][people][net]

<http://apollo.u-gakugei.ac.jp/~yoshiki/>
chalow で日記をつけている情報視覚化（可視化）の専門家。
視覚化 / Y's memo
Java / Y's memo
Ajax / Y's memo
などがみどころ。

内容は同じだが、xight.orgの方が見やすいかも。

■ comp.lang.java.gui FAQ - in Japanese [java][vis][net]

<http://homepage1.nifty.com/algafield/JavaGUIFaq19j.html>
Java で GUI とかグラフィクスをやるときのFAQ。
数が多く、更新も続けられている。
Java Tips for Beginners も、Java 一般のTips集として参考になる。

■ Jar ファイル内のクラスを利用する方法 [java]

TreeTest.java が jung.jar のクラスを利用しているときのコンパイル方法：

javac -cp "$CLASSPATH:jung.jar" TreeTest.java

その実行方法：

java -cp "$CLASSPATH:jung.jar" TreeTest

クラスパスに jung.jar を追加すればよいのだが、環境変数 CLASSPATH もリストに含めないと、
jung.jar だけしか参照できなくなる。

■ パッケージ階層の中のクラスを利用する方法 [java]

クラス edu.X が ./jung/src/edu/X.class にあり、
TreeTest.java が edu.X を利用しているときのコンパイル方法：

javac -cp "$CLASSPATH:jung/src" TreeTest.java

その実行方法：

java -cp "$CLASSPATH:jung/src" TreeTest

クラスパスを引数で指定しない場合、ふつうはカレントディレクトリがクラスパスに含まれている。
したがって、カレントディレクトリが jung/src なら、単に

java TreeTest

■ Computational Geometry Code [math][geom][algorithm][programming][net]

<http://compgeom.cs.uiuc.edu/~jeffe/compgeom/code.html>

  This page lists "small" pieces of geometric software available on the Internet.

計算幾何学に関係するプログラムの集積。
幾何の計算と可視化など。

■ Screen Presentation Tools [latex][presentation][net]

<http://www.miwie.org/presentations/html/>
LaTeX + PDF を中心に、プレゼン用のツールを網羅的に紹介。

■ LaTeXでプレゼンテーション・シリーズ：まとめ - 外圏Wiki [latex][presentation][net]

<http://windom.phys.hirosaki-u.ac.jp/fswiki/wiki.cgi?page=LaTeX%A4%C7%A5%D7%A5%EC%A5%BC%A5%F3%A5%C6%A1%BC%A5%B7%A5%E7%A5%F3%A1%A6%A5%B7%A5%EA%A1%BC%A5%BA%A1%A7%A4%DE%A4%C8%A4%E1>
pLaTex 2e 配布に含まれる slides, seminar クラスを使ったスライド作成の方法。

■ dvips の日本語フォントを変える [postscript][latex][linux]

dvips はデフォルトで東風フォントを使う。
東風フォントは大きくしたとき特にアンバランスさが気になる。
ということで、
Ghostscript 7.07 - TeX Wiki あたりを参考に、
GhostScript が使う仮想的なフォントである Ryumin-Light や GothicBBB-Medium
などに対応する実体のフォントを変更する。

/usr/share/ghostscript/7.07/lib/CIDFnmap.CJK に

/Adobe-Japan1		/IPA-Mincho		; % CIDFnmap.ipa
/Ryumin-Light		/IPA-Mincho		; % CIDFnmap.ipa
/GothicBBB-Medium		/IPA-Gothic		; % CIDFnmap.ipa

を書く。もともとある /Ryumin-Light からはじまる行は % でコメントアウトする。

/usr/share/ghostscript/7.07/lib/CIDFnmap に

(CIDFnmap.ipa) .runlibfile

追加。

/usr/share/ghostscript/7.07/lib/CIDFnmap.ipa に

/IPA-Mincho (ipam.ttf) ;
/IPA-Gothic (ipag.ttf) ;

記入。

そして、

gs --help

として最後の方にでた Search Path のどこかに、ipag.ttf, ipam.ttf を置く。

たぶん最初のファイルにいきなり /Ryumin-Light (ipag.ttf) とか書いてもよさそう。

■ wheel 以外にも su を許可する [gentoo][linux]

/etc/pam.d/su の

# auth required pam_wheel.so use_uid

をコメントアウト。

■ Perl で内部コードを UTF-8, 入出力を EUC-JP にする [perl][howto]

use encoding 'euc-jp';        # 内部コードをUTFにし、ソースコードをeuc-jpとみなす
use open ':encoding(euc-jp)'; # ファイル入出力にeuc-jpとutf-8のコード変換を掛ける
use open ':std';              # 標準入出力も変換する

入出力にファイルを使わない場合は、単に

use encoding 'euc-jp';

■ Computer room [algorithm][net]

<http://www.isl.cs.gunma-u.ac.jp/~shingo/labo/index.html>
PPM の改良とか、接尾辞配列構築の2段階ソート法の発展形とか。

■ Reconstructing a Suffix Array [string][segmentation][algorithm][net]

<http://www.cas.mcmaster.ca/~franek/proceedings/psc05.pdf>
アルファベットの順序を再定義したときの接尾辞配列の再構築。

アルファベットを拡大したときの再構築手法が欲しい。

■ When Indexing Equals Compression -- Experiments with Compressing Suffix Arrays and Applications [segmentation][algorithm][net]

<http://www.cs.duke.edu/~jsv/Papers/catalog/node89.html>
A fairly new article of
yet another compression algorithm for suffix arrays.

■ MG4J Managing Gigabytes for Java [java][algorithm][nlp][net]

<http://mg4j.dsi.unimi.it/>

MG4J (Managing Gigabytes for Java) is a free full-text indexing system for large document collections

巨大データに対する索引管理プログラム？

■ WebGraph [java][algorithm][graph][programming][net]

<http://webgraph.dsi.unimi.it/>

It provides simple ways to manage very large graphs, exploiting modern compression techniques.

巨大なグラフを保存・操作するための Java ライブラリ。

■ emacs で補完 [emacs]

Meta + /

で、現在位置までの文字列につづく文字列をバッファ内から見つけ、補完してくれる。
次の候補に変えるのも同じキー。
Case insensitive のようだ。

■ クロージャとOOPとJavaScriptの謎仕様 [javascript][net]

<http://ishikawa.arielworks.com/memo/2005/07/24/031449>

■ J2SE5のGenericsとインスタンス生成に関するメモ [java][net]

<http://ishikawa.arielworks.com/memo/2005/10/10/235348>
型変数 T をあるクラスの上位クラスとして束縛する。

public class GenericArray<T extends Comparable<? super T>> {

private Comparable<? super T>[] records;

public GenericArray(int max) {
	records = (Comparable<? super T>[]) new Comparable[max];
}
}

■ 符号長を減らすような連結がなかった場合 [segmentation]

A B C D A B C A A B C A B C C D B A D D A D A D B

のような文字列を対象として、bigram 'A B' の連結を行うと、
符号サイズが大きくなる。
そのうえで、もういちど bigram 'AB C' の連結を行うと、
符号サイズが最初よりも小さくなる。

この文字列の場合、顕著なパターン 'A B C' があり、
その一部だけを単語と認める（第2ステップ）ではむしろ符号長が長くなる。

対処：
差分が最小の連結でも符号長を増やしてしまう場合、
そこで連結をやめるべきかどうかは、
そのあとで符号長が減るかどうかによる。

符号長を増やす連結を採用する条件は、以降k回のうちに減少があること。

追記：
杞憂かも。

■ Perl で fold [perl][programming]

sub fold(&@) {
  my($f, @list) = @_;
  my $s = shift @list;
  while ( scalar @list ) {
    $s = $f->($s, shift @list);
  }
  return $s;
}

my $sum = fold { $_[0] + $_[1] } (1, 2, 3, 4, 5);

のようにして使う。

my $mean = 1 / fold { $_[0] + $_[1] } map 1/$_, (1,2,3,4,5);

■ Higher-Order Perl [perl][programming][book][net]

<http://hop.perl.plover.com/>
Perl で関数プログラミングの本。
全文が Wiki に載せられる予定らしい。

HOP will be free

My contract says that after the book is published I can distribute the complete text from my web site. The content of my book will be available to everyone everywhere for free. Watch this space for updates.

■ Perl Contains the Lambda-Calculus [perl][programming][math][net]

<http://perl.plover.com/lambda/>
Perl でλ計算。
λ計算のチュートリアルとかもある。

■ C for Java Programers [programming][net]

<http://www.javaopen.org/jfriends/cforjava/>

  Q.クラスが無いのにどうやってプログラミングするのですか?

■ 「構造化データの機械学習」研究会（ＭＯＳＴ） [segmentation][algorithm][learning][math][net]

<http://www.kecl.ntt.co.jp/icl/kpro/kazawa/most/>
構造化データのラベル付け学習とカーネル法に注目。
構造をもったラベル集合 → 構造を持ったラベル集合の写像の学習方法について。
条件付確率場(Conditional Random Field)に触れている。

■ Wordnet [linux][nlp]

portage にWordnet があった。
この形式のコマンド

wn spontaneous -over

で、こういう出力

Overview of adj spontaneous

The adj spontaneous has 3 senses (first 1 from tagged texts)
                             
1. (8) spontaneous, self-generated -- (happening or arising without apparent external cause; "spontaneous laughter"; "spontaneous combustion"; "a spontaneous abortion")
2. ad-lib, spontaneous, unwritten -- (said or done without having been planned or written in advance; "he made a few ad-lib remarks")
3. wild, spontaneous -- (produced without being planted or without human labor; "wild strawberries")

が得られる。

wnb

がGUIフロントエンド。

■ PostScript Tutorial [postscript][net]

<http://astronomy.swin.edu.au/~pbourke/dataformats/postscript/>
次の postscript ソースで、 点(100,200)から(200,250), (100,300)への太さ2 の線が描ける。

newpath
100 200 moveto
200 250 lineto
100 300 lineto
2 setlinewidth
stroke

座標は紙の左下から始まり、整数、浮動小数が使える。

■ PostScript Language Tutorial & Cookbook [postscript][net]

<http://www-cdf.fnal.gov/offline/PostScript/BLUEBOOK.PDF>

■ 条件付確率場の理論と応用 @amazon [book][net]

物理シミュレーションの本だった。

■ Towards dynamic randomized algorithms in computational geometry @amazon [geom][book]

■ Interspeech 2005 の招待講演 [segmentation][nlp][net]

<http://www.interspeech2005.org/technical/index.php?f=plenary.html>

Tuesday, September 6th
Keynote speaker: Fernando Pereira, University of Pennsylvania, USA
Title: Linear Models for Structure Prediction

Over the last few years, several groups have been developing models and algorithms for learning to predict the structure of complex data, sequences in particular, that extend well-known linear classification models and algorithms, such as logistic regression, the perceptron algorithm, and support vector machines. These methods combine the advantages of discriminative learning with those of probabilistic generative models like HMMs and probabilistic context-free grammars. I will introduce linear models for structure prediction and their simplest learning algorithms, and exemplify their benefits with applications to text and speech processing, including information extraction, parsing, and language modeling.

■ CS383 Algorithms, Fall 05, Computer Science Department, Boston College [net][algorithm]

Algorithm Designを使った講義。
講義スケジュールのページに Lecture Note が付いてる
本には図が少ないので、これで補充できる。

■ Postscript ファイルを縮小、余白調整 [postscript][howto][linux]

pstops "1:0@.95(6mm,-9mm)" s.ps > t.ps

1枚ごとに、.95倍にスケーリングして、右に6mm、下に9mm 動かす。
s.ps が元のPostScript ファイルで、t.ps が変更後のファイル。

オプションの書式は一般には

mod:num[angle]@[scale](offset)+num[angle]@[scale](offset) ...

のようになっている。
mod で何枚分を処理するかを決めて、
num はそのうちの0〜mod-1で何枚目かを指定する。
angle は R（右９０度）、L（左９０度）、U（上下反転）
scale は拡大倍率。

■ LiveCD で GLI の最新版をダウンロードして使う @Gentoo Linux Installer FAQ [net][linux][gentoo]

<http://www.gentoo.org/proj/en/releng/installer/faq.xml#newerversion>
Gentoo 2005.1 の GLI は実験バージョンのためか、途中のコンパイルでひっかかったり、
emerge の内部のエラーが出たりする。
リリースはされていないが、開発は続けられており、LiveCD から最新版を入手して実行できる。

# open a terminal
# xhost +
# sudo su -
# /opt/installer/misc/getgli
# export DISPLAY=:0.0
# cd installer/src/fe/gtk
# ./gtkfe.py

■ wall UNIXの部屋 [linux][net]

<http://x68000.q-e-d.net/~68user/unix/pickup?wall>

wall　ログイン中の全ユーザに対してメッセージを送信

シャットダウン時に実行されるコマンド。
けっこう便利かも。
ただ、mlterm では効かないみたい。

■ Daniel Jurafsky, "Speech and Language Processing" [book][nlp]

中川研から借りた。

■ Solan, Z., Horn, D., Ruppin, E., and Edelman, S. (2005) Unsupervised learning of natural languages [segmentation][algorithm][net]

<http://www.isrl.uiuc.edu/~amag/langev/paper/solan05languageLearningPNAS.html>
単語列、文字列、塩基配列などの非構造化データから、
教師無しで階層的構造を推論するアルゴリズム。

HotWiredでの記事
Cornell大学のプレスリリース
などによれば、採譜された音楽データにも適用できるとか。
誇張されていないのなら、すごい。

■ Web Site for Perfectly Random Sampling with Markov Chains [math][net]

<http://dbwilson.com/exact/>

■ David MacKay "Information Theory, Inference, and Learning Algorithms" [book][stat][math][learning][net]

<http://www.inference.phy.cam.ac.uk/mackay/itila/book.html>
情報理論と確率過程、学習アルゴリズムの教科書。
全文が PDF, PostScript で公開されている。

■ 単語分割の方針 [segmentation]

■ JUNG - Java Universal Network/Graph Framework [java][vis][algorithm][programming][net]

<http://jung.sourceforge.net/>
Java でのグラフ、ネットワークの可視化ライブラリ。
グラフのインタラクティブな更新が可能。
java.awt.event に準拠した Listener によるイベント処理機構が実装されているなど、
機能が豊富。

■ SuffixTree 構築プログラムの最適化 [string][segmentation][programming][java]

数Mバイトのデータの木を作るのに、Gバイトに近いメモリを必要とするのを
改善しようと、プロファイラにかけてメモリ使用量の多い変数を探した。

java -agentlib:hprof=cpu=samples,heap=sites,file=sample.prof -Xms20M -Xmx1000M SuffixTree < sample.txt

cpu=samples は、ときどきVMの状態を見て、そのときどのメソッドを実行していたかを記録する。
heap=sites は、変数ごとのメモリ使用量を見る。

もっとも内側での、むだなインスタンス生成をなくしたところ、
2割程度のメモリ使用量減少につながったみたい。
しかし、1桁落とすくらい（数十Mバイトを、2Gバイトのメモリで扱いたい）には至らず。

500kB, 1000kB ,1500kB ,... のランダムな UTF データで実行時間を
測定したところ、どうも線形時間で動いていない。
（メモリ使用量はおそらく線形だが）

アルゴリズムを見直す必要がある。
線形時間になっていない原因として２つが考えられる。

1. いまの実装にバグがある
   suffix link まわりが怪しい。
   suffix link はあるべきところにないとか、
   不必要に上層すぎる場所につながっていても、ただしく動くので、
   結果に誤りはでないが速度が落ちる。

2. アルゴリズムの問題
   suffix tree 関係の論文には、
   空間効率を改善するとか、大きなデータを扱うときに実用性が高い、
   とかいうアルゴリズムがある。
   Ukkonenのアルゴリズムは、オーダーでは線形だが、
   メモリアクセスの非局所性、領域量の定数部分の大きさ（suffix link分）
   などに問題点が指摘されている。

1. を見直すために、木の可視化がどうしても必要。

■ eXtensible and fleXible Library (Philipps-Universit舩 Marburg) [algorithm][programming][java][net]

<http://dbs.mathematik.uni-marburg.de/Home/Research/Projects/XXL>
Java のデータ構造ライブラリ。
機能的には STXXL [2005-10-03-4] と同じようなものらしい。
外部マージソートを含む。

■ リバーシの全探索 [algorithm][programming][net]

<http://www.d2.dion.ne.jp/~maginga/computer/othello.htm>
オセロの終盤前（あと20手くらいの時点）の全局面を計算して、
それぞれからの最善手も計算して、
ハードディスクに置いておこう、というもの。

アイデア 1：盤面を小さく表現
盤面は、64ビットのビット列を２つ使って、白の有無、黒の有無を表す。
（１面16バイト）

アイデア 1-a：重複の削除
正規化盤面を、もとの盤面の左右上下白黒反転のうち、
ビット列を整数と見たときの値がもっとも小さいもの、と定義する。

ある盤面から展開される盤面集合での重複削除には、正規化した後、
外部ソートを使う。

アイデア 2：ajax? で分散処理

別PCにまかせるとかトラフィックが多いHPや掲示板に
JavaScriptを仕込んでSUBMITで結果を返してもらうというのもよい作戦かと思われます。
クラックやエラーを考えると同じ問題をいくつも仕込んで
サムチェックも行い正しいと思われる結果を保存すれば安全でしょう。
この分散処理はデータのやり取りが少なく、
計算量が多いというグリッドコンピュータに向いた処理です。

■ STXXL -- C++ Standard Template Library for Extra Large Data Sets [cxx][programming][net]

<http://i10www.ira.uka.de/dementiev/stxxl.shtml>
C++ のデータ構造ライブラリの外部記憶版。
「ページングサイズ」を持つ外部記憶の領域の上界が与えられているアルゴリズムと
相性が良いらしい。
（ページングに関係するパラメータを設定できる？）

■ Strmat [algorithm][net]

<http://www.cs.ucdavis.edu/~gusfield/strmat.html>
DNA(4種), Protein(20種？)など、char 1文字で表せる文字列に関する、
文字列マッチングライブラリ。
接尾辞木を用いており、それ単体のライブラリとしても利用できる。

■ ECS 222A - Algorithms - Fall 2005 - Gusfield [algorithm][net]

<http://www.cs.ucdavis.edu/~gusfield/cs222/>
Gusfield さんのアルゴリズムの講義。
配布物がアップされてる。