Header menu link for other important links
X
Design of a language-independent parallel string matching unit for NLP
Vadali Srinivasa Murty
Published in Institute of Electrical and Electronics Engineers Inc.
2003
Pages: 149 - 155
Abstract
In Natural Language Processing applications, string matching is the main time-consuming operation due to the large size of lexicon. Data dependence is minimal in string matching operations, and hence it is ideal for parallelization. A dedicated hardware for string matching that uses memory interleaving and parallel processing techniques can relieve the host CPU from this burden, thereby making the system suitable for real-time applications. This paper reports the FPGA design of such a system with m parallel matching units. The time complexity of the proposed algorithm is O (log2 n), where n is the total number of lexical entries. This has been achieved by a proper selection of the value of m. A special memory organization technique, which reduces the storage space by nearly 70%, has been adopted for storing lexical entries. The techniques used for matching and storage of lexical entries make the system language independent. ©2003 IEEE.
Concepts (13)
  •  related image
    Computational linguistics
  •  related image
    Digital storage
  •  related image
    Memory architecture
  •  related image
    Natural language processing systems
  •  related image
    APPROXIMATE MATCHES
  •  related image
    INTERLEAVED LEXICON
  •  related image
    LANGUAGE INDEPENDENCE
  •  related image
    LANGUAGE INDEPENDENTS
  •  related image
    Natural language processing applications
  •  related image
    PARALLEL MATCHING
  •  related image
    PARALLEL STRING MATCHING
  •  related image
    Real-time application
  •  related image
    Computer architecture