- 著者
-
青江 順一
- 出版者
- The Institute of Electronics, Information and Communication Engineers
- 雑誌
- 電子情報通信学会論文誌 D (ISSN:09135713)
- 巻号頁・発行日
- vol.J71-D, no.9, pp.1592-1600, 1988-09-25
キー検索の応用において,あらかじめ基本的キー集合を構築しておき,後に使用者がキーを適宜追加して拡充させる場合が多々ある.このようなキー集合に対するキー検索法を準静的検索法と呼ぶ.本論文ではこの準静的検索法に適したディジタル検索法を確立するために,複数の静的なキーのパターンマッチングに利用されていたデータ構造(ダブル配列と呼ぶ)を拡張する.本拡張法では,ディジタル検索木において分岐なしに終端のノードまで連続する遷移列をダブル配列とは別のデータ構造TAILにストリングとして格納する.そして,このダブル配列とTAILを使ったディジタル検索の検索,追加,削除アルゴリズムを提案する.キーの長さをk;ダブル配列上で冗長に定義される状態番号数をm;入力記号の種類をeとするとき,検索,削除,追加の最悪の計算時間がそれぞれO(k),O(m),O(m・e+e2)となることを示す.また,1,000個以上のキー集合に対する種々の実験結果から,このmはダブル配列に定義されるべき全状態数に対して,1パーセント以下の小さな値となることがわかった.