ダブル配列におけるキー削除の効率化手法

情報処理学会 Web Site 被引用文献4件 参考文献9件

書誌事項

タイトル別名
  • ダブル ハイレツ ニ オケル キー サクジョ ノ コウリツカ シュホウ
  • An Efficient Key Deletion Method for a Double-array
  • 情報検索

この論文をさがす

抄録

トライ法は自然言語処理システムの辞書を中心として広く用いられているキー検索技法であり，トライを実現するデータ構造に検索の高速性と記憶量のコンパクト性をあわせ持つダブル配列構造がある．ダブル配列構造の欠点は，キーの削除によって生じる未使用要素により空間効率が低下する点である．これに対し森田らはダブル配列を詰め直すことにより未使用要素を除去するキー削除法を提案した．しかし，この手法はすべての未使用要素を除去できないため高い空間効率を維持できず，また削除コストが未使用要素数に依存するので，削除を連続するほど削除速度が低下するという問題がある．本論文では，トライの節のうち兄弟を持たない節が多くの割合を占めること，また，これらの節の遷移は容易に変更できるという特徴を利用し，削除を連続した場合でも空間使用率と削除速度を低下させない効率的なキー削除法を提案する．EDR日英単語辞書，WordNet英単語辞書，日本の郵便番号リスト，各5万件に対する実験より，提案法は削除を連続した場合でもきわめて高い空間使用率を維持することが，また，森田らの削除法より約50?200倍高速に削除できることが実証された．

A trie is a well known method for various dictionaries, such as spelling check and morphological analysis. A double-array structure is an efficient data structure combining fast access of a matrix form with compactness of a list form. The drawback of the double-array is that the space efficiency becomes worse by empty elements produced in key deletion. Therefore, Morita presented a key deletion method eliminating empty elements. However, the space efficiency of this method is low for high frequent deletion. Further, the deletion takes a lot of time because the cost depends on the number of empty elements. In this paper, a fast and compact deletion method is presented by using a property of nodes having no brothers. From simulation results for 50,000 keys, it turned out that the presented method is faster 50 to 200 times than Morita's method and keeps high space efficiency.

収録刊行物

被引用文献 (4)*注記

もっと見る

参考文献 (9)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ