1. Design of a high speed string matching co-processor for NLP
- Author
-
P. C. Reghu Raj, S. Raman, and V.S. Murty
- Subjects
Matching (statistics) ,Coprocessor ,Computer science ,business.industry ,Commentz-Walter algorithm ,String searching algorithm ,Parallel computing ,computer.software_genre ,Parallel processing (DSP implementation) ,Interleaved memory ,Artificial intelligence ,business ,Field-programmable gate array ,computer ,Time complexity ,Natural language processing - Abstract
In Natural Language Processing applications, string matching is the main time-consuming operation. A dedicated co-processor for string matching that uses memory interleaving and parallel processing techniques can relieve the host CPU from this burden. This paper reports the FPGA design of such a system with m parallel matching units. It has been shown to improve the performance by a factor of nearly m, without increasing the chip area by more than 45% The time complexity of the proposed algorithm is O(log/sub 2/ n), where n is the number of lexical entries. The memory used by the lexicon has been efficiently organized and the space saving achieved is about 67%.
- Published
- 2003
- Full Text
- View/download PDF