On the use of words and n-grams for Chinese information retrieval

Jian-Yun Nie, Jianfeng Gao, Jian Zhang, Ming ZhouIRAL 2000 · DOI

TL;DR

This paper investigates optimal indexing strategies for Chinese information retrieval (IR) by comparing word-based and n-gram-based methods. The authors find that combining word-based segmentation with single characters, and optionally incorporating unknown word detection, offers the best balance of performance and efficiency, outperforming pure n-gram approaches.

What Problem Does This Paper Address?

Traditional information retrieval systems rely on segmenting text into meaningful units (like words) for indexing. However, Chinese, unlike many European languages, lacks explicit word boundaries, presenting a significant challenge. This paper addresses the question of how to best segment Chinese text for effective IR, specifically exploring whether word-based segmentation, n-gram-based segmentation, or a combination thereof yields superior results. It also delves into the impact of dictionary completeness and the handling of unknown words on IR performance.

Methods

The authors compare several segmentation and indexing strategies:

  • Longest Matching Algorithm: A dictionary-based approach that identifies the longest possible word at the beginning of a string. They test this with both small and large dictionaries.
  • Full Segmentation: A simpler, linear approach that extracts all possible words from the beginning of a string, even if they overlap or are parts of longer words.
  • N-grams: Specifically, uni-grams (single characters) and bi-grams (pairs of characters) are used as indexes.
  • Combinations: The core of the study involves combining these methods:
  • Longest matching + single characters
    • Full segmentation + single characters
    • Bi-grams + single characters
    • Combinations of word-based methods (longest matching or full segmentation) with bi-grams and characters.
  • Unknown Word Detection: An NLP analyzer is used to identify and incorporate proper nouns and phrases not present in the dictionary.

Datasets

The experiments were conducted on the TREC Chinese corpus. This corpus consists of articles from the People's Daily (1991-1993) and news from the Xinhua News Agency (1994-1995). A set of 54 queries, evaluated by NIST, was used for testing.

Key Insights and Ideas

  • Dictionary Size Matters, But Only So Much: While a larger dictionary for word segmentation improves performance, the gains diminish significantly with very large dictionaries, suggesting that dictionary size alone isn't the most effective path to better IR.
  • Characters are Crucial: Combining single characters (uni-grams) with longer word units significantly boosts recall and overall performance. This is because single characters can capture relevant terms that might be missed if only longer words are used, and they help balance the weighting between compound words and single characters.
  • N-grams Offer Robustness, But at a Cost: Bi-grams are effective at handling unknown words and abbreviations without needing a dictionary. However, they dramatically increase indexing time, storage space, and retrieval time due to the sheer number of potential n-gram indexes.
  • Unknown Word Detection is a Game Changer: Automatically identifying and incorporating unknown words (like proper nouns) can further improve IR performance, especially for queries containing such terms.
  • The Best of Both Worlds: The most effective strategy appears to be a combination of word-based segmentation (specifically, longest matching) with single characters, augmented by unknown word detection. This approach balances precision (from words) and recall (from characters and unknown word handling) while remaining computationally efficient compared to n-gram heavy methods.

Key Results

  • Longest Matching + Large Dictionary: Achieved an average precision of 0.3907.
  • Longest Matching + Single Characters: Improved average precision to 0.4058 (small dictionary) and 0.4290 (large dictionary).
  • Bi-grams + Single Characters: Achieved an average precision of 0.4254, comparable to the best word-based methods.
  • Full Segmentation + Single Characters: Achieved an average precision of 0.4117, but suffered from "cross-word segmentation" errors.
  • Combination of Longest Matching + Characters + Bi-grams: Yielded an average precision of 0.4260.
  • Combination of Full Segmentation + Characters + Bi-grams: Achieved the highest average precision of 0.4400 among tested combinations.
  • Unknown Word Detection: Increased average precision from 0.4290 to 0.4342 for the 54 queries.
  • Overall Best Strategy: The paper concludes that the combination of longest matching with single characters, especially when augmented with unknown word detection, provides the best performance-to-cost ratio.

Limitations and Future Work

  • Dictionary Completeness: While a larger dictionary helps, the paper suggests that simply increasing dictionary size is not the most efficient way to improve IR performance.
  • Computational Cost of N-grams: The significant increase in indexing time and space for n-gram based methods makes them less practical for large-scale IR.
  • Cross-Word Segmentation Errors: Full segmentation, while potentially good for recall, introduces errors that negatively impact precision.
  • Future Work: The authors plan to extend this research to cross-language IR (CLIR), where bi-grams are deemed even less practical due to the difficulty of translating English words to Chinese bi-grams. They emphasize the continued importance of words and characters as primary indexes.

Summary updated

BibTeX
@inproceedings{nie2000use,
  author = {Jian-Yun Nie and Jianfeng Gao and Jian Zhang and Ming Zhou},
  title = {{On the use of words and n-grams for Chinese information retrieval}},
  booktitle = {IRAL},
  year = {2000},
  doi = {10.1145/355214.355235},
}
Figure