A Fast N-gram Index Construction Algorithm based on Forecast Allocation and Linking Memory Management for Large Chinese Corpus

摘要

To improve the speed of searching and inverted index construction in information retrieval based on large Chinese corpus.N-gram index is chosen for its fast searching speed by comparing with character index and word index.A fast N-gram index construction algorithm base on forecast allocation and linking memory management is presented here to improve the speed of inverted index construction on condition of large corpus.A forecast function is used to allocate memory for inverted list according to the history data when the inverted list is full.And new allocated memory is linked to the end of original space without moving original data.Experimental results demonstrate that the new method improves memory utilization in the course of index construction,and also the time of index construction is decreased.