A Statistical Method for Extracting Uninterrupted and Interrupted Collocations from Very Large Corpora

A Statistical Method for Extracting Uninterrupted and Interrupted Collocations from Very Large Corpora Satoru Ikehara, Satoshi Shirai and Hajime Uchino NTT Communication Science Laboratories Take 1-2356, Yokoshuka-shi, Japan (E-mail:{ikehara, shirai, uchino}@nttkb.ntt.jp) Abstract In order to extract rigid expressions with a high fre- quency of use, new algorithm that can efficiently extract both uninterrupted and interrupted collocations from very large corpora has been proposed. The statistical method recently proposed for calculating N-gram of m'bitrary N can be applied to the extraction of uninterrupted collocations. But this method posed pro- blems that so large volumes of fractional and unnecessary expressions are extracted that it was impossible to extract interrupted collocations combining the results. To solve this problem, this paper proposed a new algorithm that restrains extraction of unnecessary substrings. This is followed by the proposal of a method that enable to extract interrupted collocations. The new methods are applied to Japanese newspaper articles involving 8.92 million characters. In the case of uninterrupted collocations with string length of 2 or mere characters and frequency of appearance 2 or more times, there were 4.4 millions types of expressions (total fre- quency of 31.2 millions times) extracted by the N-gram method. In contrast, the new method has reduced this to 0.97 million types (total frequency of 2.6 million times) revealing a substantial reduction in fractional and un- necessary expressions. In the case of interrupted collo- cational substring extraction, combining the substring with frequency of 10 times or more extracted by the first method, 6.5 thousand types of pairs of substrings with the total frequency of 21.8 thousands were extracted. I. Introduction In natural language processing, the importance of large volume corpus has been pointed out together with the need for technology of analyzing these linguistic data. For example, in machine translation, there are many expres- sions that are difficult to be translated literally. Phrase translations or pattern translations based on phrase or pattern dictionaries are considered very useful for the translations of these expressions. In order to realize these translation, it is required to identify phrases of high frequency and patterns of expres- sions from the corpora. There are many method proposed to extract rigid expressions from corpora such as a method of focusing on the binding strength of two words (Church and Hanks 1990); the distance between words (Smadja and Makeown 1990); and the number of combined words and frequency of appearance (Kita 1993, 1994). But it was not easy to identify and extract expressions of arbitrary lengths and high frequency of appearance from very large corpora. Thus, conventional methods had to introduce some kinds of restrictions such as the limitation of the kind of chains or the length of chains to be extracted (Smadja 1993, Shinnou and Isahara 1995). Recently, a new method which can calculate arbitrary number of n-gram statistics for very large corpora has been proposed (Nagao and Mori 1994). This method has made it possible to automatically and quickly extract and tabulate substrings of any length used in source texts. …

Content truncated to 500 words