Introduction
Traditional Natural Language Processing (NLP) systems for English typically operate under the assumption that word boundaries are trivial to identify, usually by splitting text at whitespace. However, real-world typed text is often "noisy." Users frequently commit typographic errors that delete spaces (e.g., "witha" for "with a") or insert them (e.g., "hey er" for "never"). Furthermore, punctuation and multi-word idioms introduce ambiguities that a simple deterministic tokenizer cannot resolve.
When a system attempts to "fix" these errors before parsing, it often makes incorrect guesses due to a lack of context. Conversely, if it fails to address them, the parser often crashes or fails to find a valid structure. The CLARE system addresses this gap between low-level tokenization and high-level linguistic understanding by moving away from "one-word-at-a-time" processing in favor of a lattice-based representation.
System Architecture
CLARE utilizes a staged architecture centered around a directed acyclic graph, or lattice, where edges represent different hypotheses for tokens. This approach allows the system to delay final word identification until syntactic and semantic analysis can be applied.
Lattice Generation and Interleaved Correction
Instead of a single sequence of words, the system generates a lattice of possibilities. CLARE performs "affix-stripping" (identifying prefixes and suffixes) simultaneously with spelling correction. This allows it to handle complex errors that overlap with morpheme boundaries, such as correcting "desigend" to "designed."
The system employs both local and global recovery methods. Local methods address individual tokens, while global methods propose corrections that span across spaces, such as merging or splitting tokens to find a valid interpretation. As shown in the figure above, the lattice can represent multiple paths through the same character sequence, keeping various hypotheses alive for the parser.
Syntactic and Semantic Filtering
The generated lattice is passed to a parser that applies syntactic and semantic constraints. Many "nonsense" spelling corrections are naturally pruned because they do not conform to the grammar or the "sortal" (selectional) restrictions of the sentence. The final output is a set of Quasi Logical Forms (QLFs)—logical representations of meaning—which are then ranked by scoring functions to select the most plausible interpretation.
Experimental Methodology
The system was evaluated using 500 sentences randomly selected from the Lancaster-Oslo/Bergen (LOB) corpus. To simulate real-world conditions, these sentences were passed through a "noisy channel" with a 1% character error rate, modeling common human typographic errors such as insertions, deletions, substitutions, and transpositions. The system operated on a core lexicon of approximately 1,600 root forms.
Key Results
The primary insight of this research is the "power of delay." By maintaining multiple hypotheses in a lattice, the system leverages the parser's intelligence to resolve low-level typos. High-level linguistic constraints proved incredibly effective at reducing ambiguity.
As demonstrated in the table above, for tokens where the spelling corrector suggested multiple candidates, the average number of hypotheses was 4.57. Applying syntactic and semantic constraints (the "In any QLF" stage) reduced this to 1.69, effectively removing 72% of the uncertainty. Furthermore, parsing the lattice was found to be up to 3x faster than attempting to parse each possible string interpretation individually, as the lattice structure allows for the sharing of common paths.
Conclusion and Future Work
The CLARE system demonstrates that word identification should not be a mere pre-processing step. While the current experiment used a relatively small vocabulary, the results suggest that linguistic constraints are robust; the system produced a "false positive" (a valid but incorrect parse) in only 2% of cases where it originally failed.
Future work includes scaling the system to larger vocabularies and integrating statistical frequency data (such as n-gram probabilities) to further prune unlikely candidates. Additionally, incorporating phonological knowledge could help the system correct "competence errors" based on phonetic misspellings rather than just typographic slips.
Summary updated