Hybrid Indexing Revisited (ALENEX2018) で用いられているアルゴリズムについて説明します。この論文の筆者らは、先行研究においてHybrid Indexingという圧縮全文索引を提案していました。 [1306.4037] Hybrid Indexes for Repetitive Datasets https://roy…

以前の記事で何度か触れましたが、FM-indexという方法を使えば完全一致検索を高速に処理できます。他の良い解説の紹介とコード例をあげておきます。 構築時間 検索時間(平均) 検索時間(最悪) (1) Suffix Array O(N) (SAIS) O(M+logN) O(MlogN) (2) (1)+LCP A…

前回までの記事では、完全一致検索を高速化するためにリファレンス文字列に加えてSuffix Arrayを保持していました。しかし、文字列自体よりもSuffix Arrayのほうが大きいのが問題でした。この記事ではSuffix Arrayを圧縮して保持する方法の一つを説明します…

前回の記事で、リファレンス文字列に加えてSuffix Arrayが与えられれば完全一致検索クエリを高速に処理できることを紹介しました。そのコードの最悪時間計算量は(ただしNはリファレンス文字列の長さ、Mはクエリ文字列の長さ)でした。実はSuffix Arrayに加え…

通常の接尾辞配列(suffix array, SA)について書いておきます。 suffix array とは 短く言うと、全てのsuffixを列挙し、それらを辞書順にソートし、suffixの開始位置の順番を配列に格納したものです。例えば文字列"banana"に対するsuffix arrayは以下の通り{5…