@techreport{oai:ipsj.ixsq.nii.ac.jp:00217765,
 author = {荒川, 侑馬 and Gonzalo, Navarro and 定兼, 邦彦},
 issue = {2},
 month = {May},
 note = {反復の多い文字列を効率的に圧縮する索引は，バイオインフォマティクスやバージョン管理されたリポジトリなどの分野において有用である．Burrows-Wheeler 変換 (BWT) の連長圧縮を用いて実現される r-index はそのような索引の一種であり，BWT における run の数を r としたとき，O(r) 語の空間計算量でパターンの出現位置を高速に検索することができる．この検索は，パターンの後方探索の過程で接尾辞配列のサンプルを保持し，そのサンプルからパターンの出現位置を全て計算するアルゴリズムにより実現される．本研究では，このアルゴリズムを発展させ，パターンを双方向に拡張可能かつ，探索の任意の時点でパターンの出現位置列挙が可能である双方向 r-index(br-index) を提案する．また，数値実験により，索引サイズ，および DNA のアラインメントを模した検索クエリの速度を評価する．, Indexing highly repetitive texts is important in fields such as bioinformatics and versioned repositories. The run-length compression of the Burrows-Wheeler transform (BWT) provides a compressed representation particularly well-suited to text indexing. The r-index is one such index. It enables fast locating of occurrences of a pattern within O(r) words of space, where r is the number of equal-letter runs in the BWT. Its mechanism of locating is to maintain one suffix array sample along the backward-search of the pattern, and to compute all the pattern positions from that sample once the backward-search is complete. In this paper we develop this algorithm further, and propose a new bi-directional text index called the br-index, which supports extending the matched pattern both in forward and backward directions, and locating the occurrences of the pattern at any step of the search, within O(r+rR) words of space, where rR is the number of equal-letter runs in the BWT of the reversed text. Our experiments show that the br-index captures the long repetitions of the text, and outperforms the existing indexes in text searching allowing some mismatches except in an internal part.},
 title = {双方向r-index},
 year = {2022}
}