Sub-Term APIs: Find Sub-Terms Design

I. Introduction
This section describes the sub-term related methods used to find:

• All sub-terms of a term in a corpus
• The longest prefix sub-term of a term in a corpus

II. Algorithm

• Init Vector<String> matchTerms
• Get inWords by tokenizing newInTerm
• Go through terms from the inWords
  • Get curTerm from startIndex of inWords
  • Find branchMatches
    • Add " $_END" (the END node)
    • Tokenize normalized term into inWords as a Vector<String>
    • Set the curNode to ROOT node
    • Init Vector<String> branchMatches
    • Go through the inWords
      • Initiate curWordNode by the curWord
      • get curChilds from curNode
      • Check if curChilds has END node
        • Yes => add the branch term to branchMatches
      • Check if curChilds contains curWordNode
        • yes => update curNode
        • no => not match (false), break
  • Add branchMatches to matchTerms

III. Java Classes & Method

• SubtermApi.java: a Java class for sub-term methods
  • public static Vector FindSubtermStrs(String inTerm, Corpus corpus)
  • public static Vector FindSubterms(String inTerm, Corpus corpus)
  • public static Vector FindAllPrefixSubterms(String inTerm, Corpus corpus)
  • public static String FindLongestPrefixSubterm(String inTerm, Corpus corpus)

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:
  Who let dog and cat out
  • Normalize: who let dog and cat out
  • Go through terms from "who let dog and cat out"

    i	curTerm	branchMatches	matchTerms
    0	who let dog and cat out
    1	let dog and cat out
    2	dog and cat out	dog dog and cat	dog dog and cat
    3	and cat out		dog dog and cat
    4	cat out	cat	dog dog and cat cat
    5	out		dog dog and cat cat

• Output:

  return matched terms | start index | end indexes:

  • dog|2|3
  • dog and cat|2|5
  • cat|4|5

• Trie Tree