著者

永井 弘之 藤田茂 菅原研次

出版者

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

雑誌

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

巻号頁・発行日

vol.2006, no.53, pp.29-34, 2006-05-19

---

自然言語処理システムに広く用いられているキー検索法として,トライ法があり,トライを表現可能なデータ構造として,ダブル配列がある.ダブル配列は,検索の高速性と空間利用率の高さを兼ね備えた,優れたデータ構造である.しかし,ダブル配列ではキーの検索時間に比べ,動的追加時間が遅い欠点がある.ダブル配列に対して,キーの動的追加を行うと,衝突が発生し,その回避に多くの計算量を要している問題がある.本論文では,ダブル配列において,遷移可能な次状態が単一であるシングル状態の多数性,およびシングル状態からの遷移先であるシングル要素の機動性を利用し,キーの動的追加時に生じる衝突を,効率的に回避することで,動的追加処理を高速化する手法を提案する.評価実験では,それぞれ10万件のデータを使用し,WordNet英語単語辞書で1.9倍,IPADIC日本語単語辞書で8.7倍,郵便番号で32.5倍,森田らの手法よりも高速に追加できることを確認した.Trie is a well known key retrieve method for natural language processing systems and the Double-array is a fastand compact data structure for a trie.However,dynamic key insertion time is not as fast as key sarch time,because of resolving collisions take a lot of time.A double-array has many single states and its successor is singlee elements.Single elements have a property that easy to reallocate.In this paper,We propose a efficient key insertion method by reallocating single elements to resolve collisions.The experimental results for 100thousand keys,it turned out that the propose method is 1.9to32.5 times faster than Morita's method.