SPT - Term Match Design

I. Introduction
This section describes the method used to find if a term exists in a Trie Tree.

II. Algorithm

  • Normalize the input term:
    • LowerCase
    • Add " $_END_STR" (the END node)
  • Tokenize normalized term into inWords as a Vector<String>
  • Set the curNode to ROOT node
  • Set findFlag = false
  • Go through the inWords
    • Initiate curWordNode by the curWord
    • get curChilds from curNode
    • Check if curChilds contains curWordNode
      • yes => Check if curWordNode is END NODE
        • yes => match, set findFlag = true, break
      • update curNode
      • no => not match (false), break

III. Java Classes & Method

  • TrieTreeMatch.java: a Java class for matching in TrieTree
  • public boolean Match(String inTerm)

IV. Examples

  • Synonym Rules:

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

  • Synonym Terms:

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

  • Input Term:
    Dog and cat
    • Normalized: dog and cat $_END
    • Go through each word of "dog and cat $_END"
      icurWordNodecurNodecurChilds.contains(curWordNode)END_NODEfindFlag
      0dogROOTtruefalsefalse
      1anddogtruefalsefalse
      2catandtruefalsefalse
      3$_ENDcattruetruetrue

  • Output: True

  • Trie Tree