Efficient Methods for Multigram Compound Discovery

Efficient Methods for Multigram Compound Discovery Wu Horng Jyh, Paul Mustard Technology Pte Ltd Republic of Singapore paulwu@mustardtech.com Ng Hong I School of Computing, National University of Singapore Republic of Singapore nghi@comp.nus.edu.sg Gong Ruibin School of Computer Engineering, Nanyang Technological University Republic of Singapore gongrb@pmail.ntu.edu.sg Abstract Multigram language model has become important in Speech Recognition, Natural Language Processing and Information Retrieval. An essential task in multigram language model is to establish a set of significant multigram compounds. In Yamamotto and Church (2001), an 0(NlogN) time complexity method based on Generalised Suffix Array (GSA) has been found, which computes the (term frequency) and df (document frequency) over 0(N) classes of substrings. The ff'and df form the essential statistics on which the metrics, such as MI (Mutual Information) and RIDF (Residual Inverse Document Frequency)', are based for multigram compound discovery. In this paper, it is shown that two related data structures to GSA, Generalised Suffix Tree (GST) and Generalised Directed Acyclic Word Graph (GDAWG) can afford even more efficient methods of multigram compound discovery than GSA. Namely, 0(N) algorithms for computing ff-and df have been found in GST and GDAWG. These data structures also exhibit a series of related, and desirable properties, including an 0(N) time complexity algorithm to classify 0(N2) substrings into 0(N) classes. An experiment based on 6 million bytes of text demonstrates that our theoretical analysis is consistent with the empirical results that can be observed. 1� Introduction Multigram language model has become important in Speech Recognition (SR), Natural Language Processing (NLP) and Information Retrieval (IR) as demonstrated in Siu and Ostemdorf (2000), Peng and Schuurmans (2002), and Chien (1999). It has also been used in evaluating NLP applications such as automatic Machine Translation and Text Summarization (Panineni, etc., 2002; Lin and Hovy, 2003). For a corpus of length N, the computing cost of a naïve algorithm for the frequencies over all substrings is at least 0(N2). In Yamamoto and Church (2001), an efficient method is given for computing the term frequency (/) and document frequency (di), as well as the Mutual Information (MI) and Residual Inverse Document Frequency (RIDF), for all substrings based on Generalized Suffix Array (GSA). The method groups all N(N+ 1)/2 substrings into up to 2N-I equivalence classes, and in this way, the computation is reduced to a manageable computation over these classes, that is, 0(NlogN) time and 0(N) space. It is natural to compare Generalised Suffix Tree (GST) and Generalised DAWG (GDAWG) with GSA since they all can be viewed as compact representations of suffix tries. Moreover, the construction complexities of GST and GDAWG are 0(N), while that of GSA is 0(NlogN). This raises the question: MI and RIDF by Yamamoto and Church (2001) are given below: MI (At ) bg �P (xit ) P(xY ) x P(.111) N �f ( xlt ) x rj (Y ) r (A')�bg ((a)� (a)�2 r(xF)� (Y z ) df RIDF (x) — log — + log(1 — e�) N�r (Y ) Where x and z are tokens, …

Content truncated to 500 words