PLATO Approximate String Matching

In 1986, a survey of approximate string matching algorithms found the algorithm used in the PLATO computer-aided instruction system was third place in quality (F1 score) and was an order of magnitude faster than the best performing algorithms. The PLATO algorithm used an unusual dimensional projection approach, while the competing algorithms of the day used edit distances or phonetics. However, this approach failed to catch on and the design is rarely mentioned in the literature. This video describes how the algorithm worked and some reasons why it became forgotten.

Damerau, Fred J. "A technique for computer detection and correction of spelling errors." Communications of the ACM, vol. 7, issue 3, March 1964, 171-176. https://doi.org/10.1145/363958.363994

Navarro, Gonzalo. "A Guided Tour to Approximate String Matching." ACM Computing Surveys, vol. 33, issue 1, March 2001, 31-88. https://doi.org/10.1145/375360.375365

Nesbit, John C. “Approximate string matching in response analysis.” Journal of Computer-Based Instruction 12.3 (1985): 71-75. https://archive.org/details/sim_journal-of-computer-based-instruction_summer-1985_12_3/page/n15/mode/1up

Nesbit, John C. “The accuracy of approximate string matching algorithms.” Journal of Computer Based Instruction 13.3 (1986): 80-83. https://archive.org/details/sim_journal-of-computer-based-instruction_summer-1986_13_3/page/n18/mode/1up

Tenczar, Paul and Golden, William. "Spelling, Word, and Concept Recognition." Computer-based Education Research Laboratory, University of Illinois, 1972. https://www.computerhistory.org/collections/catalog/102723111

Ray Ozzie clip courtesy of the Computer History Museum. https://www.computerhistory.org/collections/catalog/102792129