Application of the Constrained Edit Distance Algorithm to Search Procedures


Vladimir Jovičić, Zora Konjović




Searching the sequential file to detect a given substring is a common problem appearing, among others, in text processors and database search systems. One possible approach is OOmmen's constrained edit distance algorithm. The paper contains a brief description of this algorithm and some results of a simulation experiment regarding accuracy and execution speed of the algorithm depending on the probability of the insertion, deletion and substitution errors. The paper also presents one possible practical application of the algorithm to search procedures. Application is based on reduction of the dictionary size according to the probability of editing errors and organization of the contents of the dictionary in a way to so as speed up the search process . Some comparative simulation results are presented illustrating direct and suggested practical applications of the constrained edit distance algorithm to search procedures.