|
In computer science, an FM-index is a compressed full-text substring index based on the Burrows-Wheeler transform, with some similarities to the suffix array. It was created by Paolo Ferragina and Giovanni Manzini,〔Paolo Ferragina and Giovanni Manzini (2000). "Opportunistic Data Structures with Applications". Proceedings of the 41st Annual Symposium on Foundations of Computer Science. p.390.〕 who describe it as an opportunistic data structure as it allows compression of the input text while still permitting fast substring queries. The name stands for Full-text index in Minute space.〔Paolo Ferragina and Giovanni Manzini (2005). "Indexing Compressed Text". Journal of the ACM (JACM), 52, 4 (Jul. 2005). p. 553〕 It can be used to efficiently find the number of occurrences of a pattern within the compressed text, as well as locate the position of each occurrence. Both the query time and storage space requirements are sublinear with respect to the size of the input data. The original authors have devised improvements to their original approach and dubbed it "FM-Index version 2".〔(Paolo Ferragina and Rossano Venturini "FM-Index version 2" )〕 A further improvement, the alphabet-friendly FM-index, combines the use of compression boosting and wavelet trees 〔P. Ferragina, G. Manzini, V. Mäkinen and G. Navarro. An Alphabet-Friendly FM-index. ''In Proc. SPIRE'04'', pages 150-160. LNCS 3246.〕 to significantly reduce the space usage for large alphabets. The FM-index has found use in, among other places, bioinformatics.〔Simpson, Jared T. and Durbin, Richard (2010). "Efficient construction of an assembly string graph using the FM-index". Bioinformatics, 26, 12 (Jun. 17). p. i367〕 == Background == Using an index is a common strategy to efficiently search a large body of text. When the text is larger than what reasonably fits within a computer's main memory, there is a need to compress not only the text but also the index. When the FM-index was introduced, there were several suggested solutions that were based on traditional compression methods and tried to solve the compressed matching problem. In contrast, the FM-index is a compressed self-index, which means that it compresses the data and indexes it at the same time. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「FM-index」の詳細全文を読む スポンサード リンク
|