Efficient Methods for Multigram Compound Discovery
Horng Jyh Paul Wu, Hong I Ng, Ruibin Gong · Waseda University Repository (Waseda University) · 2003
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.