Automatic error-correction in natural languages

A.j. SzanserCOLING 1969

TL;DR

This paper introduces "elastic matching," a novel technique for automatically correcting spelling errors in natural language processing. By representing words as sequences of "lines" and comparing them with shifts, it efficiently handles common typos like missing, extra, or swapped letters, paving the way for more robust text processing systems.

What Problem Does This Paper Address?

As computers become increasingly involved in processing natural language, a significant challenge arises from errors introduced by human operators during data input. These errors, often simple typos, can render text unreadable to machines. Traditional methods of checking every possible correction are computationally prohibitive. This paper tackles the problem of efficiently and accurately correcting these common spelling mistakes in natural language texts, aiming to improve the reliability of computer-based language processing.

Methods

The core innovation presented is "elastic matching." This method involves:

  1. Linearization: Words are converted into a sequence of "lines" based on a pre-determined order of letters (a custom alphabet sequence optimized for text). This means letters are arranged into segments based on their position in this custom sequence.
  2. Line-by-Line Matching: The "linearized" word is then compared with a correct word from a dictionary, also in its linearized form. The comparison is done line by line.
  3. Shifted Matching: If the number of lines in the misspelled word and the correct word differ (due to extra or missing letters), the lines of the longer version are shifted to find the best match.
  4. Error Detection: Discrepancies between the lines are identified as "disagreeing bits," which correspond to potential errors.
  5. Error Classification: Simple checks are applied to distinguish between single errors (like a missing letter, an extra letter, or a wrong letter) and multiple errors (which are generally rejected if they exceed a defined limit, e.g., one error per word).

To further refine the process and resolve ambiguities (multiple potential correct words), two supplementary procedures are proposed:

  • General-Content Check: This method leverages the observation that words tend to be repeated within a text. It stores frequently occurring "content" words (nouns, verbs, adjectives) from the input text and prioritizes dictionary matches that are present in this store.
  • Syntactic Analysis: This approach uses grammatical structure to disambiguate potential matches, particularly useful for shorter "function" words that might otherwise lead to many possible corrections.

Datasets

The paper describes an experiment conducted at the National Physical Laboratory. For this experiment:

  • A custom linearizing sequence for English texts was established through statistical and linguistic analysis, and refined using computer tests. The sequence found is: FJVWMBPHIOQUEARLNXGS CK TDYZ.
  • Due to the lack of a comprehensive dictionary at the time, the general-content check procedure was used to compile lists of words from selected stretches of English text (parts of articles on physics, linguistics, and socio-politics), totaling approximately 3,000 text words.
  • Later stages of the experiment involved using the Palantype-English dictionary, containing about 80,000 entries, with an initial focus on entries starting with the letter 'S' (approximately 10% of the dictionary).

Key Insights and Ideas

  • The Power of "Elasticity": The core idea of "elastic matching" is that by treating words as flexible sequences of "lines" that can be shifted, the system can gracefully accommodate common typographical errors without needing to exhaustively check every permutation.
  • Custom Alphabets Matter: The choice of the linearizing sequence is crucial. The paper highlights that a custom sequence, rather than the standard alphabet, can optimize the "line" formation, leading to more efficient matching and fewer lines per word.
  • Complementary Error Correction: The paper effectively argues that "elastic matching" is most powerful when combined with other techniques. The "general-content check" and "syntactic analysis" are presented as essential complements to handle the ambiguities that elastic matching alone might produce, especially for shorter or more common words.
  • Content vs. Function Words: The distinction between "content" words (rich in meaning) and "function" words (grammatical glue) is recognized as important for error correction strategies, with content words being more amenable to general-content checks and function words benefiting more from syntactic analysis.

Key Results

The experiment yielded several key findings:

  • High Accuracy: The retrievals were reported as both "exact and complete," meaning no misspelled words within the defined error limit were missed, and no incorrect words were suggested.
  • Ambiguity Increases with Shorter Words: The number of multiple possible corrections increased significantly as the length of the misspelled word decreased, particularly for words with fewer than four letters.
  • Content Words Yield Fewer Ambiguities: "Content" words generally resulted in only one correct retrieval, whereas "function" words frequently produced multiple equivalents.
  • Successful Application to Palantype: The elastic matching technique was also explored for the automatic transcription of machine-shorthand (Palantype system), demonstrating its versatility beyond standard text input.

Limitations and Future Work

  • Dictionary Size: The initial experiments were limited by the availability of a comprehensive English dictionary. The paper notes that using a larger dictionary (like the 80,000-entry Palantype-English dictionary) is a crucial next step.
  • Real-Time Performance: While the methods show promise, achieving true "real-time" error correction for all applications remains a challenge, especially with full dictionary lookups. The possibility of generating an "errata" sheet immediately after normal output is suggested.
  • Syntactic Analysis Depth: The paper mentions that syntactic analysis for resolving ambiguities was initially limited to inspecting only adjacent words. Further study is planned to explore more comprehensive syntactic checks.
  • Non-Textual Material: The supplementary methods (general-content check and syntactic analysis) are noted as not being directly applicable to non-textual material like lists of names.
  • Further Plans: The authors intend to extend the work to the full English dictionary, investigate optimal dictionary organization, and further study the application of syntactic analysis for ambiguity resolution. They also mention considering applications for retrieving misspelled proper names from lists.

Summary updated

BibTeX
@inproceedings{szanser1969automatic,
  author = {A.J. Szanser},
  title = {{Automatic error-correction in natural languages}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1969},
}
Figure