Left-leaning Red-Black Trees - やた＠はてな日記
いろいろなところで引用されています．実装が楽な赤黒木で，以下のスライドを見れば（むしろ，ほとんどコピーする感じで），簡単に実装できます． 論文 http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf スライド http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf 以下は，少し普通じゃない感じで，とりあえず追加のみを実装してみたものです．64 ビット環境だとポインタに割り当てられる領域も無視できないことがあったりなかったり，という思いが反映されています．ただし，試作品なので少しだけ…． template <typename ValueType, typename IndexType = unsigned, typename LessThanType = less<ValueType>,
ハッシュの話で思い出した資料 - やた＠はてな日記
以前，「もっと小さい辞書構造ないかなー」という話があって，「完全ハッシュをコンパクトに実現する手法がありますよ」（Bep のこと）なんて軽く返したところ，「学部生にも分かるように説明して」などと冗談のような返しをされて凹んだことがありました． というのを思い出して，資料を引っ張り出してきました． 最小完全ハッシュ関数の説明（PDF） http://sites.google.com/site/headdythehero/cabine/2009/0402/PracticalMinimalPerfectHashFunction.pdf # 実は他の場所に置いてあったのですが，PowerPoint から PDF への変換時に肝心な部分が失われていたようで，ただのゴミと化していました．
スライド（重複レコードの多いトライ辞書の圧縮） - やた＠はてな日記
重複レコードの多い辞書については，トライから Directed Acyclic Word Graph (DAWG) への変換で大幅に圧縮できるかもしれません．…という内容のスライドです． 重複レコードの多いトライ辞書の圧縮（pptx） http://sites.google.com/site/headdythehero/cabine/2009/0905/fit-2009.pptx DAWG の利点は，検索時間を落とさずに辞書を圧縮できることです．内部データ構造にダブル配列を採用すれば，Darts と同等の検索時間を実現できます．というわけで，速度重視で重複レコードが多いという場面での活躍が期待されます． # URL のようにキーが長いと，Minimal Prefix (MP) トライの方が有利になるかもしれません．また，辞書のサイズを優先するのであれば，簡潔データ構造である Level-O
Darts clone のデータ構造 - やた＠はてな日記
トライをダブル配列で表現する Darts に対して，Darts clone は，基礎のデータ構造として Directed Acyclic Word Graph (DAWG) というグラフ構造を採用し，DAWG をダブル配列で表現するようになっています． Directed Acyclic Word Graph (DAWG) トライの共通部分木を併合することで得られるグラフ構造が DAWG です．トライからDAWG への変換では，登録するキーの末尾に共通性があるほど，多くのノードを取り除くことができます．これまでの実験により，日本語や英語の単語をたくさん登録する場合であれば，全体の 60 〜 70% 程度のノードを取り除けることが分かっています．特に有効なデータの例として，日本の郵便番号を DAWG に登録すると，そのサイズはトライの約 1/10 になります． DAWG はトライを圧縮したデー
ダブル配列の資料（更新に関する内容） - やた＠はてな日記
ダブル配列の資料にスターが付いているようなので，関連する資料も公開することにしました．今回の資料は，情報処理学会第 71 回全国大会で使用したスライドで，ダブル配列の更新に関する内容となっています． ダブル配列による動的辞書の構成と評価 http://sites.google.com/site/headdythehero/cabine/2009/0418/ipsj-2009-yata.pdf?attredirects=0 提案手法自体は，従来手法における最悪ケースに対処するための手法なので，使いどころが難しいと思います．でも，どういう手法があるのかを見る程度には役立つのではないでしょうか． 実験結果については，従来手法でうまくいかない状況を想定した内容になっています．同じコーパス（Google n-gram の 1-gram）を使っても，辞書順に登録する場合，これほど大きな差はありません．
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
