接頭辞ダブル配列における空間効率を低下させないキー削除法

• 矢田, 晋

• 大野, 将樹

• 森田, 和宏

• 泓田, 正雄

• 吉成, 友子

• 青江, 順一

書誌事項

タイトル別名

• セットウ ジ ダブル ハイレツ ニ オケル クウカン コウリツ オ テイカ サセナイ キー サクジョホウ
• A Deletion Method for Minimal Prefix Double-array without Increasing Empty Elements
• 情報検索

抄録

接頭辞ダブル配列はトライを高速かつコンパクトに実現するデータ構造である．しかし，キーの削除によって配列中に未使用の要素が蓄積し，空間効率が低下するという欠点がある．また，更新時間が未使用要素の数に依存するため，削除による空間効率の低下は更新時間の悪化にもつながる．本稿では，未使用要素を増加させることなく接頭辞ダブル配列からキーを削除する手法を提案する．EDR電子化辞書の日英単語各10 万件に対する実験により，提案法は従来法と比べて約17?460 倍高速であり，高い空間効率を維持することが実証された．

Minimal Prefix (MP) double-array represents a trie with two advantages 窶髏€ a fast retrieval and a compact dictionary. However, a key deletion produces empty elements and degrades the space efficiency of MP double-array. In addition, the deletion speed of MP double-array is degraded by the key deletion because the deletion time depends on the number of empty elements. This paper presents an efficient deletion method for MP double-array. The method dynamically removes keys from MP double-array without increasing empty elements. From experimental results for the key set which consists of 100,000 keys, it turned out that the presented method is about 17窶骭€460 times faster than the conventional method and maintains high space efficiency.

収録刊行物

• 情報処理学会論文誌

  情報処理学会論文誌 47 (6), 1894-1902, 2006-06-15

  東京 : 情報処理学会

キーワード

• 論文

詳細情報

• CRID: 1050001337882545536
• NII論文ID: 110004729750
• NII書誌ID: AN00116647
• ISSN: 18827764
• ISSN: 03875806
• NDL書誌ID: 7993421
• Web Site: http://id.nii.ac.jp/1001/00010277/
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I7993421
• 本文言語コード: ja
• 資料種別: journal article
• データソース種別:
  • IRDB
  • NDL
  • CiNii Articles
  • KAKEN