Quality of early 1970s approximate string matching algorithms

2022-06-16

Approximate string matching algorithms (ASMA) determine if two strings are the same, “close enough”, or are distinct. Spelling error detection and correction were early applications of these algorithms, and today ASMAs (or similar techniques) are used in natural language understanding applications. Hundreds of papers have been written on the subject (1980 survey, 2001 survey), but this post is focused on the subset of algorithms that were considered commercially viable for the field of computer-assisted instruction (CAI), an early hardware/software-as-a-service business.

Background

Between 1985 and 1986, John C. Nesbit wrote a pair of articles¹² for the Journal of Computer-Based Instruction examining the accuracy of ASMAs. His interest was using the algorithms for student response matching in computer-aided instruction. A student response is a typed answer to a question posed by an educational program. For example, the question “who was the second president of the United States?” might wish to accept variants such as:

1. John Adams
2. John A Adams
3. John A. Adams
4. President Adams
5. Pres. Adams
6. Adams

If the student responded with “Jon Adams” (misspelling John), the developer may wish that answer to be accepted or to coax the student to fix their answer rather than rejecting it outright. Similarly, if the student answered “Thomas Jefferson” (or variants thereof), the developer may want to reject the answer with a suggestive message such as “Jefferson was the third president”. As you likely intuiting, the sheer range of variants possible would be very tedious for the developer unless the CAI system added labor-saving techniques.

Some CAI systems would go beyond simple spell-correction and provide response normalization features. For instance, PLATO would treat “three” and “3” as equivalent, as well as “1/2”, “0.5”, “2/4”, and “50/100”. There were also facilities to treat mathematical expressions such as “100 + (a * b)/(c + d)” as equivalent to all the other possible forms. Given the limited CPU and memory available (and the fact that response matching was a very common operation), these features used a number of tricks and heuristics, rather than implementing a computer algebra system.

Nesbit selected a group of ten algorithms that were either being used for CAI applications or had performed well in previous studies. He implemented and evaluated all of the algorithms on a DEC VAX-11/780 except for PLATO, which ran on its native CDC CYBER 170/720.

There were two operative theories for how words became misspelled. The first theory was that words were often misspelled such that they were correct phonetically. The second theory is that misspellings come from random errors that drop, insert, substitutions, and sometimes transpose characters. Blair, PLANIT, Soundex, and Symonds were based on the phonetic theory. Alberga, EDIST1, EDIST2, and Damerau were based on edit distance. Damerau-Symonds combined the two theories. PLATO projected words into a bitstring via a variety of feature extraction rules.

Results

Table 1 is based on the four figures from (Nesbit 1986). We extracted the Type I and Type II errors from the figures via visual examination, and based on data about the four datasets (Table 2), computed a F1 score. For the algorithms Alberga, EDIST1, and EDIST2, since the figures included a range of values, we took the value closest to the origin. Table 3 summarizes the results for each algorithm using the harmonic mean of the F1 score from each of the four datasets.

Table 1: Qualitative measurements from (Nesbit 1986) plus F1 Score

Table 2: Datasets used in (Nesbit 1986)

Table 3: Harmonic Mean of F1 Scores

In descending order, the best performing algorithms by quality were EDIST2, EDIST1, PLATO, Damerau-Symonds, Alberga, Damerau, Soundex, Blair, and Symonds.

Conclusion

By the early 1970s, edit distance based algorithms were showing their qualitative superiority to phonetically based algorithms. Furthermore, edit distance based algorithms were more amenable to multiple languages, while the phonetic algorithms evaluated were all tuned for English text. (However, all the datasets used English examples.) However, edit distance algorithms were more costly to compute than the others in the sample (except Damerau, which restricted the error count to one). EDIST1 and EDIST2 both required computing the edit distance, which cost \(O(mn)\) time and \(O(mn)\) space where m and n were the length of the two strings, although in 1980 a solution with \(O(m)\) space was found (Navarro 2001). Solutions with \(O(kn)\) time were found in the 80s and 90s, where k was the error threshold. Today, edit distance is the standard technique for handling errors in information retrieval, conversational analytics, and biological informatics.

The PLATO algorithm stands apart in the group due to its excellent performance, both in terms of quality and computational speed. Its design was inspired by a numerical taxonomy approach and uses techniques from cluster analysis. Due to the novelty and effectiveness of the approach, we will discuss details of the implementation in a future production.