Candidate Generators

I. Introduction

Tokens that are identified as spelling errors from detectors will be corrected. The first step is to find correct spelling candidates, then use ranking system to find the best match (highest rank) from the candidate list. The Church's reverse minimum edit distance technique was used to generate non-word spelling and split candidates to avoid expensive edit distance computations between a misspelled word and all words (~0.6 million) in the dictionary. In general, two steps are implemented to find candidates for 1-to-1 and split correction:

• Find the possible candidate from edit distance, phonetic similarity, etc.
  • Edit Distance: over 91% of correction are within 2 edit distance in our training set (baseline - 472 files, 468 instances of dictionary based corrections):

    Edit Distance	Instance	Percentage	Accu. Percentage
    1	317	67.74%	67.74%
    2	110	23.50%	91.24%
    3	24	5.13%	96.37%
    4	8	1.71%	98.08%
    5	6	1.28%	99.36%
    6	2	0.43%	99.79%
    7	1	0.21%	100.00%
    Total	468	100.00%	100.00%

  • Use edit distance 2 as initial specification to cover over 91% of errors.
  • Phonetic and adjacent keys are planned to be investigated and implemented (if needed) for instances with edit distance between 2 and 3 to reach higher recall.
  • Confusion matrix with frequency of letter substitutions could increase the recall (future work).
• Filter by suggestion dictionary
  • A domain specific (customer's) dictionary should be derive for best performance (precision and recall). In general, this dictionary can be the same (or smaller than) checking dictionary. Specific filters (such as multiwords, abbreviations, acronyms, spelling variants, Semantic types, etc.) might be used to derive this dictionary.

II. Algorithm

• candidateNo <= 30 (configurable: CS_CAN_MAX_CANDIDATE_NO)

• 1-To-1 Spelling Candidate Generator
• Split Candidate Generator

• Merge Candidate Generator