A model and a fast algorithm for multiple errors spelling correction
type: Item
instance of: scholarly article
title: A model and a fast algorithm for multiple errors spelling correction
zbMATH Open document ID: 0732.68044
DOI: 10.1007/BF01185682
author: N. E. Zubov
published in: Acta Informatica
publication date: 1992-01-01T00:00:00Z
review text: A new model for new multiple errors spelling correction is proposed. The model handles insert, delete, change, and transpose errors. In the new model, we put constraints on possible editing sequences to reflect the error occurrence phenomenon in spelling, resulting in an error measure different from the traditional editing distance error measure. Properties of the ``error distance matrix'' between two character strings are studied under the assumptions of the new model. A cut-off criterion has been discovered, which can detect whether the error distance between two character strings is greater than a prespectified value during the calculation. Based on this cut-off criterion, a fast algorithm has been developed to find the nearest neighbors of a given character string in a dictionary. Experiments have been conducted with results showing that the cut-off criterion can greatly cut down the computation time needed for the nearest neighbor searching.
Mathematics Subject Classification ID: 68W10
zbMATH DE Number: 4211496
zbMATH Keywords: errors spelling correction
zbMATH Keywords: error distance between two character strings
MaRDI profile type: Publication
cites work: A program for correcting spelling errors
cites work: Data structures and algorithms for approximate string matching
cites work: An Extension of the String-to-String Correction Problem
cites work: Spelling correction in systems programs
cites work: A fast algorithm for the longest-common-subsequence problem
cites work: The String-to-String Correction Problem
description: scientific article; zbMATH DE number 4211496