« July 2006 | Main | September 2006 »

2006.08.25

休日(2)

休みの日にどこいったか日記

ヨセミテ国立公園に行ってきました。
昔世界ふしぎ発見で見て以来いつか行ってみたいと思っていたがこんなに早くチャンスにめぐりあうとは。

街から3-4時間ぐらい?そんなに山奥ではなかった。最初に出迎えたのがエルキャピタンという一枚岩(下の写真は違う?)。人が数日かけて壁を登っているらしい。
Elcapitan

山なので夏でも寒いかと思い防寒着を持ってきたけどみんな半袖で、サンダル。
最初は近場のヨセミテ滝を。
Yosemitefall
で、ピザ食って次はバーナル滝。ここにたどり着くまでの山道でみんな疲労困憊。本来はもっと奥まで行く予定だったが、ここが元からゴールだったということにした。目的達成。滝はこんなの
Yosemitefall2
とかこんなの
Yosemitefall3
で、とりあえずこの日は下山。ふもとの街に泊まる。夕食は”おすすめ”キラーガーリックポテトを食べた。

翌日もヨセミテに向かい、この日はミラーレイクに向かった。途中で道を間違えたのか、馬ふんがとにかく多かった。で、1時間ぐらいで湖についた。
Yosemitelake
雪解け水が湖の供給源なので、今の季節は水の量が少なかった。とても冷たく泳げないだろう
湖の底はゴールドラッシュの舞台の近くということもあり砂金らしいものが肉眼でもみえるぐらいあった。
Gold
周りに比べて元気がないので、はしゃいでいる感じで撮ってみようとした写真。
Fight

Yosemitehalfdome

で下山。自然を満喫しました。
帰りに夕食でタイ料理を。マイルドにしたはずが、みんなむせていた。強くありたい

| | Comments (59) | TrackBack (0)

2006.08.14

休日

休みにどこいったか日記

先々週、土曜は電車に乗って、こちらの電気屋さんでは有名なFry's electronics に行き液晶を買いました。とにかくでかい。夜は寿司食って酒飲んでました。日曜は近くの日本人街に行って、コロッケ定食を食べ、久しぶりの日本食のうまさに泣きそうになりました。サンノゼグランプリもこの日
Frysele

Sanjosegranprix

先週は土曜にウォルマートに行って、雑貨と食料と自転車を購入。超巨大なドッグフードの袋を見て犬が不憫になりましたが(飽きるだろうと)、近くにあった超巨大なコーンフレークを見て、人も同じかと。
Pedigree

翌日はテックミュージアムに行き、三次元データをとってもらったりした後、ベトナム料理屋で麺を食べる。うまい。夜はカレーを作って食べる。
Dinner

今週の土はモントレー半島行って、海を見ようと。水着を持参したもののとても泳ぐような気温と水温、そして雰囲気ではないことということで断念し、水族館でラッコとマグロとサメを鑑賞。17マイルドライブを飛ばし帰りにギルロイアウトレットへ。夕食はハイソなベトナム料理屋で食べますか食べませんか問題で食べて帰る。
Montley

Umi

日曜はパロアルトに行き、スタンフォードショッピングセンターに行ってアップル製品を吟味した後、スタンフォード大学を見学。学生がやってくれている1時間の無料ツアーがとてもよく、いろいろな学生生活の詳細が聞けた。CSの学生は大体どこも同じらしい本屋さんで面白そうな本がたくさんあったので吟味していたが、三冊[,1,2,3]買ってみた。アマゾンにも売っているのでわざわざここで買う必要はないかもしれないけど衝動買い
その後、ピザを食べカルトレインに乗り帰宅。

Stanford

Gates
ゲイツが寄付したゲイツビル(しゃれじゃない)でコンピュータサイエンス学科のビル。

| | Comments (16) | TrackBack (0)

2006.08.10

Kautz-Zeckendorf符号

符号化(文字列を0と1からなるビット列に変換)に求められる性質として元の文字列に正しく復元できることはもちろんですが、他に瞬時復元可能(前から順番に文字を確定できる)なども要求されます。今日紹介するKautz-Zeckendorf符号(KZ符号)は変わった性質を持っていて、符号化されたビット列を途中からみても、どこが文字の始まりかがわかるという符号です。

KZ符号の面白い点は符号化にフィボナッチ数列を利用しているということです。
フィボナッチ数列 f(0)...f(n)はf(0)=1, f(1)=1 が最初に与えられ、f(n)=f(n-1)+f(n-2)として定義される数列で1,1,2,3,5,8,13...とふえていきます。このフィボナッチ数列の性質の一つに、全ての自然数はフィボナッチ数の和で表すことができ、このとき、同じフィボナッチ数は2回使うことなく、また隣り合うフィボナッチ数は使われないことが知られています。# f(1)はじまりと考えます

さて、この性質を符号化にどのように利用するかというと、ある自然数Nをビット列に変換するとき、そのビット列のi番目は、もしf(i)がNの和を表現するときに使われるのならば1、そうでないならば0とします。

例えば、
1 = 1   # 1
2 = 01 # 2
3 = 001 # 3
4 = 101 # 1 + 3
5 = 0001 # 5
6 = 1001 # 1 + 5
7 = 0101 # 2 + 5
...
というかんじです。このビット列には先程の隣合うフィボナッチ数は使われないという性質から1であるbitは連続しないという性質があります。
KZ符号は先程のビット列のそれぞれの頭に110をつけたビット列をその文字の符号とします。

1 = 110 1
2 = 110 01
3 = 110 001
4 = 110 101
...
するとデータの途中で"110"を見つけた場合にはそこが文字の始まりだということが分かります。

この符号はもともと同期を取ったりするときに使われていたのですが、最近 "FM-KZ: An Even Simpler Alphabet-Independent FM-Index."[link(ps.gz)]で提案された新しい圧縮全文索引では入力文字列をKZ符号でまず符号化してビット列に変換し、得られたビット列に対してFM-indexを作るという方法を提案しています。
変換したことにより、ビット列に対する問題になっているので、FM-indexの構築や検索が簡単になります。以前提案されたHuffman符号を使ってビット列に変換する方法では変換前の文字との同期をとる必要があり余計なデータ構造を使っていましたが、KZ符号を使うと、自然と同期がとれ作業領域量が小さいという利点があります(上の例の場合、110で始まるsuffixはsuffix arrays上では一箇所に固まっている)。

他にも使えそうな符号です。

| | Comments (2485) | TrackBack (0)

2006.08.05

私達のNグラムはすべてあなたに属するある

Googleが10兆語のデータから作成したn-gram(n単語列)の出現回数などを記録したデータを研究用途向けに配布するそうです[link]。機械翻訳、スペリングチェック、情報検索、構文解析、意味抽出、音声認識などなど用途は広いですね。クローリングして良質のデータを集めるのは一苦労なので、使ってみるとおもしろそう。

#All Our N-gram are Belong to You についてはここ参照。本タイトルではもう一回日本語に訳しなおしてみました

| | Comments (12) | TrackBack (0)

« July 2006 | Main | September 2006 »