A high speed string correction method using a hierarchical file

This paper describes a high speed string correction method using a hierarchical file. After reviewing a string correction method based on the Levenshtein distance, a hierarchical file construction method is introduced. A multistage string correction method using this file is proposed. The lower bound of computational complexity is estimated, and it is shown that a multistage method using a special type of a hierarchical file can reduce computational labor greatly. The larger the number of strings considered is, the more efficient the method becomes. The results of computer simulations on 5374 phoneme sequences using two and three stage correction methods are stated. The condition for a multistage string correction method to obtain higher correction rates than an ordinary dictionary method is included.