| Character string matching, which involves finding all the occurrences of a pattern of length 'm' in a string of length 'n', is a very well known problem in the field of information systems. The strings may represent names of persons, postal addresses, number plates of vehicles, DNA sequences, or music notes, depending upon applications, and accordingly, the string matching can either be exact or approximate. Numerous algorithms like KMP [30], Boyer Moore [29], Wagner and Fischer [5], Ukkonen's [3], and CASM [11] have been developed so far to solve this problem efficiently. As the string lengths increase, the overall algorithm complexity in time and space also increases. There has been a huge amount of efforts put forth in the research community to increase the efficiency of such algorithms.;This thesis presents a very simple, efficient and fast implementation method for performing different string operations. The proposed method of implementation is to map the string matching operations into digital hardware. In this thesis, we used a Field Programmable Gate Array (FPGA) to perform the string operations at the lowermost level by representing strings in terms of bits. Several string functions implemented using the FPGA with this approach were found to produce the desired results within few nanoseconds. The efficiency of the aforesaid approach is evident from the experimental results obtained for a variety of string operations. Although we chose to implement the character string algorithms in FPGA technology, these results are equally applicable to dedicated Application Specific Integrated Circuits (ASIC) or other digital circuit implementation technology. |
