著者

矢田 晋 大野 将樹 森田 和宏 泓田 正雄 吉成 友子 青江 順一

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.47, no.6, pp.1894-1902, 2006-06-15

被引用文献数

3

---

接頭辞ダブル配列はトライを高速かつコンパクトに実現するデータ構造である.しかし,キーの削除によって配列中に未使用の要素が蓄積し,空間効率が低下するという欠点がある.また,更新時間が未使用要素の数に依存するため,削除による空間効率の低下は更新時間の悪化にもつながる.本稿では,未使用要素を増加させることなく接頭辞ダブル配列からキーを削除する手法を提案する.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.