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:

  word	synonym
  dog	canine
  cat	feline
  canine	K9
  K9	bull dog
  Dog and cat	pets
  puppy and kitty	pets

• 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"

    i	curWordNode	curNode	curChilds.contains(curWordNode)	END_NODE	findFlag
    0	dog	ROOT	true	false	false
    1	and	dog	true	false	false
    2	cat	and	true	false	false
    3	$_END	cat	true	true	true

• Output: True

• Trie Tree