ダブル配列の実装方法
2. ダブル配列(Double Array)とは • トライ木の実装方法の一つ • トライ木とは？ • 大語彙で前方一致検索を高速に行うことが可能なデータ構造 • 例えば形態素解析、かな漢字変換で利用される • どこが単語の始まりでどこが単語の終わりかわからない時に有用 ハッシュテーブルを使ってルックアップする方法の場合 単語境界がわからないので一文字づつ文字数を増やしてルックアップするしかない 最後までいったら開始点を１文字ずらして再度ルックアップ O(n^2) (入力文字数がn) わ た し の な ま え は な か の で す 。 ・・・ 3. ダブル配列(Double Array)とは • トライ木の実装方法の一つ • トライ木とは？ • 大語彙で前方一致検索を高速に行うことが可能なデータ構造 • 例えば形態素解析、かな漢字変換で利用される • どこが単語の始
Double-Array Construction
ダブル配列は動的に更新できるデータ構造として提案されました． しかし，キーを追加するとき，衝突（ Collision ） という厄介な問題が発生します． そこでまず，キーの追加や削除を考慮せず， 登録するキーがすべて分かっている状態からの構築方法について説明します． 更新が遅いと評判のダブル配列ですが， 登録するキーの数が 10 万件くらいであれば， 1 秒以内で構築することができます． ただし，なぜか評価実験でよく使われている郵便番号のように， 網羅性の高いキー集合を対象とする場合は時間がかかります． なお，網羅性が高いという表現は，分岐数（節から出る枝の数）の平均が 大きいことを意味しています． ダブル配列を構築する前に，マルチキークイックソート （ Multikey Quicksort ） などを使用してキー集合を整列します． マルチキークイックソートは基数ソートとクイックソートを合
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
