08/12/12 02:43:00
とりあえず、論文を概要まで翻訳してみました。(翻訳サイトありがとう)
間違いがあるかもしれませんが。。。
-----------------------------------------------------------
HAT-trie: キャッシュを考慮したトライベースの文字列のデータ構造
Nikolas Askitis Ranjan Sinha
School of Computer Science and Information Technology,
RMIT University, Melbourne 3001, Australia.
Email: {naskitis,rsinha}@cs.rmit.edu.au
概要
トライは文字列を扱うツリーベースの最速のデータ構造だが、メモリ食いである。
burst-trieはほとんど同じぐらい速いが、バケツの中へトライチェーンを押し込む事でメモリを節約する。
しかしながらこれは、キャッシュを考慮したアプローチではなく、現在のプロセッサでは
不十分なパフォーマンスにつながり得る。
この論文では、既存の手法とうまく組み合せたキャッシュを考慮した
トライベースのデータ構造であるHAT-trieを提案する。
いくつかの現実のデータセットを使用したり、他の高性能なデータ構造と比較して性能を評価する。
ほとんどの場合、キャッシュを考慮したハッシュテーブルに匹敵するぐらいの
実行時間とメモリ使用量の改善が見られた。
HAT-trieはソート順を維持した可変長文字列を扱う最も効率的なトライベースのデータ構造と思われる。
851:デフォルトの名無しさん
08/12/12 11:22:50
引き続き翻訳してみます。
初めて本格的な翻訳作業をしますがなかなか面白いですね。
段落ごとにまったりとやっていきますので。。
----------------
3 The HAT-trie
現在可変長文字列を扱う(格納、検索)利用可能な最も速いデータ構造はburst-trieと
アクセス時にmove-to-frontするチェーンハッシュテーブルである。(Zobel et al. 2001)
これらのデータ構造は検索と更新に必要な命令を最小にするので速いが
とくにキャッシュを考慮しているわけではない。
我々は資料からlinked lists(bucketsやchainsとしてそれぞれ利用される)が原因である事を知っている。
852:デフォルトの名無しさん
08/12/12 11:24:46
最後の「原因」は「問題」の方が良さそうです。
853:デフォルトの名無しさん
08/12/12 20:03:11
アクセス時にmove-to-frontする
ってどういう事？
854:デフォルトの名無しさん
08/12/12 20:08:11
あ、文字列のMTFじゃなくて自己組織化探索の方か。
855:デフォルトの名無しさん
08/12/13 01:06:00
論文の英文和訳なんてこんなところでやらんでくれ。
856:デフォルトの名無しさん
08/12/13 09:13:33
>>853
翻訳が怪しくなりそうなところは英単語のままにしてあります。
アクセス時にmove-to-frontするというのは良く分かりませんが、直訳ぐらいにはなってるでしょうか。
>>855
すみません。今回は翻訳は置いといて（継続！？）
お詫びに、昨日お風呂の中でふと思いついたネタを投下します。
はじめに（論文っぽく）
ハッシュは完全ハッシュしか良いとは思っていません。例えば、>>844でいうと
1 <= A->B->C->A
2 <= A->B->C->B
3 <= A->C->C->C->D
という処理をハッシュでやると、右側を文字列として
int[][][][][] pattern;
pattern['A']['B']['C']['A'][0] = 1;
pattern['A']['B']['C']['B'][0] = 2;
pattern['A']['C']['C']['C']['D'] = 3;
という感じでやります。
しかし、たった5文字でint * 256^5=int * 1099511627776Byteのメモリを使います。
そこで最小完全ハッシュを考えます。最小完全ハッシュとはハッシュ値を
0からデータ数-1に割り振る事です。例えば'A'を1、'B'を2、'C'を3にする事を考えますと
すぐに思いつくものはkey['A'] = 1という感じでやれば出来ます。
このまま終わればそっちのネタになってしまいますが、ここからが本題です。
最小完全ハッシュの為のキーを返す処理にただの完全ハッシュを使うのでは本末転倒ですが
その処理を量子演算、量子アルゴリズムを使えば簡単に出来てしまうのではないか
という事を思いつきました。ただの思いつきではなくて見込みのある思いつきだと思います。
そこで量子演算、量子アルゴリズムについて話題を振りたいと思います。（おれ誰？）あ、出掛けます。。。
857:デフォルトの名無しさん
08/12/14 04:24:47
ハッシュはキー全体が定まらないと使えないから>>844の条件には合わないよ
858:デフォルトの名無しさん
08/12/14 06:01:04
>>856
そんなこと普通に勉強してれば思いつく程度だし、第一そのアプローチだと「神は存在するんだ！」みたいなドツボにはまるだろう。
＞しかし、たった5文字でint * 256^5=int * 1099511627776Byteのメモリを使います。
だってこの発想からだろｗ
続きはブログでやれ。ブログぐらい持ってるよな？ｗ
859:デフォルトの名無しさん
08/12/14 11:40:59
ふつーにBM法？
860:デフォルトの名無しさん
08/12/15 04:18:46
>>857
その通りでした。でも、完全ハッシュを説明する為の例なので、言いたい事が伝わればいいかなと思います。
>>858
ブログありますよ。だいぶ書いてないので、仕様で少し大きめの広告をのせられてますが。。。
>>859
BM法は今まで使う機会が無かったですが、>>844には良さそう（？）です。良く分かりませんが。
量子アルゴリズムには一匹も釣れ・・誰も反応しませんねぇ。改めてWebで調べたら思っていたのと
ちょっと違う感じでしたが、少し考えを進ませました。量子アルゴリズムは厳密ではなくても高速で
結果を知りたい場合に有効らしいので、それを元に考えてみました。例えば、キーが3bitで表せるとして
101, 000, 010のデータに最小完全ハッシュを施すのに、3bitの全パターンの全並び（順列）の中から
データがなるべく始めの方に固まっているパターンを見つけます。 例えば100 000 010 101 001 111 110 011
という並びは、始めの4つまでに全データが現れるので、ハッシュの大きさは4つ分ですみます。
次に、全並びに番号をつけたとしてその並びの番号を覚えます。この場合は0～!(2^3)-1の番号をつけて974を
覚えます。そして、例えば000のキーが知りたい場合は、番号から並びをほぼ正確に復元して
データのある位置がキーになり、なるべく正しい位置を探します。
この処理のどこかに量子アルゴリズムを適応できるか。あと、格納は置いときます。
翻訳>>851のつづき
-------------------------------------------------------------------------------
burst-trieのボトルネックを解決する為、トライ走査のコスト(作成されるだろうトライノードの数)を
かなり削減しなければならないが、より重要なのはbucketsを探すコストであるが、
それらが現在アクセスする中で最もコストのかかる要素だからである。
そのような削減はbucketsの表現をlinked listからキャッシュを考慮した巨大な配列に
変える事でしか達成できない。したがって、それはキャッシュを考慮したハッシュテーブルの
bucketsの構造化を考えるとよい(Askitis & Zobel 2005)。
シンプルな配列と対照させてハッシュ配列を使う利点は、bucketsがはるかに効率的にscale muchでき、
さらに保持されるトライノード数を減らせることである。
861:デフォルトの名無しさん
08/12/15 04:47:32
>>860
ここに長文を置かずにBlogに置いて、ここから誘導するようにすると喜ばれるでしょう。
862:デフォルトの名無しさん
08/12/15 04:56:42
多少自分の英語に自身があるからといって、日本人は英語が出来ないとか見下している奴だろ。そのオーラがビンビンしてるじゃんｗ
なんつーか、層化みたいな新興宗教の奴らと同じなんだよね。
863:デフォルトの名無しさん
08/12/16 12:04:51
>>862 から僻み野郎の気配がビンビン感じられる件
864:デフォルトの名無しさん
08/12/16 16:41:59
流れはよく判らんけど訳すなら全部訳してくれると嬉しい
中途半端はよくないよ
865:デフォルトの名無しさん
08/12/16 20:58:14
全部訳してテキストか pdf にしてどこかのアップローダにあげてくれ。
多くの人は途中経過に興味はないだろうし、俺は結果にも興味は無い。
866:デフォルトの名無しさん
08/12/17 18:29:56
木構造の葉ノードをIteratorパターンで順々に得る方法を実装したいのですが、どのようにすればいいでしょうか？
ただし、各ノードは子ノードだけ持っていて親ノードや兄弟ノードに関する情報は持ってないものとします
現在考えているのは、Iteratorの内部に現在たどっているノードをスタックで保持するってかんじなんですが、
もっと効率よい方法があるんじゃないのかなー？って思ったんです
867:デフォルトの名無しさん
08/12/17 18:44:55
自分でスタック作ってそのハンドルをイテレータのインスタンスとして持ちまわる。
木構造のイテレータは全部それで実装したよ。
効率が良いとされる方法はB+木みたく葉を全部末端に集めて
線形に辿らせるぐらいしかないんじゃないの。
構造に依存するし付け替えも面倒だけど。
868:デフォルトの名無しさん
08/12/17 18:46:22
あと昔のアルゴリズム事典に紐付き2分木というのがあったな。
末端の空きノードを利用するって事だったけど忘れた。
869:デフォルトの名無しさん
08/12/17 18:49:46
まあ何も考えずスタックで組んだほうが保守も楽だし、
追加や削除で余計なコストも掛からないから速度も大して変わらないと思うけどね。
870:デフォルトの名無しさん
08/12/20 01:36:40
昔GCのマーク処理をリンクの付け替えだけで全部やってるコードを見た事がある。
あれと同じようにすればいいんじゃないか。