圧縮ディジタル探索木における辞書情報更新の高速化手法

• Item type: Trans(1)
• 公開日: 2006-09-15
• タイトル: 圧縮ディジタル探索木における辞書情報更新の高速化手法
• タイトル / 言語: en
• タイトル: Fast Computation of Updating Method of a Dictionary for Compression Digital Search Tree
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 研究論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 大阪教育大学
• 著者所属: 大阪教育大学
• 著者所属(英): en
• 著者所属(英): Osaka KyoikuUniversity
• 著者所属(英): en
• 著者所属(英): Osaka KyoikuUniversity
• 著者名: 中村, 康正; 望月久稔
• 著者名(英): Yasumasa, Nakamura; Hisatoshi, Mochizuki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ディジタル探索は，自然言語処理システムの辞書情報構築を中心に広く用いられている検索技法である．また，ディジタル探索木には共通接頭辞のみを格納した圧縮ディジタル探索木がある．圧縮ディジタル探索木のデータ構造として高速性とコンパクト性をあわせ持つダブル配列法があるが，他の動的検索法に比べ更新速度が高速であるとはいえない．そこで本論文では，ダブル配列法に対する更新処理の高速化手法を提案する．提案手法では，圧縮ディジタル探索木上の新規節点を管理することにより追加処理を高速化し，高速化にともなう削除時間の増加を抑制する．20万語の辞書データに対する実験を行った結果，従来法と比べ追加処理は高速となり，削除処理は同等となることが分かった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Digital search is a information retrieval application used widely, such as dictionary information construction of natural language processing system. Digital search tree has compression digital search tree stored only common prefix. As a fast and compact data structure for compression digital search tree, a double窶殿rray is presented. However, the updating processing is not faster than other dynamic retrieval methods. In this paper, we presents a faster method of updates for double-array. In the proposed method, we make insertion algorithm fast by managing a new node position on a compression digital search tree, and reduction algorithm of deletion time. The simulation results for 200 thousands keys turned out that the presented method for insertion processing is faster than original method, and deletion processing is equivalent to original method.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464847
• 書誌情報: 情報処理学会論文誌データベース（TOD）; 巻 47, 号 SIG13(TOD31), p. 16-27, 発行日 2006-09-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7799
• 出版者 / 言語: ja
• 出版者: 情報処理学会