Approximate String Matching by Combining Automaton Approach and Binary Neural Networks

T. Beran, M. Skrbek, and T. Macek (Czech Republic)


Binary neural networks, correlation matrix memory, and approximate string matching.


This article describes an approximate string matching method based on Correlation Matrix Memories (CMMs). As the measure of similarity, we use the Damerau Levenshtein string edit distance, which is suitable for typ ing errors. CMMs are type of binary neural networks. They are capable of both exact and approximate match ing (based on the Hamming distance). While the substi tution operation can be performed by the common recall ing method of CMM, the other edit operations (insertion, deletion and transposition) require enhancement of the re calling method. We incorporated a simple automaton for each of these operations into the recalling process. The pro posed method preserves the advantage of this type of neural network: its simplicity. To keep both simplicity and the re calling speed, we primarily focus on approximate matching allowing a single error. Besides the edit distance problem we proposed two methods that speeds up the recalling pro cess of CMMs.

Important Links:

Go Back