On optimizing syntactic pattern recognition using tries and AI-based heuristic-search strategies

• Published in: IEEE transactions on cybernetics 2006-06, Vol.36 (3), p.611-622
• Main Authors: Badr, G., Oommen, B.J.
• Format: Article
• Language: English
• Subjects: Algorithms; Approximate string matching; Artificial Intelligence; artificial intelligence (AI); Benchmarking; Computer science; Costs; Cybernetics; Data structures; Dictionaries; Errors; Information Storage and Retrieval - methods; Language; local beam search (BS); Natural Language Processing; noisy syntactic recognition using tries; Optimization; Pattern matching; Pattern recognition; Pattern Recognition, Automated - methods; Searching; Speech Recognition Software; Strings; trie-based syntactic pattern recognition (PR)
• ISSN: 1083-4419; 2168-2267; 1941-0492; 2168-2275
• DOI: 10.1109/TSMCB.2005.861860

This paper deals with the problem of estimating, using enhanced artificial-intelligence (AI) techniques, a transmitted string X/sup */ by processing the corresponding string Y, which is a noisy version of X/sup */. It is assumed that Y contains substitution, insertion, and deletion (SID) errors. The best estimate X/sup +/ of X/sup */ is defined as that element of a dictionary H that minimizes the generalized Levenshtein distance (GLD) D(X,Y) between X and Y, for all X/spl isin/H. In this paper, it is shown how to evaluate D(X,Y) for every X/spl isin/H simultaneously, when the edit distances are general and the maximum number of errors is not given a priori, and when H is stored as a trie. A new scheme called clustered beam search (CBS) is first introduced, which is a heuristic-based search approach that enhances the well-known beam-search (BS) techniques used in AI. The new scheme is then applied to the approximate string-matching problem when the dictionary is stored as a trie. The new technique is compared with the benchmark depth-first search (DFS) trie-based technique (with respect to time and accuracy) using large and small dictionaries. The results demonstrate a marked improvement of up to 75% with respect to the total number of operations needed on three benchmark dictionaries, while yielding an accuracy comparable to the optimal. Experiments are also done to show the benefits of the CBS over the BS when the search is done on the trie. The results also demonstrate a marked improvement (more than 91%) for large dictionaries.