大会名称 |
---|
2009年 情報科学技術フォーラム(FIT) |
大会コ-ド |
F |
開催年 |
2009 |
発行日 |
2009/8/20 |
セッション番号 |
2D |
セッション名 |
辞書・インデキシング |
講演日 |
2009/09/02 |
講演場所(会議室等) |
D会場(9号館1F 914教室) |
講演番号 |
RD-001 |
タイトル |
ダブル配列の遷移集合管理による追加・削除処理の高速化 |
著者名 |
重越 秀美, 蔵満 琢麻, 望月 久稔, |
キーワード |
トライ, ダブル配列, 情報検索 |
抄録 |
自然言語処理システムの辞書を中心に広く用いられるトライのデータ構造として,コンパクトかつ探索処理が高速なダブル配列がある.しかし,ダブル配列は,遷移を定義する際に,遷移集合の取得や配列内の未使用である要素の探索が必要であり,キーの追加・削除処理が高速であるとは言えない. そこで本論文では,各節点における遷移集合を管理するデータ構造を導入することで,遷移定義に要する時間を抑制し,キーの追加・削除処理を高速化する手法を提案する.また,節点集合の要素数に応じて新規節点集合の取得方法を変更することで,追加処理の更なる高速化を図る. |
本文pdf |
PDF download (236KB) |