SPT - Pattern Permutation Design

I. Introduction
This page describes the algorithm used to find all patterns permutation of sub-term from a given input. A pattern is one of possible synonym permutation (please see the example for details).

II. Algorithm

  • Find all sub-terms of the input that has synonyms
    • Sort by the order of start index, then end index
    • subTerms: terms has synonyms

  • Find all patterns
    • parameters:
      • inWordIndex: the index of InWords
      • subTermObjIndex: the index of SubTerm Objs

      • subTermObj: SubTerm object includes: sub term|start index|end Index
      • startIndex: start index of SubTerm object[SubTerm Index]
      • prevStartIndex: previous start index of SubTerm Object[SubTerm Index-1]

      • patterns: pattern of terms|synonyms
      • baseTermsWordCount: word count of the base terms in the pattern

    • Initiation
      • inWordIndex = 0
      • subTermIndex = 0
      • patterns = new Vector<Pattern>();

    • Go through each InWord (word from input) and perform following actions:
      • Go through each subTerm (terms have synonyms)
        • CASE-I: current inWord is not a subTerm (starting word)

          ConditionsActions
          • subTermObjIndex >= subTerms.size() or
            current inWord is after the last subTerms
          • inWordIndex != startIndex
            current inWord is not a subTerm
          • add inWord (no synonyms) to all patterns
          • move to next inWord (inWordIndex++)

        • CASE-II: current inWord is a subTerm (starting word)
          • subTermObjIndex < subTerms.size() and
          • inWordIndex == startIndex
          • instantiate synonyms with current subTermObj
          • CASEConditionsActions
            II.1
            • subTermObj.GetEndIndex()-1 == subTermObj.GetStartIndex()
              => the base form of subTerm is a single word
              => this word must be the first subTerm starting with current inWord (sorted)
            • add synonyms to all patterns
            II.2
            • subTermObj.GetEndIndex()-1 != subTermObj.GetStartIndex()
              => base term of subTerm is a multi-words
            • add inWord to all patterns

            • get last patterns
              • get all patterns with last element removed
              • add to lastPatterns if
                • startIndex == totalBaseTermsWordCount
                  =>same position for subTerm replacement
                • pattern does not exist in lastPatterns
            • add synonyms to all lastPatterns
            • add all lastPatterns to patterns
          • move to next inWord (inWordIndex++) if current inWord is not the next subTerm (startIndex != nextStartIndex)
          • move to next subTerm (subTermObjIndex++) if subTerm is not the last one (subTermObjIndex < subTerms.size( ))

  • Add synonyms (Vector<String> with a single element, single word) to patterns

    ConditionAction
    patterns.size() == 0
    =>no pattern exist, first word
    • instantiate a new pattern
    • add synonyms to this new pattern
    • add this new pattern to patterns
    patterns.size() > 0
    pattern exist, not the first word
    • go through all pattern
    • add synonyms to each pattern if the last element does not contains the subTerm (of this single inWord)

III. Java Classes & Method

  • Pattern.java: a Java class for pattern object
  • PatternPermutation.java: a Java class for pattern permutation
  • public Vector<pattern> FindPatternPermutation(String inTerm, SynonymsMapping synonymsMapping, TrieTreeMatch trieTreeMatch, boolean recursiveFlag)

IV. Examples

  • Input: Synonym Rules

    wordsynonym
    dogcanine
    catfeline
    canineK9
    K9bull dog
    Dog and catpets
    puppy and kittypets

  • Input: Synonym Terms

    Terms
    dog
    canine
    cat
    feline
    k9
    bull dog
    dog and cat
    pets
    puppy and kitty

  • Input Term:
    Who let dog and cat out
    InWord Index012345
    InWordwholetdogandcatout

  • Permutation Algorithm Example
    • Find all sub-terms of the input that has synonyms from previous section
      • Sort by the order of start index, then end index

      • SubTerm IndexSub TermStart IndexEnd Index
        0dog23
        1dog and cat25
        2cat45

    • Find all patterns
      InWord IndexInWordSubTerm IndexSubTerm ObjStart IndexPrev Start IndexCasePatterns Obj
      0who0dog|2|32-1I
      • pattern-1:
        • who|
        • [1]
      1let0dog|2|32-1I
      • pattern-1:
        • who|
        • let|
        • [2]
      2dog0dog|2|32-1II.1
      • pattern-1:
        • who
        • let|
        • dog|canine|k9|bull dog|
        • [2]
      2dog1dog and cat|2|522II.2
      • pattern-1:
        • who
        • let|
        • dog|canine|k9|bull dog|
        • [2]

      • pattern-2:
        • who
        • let|
        • dog and cat|pets|puppy and kitty|
        • [5]
      3and2cat|4|542I
      • pattern-1:
        • who
        • let|
        • dog|canine|k9|bull dog|
        • and|
        • [4]

      • pattern-2:
        • who
        • let|
        • dog and cat|pets|puppy and kitty|
        • [5]
      4cat2cat|4|542II.1
      • pattern-1:
        • who
        • let|
        • dog|canine|k9|bull dog|
        • and|
        • cat|feline|
        • [5]

      • pattern-2:
        • who
        • let|
        • dog and cat|pets|puppy and kitty|
        • [5]
      5out3null-14I
      • pattern-1:
        • who
        • let|
        • dog|canine|k9|bull dog|
        • and|
        • cat|feline|
        • out
        • [6]

      • pattern-2:
        • who
        • let|
        • dog and cat|pets|puppy and kitty|
        • out
        • [6]

  • Outputs:

    Pattern 1
    word|synonyms
    who|
    let|
    dog|canine|k9|bull dog|
    and|
    cat|feline|
    out|

    Pattern 2
    word|synonyms
    who|
    let|
    dog and cat|pets|puppy and kitty|
    out|