近似文字列照合による全文検索のための接尾辞配列の高速走査法 | CiNii Research
タイトル別名 Fast Traversal of Suffix Arrays for Full - text Approximate String Matching キンジ モジレツ ショウゴウ ニ ヨル ゼンブン ケンサク ノ タメ ノ セツビ ジ ハイレツ ノ コウソク ソウサホウ 近似文字列照合による全文検索では，入力パターンと一定以下の編集距離にある部分テキストすべてをテキストから検索する．近似文字列照合による全文検索は，テキストを接尾辞トライにより索引付けし，それを利用して検索することにより実現できる．しかし，接尾辞トライの占める空間領域は大きいため，接尾辞配列を索引として利用することもある．接尾辞配列を索引として利用する場合には，従来研究では，接尾辞トライ上での探索を接尾辞配列上での2分探索により模擬している．それに対して，本稿では，2分探索ではなく，補助的な配列を用いることに
pdf: Suffix Array 用語解説
人工 知能学会誌 15 巻 6 号（2000 年 11 月） 1 用語 Suffix Array 解 説 suffix array とは高速な文字列検索を可能にするデー タ構造である。UNIX の grep コマンドのような「テキ ストに対するあらゆる部分文字列の検索」を高速∗1 に行 なうことができる。ただし、あらかじめ検索用インデッ クス ( = suffix array) を作成しておく必要がある。 suffix array のしくみについて説明する前に、まず suffix について説明する。suffix とは検索対象となるテキス ト中のある位置から始まりテキスト末尾までの範囲の文 字列である。どの suffix も開始位置が特定されれば一意 に決まる。この開始位置をインデックスポイント (index point) と呼ぶ [Baeza-Yates 99]。例えば、テキスト「さ くさくさくら」に
SuffixArrayにまつわるソートアルゴリズムの話
This document discusses suffix arrays and methods for constructing them. It provides an overview of suffix arrays, describes common construction algorithms like Ternary QuickSort, Doubling Algorithm by Manber and Myers, and Doubling Algorithm by Larsson and Sadakane. It notes the time complexities of each algorithm and that Larsson and Sadakane's method tends to outperform Ternary QuickSort for la
Suffix Array 検証その後
1. The document discusses suffix arrays, which are data structures that allow efficient full-text searches of a string collection. 2. Suffix arrays build an index by sorting all suffixes of the input strings and can support searches in time proportional to the search pattern length. 3. The document compares search performance between Lucene, which uses inverted indexes, and a Java implementation o
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
インクリメンタルな更新を伴う全文検索インデックスの分散並列処理方式 | CiNii Research
インクリメンタルな更新を伴う全文検索インデックスの分散並列処理方式 | CiNii Research
Suffix arrayの効率的な構築法 | CiNii Research
大規模テキストに対する Suffix Array の効率的な構築法 | CiNii Research
Algorithms on Strings based on the Compressed Suffix Arrays | CiNii Research
インクリメンタルな更新機構を持つ全文検索インデックスの分散並列処理方式 | CiNii Research
省スペースな圧縮接尾辞配列構成アルゴリズム | CiNii Research
分散記憶型並列計算機における大規模接尾辞配列の構築法 | CiNii Research
圧縮接尾辞配列構築アルゴリズムの改良 | CiNii Research
文書データベースへの効率的な索引付けとその更新に関する研究 | CiNii Research
接尾辞配列による効率的な文字列上の同値類計算 | CiNii Research
インクリメンタルな更新機構を備えた全文検索インデックスの分散並列処理方式 | CiNii Research