著者

中村 康正 望月久稔

出版者

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

雑誌

情報処理学会研究報告自然言語処理(NL) (ISSN:09196072)

巻号頁・発行日

vol.2005, no.94, pp.117-122, 2005-09-30

---

トライ法は,自然言語処理システムの辞書情報構築を中心に広く用いられている.このトライ法のデータ構造として,青江らが提案したダブル配列法がある.ダブル配列法は高速性とコンパクト性をあわせもっており有効なデータ構造であるが,動的検索法に比べデータの更新処理が高速であるとはいえない.そこで現在では未使用要素を単方向リストとして連結する手法が知られているが,トライ木の希点を追加および削除する際に大きなコストを必要とする.そこで本論文では,未使用要素を双方向リストとして連結することにより追加処理を高速化し,さらに削除時間を抑えるアルゴリズムを提案する.10万語の辞書データに対する実験を行った結果,追加速度は単方向リストよりも約1.5倍,削除時間は未使用要素リストを用いない従来法と同等となることが判った.A trie is used widely, such as dictionary information construction of natural language processing system. As a data structure of trie, there is the double-array structure which Aoe and others proposed. A double-array structure is an efficient data structure combining fast access with compactness. However, the updating processing is not faster than other dynamic retrieval methods. Then, although the technique of connecting empty elements as linked list is known now, big cost is needed in the node of a trie tree is inserted and deleted. In this paper, we presents a fast insertion algorithm by connecting empty elements as doubly list and reduction algorithm of deletion time. From the simulation results for 100 thousands keys, it turned out that the presented method for insertion is about 1.5 times faster than the linked list method, and deletion time is equivalent to original method which is not used 1Inked list.