DAWGを用いたダブル配列による全文検索手法
この論文をさがす
抄録
従来,全文検索に用いられる圧縮接尾辞配列は省スペースであるが,順序木の節点数に応じて検索時間が増大する.一方で,ダブル配列は節点間の遷移をO(1)で実現するデータ構造である.そのため,検索時間は検索キーの文字数にのみ依存する.だが圧縮接尾辞配列に比べて,記憶サイズは大きくなる.従来のダブル配列は自然言語処理分野において利用される事例が多かったが,全文検索へ応用したダブル配列構造は発表されていない.そこで本論文では,DAWGを用いてダブル配列を構築し,全文検索を行う手法を提案する.また,大規模な英文やDNA配列におけるサイズおよび検索速度に関して,圧縮接尾辞配列や従来のダブル配列との比較を行う.
収録刊行物
-
- 第77回全国大会講演論文集
-
第77回全国大会講演論文集 2015 (1), 695-696, 2015-03-17
- Tweet
キーワード
詳細情報 詳細情報について
-
- CRID
- 1050292572131343488
-
- NII論文ID
- 170000164719
-
- NII書誌ID
- AN00349328
-
- Web Site
- http://id.nii.ac.jp/1001/00164151/
-
- 本文言語コード
- ja
-
- 資料種別
- conference paper
-
- データソース種別
-
- IRDB
- CiNii Articles