WEKO3
アイテム
遷移先節点集合を導入したトライ構造における更新手法の実現
https://ipsj.ixsq.nii.ac.jp/records/43004
https://ipsj.ixsq.nii.ac.jp/records/430043bdb1830-06dd-4b41-8059-6349a39c37ee
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-DD06054001.pdf (342.0 kB)
|
Copyright (c) 2006 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2006-03-22 | |||||||
| タイトル | ||||||||
| タイトル | 遷移先節点集合を導入したトライ構造における更新手法の実現 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Implementation of Updation Techniques for the Trie Structure Based on the Set of Terminal Node | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 大阪教育大学 | ||||||||
| 著者所属 | ||||||||
| 大阪教育大学 | ||||||||
| 著者所属 | ||||||||
| 大阪教育大学 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Osaka Kyoiku University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Osaka Kyoiku University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Osaka Kyoiku University | ||||||||
| 著者名 |
中村, 康正
× 中村, 康正
|
|||||||
| 著者名(英) |
Yasumasa, NAKAMURA
× Yasumasa, NAKAMURA
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 自然言語処理システムを中心に広く用いられているトライ法のデータ構造として、2つの1次元配列を用いたダブル配列法がある。ダブル配列法は高速性とコンパクト法をあわせもつ有効なデータ構造であるが、動的検索法に比べ更新処理が高速であるとはいえない。そのため現在では、未使用要素を双方向リストとして連結する手法が知られているが、遷移先節点探索の計算回数を抑制する手法ではない。そこで本論文では、更新処理を高速化するため、ダブル配列法に遷移情報を格納する1次元配列を新たに用いた手法を提案する。キー集合20万語に対する実験を行った結果、提案手法は双方向リストを用いた手法より、追加処理は約2.4倍、削除処理は約2.1倍高速となった。 | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | 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 doubly list is known now, it is not the technique of controlling the complexity of terminal node search. In this paper, we presents a fast insertion and deletion algorithms by connecting empty elements as doubly list and reduction algorithm of deletion time. From the simulation results for 200 thousands keys, it turned out that the presented method for insertion is about 2.4 times faster than the doubly list method, and deletion is about 2.1 times faster than the doubly list method. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN10539261 | |||||||
| 書誌情報 |
情報処理学会研究報告デジタルドキュメント（DD） 巻 2006, 号 33(2006-DD-054), p. 1-6, 発行日 2006-03-22 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
