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を圧縮して保持する方法の一つを説明します…