自然言語処理における効果的な辞書情報更新アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2005-09-30
• タイトル: 自然言語処理における効果的な辞書情報更新アルゴリズム
• タイトル / 言語: en
• タイトル: Effective Update Algorithms of Dictionary Information in Natural Language Processing
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪教育大学
• 著者所属: 大阪教育大学
• 著者所属(英): en
• 著者所属(英): Osaka Kyoiku University
• 著者所属(英): en
• 著者所属(英): Osaka Kyoiku University
• 著者名: 中村, 康正; 望月久稔
• 著者名(英): YASUMASA, NAKAMURA; HISATOSHIMOCHIZUKI
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: トライ法は，自然言語処理システムの辞書情報構築を中心に広く用いられている．このトライ法のデータ構造として，青江らが提案したダブル配列法がある．ダブル配列法は高速性とコンパクト性をあわせもっており有効なデータ構造であるが，動的検索法に比べデータの更新処理が高速であるとはいえない．そこで現在では未使用要素を単方向リストとして連結する手法が知られているが，トライ木の希点を追加および削除する際に大きなコストを必要とする．そこで本論文では，未使用要素を双方向リストとして連結することにより追加処理を高速化し，さらに削除時間を抑えるアルゴリズムを提案する．10万語の辞書データに対する実験を行った結果，追加速度は単方向リストよりも約1．5倍，削除時間は未使用要素リストを用いない従来法と同等となることが判った．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10115061
• 書誌情報: 情報処理学会研究報告自然言語処理（NL）; 巻 2005, 号 94(2005-NL-169), p. 117-122, 発行日 2005-09-30
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会