ダブル配列における動的更新の効率化アルゴリズム

IPSJ Web Site 6 Citations 13 References

Bibliographic Information

Other Title
  • ダブル ハイレツ ニ オケル ドウテキ コウシン ノ コウリツカ アルゴリズム
  • Efficient Dynamic Update Algorithms for a Double-array Structure
  • 自然言語処理

Search this article

Abstract

トライ構造はキーの表記文字単位に構成された木構造を用いて検索するキー検索技法の1つであり，自然言語辞書を中心として広く用いられている．このトライ構造を実現するデータ構造として高速性とコンパクト性を満足するダブル配列法があるが，この手法は，キーの更新が頻繁に生じない検索法として確立しているため，動的検索法に比べて追加時間は高速であるとはいえず，また削除で生じる不要なノードや未使用要素により記憶量に無駄が生じていた．本論文ではこれらの問題を解決し，ダブル配列を動的検索法として確立するため，未使用要素を連結することで追加処理を高速化する手法，削除時に生じる不要ノードの削除と未使用要素の詰め直しによる圧縮法を提案する．10万語の辞書データに対する実験結果により，追加速度については約1 600倍高速となることが，また大量の削除が起こった場合でも50%以上の空間使用率を維持することが分かった．

In many information retrieval applications,it is necessary to be able to adopt a trie search for looking at the input character by character.As a fast and compact data structure for a trie, a double-array is presented.However, the insertion time isn't faster than other dynamic retrieval methods because the double-array is a semi-static retrieval method that cannot treat high frequent updating.Further, the space efficiency of the double-array degrades with the number of deletions because it keeps empty elements produced by deletion.This paper presents a fast insertion algorithm by linking empty elements to find inserting positions quickly and a compression algorithm by reallocating empty elements for each deletion.From the simulation results for 100 thousands keys,it turned out that the presented method for insertion is about 1,600 times faster than the original method,and that the presented method for space efficiency keeps the activity ratio more than 50%.

Journal

Citations (6)*help

See more

References(13)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top