接頭辞ダブル配列における空間効率を低下させないキー削除法
Bibliographic Information
- Other Title
-
- セットウ ジ ダブル ハイレツ ニ オケル クウカン コウリツ オ テイカ サセナイ キー サクジョホウ
- A Deletion Method for Minimal Prefix Double-array without Increasing Empty Elements
- 情報検索
Search this article
Abstract
接頭辞ダブル配列はトライを高速かつコンパクトに実現するデータ構造である．しかし，キーの削除によって配列中に未使用の要素が蓄積し，空間効率が低下するという欠点がある．また，更新時間が未使用要素の数に依存するため，削除による空間効率の低下は更新時間の悪化にもつながる．本稿では，未使用要素を増加させることなく接頭辞ダブル配列からキーを削除する手法を提案する．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.
Journal
-
- 情報処理学会論文誌
-
情報処理学会論文誌 47 (6), 1894-1902, 2006-06-15
東京 : 情報処理学会
- Tweet
Keywords
Details 詳細情報について
-
- CRID
- 1050001337882545536
-
- NII Article ID
- 110004729750
-
- NII Book ID
- AN00116647
-
- ISSN
- 18827764
- 03875806
-
- NDL BIB ID
- 7993421
-
- Text Lang
- ja
-
- Article Type
- journal article
-
- Data Source
-
- IRDB
- NDL
- CiNii Articles
- KAKEN
