A Syntax Parser Based on the Case Dependency Grammar and Its Efficiency

Toru Hitaka, Sho YoshidaCOLING 1980

TL;DR

This paper introduces a novel, efficient parsing algorithm for Japanese sentences based on a case dependency grammar. It achieves near-optimal parsing times, comparable to general context-free grammar parsers, by leveraging a bottom-up, breadth-first approach that models sentence structure through B-phrases and their dependency relations.

What Problem Does This Paper Address?

Processing Japanese, a language that typically omits spaces between words and B-phrases (syntactic units), poses a significant challenge for natural language processing (NLP). Unlike English, where word segmentation is straightforward, Japanese requires explicit identification of these units to enable grammatical analysis. While augmented transition network (ATN) grammars are common, their flexibility can hinder efficient parsing. This paper aims to develop an efficient parsing algorithm specifically for Japanese, addressing the need for clear unit segmentation and grammatical structure analysis within a case dependency framework.

Methods

The authors propose a parsing algorithm that breaks down Japanese sentences into B-phrases, which are the minimal units of case dependency. The syntax is then modeled in two parts: the internal structure of a B-phrase (as a string of words) and the structure of a sentence (as a string of B-phrases).

The core of their approach is a bottom-up, breadth-first parsing strategy that constructs two key data structures:

  • B-phrase Parse List (BL): This list stores information about potential B-phrases within substrings of the input sentence, including word structures and dependency information. It's built using a dynamic programming approach.
  • Dependency Parse List (DL): This list captures the dependency relationships between B-phrases, representing potential dependency structures of the entire sentence.

The algorithm involves several sub-algorithms: constructing the BL, obtaining B-phrase structures, constructing the DL, and finally, deriving the dependency structure of the sentence. The efficiency is achieved by carefully managing the information stored and the transitions between states, aiming for polynomial time and space complexity.

Datasets

Not discussed in the paper. The paper focuses on the algorithmic aspects and uses hypothetical examples for illustration.

Key Insights and Ideas

  • B-phrase as the fundamental unit: The paper highlights the B-phrase as the crucial unit for analyzing Japanese case dependency, simplifying the parsing problem by decomposing it into intra-B-phrase and inter-B-phrase structures.
  • Bottom-up, breadth-first parsing for efficiency: By building up potential parse structures from smaller units (words and B-phrases) and exploring all possibilities simultaneously, the algorithm avoids the combinatorial explosion often seen in top-down parsers.
  • Dynamic programming for dependency information: The use of dynamic programming to construct the B-phrase parse list (BL) and dependency parse list (DL) allows for efficient reuse of computed information, leading to polynomial time complexity.
  • Near-optimal efficiency: The algorithm achieves parsing times of O(n³) and memory space of O(n²), which is comparable to the most efficient general context-free grammar parsers like the Earley parser. This efficiency is further improved to O(n²) time if the dependency information for each B-phrase is unambiguous.

Key Results

The paper demonstrates that their parsing algorithm can process Japanese sentences with:

  • Time Complexity: O(n³) for general cases, and O(n²) when dependency information is unambiguous, where 'n' is the length of the input sentence.
  • Space Complexity: O(n²) for the parsing algorithm.

The authors claim their parser's efficiency is "nearly equal to the Earley's parser," positioning it as a highly competitive method for Japanese sentence analysis.

Limitations and Future Work

  • Ambiguity: While the paper discusses scenarios where unambiguous dependency information leads to faster parsing, it doesn't deeply explore strategies for handling or resolving ambiguity in dependency relations themselves.
  • Practical Implementation: The paper focuses on the theoretical algorithm and its complexity. Details on practical implementation, handling of real-world linguistic variations, and performance on large corpora are not discussed.
  • Future Work: The authors suggest that further research could explore the efficiency of their algorithm on various types of Japanese sentences and potentially extend it to handle more complex linguistic phenomena.

Summary updated

BibTeX
@inproceedings{hitaka1980syntax,
  author = {Toru Hitaka and Sho Yoshida},
  title = {{A Syntax Parser Based on the Case Dependency Grammar and Its Efficiency}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1980},
}
Figure