WEKO3
アイテム
ダブル配列におけるキー削除の効率化手法
https://ipsj.ixsq.nii.ac.jp/records/11233
https://ipsj.ixsq.nii.ac.jp/records/11233ffe72bc5-b68f-46ce-8d21-39a83dcc4225
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JNL4405015.pdf (683.5 kB)
|
Copyright (c) 2003 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Journal(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2003-05-15 | |||||||
| タイトル | ||||||||
| タイトル | ダブル配列におけるキー削除の効率化手法 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | An Efficient Key Deletion Method for a Double-array | |||||||
| 言語 | ||||||||
| 言語 | 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 | ||||||||
| 著者名 |
大野, 将樹
× 大野, 将樹
|
|||||||
| 著者名(英) |
Masaki, Oono
× Masaki, Oono
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | トライ法は自然言語処理システムの辞書を中心として広く用いられているキー検索技法であり，トライを実現するデータ構造に検索の高速性と記憶量のコンパクト性をあわせ持つダブル配列構造がある．ダブル配列構造の欠点は，キーの削除によって生じる未使用要素により空間効率が低下する点である．これに対し森田らはダブル配列を詰め直すことにより未使用要素を除去するキー削除法を提案した．しかし，この手法はすべての未使用要素を除去できないため高い空間効率を維持できず，また削除コストが未使用要素数に依存するので，削除を連続するほど削除速度が低下するという問題がある．本論文では，トライの節のうち兄弟を持たない節が多くの割合を占めること，また，これらの節の遷移は容易に変更できるという特徴を利用し，削除を連続した場合でも空間使用率と削除速度を低下させない効率的なキー削除法を提案する．EDR日英単語辞書，WordNet英単語辞書，日本の郵便番号リスト，各5万件に対する実験より，提案法は削除を連続した場合でもきわめて高い空間使用率を維持することが，また，森田らの削除法より約50?200倍高速に削除できることが実証された． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | A trie is a well known method for various dictionaries, such as spelling check and morphological analysis. A double-array structure is an efficient data structure combining fast access of a matrix form with compactness of a list form. The drawback of the double-array is that the space efficiency becomes worse by empty elements produced in key deletion. Therefore, Morita presented a key deletion method eliminating empty elements. However, the space efficiency of this method is low for high frequent deletion. Further, the deletion takes a lot of time because the cost depends on the number of empty elements. In this paper, a fast and compact deletion method is presented by using a property of nodes having no brothers. From simulation results for 50,000 keys, it turned out that the presented method is faster 50 to 200 times than Morita's method and keeps high space efficiency. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN00116647 | |||||||
| 書誌情報 |
情報処理学会論文誌 巻 44, 号 5, p. 1311-1320, 発行日 2003-05-15 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7764 | |||||||
