An efficient document retrieval method using n-gram indexing

✍ Scribed by Yasushi Ogawa; Toru Matsuda

• Book ID: 104591078
• Publisher: John Wiley and Sons
• Year: 2002
• Tongue: English
• Weight: 169 KB
• Volume: 33
• Category: Article
• ISSN: 0882-1666
• DOI: 10.1002/scj.1106

✦ Synopsis

Abstract

In Japanese, the border between words is not explicitly indicated. Consequently, n‐gram (a tuple of n characters) indexing is usually applied to document retrieval. Retrieval based on the n‐gram indexing is performed for long retrieval words as follows. After dividing the long retrieval word into n‐grams, two‐stage processing is applied, consisting of determination of the retrieval candidate document containing the divided n‐gram, and noise elimination in the candidate document by matching the position of the n‐gram. This paper proposes two methods to speed up the above retrieval processing. One selects the combination that minimizes the processing cost for noise elimination from the n‐gram extracted from the long retrieval word. The other applies additionally an n‐gram other than the one minimizing the cost, extracted from the retrieval word, to the determination of the candidate document, which improves efficiency in narrowing the range of the candidate documents. An evaluation experiment was performed, using 4 years of newspaper articles, and the effectiveness of the proposed methods was demonstrated. © 2002 Scripta Technica, Syst Comp Jpn, 33(2): 54–63, 2002