CoChat
Sign Up
Cited by 586Algorithms and Data CompressionData Quality and ManagementNatural Language Processing Techniques

Approximate String Matching

Open access
Hall, Patrick A. V., Dowling, Geoff R.·1980·ACM Computing Surveys
DOI 10.1145/356827.356830
Open this paper in CoChat — free accountOpen PDF

Abstract

Approximate matching of strings is reviewed with the aim of surveying techniques suitable for finding an item in a database when there may be a spelling mistake or other error in the keyword.The methods found are classified as either equivalence or similarity problems.Equivalence problems are seen to be readily solved using canonical forms.For sinuiarity problems difference measures are surveyed, with a full description of the wellestablmhed dynamic programming method relating this to the approach using probabilities and likelihoods.Searches for approximate matches in large sets using a difference function are seen to be an open problem still, though several promising ideas have been suggested.Approximate matching (error correction) during parsing is briefly reviewed.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/356827.356830

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 65

  1. AHO, A. V., AND ~ORASICE, M.J. "Fast pattern matching: An aid to bibliographic search," Commun. ACM 18, 6 (June 1975), 333-340.
  2. AHO, A. V., HmSCHSERG, D. S., AND ULL- MAN, J.D. "Bounds on the complexity of the longest common subsequence prob- lem, J. ACM 23, 1 (Jan. 1976), 1-12.
  3. ALBEROA, C.N. "String similarity and misspellings," Commun. ACM 10, 5 (May 1967), 302-313.
  4. BELL, D. "Programmer selection and programming errors," Comput. J. 19, 3 (1976), 202-206.
  5. BLAIR, C.R. "A program for correcting spelling errors," Inf. Control 3 (1960), 60- 67.
  6. BOURNE, C. P., AND FORD, D. J. "A study of methods for systemtically abbre- viating English words and names," J. ACM 8, 4 (Oct. 1961), 538-552.
  7. BOURNE, C.P. "Frequency and impact of spelling errors in bibiographic data bases," Inf. Process. Manage. 13, 1 (1977), 1-12.
  8. BOYER, R. S., AND MOORE, J. S."A fast string searching algorithm." Commun. ACM 20, 10 (Oct. 1977), 762-772.
  9. CORMACK, R.M. "A review of classifi- cation," Royal Statistical Soc. J. 134 (Se- ries A, 1971), 321-367.
  10. DAMERAU, F.J. "A technique for com- puter detection and correction of spelling errors," Commun. ACM 7, 3 (March 1964), 171-176.
  11. DAVlDSON, L. "Retrieval of misspelled Computing Surveys, Vol. 12, No. 4, December 1980
  12. DowL74 DOWL77 EARLT0 EGGE72 ERMA80 FREE63 FU76 i FUNG75 GALI79 GIMP76 GRAH75 GRIE71 HALL71 HALL78 HECK78 HOPC66 names in an airline's passenger record sys- tem," Commun. ACM 5, 3 (March 1962), 169-171.
  13. DOWLING, G. R., AND HALL, P. A. V. "Elastic template matching in speech recognition, using linguistic information," in 2nd Int. Joint Conf. Pattern Recogni. tmn, Copenhagen, Aug. 1974, pp. 249-250 (available from IEEE.).
  14. EARLEY, J. "AII efficient context-free parsing algorithm," Commun. ACM 13, 2 (Feb. 1970), 94-102.
  15. FREEMAN, D. "Error correction in CORC: The Cornell computing language," Ph.D. Dissertation, Cornell University, Ithaca, N.Y., 1963.
  16. Fu, K.S. "Error-correcting parsing for syntactic pattern recognition," in Data- structures, computer graphics and pat- tern recognition, Klinger et al. (Eds.) Ac- ademic Press, New York, 1976.
  17. FUNG, L. W., AND FU, K.S. "Maximum- likelihood syntactic decoding," IEEE Trans. Inform. Theory IT-21 (July 1975), 423-43O.
  18. GALIL, Z. "On improving the worst case running ttme of the Boyer-Moore string matching algorithms," Commun. ACM 22, 9 (Sept. 1979), 505-508.
  19. GIMPEL, J. F. Algorithms m SNOBOL 4, Wiley-Interscience, New York, 1976.
  20. GRAHAM, S. L., AND RHODES, S. P. "Practical syntactic error recovery," Commun. ACM 18, 11 (Nov. 1975), 639- 650.
  21. GRIES, D. Compiler construction for digital computers, Wiley, New York, 1971.
  22. HALL, P. A.V. "Branch and bound and beyond," in Int Joint Conf. Artificial In- telhgence, Imperial College, London, Sept. 1971, pp. 641-650 (available from British Computer Society).
  23. HALL, P. A V., AND HUSSEIN, I. "Design of information systems for Arabic," in In- formation systems methodology, ECI 78 Conference, Venice, Springer-Verlag, New York, 1978, pp. 643-663.
  24. HECKEL, P. "A technique for isolating differences between files," Commun. ACM 21, 4 (April 1978), 264-268.
  25. HUNT77 HUNT, J. W., AND SZYMANSKI, T.G. "A fast algorithm for computing longest com- mon subsequences," Commun. ACM 20, 5 (May 1977), 350-353.
  26. IRONS, E.T. "An error-correcting parser algorithm" '~ Commun. ACM 6, 11 (Nov. 1963), 669-673.
  27. JAME73 JAMES, E. B., AND PARTRIDGE, D. P. "Adaptive correction of program statements," Commun. ACM 16, 1 (Jan. 1973), 27-37.
  28. JENK76 JENKS, R.D. 1976 ACa~ Conf. Symbolic and Algebraic. Computation (ACM), 1976.
  29. KNUT73 KNUTH, D. E. Sorting.and searching, Addison-Wesley, Reading, Mass., 1973.
  30. KNUTH, D. E., MORRIS, J. H., AND PRATT, V.R. "Fast pattern matching in strings," SIAM J. Comput, 6 (1977), 323-350.
  31. LEVY75 LEVY, J. P. "Automatic correction of syntax errors ~ programming languages," Acta Inf. 4 (1975), 271-292.
  32. LiPs79 LIPSKI, W., JR. "On semantic issues con- nected with incomplete information data- bases" ACM Trans. Database Syst. 4, 3 (Sept. 1979), 262-296.
  33. LITE76 LITECKY, C. R., AND DAVIS, G.B. "A study of errors, error.proneness, and error diagnosis in COBOL," Commun. ACM 19, 1 (Jan. 1976), 33-37.
  34. LOWR75 LOWRANCE, S.) AND WAGNER, R. A. "An extension of'the string-to-string correction problem," J. ACM 22, 2 (April 1975), 177-183.
  35. LYON74 LYON, G. "Syntax.directed least-errors analysis for conte~t=free languages: A practical approach," Commun. ACM 17, 1 (Jan, 1974), 3-14., "' MART75 MARTIN, J. Com~uter data base orga- nizatton, Prentice-Hall,~nglewood Cliffs, N.J., 1975.
  36. MicE78 MICKUNAS, M. ~D., ~D MODRY, J. A. "Automatic error recovery for LR parsers," Commun. ACM 21, 6 (June 1978),.459-465.
  37. MORG70 MORGAN, H.L. "Spelling correction in systems progran~" Commun. ACM 13, 2 (Feb. 1970), 90-94.
  38. MUTH77 MUTH, F. E., JR., AND THARP, A. L. "Correcting human error in alphanu- meric terminal input," Inf. Process. Man- age. 13, 6 (1977), 329-337.
  39. 0DELL, M. K., AND RUSSELL, R.C. U,S. Patent nos. 1,261,167 (1918) and 1,435,683 (1922).
  40. PAN, V. YA. "Field extension and tri- TANA78 linear aggregating, uniting, and canceling for the acceleration of matrix multiplica- tions," in Proe. 20th Annual Syrup. Foun- dations of Computer Science, Oct. 1979, TARJ75 pp. 28-38.
  41. PETERSON, W. W. Error.correcting codes, Wiley, New York, 1961.
  42. RAVECKL T. "New approach to the ULLM77 problem of information system effective- ness evaluation," Inf. Process. Manage. 12, 5 (1976), 319-326.
  43. RISEMAN, E. M., AND HANSON, A.R. "A contextual post-processing system for er- VELI70 rot-correction using binary n-grams," IEEE Trans. Comput. C-23, 5 (1974), 480-493.
  44. ROGET The new Roger's thesaurus, N. Lewis (Ed.), Putnam, 1961.
  45. SAKOE, H. "Two level DP.matching--A dynamic programming based pattern matching algorithm for connected word recognition," IEEE Trans. Acoust., Speech, Signal Proc. ASSP-27, 6 (Dec. 1979), 588-595.
  46. SALTGN, G. Automatic reformation or- ganization and retrieval, McGraw-HiU, New York, 1968.
  47. SALTON, G., AND WONG, A. "Generation and search of clustered files," ACM Trans. Database Syst. 3, 4 (Dec. 1978), 321-346.
  48. SHAFFER, L. H., AND HARDWICH, J. "Typing performance as a function of text," Qt. J. Exper. Psychol. 20, 4 (1968), 360-369.
  49. SHAPIRO, M. "The choice of reference points in best match file searching," Com- mun. ACM 20, 5 (May 1977), 339-343.
  50. SMITH, W.B. "Error detection in formal languages," J. Comput. Syst. Sci, 4 (1970), 385-405.
  51. SLINN, C. "Retrieval mechanisms and Arabic strings," in 5th Saudi Arabian WAGN74a WAGN74b WHIT76 WONG76 RECEIVED JANUARY 1980; FINAL REVISION ACCEPTED AUGUST 1980. Computer Conf., Dhahran, Saudi Arabia, March 1979.
  52. SZANZER, A. J. "Error-correcting methods in natural language processing," in Information processing 68, IFIP 1969, pp. 1412-1416.
  53. SZANZER, A.J. "Bracketing technique in elastic matching," Comput. J. 16, 2 (1973), 132-134.
  54. TANAKA, E., AND FU, K.S. "Error-cor. recting parsers for formal languages," IEEE. Trans. Comput. C-27, 7 (July 1978), 605--616.
  55. TAP, JAN, R.E. "Efficiency of a good but not linear set union algorithm," J. ACM 22, 2 (April 1975), 215-225.
  56. TEITELBAUM, R. "Minimal distance analysis of syntax errors in computer pro- grams," Ph.D. Dissertation, Carnegie- Mellon Univ., Pittsburgh, Pa., 1976.
  57. ULLMAN, J.R. "A binary n-gram tech- nique for automatic correction of substi- tution, deletion, insertion and reversal er- rors in words," Comput. J. 20, 2 (1977), 141-147.
  58. UNESCO SPINES thesaurus, The UNESCO Press, Paris, 1976.
  59. VELICHKO, V. M., AND ZAGARUIKO, N. G, "Automatic recognition of 200 words," Int. J. Man.Mack Stud. 2 (1970), 223-234.
  60. VINTSYUK, T. K. "Speech discrimina- tion by dynamic programming," Kiber- netika 4, 1 (1968), 81-88 (in Russian); translated in Cybernetics 4, 1, 52-58.
  61. WAGNER, R. A., AND FISCHER, M. J. "The string-to-string correction prob- lem," J. ACM 21, 1 (Jan 1974), 168-178.
  62. WAGNER, R.A. "Order-n correction for regular languages," Commun. ACM 17, 5 (May 1974), 265-268.
  63. WHITE, G. M., AND NEELY, R. B. "Speech recognition experiments with linear prediction, bandpass filtering, and dynamic programming," IEEE Trans. Acoust., Speech, Signal Proc. ASSP-24, 2 (April 1976), 183-188.
  64. WILCOX, T. R., DAvis, A. M., AND Tm- DALL, M.H. "The design and implemen- tation of a table-driven interactive diag- nostic programming system," Commun. ACM 19, 11 (Nov. 1976), 609-616.
  65. WONG, C. K., AND CHANVRA, A. K. "Bounds for the string editing prob- lem," J. ACM 23, 1 (Jan. 1976), 13-16.

Cited by

Sorted by citations

Authors
Hall, P. A. V., & Dowling, G. R.
Affiliations
  • SCICON Consultancy International Limited, Sanderson House, 49 Berners Street, London WIP 4AQ, England
  • City, University of London (GB)
Venue
ACM Computing Surveys
Publisher
Association for Computing Machinery (ACM)
Published
1980-12
Volume
12
Issue
4
Pages
381-402
ISSN
  • 0360-0300 (ISSN-L)
  • 1557-7341
DOI
10.1145/356827.356830
OpenAlex
W2010392031
Cited by
586
References
0
Citations by year
2026: 3 · 2025: 8 · 2024: 7 · 2023: 13 · 2022: 7 · 2021: 18 · 2020: 11 · 2019: 7 · 2018: 18 · 2017: 16 · 2016: 17 · 2015: 14 · 2014: 23 · 2013: 22 · 2012: 16
FWCI
9.24
Type
journal article
Language
en
Open access
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)
Locations
ACM Computing Surveys (publishedVersion)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
  • Social Sciences › Decision Sciences › Management Science and Operations Research › Data Quality and Management
  • Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
Keywords
approximate string matching, spelling errors, canonical form, similarity measures, dynamic programming, likelihood, error correction, syntactic analysis, database searching, difference function

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review