Approximate String Matching
ACM Computing SurveysPublished 1 December 1980Open access
Patrick A. V. Hall, Geoff R. Dowling
Citations586
SJR quartileQ1
SJR score5.80
SNIP11.03
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
article Free Access Share on Approximate String Matching Authors: Patrick A. V. Hall SCICON Consultancy International Limited, Sanderson House, 49 Berners Street, London WIP 4AQ, England SCICON Consultancy International Limited, Sanderson House, 49 Berners Street, London WIP 4AQ, EnglandView Profile , Geoff R. Dowling Department of Computer Science, The City University, Northampton Square, London EC1V OHB, England Department of Computer Science, The City University, Northampton Square, London EC1V OHB, EnglandView Profile Authors Info & Claims ACM Computing SurveysVolume 12Issue 4pp 381–402https://doi.org/10.1145/356827.356830Published:01 December 1980Publication History 404citation4,280DownloadsMetricsTotal Citations404Total Downloads4,280Last 12 Months374Last 6 weeks62 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
Keywords
Computer Science
Journal of the ACMThe String-to-String Correction Problem
3,063 Citations1974Robert A. Wagner, Michael J. Fischer
An algorithm is presented which solves the string-to-string correction problem in time proportional to the product of the lengths of the two strings.
Communications of the ACMEfficient string matching
2,946 Citations1975Alfred V. Aho, Margaret J. Corasick
A simple, efficient algorithm to locate all occurrences of any of a finite number of keywords in a string of text that has been used to improve the speed of a library bibliographic search program by a factor of 5 to 10.
SIAM Journal on ComputingFast Pattern Matching in Strings
2,917 Citations1977Donald E. Knuth, James H. Morris +1 more
An algorithm is presented which finds all occurrences of one given string within another, in running time proportional to the sum of the lengths of the strings, showing that the set of concatenations of even palindromes, i.e., the language $\{\alpha \alpha ^R\}^*$, can be recognized in linear time.
Communications of the ACMA fast string searching algorithm
2,292 Citations1977Robert S. Boyer, J Strother Moore
The algorithm has the unusual property that, in most cases, not all of the first i.” in another string, are inspected.
ACM Computing SurveysUbiquitous B-Tree
1,826 Citations1979Douglas E. Comer
The major variations of the B-tree are discussed, especially the B+-tree, contrasting the merits and costs of each implementation and illustrating a general purpose access method that uses a B- tree.
Communications of the ACMA technique for computer detection and correction of spelling errors
1,573 Citations1964Fred J. Damerau
The method described assumes that a word which cannot be found in a dictionary has at most one error, which might be a wrong, missing or extra letter or a single transposition.
Sorting and Searching
1,536 Citations1973Donald E. Knuth
Formal Languages and Their Relation to Automata
1,341 Citations1969John E. Hopcroft, Jeffrey D. Ullman
The theory of formal languages as a coherent theory is presented and its relationship to automata theory is made explicit, including the Turing machine and certain advanced topics in language theory.
ACM Computing SurveysThe Hearsay-II Speech-Understanding System: Integrating Knowledge to Resolve Uncertainty
1,341 Citations1980Lee D. Erman, Frederick Hayes‐Roth +2 more
The characteristics of the speech problem in particular, the special kinds of problem-solving uncertainty in that domain, the structure of the Hearsay-II system developed to cope with that uncertainty, and the relationship between Hearsey-II's structure and those of other speech-understanding systems are discussed.
Communications of the ACMAn efficient context-free parsing algorithm
817 Citations1970Jay Earley
A parsing algorithm which seems to be the most efficient general context-free algorithm known is described and appears to be superior to the top-down and bottom-up algorithms studied by Griffiths and Petrick.
Communications of the ACMA fast algorithm for computing longest common subsequences
692 Citations1977James Hunt, Thomas G. Szymanski
An algorithm for finding the longest common subsequence of two sequences of length n which has a running time of O((r + n) log n), where r is the total number of ordered pairs of positions at which the two sequences match.
A Survey of Modern Algebra
673 Citations2017Garrett Birkhoff, Saunders Mac Lane
ACM Transactions on Database SystemsOn semantic issues connected with incomplete information databases
513 Citations1979Witold Lipski
This work emphasizes the distinction between two different interpretations of the query language—the external one, which refers the queries directly to the real world modeled in an incomplete way by the system, and the internal one, under which the queries refer to the system's information about this world, rather than to the world itself.
CERN Document Server (European Organization for Nuclear Research)Compiler construction for digital computers
451 Citations1971David Gries
The techniques involved in writing compilers for high-level languages such as FORTRAN or PL/1, as well as semantic routines, are described.
Journal of the ACMAn Extension of the String-to-String Correction Problem
318 Citations1975Robert A. Wagner, Roy Lowrance
The set of allowable edit operations is extended to include the operation of interchanging the positions of two adjacent characters under certain restrictions on edit-operation costs, and it is shown that the extended problem can still be solved in time proportional to the product of the lengths of the given strings.
IEEE Transactions on Acoustics Speech and Signal ProcessingTwo-level DP-matching--A dynamic programming-based pattern matching algorithm for connected word recognition
258 Citations1979Hiroaki Sakoe
A general principle of connected word recognition is given based on pattern matching between unknown continuous speech and artificially synthesized connected reference patterns and Computation time and memory requirement are both proved to be within reasonable limits.
Journal of the ACMBounds on the Complexity of the Longest Common Subsequence Problem
248 Citations1976Jeffrey D. Ullman, Alfred V. Aho +1 more
It is shown that unless a bound on the total number of distinct symbols is assumed, every solution to the problem can consume an amount of time that is proportional to the product of the lengths of the two strings.
SIAM Journal on ComputingA Minimum Distance Error-Correcting Parser for Context-Free Languages
230 Citations1972Alfred V. Aho, Thomas G. Peterson
An algorithm is presented that will parse any input string to completion finding the fewest possible number of errors on a random access computer.
International Journal of Man-Machine StudiesAutomatic recognition of 200 words
223 Citations1970V. Velichko, N. G. Zagoruyko
The logarithmic characteristics of acoustic signal in five bands are extracted as features and the measure of similarity between the words of standard and control sequences is calculated by the words maximizing a definite functional using dynamic programming.
IEEE Transactions on Acoustics Speech and Signal ProcessingSpeech recognition experiments with linear predication, bandpass filtering, and dynamic programming
158 Citations1976Greg White, Richard Neely
Automatic speech recognition experiments are described in which several popular preprocessing and classification strategies are compared and it is shown that dynamic programming is of major importance for recognition of polysyllabic words.
The Computer JournalA binary n-gram technique for automatic correction of substitution, deletion, insertion and reversal errors in words
132 Citations1977J. Ullmann
Journal of the ACMBounds for the String Editing Problem
123 Citations1976C. K. Wong, Ashok K. Chandra
It is shown that if the operations on symbols of the strings are restricted to tests of equality, then O(nm) operations are necessary (and sufficient) to compute the distance between two strings.
Communications of the ACMA technique for isolating differences between files
123 Citations1978Paul Heckel
A simple algorithm is described for isolating the differences between two files that corresponds closely to the intuitive notion of difference, is easy to implement, and is computationally efficient, with time linear in the file length.
IEEE Transactions on ComputersA Contextual Postprocessing System for Error Correction Using Binary n-Grams
112 Citations1974Edward M. Riseman, Allen R. Hanson
Various algorithms utilizing context are considered, from a dictionary algorithm which has available the maximum amount of information, to a set of contextual algorithms utilizing positional binary n-gram statistics.
Communications of the ACMOrder- <i>n</i> correction for regular languages
110 Citations1974Robert A. Wagner
The method presented requires time proportional to the number of characters in α.
ACM Transactions on Database SystemsGeneration and search of clustered files
107 Citations1978Gerard Salton, Anita M.-Y. Wong
An abstract model is introduced to predict the retrieval effectiveness of various search methods in a clustered file environment and to demonstrate the role of various parameters in the cluster search process.
Communications of the ACMSpelling correction in systems programs
106 Citations1970Howard L. Morgan
By using systems which perform spelling correction, the number of debugging runs per program has been decreased, saving both programmer and machine time.
Communications of the ACMOn improving the worst case running time of the Boyer-Moore string matching algorithm
105 Citations1979Zvi Galil
It is shown how to modify the Boyer-Moore string matching algorithm so that its worst case running time is linear even when multiple occurrences of the pattern are present in the text.
OPAL (Open@LaTrobe) (La Trobe University)Speech-understanding systems : final report of a study group
84 Citations2018Allen Newell
An evaluation of the state of the art and a program for research towards the development of speech understanding systems to assess the possibility of such systems four specific tasks were considered and evaluated.
Information and ControlA program for correcting spelling errors
83 Citations1960Charles R. Blair
A program using a simple, heuristic procedure for associating “similar” spellings is able to correct misspelled words using only a vocabulary of properly spelled words.
Communications of the ACMSyntax-directed least-errors analysis for context-free languages
83 Citations1974Gordon Lyon
A least-errors recognizer is developed informally using the well-known recognizer of Earley, along with elements of Bellman's dynamic programming, and takes a general class of context-free grammars as drivers and any finite string as input.
Quarterly Journal of Experimental PsychologyTyping Performance as a Function of Text
76 Citations1968L. H. Shaffer, Jane Hardwick
Communications of the ACMThe choice of reference points in best-match file searching
75 Citations1977Marvin B. Shapiro
The proper choice of reference points is discussed and the previous algorithm to use more than one reference point is extended and it is shown that reference points should be located outside of data clusters.
Communications of the ACMRetrieval of misspelled names in an airlines passenger record system
72 Citations1962Leon Davidson
It is evident that a policg statemerd regarding publishb~9 of p(tpers m~ business subjects would be bellyful, and it is highlg desirable to hate papers on busb~ess attd sei(utt~/ie ttpplications in the same department.
Communications of the ACMAn error-correcting parse algorithm
65 Citations1963Edgar T. Irons
It is the author's opinion that those algorithms which do the best job of error recovery are those which are restricted to simpler forms of formal languages.
Communications of the ACMString similarity and misspellings
63 Citations1967Cyril N. Alberga
The problem of programming a computer to determine whether or not a string of characters is a misspelling of a given word was considered and a number of algorithms were evaluated--some proposed by other writers, some by the author.
Acta InformaticaAutomatic correction of syntax-errors in programming languages
63 Citations1975J. -P. L�vy
A formal model for automatic error-correction that considers clusters of errors, using a local context to determine the corrections, can be embedded in left-to-right recognizers.
Communications of the ACMA study of errors, error-proneness, and error diagnosis in Cobol
54 Citations1976Charles R. Litecky, Gordon B. Davis
Data is provided on Cobol error frequency for correction of errors in student-oriented compilers, improvement of teaching, and changes in programming language to imply high potential effectiveness for software-based correction of Cobol.
IEEE Transactions on ComputersError-Correcting Parsers for Formal Languages
46 Citations1978Tanaka, King‐Sun Fu
This paper describes error-correcting parsers for context-free and context-sensitive languages with substitution, insertion and deletion errors with weighted Levenshtein metric.
Information Processing & ManagementFrequency and impact of spelling errors in bibliographic data bases
45 Citations1977Charles P. Bourne
Estimates were made of the spelling error frequencies of each of these data bases, as well as the frequency of posting to misspelled terms, using a composite sample of over 3600 index terms drawn from 11 different machine-readable bibliographic data bases.
Communications of the ACMThe design and implementation of a table driven, interactive diagnostic programming system
44 Citations1976Thomas R. Wilcox, Alan M. Davis +1 more
CAPS is a highly interactive diagnostic compiler/interpreter that allows beginning programmers to prepare, debug, and execute fairly simple programs at a graphics display terminal.
Field extension and trilinear aggregating, uniting and canceling for the acceleration of matrix multiplications
43 Citations1979Victor Y. Pan
The acceleration of matrix multiplication MM, is based on the combination of the method of algebraic field extension and trilinear aggregating, uniting and canceling and a fast algorithm of O(N2.7378) complexity for N × N matrix multiplication is derived.
Journal of the ACMA Study of Methods for Systematically Abbreviating English Words and Names
40 Citations1961Charles P. Bourne, Donald F. Ford
This study investigated various techniques for systematically abbreviating English words and names and particular attention was paid to techniques that could process incoming information without prior knowledge of its existence.
Information Processing & ManagementCorrecting human error in alphanumeric terminal input
34 Citations1977Frank E. Muth, Alan L. Tharp
The computerized correcting process is presented as a heuristic tree search and has the highest error correction accuracy to date.
Communications of the ACMAutomatic error recovery for LR parsers
33 Citations1978M. Dennis Mickunas, John A. Modry
The approach, which is patterned after that of Levy and Graham and Rhodes, appears to provide error recovery which is both simple and powerful.
Elsevier eBooksError-Correcting Parsing For Syntactic Pattern Recognition
24 Citations1977K. S. Fu
A clustering procedure is proposed, where error-correcting parsers are employed to determine the distance between an input syntactic pattern and a formed cluster, or a language.
International Joint Conference on Artificial IntelligenceBranch-and-bound and beyond
22 Citations1971Patrick A. V. Hall
The branch-and-bound algorithm is stated in generality, and illustrated by two applications, unidirectional graph search, and reducing a sparse matrix to its minimal band form, which is generalised to multiple partitions, applied to bidirectionalgraph searching for both heuristic and non-heuristic searches, and further extended to graph searches and problem solving with subgoals.
Journal of Computer and System SciencesError detection in formal languages
14 Citations1970William Bridges Smith
It is found that the first two classes of errors yield essentially equivalent effects on properties of the automata considered, and that the same is true for the latter two classes (called ''expanding'' errors).
Communications of the ACMAdaptive correction of program statements
13 Citations1973E. B. James, Derek Partridge
This method involves principles at present mainly confined to studies in the area of artificial intelligence such as feature extraction, approximate tree matching, and strategy improvement by feedback from the matching process.
Error correction in CORC
12 Citations1964David N. Freeman
CORC, the Cornell Computing Language, is an experimental compiler language developed at Cornell University that has a radically simpler syntax than either FORTRAN and ALGOL, since it was designed to serve university students and faculty.
Information Processing & ManagementNew approach to the problem of information system effectiveness evaluation
12 Citations1976Tadeusz Radecki
The concepts of relevance and pertinence, which are the basic concepts used in determining the indices of information system effectiveness evaluation, have been defined and parameters of quality evaluation of the process of profile control of a document set of the information system have beendefined.
Lecture notes in computer scienceDesign of information systems for Arabic
2 Citations1978Patrick A. V. Hall, Ismael A. Hussein
The design of information systems for the handling of Arabic text is considered and the final objective is assumed to be the storage of information in Arabic, with the requirement later to retrieve the information using Arabic.