WEKO3
アイテム
ダブル配列における動的更新の効率化アルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/11861
https://ipsj.ixsq.nii.ac.jp/records/1186141d6e72d-6c8b-4da5-86aa-f3f719346a68
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JNL4209005.pdf (286.4 kB)
|
Copyright (c) 2001 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Journal(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2001-09-15 | |||||||
| タイトル | ||||||||
| タイトル | ダブル配列における動的更新の効率化アルゴリズム | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Efficient Dynamic Update Algorithms for a Double-array Structure | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | 論文 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| その他タイトル | ||||||||
| その他のタイトル | 自然言語処理 | |||||||
| 著者所属 | ||||||||
| 徳島大学工学部 | ||||||||
| 著者所属 | ||||||||
| 徳島大学工学部 | ||||||||
| 著者所属 | ||||||||
| 徳島大学工学部 | ||||||||
| 著者所属 | ||||||||
| 徳島大学工学部 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculty of Engineering, Tokushima University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculty of Engineering, Tokushima University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculty of Engineering, Tokushima University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculty of Engineering, Tokushima University | ||||||||
| 著者名 |
森田, 和宏
× 森田, 和宏
|
|||||||
| 著者名(英) |
Kazuhiro, Morita
× Kazuhiro, Morita
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | トライ構造はキーの表記文字単位に構成された木構造を用いて検索するキー検索技法の1つであり，自然言語辞書を中心として広く用いられている．このトライ構造を実現するデータ構造として高速性とコンパクト性を満足するダブル配列法があるが，この手法は，キーの更新が頻繁に生じない検索法として確立しているため，動的検索法に比べて追加時間は高速であるとはいえず，また削除で生じる不要なノードや未使用要素により記憶量に無駄が生じていた．本論文ではこれらの問題を解決し，ダブル配列を動的検索法として確立するため，未使用要素を連結することで追加処理を高速化する手法，削除時に生じる不要ノードの削除と未使用要素の詰め直しによる圧縮法を提案する．10万語の辞書データに対する実験結果により，追加速度については約1 600倍高速となることが，また大量の削除が起こった場合でも50%以上の空間使用率を維持することが分かった． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | In many information retrieval applications,it is necessary to be able to adopt a trie search for looking at the input character by character.As a fast and compact data structure for a trie, a double-array is presented.However, the insertion time isn't faster than other dynamic retrieval methods because the double-array is a semi-static retrieval method that cannot treat high frequent updating.Further, the space efficiency of the double-array degrades with the number of deletions because it keeps empty elements produced by deletion.This paper presents a fast insertion algorithm by linking empty elements to find inserting positions quickly and a compression algorithm by reallocating empty elements for each deletion.From the simulation results for 100 thousands keys,it turned out that the presented method for insertion is about 1,600 times faster than the original method,and that the presented method for space efficiency keeps the activity ratio more than 50%. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN00116647 | |||||||
| 書誌情報 |
情報処理学会論文誌 巻 42, 号 9, p. 2229-2238, 発行日 2001-09-15 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7764 | |||||||
