颁辞肠辞补勉强会#32-表形式のデータに顺序を记録する方法
0 likes456 views
Cocoa勉強会#32 2009/2/7 表形式のデータに順序を記録する方法 新居雅行
More Related Content
More from Masayuki Nii (20)
Recently uploaded (15)
颁辞肠辞补勉强会#32-表形式のデータに顺序を记録する方法
- 5. VLEIコードの解釈 ? VLEIコード ? ? ? Variable Length Endless Insertable code） 東京工業大学の横田先生を中心にXMLのラベル付けに関する論文が ある 順序を記録するための2進数によるラベル ? ? ? あるラベルより前のラベルは0を続ける、後は1を続ける 2分木として表現可能で、ノードが1つ1つのラベルに対応 末尾に連続してレコードを追加するような場合などで、桁数が急速 に増大する 5
- 7. バイナリ表現＝2分木 ? ? ? ラベルは2分木のノードのどれかとなる 集合論的には { 0, φ, 1 } の集合の直積 中間ラベルを求める問題 ? ? ? 部分木の間順走査で得られるノードのどれか 一般には短いものを使うといいと思うかもしれない だが、実験してみると、「いちばん長いもの」でも 大して変わらない 000 00 001 0 010 01 011 ? 100 10 101 1 110 11 111 7
- 10. 延長手法の一提案 ? 隣接ノードの中間を求める場合の延長ノードを一般化 ? ? ?先頭と末端に追加する場合 ? ? ? ? 本来延長する方向＝AとBの中間であれば、Bに対して0を付加 さらに、本来の方向にf個延長し、逆方向にe個分延長する 末端に追加する場合に最後のラベルが1のみで構成されている場合 1を f+1 個追加し、0をe個追加する 先頭に追加する場合に最初のラベルが0のみで構成されている場合 0を f+1 個追加し、1をe個追加する f e A B e+f 10
- 11. 順序記録手法の実験結果 ? !"!# ? ?e=0, f=0と比較 ? 一部の条件では、平均桁数、 平均最大桁数は減少する B e e+f '!"!# (!!"!# %!"!# &!"!# '!"!# (!!"!# $!"!# %!"!# &!"!# '!"!# (!!"!# ,*(# f=0 ,*$# ,*-# ,*%# 20回の平均値 A &!"!# ,*!# ランダムに30、連続して20 レコードを生成。これを10回 繰り返す f $!"!# !"!# ? %!"!# !"!# 500レコード生成 $!"!# )*!+,*!# ,*!# ,*(# f=1 ,*$# ,*-# ,*%# )*!+,*!# ,*!# ,*(# f=2 ,*$# ,*-# ,*%# 130.2 平均桁数 平均最大桁数 11
- 12. 記録のためのコード化 ? ? {0, φ, 1} をそれぞれ、0, 1, 2とした 3進数を利用 4ビットごとにアルファベットに置き 換える ? 81通りあり得るが、φは末尾から連続した ものしか存在しないので、結果的には、31 通りしかない ? ?ソート時の問題 ? ? 0～9、A～Uを割り当てれば良い 比較するデータのすべての桁を揃えないとい けない 最大桁数に合わせてその場で生成が必要 12