近似文字列照合による全文検索のための接尾辞配列の高速走査法 | CiNii Research

タイトル別名 キンジ モジレツ ショウゴウ ニ ヨル ゼンブン ケンサク ノ タメ ノ セツビ ジ ハイレツ ノ コウソク ソウサホウ Fast Traversal of Suffix Arrays for Full - text Approximate String Matching 近似文字列照合による全文検索では，入力パターンと一定以下の編集距離にある部分テキストすべてをテキストから検索する．近似文字列照合による全文検索は，テキストを接尾辞トライにより索引付けし，それを利用して検索することにより実現できる．しかし，接尾辞トライの占める空間領域は大きいため，接尾辞配列を索引として利用することもある．接尾辞配列を索引として利用する場合には，従来研究では，接尾辞トライ上での探索を接尾辞配列上での2分探索により模擬している．それに対して，本稿では，2分探索ではなく，補助的な配列を用いることに