Optimizing a text retrieval system utilizing N-gram indexing
Fatih Mehmet Comlekoglu · Medical Entomology and Zoology · 1990
This dissertation presents an alternative to classical automated text retrieval methods, such as full text scanning, word indexing, and multiattribute retrieval. It explores a new approach to text retrieval that uses a finite number of word fragments, called n-grams. The dissertation classifies n-grams as overlapping or nonoverlapping and studies their distributions in a sample of English text, called the Brown corpus, and a list of 275,981 unique English words. The impact of n-gram size and the resulting n-gram distributions on the overall performance of an n-gram inverted text retrieval system is measured by implementing an experimental n-gram inverted text retrieval system. N-gram inverted systems are compared and contrasted on the basis of n-gram size and on the basis of overlapping and nonoverlapping n-grams, in accordance with text retrieval performance parameters defined as main and secondary memory utilization and average query response time. The dissertation concludes that, for certain n-grams, n-gram inverted text retrieval systems are unequivocally superior to classical word inversion techniques when the ability to respond to Variable Length 'Don't Care' (prefix, infix, and postfix) queries is a prominent factor in the design of a text retrieval system. It further concludes that there is no unique way of determining the optimum size of an n-gram when implementing an n-gram inverted text retrieval system. Rather, the study concludes that optimum n-gram size is highly dependent on the subjective judgment of the designer, especially with regard to trade-offs among three subjective decision parameters: availability of main memory, availability of secondary storage, and desired response time.