Spelling Variant Patterns - MCES (Metaphone, Caverphone Edit Distance, Sorted Distance)

I. Introduction

This enhanced MCES model is based on Double Metaphone (with maxCodeLength = 60, Caverphone 2.0, Edit distance, and min. sorted distance). They are descibed below:

II. Algorithm

This algorithm must apply on a spVar grouped file (such as from SpVarNorm). For those terms are not identified in any spelling variant group, MCES algorithm is used to add more spVars to the existing group by checks following properties:

• Same Metaphone (double) - set maxCodeLength to 60
  • Apache Commons Codec 1.10
  • Apache Commons Codec - Double metaphone
  • Metaphone Generator
• Same Caverphone (2.0)
  • Apache Commons Codec 1.10
  • Apache Commons Codec - Caverphone 2.0
• Exclude GrecoLatin plural
• Limited Edit distance (1: 80.26%, 2:95.41%, 3:99.07%, 4:99.75%)
  • Edit Distance Calculator
• The smallest sorted distance (of candidates match above criteria):
  • All terms are sorted in the alphabetical order. The difference in indexes of two terms is the sorted distance.
  • The closer the sorted distance of two terms is, the more chance that these terms are spelling variants
  • A single term should be only assigned to 1 targetSpVar group (the one with min. sorted distance)

III. Algorithm Details

• Inputs: norm-form|spVar-1|spVar-2|...
• Outputs: base-form|spVar-1|spVar-2|...
• Steps:
  • Save input to HashMap<String, HashSet<String>>
    key-value pairs of (norm-form, HashSet of spVars)
  • group more spVars
    • Pre-process:
      Go through all input norm-form to get:
      • singleSpVarList: the list of single terms (without spVar)
        => It is used as source to add to target spVar group
        => sorted alphabetically
      • sortedSpVarList: the list of sorted spVars
        => It is used for sorted distance
        => sorted alphabetically
      • baseSpVarsMap: the map of (base, list of (sorted spVars))
        => It is the (unsorted) result
        => SpVars is sorted by lexCheck.CheckCont.BaseCompartor
        => base is the first element in the sorted SpVars
        Same comparator used in Lexicon
        1. pure ASCII first
        2. no punctuation first
        3. shortest first
        4. case sensitive alphabetic sort
      • spVarBaseMap: the map of (spVar, base)
        => This map serves as index for adding spVar to the right base
        => All spVars are supposed to be unique
      • mpSpVarsMap: map of (metaphone, set of (spVars))
        =>Used to find all spVars with same metaphone

    • Process:
      Go through all single terms in singleSpVarList to add to spVar class if:
      • Find sameMpSpVarList for spVars with same Metaphone
        • Find metaphone of each singleSpVar
        • Find spVars with same methpahone, sameMpSpVarList, by using mpSpVarsMap
      • Find sameCpSpVarList for spVars with same Caverphone 2.0
      • Find sameCpSpVarList for spVars are not GrecoLatin plural form (to singleSpVar)
      • Find withinEdSpVarList for spVars with same metaphone and within specified edit distance
        • Go through each spVar in sameMpSpVarList from above
        • Check if within specified edit distance
          if so, add all spVar to withinEdSpVarList
      • Find the tragetSpVar with the min. sorted distance to add
        • Go through each spVar in withinEdSpVarList from above
        • Find the targetSpVar with min. sorted distance in withinEdSpVarList, using sortedSpVarList
          targetSpvar is the where the single spvar to add (spVars of single spVar)
      • Add singleSpVar to baseSpVarsMap at tragetSpVar
        • Get targetKey from spVarBase using targetSpVar
        • Get targetValues from spVarBase using singleSpVar
        • Get sourceKey from spVarBase using singleSpVar
        • Get sourceValues from spVarBase using singleSpVar
        • Add sourceValues to the values of baseSpVarsMap with key is targetKey
        • remove sourceKey from baseSpVarsMap
        • update spVarBaseMap by replacing new targetKey with srcValue
      • Final formating for result baseSpVarsMapMES by sorting baseSpVarsMap
        • Go through each baseSpVarsMap
        • Sort values (using LexCheck base comparator)
        • Assign base to the sorted[0]
        • Put to the result baseSpVarsMapMES
  • Print out baseSpVarsMapMES: base-form|spVar-1|spVar-2|...
    • sorted by key (base)

IV. Algorithm Examples