首页|Efficient Construction of FM-index Using Overlapping Block Processing for Large Scale Texts
Efficient Construction of FM-index Using Overlapping Block Processing for Large Scale Texts
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NETL
In previous implementations of FM-index， the construction algorithms usually need several times larger memory than text size。 Sometimes the memory requirement prevents the FM-index from being employed in processing large scale texts。 In this paper， we design an approach to constructing FM-index based on overlapping block processing。 It can build the FM-index in linear time and constant temporary memory space， especially suitable for large scale texts。 Instead of loading and indexing text as a whole， the new approach splits the text into blocks of fixed size， and then indexes them respectively。 To assure the correctness and effectiveness of query operation， before indexing， we further append certain length of succeeding characters to the end of each block。 The experimental results show that， with a slight loss on the compression ratio and query performance， our implementation provides a faster and more flexible solution for the problem of construction efficiency。
FM-indexself-indexblock processing
Di Zhang、Yunquan Zhang、Jing Chen
展开 >
Institute of Software, Chinese Academy of Sciences
State Key Laboratory of Computer Science
Microsoft Research Asia
European Conference on IR Research(ECIR 2007)
Rome(IT)
Advances in Information Retrieval; Lecture Notes in Computer Science; 4425
NETL
