| The collocation discussed in this article is generalized collocation,a co-occurrence relationship among given contexts,which is also an arbitrary recurrent word combination.Thus,the extraction of collocation is mainly focus on arbitrariness and recurrence.Arbitrariness mentioned here is referred to that the combinations between words can’t be predicted,that is to say,we can’t enumerate all possible rules to constitute a collocation.Secondly,the relative position between the two words of a collocation is uncertain.Two words could be close neighbor,or might be separated by one word,two words or more.Those characteristics make the work of extraction much harder.As collocation is recurrent word combinations among certain range,then,how to find those arbitrary recurrent word combinations in the large-scale corpus?First of all,we applied the method of suffix array to extract collocation with a single computer.Suffix array is an efficient data storage structure,and the sort algorithm of strings is the key procedure to construct a suffix array.But the time complexity of traditional sort algorithm O(nlogn)cannot meet the need of large-scale corpus processing.This paper proposed a modified quick sort algorithm of Chinese strings,whose time complexity is O(n).In order to shorten the processing time,we divided the corpus into several parts,which can be parallel processed by using multithreading techniques.Secondly,we use Hadoop platform to meet the needs of large-scale corpus’ processing and implemented a MapReduce algorithm to extract the long distance collocation.We carried out experiments on different size of test set range from 1MB to 2.73GB.The result shows that,our algorithm has very good performance and scalability.As a result,we acquired a large number of long distance collocation,which cannot be extracted by suffix array.Thirdly,we applied four statistical methods to identify significant collocations,including the mutual information,t-test,chi-square test and log-likelihood ratio test.We found that every methold has its own defects,and not good to be used alone.So,we proprosed a cascaded collocation filtering metholds which make full use of all the four metholds.Finally,we automatically extracted about 4 million two word combinations from the 2.73GB corpus by using the algorithm base on suffix array.Meanwhile,we extracted about 18.13 million long-distance collocation candidates.After the cascaded filtering,we get about 0.945 million common collocations and about 1.794 million long distance collocations. |
