2013/1/9に統数研チャンネルにて、ウェーブレット木の解説をしました。岩波書店より出版されました「高速文字列解析の世界」の解説になっています。
ダブル配列の実装方法
2013/1/9に統数研チャンネルにて、ウェーブレット木の解説をしました。岩波書店より出版されました「高速文字列解析の世界」の解説になっています。
Double-Array Construction
ダブル配列は動的に更新できるデータ構造として提案されました． しかし，キーを追加するとき，衝突（ Collision ） という厄介な問題が発生します． そこでまず，キーの追加や削除を考慮せず， 登録するキーがすべて分かっている状態からの構築方法について説明します． 更新が遅いと評判のダブル配列ですが， 登録するキーの数が 10 万件くらいであれば， 1 秒以内で構築することができます． ただし，なぜか評価実験でよく使われている郵便番号のように， 網羅性の高いキー集合を対象とする場合は時間がかかります． なお，網羅性が高いという表現は，分岐数（節から出る枝の数）の平均が 大きいことを意味しています． ダブル配列を構築する前に，マルチキークイックソート （ Multikey Quicksort ） などを使用してキー集合を整列します． マルチキークイックソートは基数ソートとクイックソートを合
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
