A Hardware Algorithm for High Speed Morpheme Extraction and Its Implementation

A HARDWARE ALGORITHM FOR HIGH SPEED MORPHEME EXTRACTION AND ITS IMPLEMENTATION Toshikazu Fukushima, Yutaka Ohyama and Hitoshi Miyai C&C Systems Research Laboratories, NEC Corporation 1-1, Miyazaki 4-chome, Miyamae-ku, Kawasaki City, Kanagawa 213, Japan (fuku@tsl.cl.nec.co.jp, ohyama~tsl.cl.nec.co.jp, miya@tsl.cl.nec.co.jp) ABSTRACT This paper describes a new hardware algorithm for morpheme extraction and its implementation on a specific machine (MEX-I), as the first step toward achieving natural language parsing accel- erators. It also shows the machine's performance, 100-1,000 times faster than a personal computer. This machine can extract morphemes from 10,000 character Japanese text by searching an 80,000 morpheme dictionary in I second. It can treat multiple text streams, which are composed of char- acter candidates, as well as one text stream. The algorithm is implemented on the machine in linear time for the number of candidates, while conven- tional sequential algorithms are implemented in combinational time. 1 INTRODUCTION Recent advancement in natural language pars- ing technology has especially extended the word processor market and the machine translation sys- tem market. For further market extension or new market creation for natural language applications, parsing speed-up as well as improving parmng ac- curacy is required. First, the parsing speed-up directly reduces system response time required in such interactive natural language application sys- tems as those using natural language interface, speech recognition, Kana-to-Kanjl i conversion, which is the most popular Japanese text input method, and so on. Second, it also increases the advantage of such applications as machine transla- tion, document proofreading, automatic indexing, and so on, which are used to treat a large amount of documents. Third, it realizes parsing meth- ods based on larger scale dictionary or knowledge database, which are necessary to improve parsing accuracy. Until now, in the natural language processing field, the speed-up has depended mainly on perfor- mance improvements achieved in sequential pro- cesslng computers and the development of sequen- tial algorithms. Recently, because of the further IKan~ characters are combined consonant and vowel symbols used in written Japanese. Kanjl characters ~re Chinese ideographs. speeded-up requirement, parallel processing com- puters have been designed and parallel parsing al- gorithms (Matsumoto, 1986) (Haas, 1987) (Ryt- ter, 1987) -(Fukushima, 1990b) have been pro- posed. However, there are many difficult problems blocking efficient practical use of parallel process- ing computers. One of the problems is that ac- cess confiicts occur when several processors read or write a common memory simultaneously. An- other is the bottle-neck problem, wherein commt- nication between any two processors is restricted, because of hardware scale limitation. On the other hand, in the pattern processing field, various kinds of accelerator hardware have been developed. They are designed for a special purpose, not for general purposes. A hardware approach hasn't been tried in the natural language processing field yet. The authors propose developing natural lan- guage parsing accelerators, a hardware approach to the parsing speed-up (Fukushima, 1989b) -(Fukushima, 1990a). This paper describes a new hardware algorithm for high speed morpheme ex- traction and its implementation on a specific ma- chine. This morpheme extraction …

Content truncated to 500 words