WEKO3
アイテム
シングル状態を利用したダブル配列における動的追加の高速化
https://ipsj.ixsq.nii.ac.jp/records/47926
https://ipsj.ixsq.nii.ac.jp/records/479265fa816e7-908b-4065-b87f-dd50b84e25f2
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-NL06173005.pdf (943.9 kB)
|
Copyright (c) 2006 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2006-05-19 | |||||||
| タイトル | ||||||||
| タイトル | シングル状態を利用したダブル配列における動的追加の高速化 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Efficient Dynamic Key Insertion Algotithms by using Single State for a Double-array structure | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 千葉工業大学大学院情報科学専攻 | ||||||||
| 著者所属 | ||||||||
| 千葉工業大学情報工学科 | ||||||||
| 著者所属 | ||||||||
| 千葉工業大学情報ネットワーク学科 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Information and Computer Science ，Department of Computer Science，Department of Information and Network Science，Chiba Institute of Technology | ||||||||
| 著者名 |
永井, 弘之
× 永井, 弘之
|
|||||||
| 著者名(英) |
HIROYUKI, NAGAI，ＳＨＩＧＥUＦUＪITA，ａｎｄＫＥＮＪＩＳUＧＡWＡＲＡ
× HIROYUKI, NAGAI，ＳＨＩＧＥUＦUＪITA，ａｎｄＫＥＮＪＩＳUＧＡWＡＲＡ
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 自然言語処理システムに広く用いられているキー検索法として，トライ法があり，トライを表現可能なデータ構造として，ダブル配列がある．ダブル配列は，検索の高速性と空間利用率の高さを兼ね備えた，優れたデータ構造である．しかし，ダブル配列ではキーの検索時間に比べ，動的追加時間が遅い欠点がある．ダブル配列に対して，キーの動的追加を行うと，衝突が発生し，その回避に多くの計算量を要している問題がある．本論文では，ダブル配列において，遷移可能な次状態が単一であるシングル状態の多数性，およびシングル状態からの遷移先であるシングル要素の機動性を利用し，キーの動的追加時に生じる衝突を，効率的に回避することで，動的追加処理を高速化する手法を提案する．評価実験では，それぞれ１０万件のデータを使用し，WordNet英語単語辞書で１．９倍，IPADIC日本語単語辞書で8.7倍，郵便番号で32.5倍，森田らの手法よりも高速に追加できることを確認した． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Trie is a well known key retrieve method for natural language processing sysｔｅms and ｔｈｅ Double-array ｉｓ ａ fastand compact data structure for a trie.However,dynamic key insertion time is not as ｆast as key sarch time,because of resolving collisions take a lot of time.Ａ double-array has many single states and its successor is singlee elements.Single elements have a property that easy to reallocate.In this paper,We propose a efficient key insertion method by reallocating single elements to resolve collisions.The experimental results for 100thousand keys,ｉｔ ｔｕrnｅｄ oｕｔ ｔｈａｔ ｔｈｅ propose ｍｅｔｈod is 1.9to32.5 times faster than Morita's method． | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN10115061 | |||||||
| 書誌情報 |
情報処理学会研究報告自然言語処理（NL） 巻 2006, 号 53(2006-NL-173), p. 29-34, 発行日 2006-05-19 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
