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