A Large Russian Morphological Vocabulary for Ibm Compatibles and Methods of Its Compression

Igor A. BolshakovCOLING 1990

TL;DR

This paper introduces a comprehensive Russian morphological vocabulary designed for IBM-compatible PCs, addressing the need for efficient spell-checking and natural language processing tools in the USSR. The authors present novel methods for compressing this large vocabulary, achieving significant size reductions while maintaining usability for applications.

What Problem Does This Paper Address?

Developing robust natural language processing (NLP) tools, particularly for languages with rich morphology like Russian, requires extensive linguistic data. In the USSR during the time of this paper's writing, there was a scarcity of Russian vocabularies available in a computer-readable format suitable for applications like spell checkers. Creating such a vocabulary involves several challenges: it needs to be large enough to cover a significant portion of the language (over 100,000 lexemes), linguistically diverse to handle various domains (science, technology, humanities, everyday life), and account for the complex inflectional nature of Russian words. Furthermore, storing such a large vocabulary on the limited computing resources of IBM-compatible PCs prevalent at the time necessitated efficient compression techniques.

Methods

The authors developed a novel morphological classification scheme for Russian stems, which goes beyond simple word formation to include word derivation. This scheme resulted in 118 classes and 1901 distinct flections (suffixal variations). To compress the resulting vocabulary, they explored several methods. The primary approach involved using Huffman coding for morphological class numbers and the Cooper method for encoding stems. Additionally, the RADIX-50 method was applied to both components of each vocabulary entry. Further compression was achieved by exploiting redundancies such as identical stems across different classes and the adjacency of letters in sequential stems. They also proposed using unoccupied values in the RADIX-50 code table for re-coding frequent final stem letters, digrams, and trigrams.

Datasets

The paper describes the creation and characteristics of a new Russian morphological vocabulary.

  • Size: 67,400 stems covering over 104,700 Russian lexemes and 1.425 million word-forms.
  • Stem Lengths: Minimal: 1 letter, Mean: 7.8 letters, Maximal: 32 letters.
  • Textual Form Size: Approximately 865 KB.
  • Compressed Form Size: Approximately 190 KB.

No external datasets are explicitly mentioned as being used for training or evaluation; the vocabulary itself appears to be the primary dataset constructed by the authors.

Key Insights and Ideas

  • Morphological Classification is Key: The paper highlights that a sophisticated morphological classification system, going beyond simple word formation, is crucial for effectively organizing and compressing a highly inflected language like Russian.
  • Compression is Essential for Usability: The sheer size of a comprehensive Russian vocabulary makes it impractical for direct use on typical PCs. Effective compression is not just a nice-to-have but a necessity for practical applications.
  • Multi-faceted Compression Strategy: A single compression technique is insufficient. Combining methods like Huffman coding, Cooper's method, and RADIX-50, along with exploiting linguistic redundancies, yields the best results.
  • Exploiting Linguistic Patterns: The authors demonstrate that understanding and leveraging patterns in word formation (like letter adjacencies and frequent letter combinations) can significantly improve compression ratios.

Key Results

The authors successfully built a Russian morphological vocabulary with 67,400 stems, covering over 104,700 lexemes and 1.425 million word-forms. The textual form of this vocabulary was about 865 KB. Through their compression methods, they achieved a squeeze ratio of approximately 3.4, which was further increased to 4.2-4.5 by incorporating additional techniques. This resulted in a compressed working form of approximately 190 KB, making it highly suitable for resident use in text processors. The authors claim this size is competitive with English language spell checkers, despite Russian's more complex inflectional system.

Limitations and Future Work

The paper acknowledges that the textual form of vocabularies is not convenient for applications and requires transformation into a binary working form. While they developed utilities for compiling, debugging, and squeezing, the paper doesn't detail the performance of these utilities on other natural language vocabularies beyond Russian. The authors suggest that their methods are applicable to processing any other natural language vocabulary, implying future work could involve testing and adapting these techniques to different languages. The effectiveness of the compression for languages with less complex morphology might also be an area for future exploration.

Summary updated

BibTeX
@inproceedings{bolshakov1990large,
  author = {Igor A. Bolshakov},
  title = {{A Large Russian Morphological Vocabulary for Ibm Compatibles and Methods of Its Compression}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1990},
}
Figure