VERY FAST APPROXIMATE STRING MATCHING ALGORITHMS FOR MULTIPLE ERRORS SPELLING CORRECTION

摘要

string data processing system using fast algorithms for determining an approximate correspondence with character strings in a dictionary (23). For want of example described, it has planned operations on strings with multiple misspellings. The example of fault, '' S-trace '', is used to develop algorithms, and a reduction of four-step process improves the efficiency of a fuzzy matching algorithm chains. This approach to spell checking (of using the upper limit, the partitioning of specific chain length and the cutting test) shows three improvements over that which is to perform a careful comparison. Each is easily incorporated into the next stage. At the fourth step, a calculating method of addressing avoids comparing a specified string with widely separated when words are searched in the vicinity over a small distance. Thus, a sub-linear algorithm to the number of words in the dictionary (23). The application of the algorithms to a library information system is to use original text files (21), a description file information (22) and a negative dictionary (23) stored on disks (12).