WEKO3
アイテム
近似直線を用いたダブル配列の圧縮法
https://ipsj.ixsq.nii.ac.jp/records/102429
https://ipsj.ixsq.nii.ac.jp/records/102429d04f4032-d351-43af-a187-93fe4c311cc4
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-IFAT14115011.pdf (599.6 kB)
|
Copyright (c) 2014 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2014-07-25 | |||||||
| タイトル | ||||||||
| タイトル | 近似直線を用いたダブル配列の圧縮法 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | A Compression Method of Double Array Structures using Approximate Straight Lines | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | トピック抽出・効率化 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 徳島大学 | ||||||||
| 著者所属 | ||||||||
| 徳島大学 | ||||||||
| 著者所属 | ||||||||
| 徳島大学 | ||||||||
| 著者所属 | ||||||||
| 徳島大学 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| University of Tokushima | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| University of Tokushima | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| University of Tokushima | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| University of Tokushima | ||||||||
| 著者名 |
神田, 峻介
× 神田, 峻介
|
|||||||
| 著者名(英) |
Shunsuke, Kanda
× Shunsuke, Kanda
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | トライ法とはキー検索を実現する手法のひとつであり，自然言語処理などにおいて幅広く活用されている．トライ法を実現するデータ構造としては，ダブル配列や LOUDS などがあげられる．ダブル配列は，トライのノード間の遷移を O(1) で実現する高速性を備えたデータ構造であるが，簡潔データ構造である LOUDS と比べ，記憶量は大きい．LOUDS は，ビットベクトルによりトライを表現するため，コンパクト性に優れたデータ構造であるが，ダブル配列に対し検索速度は劣る．本稿では，近似直線との差分値を用いたダブル配列の圧縮法を提案する．また，Wikipedia 日英タイトル各 20 万語～100 万語に対する実験により，提案手法は従来のダブル配列と比べて，記憶量を約 60%に圧縮し，且つ LOUDS より約 12 倍高速に検索がおこなえることが実証された． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | A trie is one of the method for key search algorithm and utilized in natural language processing and so on. It is represented by a double array and LOUDS. The double array provides fast retrieval at time complexty of O(1), but its space usage is larger than that of LOUDS. LOUDS is a succinct data structure using bit-vector. Its space usage is extremely compact, but its retrieval speed is not so fast. This paper presents a compression method of the double array using approximate straight lines. From simulation results for 200,000～1,000,000 keys, it turned out that the space usage of the presented method becomes about 60% compared with the double array and its retrieval speed is about twelve times faster than that of LOUDS. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN10114171 | |||||||
| 書誌情報 |
研究報告情報基礎とアクセス技術（IFAT） 巻 2014-IFAT-115, 号 11, p. 1-6, 発行日 2014-07-25 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
