TL;DR
This paper introduces a novel, memory-efficient algorithm for calculating n-gram statistics for very large values of 'n' in Japanese text. This breakthrough enables the automatic extraction of words, compound words, and collocations from massive text corpora, overcoming previous computational limitations.
What Problem Does This Paper Address?
The foundational concept of information theory, as proposed by C.E. Shannon, suggests that natural language can be modeled as an n-th order Markov process. This involves calculating the frequencies of character sequences (n-grams). However, applying this to large text datasets and for large 'n' has been computationally prohibitive due to immense memory requirements and processing time. For instance, calculating 10-grams for English would necessitate an astronomical amount of memory. This limitation has historically restricted n-gram analysis to small values of 'n' (typically 4 or 5), hindering deeper linguistic insights. Furthermore, languages like Japanese, which lack explicit word delimiters (spaces), present an additional challenge in automatically identifying word boundaries.
Methods
The authors propose a two-stage algorithm designed for efficient n-gram calculation with large 'n'.
- Stage 1: Substring Sorting and Prefix Coincidence:
- The input text is treated as a single, long character string.
- A pointer table is created, where each entry points to a substring starting from a specific character position to the end of the text. These substrings are effectively treated as "words" for sorting purposes.
- These "words" are then sorted alphabetically using an efficient sorting algorithm (comb sort). The sorting is performed on the leftmost 'n' characters (up to 255) to manage computational complexity.
- Crucially, for adjacent sorted substrings, the length of their common prefix is calculated and stored. This "coincidence number" is key to the next stage.
- This stage is memory-efficient, requiring approximately 71 bytes per character for two-byte encoded text (like Japanese).
- Stage 2: N-gram Frequency Calculation:
- This stage leverages the sorted pointer table and the prefix coincidence table.
- For a given 'n', the algorithm iterates through the sorted substrings. By examining the coincidence numbers between adjacent substrings, it efficiently determines how many times a specific n-character prefix occurs.
- This process avoids pre-allocating massive tables for all possible n-grams. Instead, it calculates frequencies on demand, only storing entries for existing character combinations.
- The authors developed two software versions: one using main memory and another employing disk merge sort for handling extremely large texts.
Datasets
The authors utilized three Japanese text datasets for their experiments:
- Encyclopedic Dictionary of Computer Science: 3.7 MB
- Journalistic essays from Asahi Newspaper: 8 MB
- Miscellaneous texts: 59 MB
The first two datasets were small enough to fit into main memory, while the third, larger dataset required disk-based processing.
Key Insights and Ideas
- Breaking the Memory Barrier: The core innovation is a method that circumvents the prohibitive memory requirements of traditional n-gram calculation, enabling analysis for much larger 'n' values.
- Linguistic Feature Extraction: The primary goal is not just entropy calculation but the practical extraction of linguistic units like words, compound words, and collocations, especially in languages without explicit word separators.
- Word Boundary Determination: The n-gram statistics, particularly for Japanese, are shown to be instrumental in determining word boundaries, a significant challenge in such languages.
- Compound Word Structure: By comparing n-gram frequencies for different 'n' values, the paper demonstrates a method to identify and segment compound words into their constituent parts.
- Collocation Identification: The method effectively identifies strong collocational relationships between words by observing high-frequency co-occurrences in n-grams.
- Unexpected Entropy Behavior: The authors observed that the entropy of Japanese text, contrary to expectations for English, continued to decrease towards zero with increasing 'n' for the datasets used. They attribute this to the large character set of Japanese and the relatively small text quantity, suggesting that significantly larger corpora are needed for meaningful entropy convergence in such languages.
Key Results
- The developed algorithm successfully calculated n-grams for Japanese text with 'n' values up to 30, from texts ranging from 2 to 30 million characters.
- The method enabled the automatic extraction of words, compound words, and collocations.
- The processing time for the first stage was relatively short (1-2 hours for smaller texts on a standard SUN SPARC Station), while the second stage (frequency calculation) was also efficient. The largest dataset (59 MB) required about 24 hours for the first stage due to disk operations.
- The paper provides examples of extracted compound words and collocations, demonstrating the practical utility of the method.
Limitations and Future Work
- Text Quantity for Entropy: The authors acknowledge that the text quantity used was insufficient to observe a stable entropy value for Japanese, suggesting that much larger corpora (gigabytes or more) are needed for meaningful entropy calculations, especially for languages with large character sets.
- Generalizability: While the method is presented as potentially useful for languages like Chinese and European languages, further validation on these languages would be beneficial.
- Future Directions: The authors suggest that this n-gram calculation method could be extended to analyze part-of-speech tagged data to extract grammar rules and could also be applied to phoneme sequences for more detailed IIMM models. They emphasize the value of large, annotated text data for linguistic information extraction.
Summary updated