Description
Trie
A trie is a special rooted tree. that allows us to store a set of words by sharing their common prefixes.
Example # 1
Consider the following list of five words:
hello, jello, he, hello, jelly
The trie data structure for this list above is given below:
A trie node can be of three types:
- Root of the trie (shown as a diamond)
- Internal non-terminal node of a trie (white ovals)
- Word-ending node of a trie (green ovals).
Note: A word-ending node need not be a leaf. Also, such nodes are associated with a number that represents the frequency of the corresponding word.
Each trie edge is labelled with an alphabet.
Reading the words in the dictionary.
Starting from the root (diamond node), as we traverse a path along the trie, the letters along a path form a word. Whenever we encounter a word-ending node, we can stop and read off a valid word in the dictionary.
For instance, we note the correspondence between the list of words:
hello, hello, jello, he, jelly
and the paths in the trie.
Note: The word he is a prefix of the word hello. Therefore, in the trie, starting from the root, we see that a word-ending node corresponding to he is extended by the suffix “llo” to form a word-ending node for hello.
The frequency of occurrence of a word is the number associated with its corresponding word-ending node. Notice how the frequency of “he” is 1 but the frequency of “hello” is 2.
Finally, two words with a common prefix such as “jelly” and “jello” will share a common path corresponding to the prefix “jell” in the trie.
Trie Data Structure: Specification
A trie (or a prefix tree) data structure allows us to store a set of strings from a dictionary along with a frequency count for each strings. The following operations should be supported:
| Operation | Description | Return Type |
|---|---|---|
addWord(w) |
Insert a word w into the trie | None |
lookupWord(w) |
Return the frequency of w in the trie (0 if not present) | int |
autoComplete(w) |
Return a list of words in the trie along with their frequencies so that w is a prefix of each word in the list |
list of (str,int) |
Example : Adding Words to the Trie
We will illustrate the process of constructing a trie using an example.
At the beginning the empty trie is simply a root node:
Suppose we add the strings in the following order:
test, testament, testing, ping, pin, pink, pine, pint, testing, pinetree
| Trie | Operation |
|---|---|
 |
addWord(test) |
 |
addWord(testament) |
 |
addWord(testing) |
 |
addWord(ping) |
 |
addWord(pin) addWord(pink) addWord(pine) addWord(pint) addWord(testing) addWord(pinetree) |
Example: Trie Lookup
The operation lookupWord allows us to count the frequency of a word in a trie. If a word does not belong to a trie, then the frequency is 0.
For instance, consider the trie above:
lookupWord('test’) = 1 lookupWord('testing’) = 2 lookupWord('tesla’) = 0 lookupWord('tom’) = 0 lookupWord('pinetree’) = 1
Example: Autocomplete
The operation autoComplete provides a list of completions of a given string along with their frequencies.
autoComplete('pi’) = [ ('pin’,1), ('pink’,1), ('pine’,1),('pinetree’,1),('pint’,1), ('ping’,1) ] autoComplete('tom’) = [ ] # emtpy list because no word with prefix tom belongs to the trie autoComplete('testi’) = [ ('testing’,2) ]
Implementation
Your job is to implement the operations addWord, lookupWord and autoComplete in the class MyTrieNode defined below.
import sys
# We will use a class called my trie node
class MyTrieNode:
# Initialize some fields
def __init__(self, isRootNode):
#The initialization below is just a suggestion.
#Change it as you will.
# But do not change the signature of the constructor.
self.isRoot = isRootNode
self.isWordEnd = False # is this node a word ending node
self.isRoot = False # is this a root node
self.count = 0 # frequency count
self.next = {} # Dictionary mapping each character from a-z to
# the child node if any corresponding to that character.
def addWord(self,w):
assert(len(w) > 0)
# YOUR CODE HERE
# If you want to create helper/auxiliary functions, please do so.
return
def lookupWord(self,w):
# Return frequency of occurrence of the word w in the trie
# returns a number for the frequency and 0 if the word w does not occur.
# YOUR CODE HERE
return 0 # TODO: change this line, please
def autoComplete(self,w):
#Returns possible list of autocompletions of the word w
#Returns a list of pairs (s,j) denoting that
# word s occurs with frequency j
#YOUR CODE HERE
return [('Walter',1),('Mitty',2),('Went',3),('To',4),('Greenland',2)] #TODO: change this line, pleaseDescription of MyTrieNode Class
A trie node structure has the following attributes/fields:
isRootA Boolean flag denoting if the node is a root.isWordEndA Boolean flag denoting if the node is the word ending node.countA count field for frequency count for a word ending node.next:A dictionary that maps from each of the alphabets ‘a’ – ‘z’ to the child node corresponding to the alphabet.
# The original example: let us see if the code works
t= MyTrieNode(True) # Create a root Trie node
lst1=['test','testament','testing','ping','pin','pink','pine','pint','testing','pinetree']
# Insert the words in lst1
for w in lst1:
t.addWord(w)
# Perform lookups
j = t.lookupWord('testy') # should return 0
j2 = t.lookupWord('telltale') # should return 0
j3 = t.lookupWord ('testing') # should return 2
# Run autocompletes
lst3 = t.autoComplete('pi')
print('Completions for \"pi\" are : ')
print(lst3)
lst4 = t.autoComplete('tes')
print('Completions for \"tes\" are : ')
print(lst4)Completions for "pi" are :
[('Walter', 1), ('Mitty', 2), ('Went', 3), ('To', 4), ('Greenland', 2)]
Completions for "tes" are :
[('Walter', 1), ('Mitty', 2), ('Went', 3), ('To', 4), ('Greenland', 2)]
Testing Your Work : Do not Edit
We have coded up 5 tests that your code must pass.
import sys
def lookupTest(t, lstToLookup):
retValue = True
for (w,k) in lstToLookup:
j = t.lookupWord(w)
if (j != k):
print('\t Lookup for word %s failed. Expected result: %d, obtained from your trie: %d \n'%(w,k,j))
retValue = False
return retValue
def autoCompleteTest(t, stem, expResult):
lst1 = sorted(t.autoComplete(stem))
lstRet = sorted(expResult)
if (len(lst1) != len(lstRet)):
print('\t autoComplete(\"%s\") failed'%(stem))
print('\t\t Expected: ',lstRet)
print('\t\t Got: ', lst1)
return False
n = len(lstRet)
for i in range(0,n):
(expI,freqI) = lstRet[i]
(gotI,freqJ) = lst1[i]
if (expI != gotI or freqI != freqJ):
print('autoComplete(\"%s\") failed'%(stem))
print('\t Expected: ',lstRet)
print('\t Got: ', lst1 )
return False
return True
def runTest(specs):
try:
t = MyTrieNode(True)
lNum = 0
result = True
spec_lines = specs.split('\n')
for line in spec_lines:
lNum += 1
lst = [x.strip() for x in line.split(',')]
if (lst[0] == 'W'):
print('\t Insert:',lst[1])
t.addWord(lst[1])
elif (lst[0] == 'L'):
print('\t Lookup:', lst[1])
j = t.lookupWord(lst[1])
if (j != int(lst[2])):
print('\t\t Failed --> expected : %s, got %d'%(lst[2],j))
result=False
elif (lst[0] == 'A'):
wrd = lst[1]
rList = lst[2::]
rWords = rList[0::2]
print('\t Autocomplete: ',lst[1])
rNums = [int(x) for x in rList[1::2] ]
retList = sorted(zip (rWords,rNums))
result = (autoCompleteTest(t,wrd, retList)) and result
else:
print('Error in test specification line number %d -- Unknown command spec %s'%(lNum,lst[0]))
sys.exit(1)
return result
except IOError:
print('Unable to open',fileName)
str_spec1='''W,hello
W,hello
W,he
W,jello
W,jelly
L,hello,2
L,hell,0
L,howdy,0
A,he,hello,2,he,1
A,je,jello,1,jelly,1'''
rslt = runTest(str_spec1)
if (rslt):
print('Test 1 PASSED')
else:
print('Test 1 FAILED') Insert: hello
Insert: hello
Insert: he
Insert: jello
Insert: jelly
Lookup: hello
Failed --> expected : 2, got 0
Lookup: hell
Lookup: howdy
Autocomplete: he
autoComplete("he") failed
Expected: [('he', 1), ('hello', 2)]
Got: [('Greenland', 2), ('Mitty', 2), ('To', 4), ('Walter', 1), ('Went', 3)]
Autocomplete: je
autoComplete("je") failed
Expected: [('jello', 1), ('jelly', 1)]
Got: [('Greenland', 2), ('Mitty', 2), ('To', 4), ('Walter', 1), ('Went', 3)]
Test 1 FAILED
str_spec2 = '''W,hello
W,how
W,are
W,you
W,hell
L,howdy,0
W,howdy
W,arid
W,arachnid
L,orange,0
L,hello,1
L,hell,1
L,howdy,1
A,ho,howdy,1,how,1'''
rslt = runTest(str_spec2)
if (rslt):
print('Test 2 PASSED')
else:
print('Test 2 FAILED') Insert: hello
Insert: how
Insert: are
Insert: you
Insert: hell
Lookup: howdy
Insert: howdy
Insert: arid
Insert: arachnid
Lookup: orange
Lookup: hello
Failed --> expected : 1, got 0
Lookup: hell
Failed --> expected : 1, got 0
Lookup: howdy
Failed --> expected : 1, got 0
Autocomplete: ho
autoComplete("ho") failed
Expected: [('how', 1), ('howdy', 1)]
Got: [('Greenland', 2), ('Mitty', 2), ('To', 4), ('Walter', 1), ('Went', 3)]
Test 2 FAILED
str_spec3='''L,lolo,0
L,popo,0
W,cat
W,hat
W,mat
W,hatter
W,mad
W,maddening
W,catherine
A,cath,catherine,1'''
rslt = runTest(str_spec3)
if (rslt):
print('Test 3 PASSED')
else:
print('Test 3 FAILED')
Lookup: lolo
Lookup: popo
Insert: cat
Insert: hat
Insert: mat
Insert: hatter
Insert: mad
Insert: maddening
Insert: catherine
Autocomplete: cath
autoComplete("cath") failed
Expected: [('catherine', 1)]
Got: [('Greenland', 2), ('Mitty', 2), ('To', 4), ('Walter', 1), ('Went', 3)]
Test 3 FAILED
str_spec4 = '''W,jelly
W,jello
W,just
W,justin
W,jejunum
W,jellyfish
L,jell,0
L,jel,0
L,jellyfish,1
L,justtin,0
L,jus,0
L,justin,1'''
rslt = runTest(str_spec4)
if (rslt):
print('Test 4 PASSED')
else:
print('Test 4 FAILED')
Insert: jelly Insert: jello Insert: just Insert: justin Insert: jejunum Insert: jellyfish Lookup: jell Lookup: jel Lookup: jellyfish Failed --> expected : 1, got 0 Lookup: justtin Lookup: jus Lookup: justin Failed --> expected : 1, got 0 Test 4 FAILED
str_spec5='''W,a
W,aah
W,aardvark
W,ab
L,abdomen,0
W,aback
W,abacus
W,abaft
W,abalone
W,abandon
W,abandonment
W,abase
W,abasement
W,abash
W,abashed
W,abashment
W,abate
W,abated
W,abatement
W,abattoir
W,abbe
W,abbess
W,abbey
W,abbot
W,abbr
W,abbrev
W,abbreviate
W,abbreviation
W,abdicate
W,abdication
W,abdomen
W,abdominal
W,abduct
W,abductee
W,abduction
W,abductor
W,abeam
W,aberrant
W,aberration
W,aberrational
W,abet
W,abetted
W,abetting
W,abettor
W,abeyance
W,abhor
W,abhorred
W,abhorrence
W,abhorrent
W,abhorring
W,abidance
W,abide
W,abiding
W,ability
W,abject
W,abjection
W,abjectness
W,abjuration
W,abjuratory
W,abjure
W,abjurer
W,ablate
W,ablation
W,ablative
W,ablaze
W,able
W,abler
W,abloom
W,ablution
W,abnegate
W,abnegation
W,abnormal
W,abnormality
W,aboard
W,abode
W,abolish
W,abolition
W,abolitionism
W,abolitionist
W,abominable
W,abominably
W,abominate
W,abomination
W,aboriginal
W,aborigine
W,aborning
W,abort
W,abortion
W,abortionist
W,abortive
W,abound
W,about
W,above
W,aboveboard
W,abracadabra
W,abrade
W,abrasion
W,abrasive
W,abrasiveness
W,abreast
W,abridge
W,abridgment
W,abroad
W,abrogate
W,abrogation
W,abrogator
W,abrupt
W,abruptness
W,abs
W,abscess
W,abscissa
W,abscission
W,abscond
W,absconder
W,abseil
W,absence
W,absent
W,absentee
W,absenteeism
W,absentminded
W,absentmindedness
W,absinthe
W,absolute
W,absoluteness
W,absolution
W,absolutism
W,absolutist
W,absolve
W,absorb
W,absorbency
W,absorbent
W,absorbing
W,absorption
W,absorptive
W,abstain
W,abstainer
W,abstemious
W,abstemiousness
W,abstention
W,abstinence
W,abstinent
W,abstract
W,abstracted
W,abstractedness
W,abstraction
W,abstractness
W,abstruse
W,abstruseness
W,absurd
W,absurdity
W,absurdness
W,abundance
W,abundant
W,abuse
W,abuse
W,abuser
W,abusive
W,abusiveness
W,abut
W,abutment
W,abutted
W,abutting
W,abuzz
W,abysmal
W,abyss
W,abyssal
W,ac
W,acacia
W,academe
W,academia
W,academic
W,academical
W,academician
W,academy
W,acanthus
W,accede
W,accelerate
W,acceleration
W,accelerator
W,accent
W,accented
W,accentual
W,accentuate
W,accentuation
W,accept
W,acceptability
W,acceptableness
W,acceptably
W,acceptance
W,acceptation
W,accepted
W,access
W,accessibility
W,accessible
W,accessibly
W,accession
W,accessorize
W,accessory
W,accident
W,accidental
W,acclaim
W,acclamation
W,acclimate
W,acclimation
W,acclimatization
W,acclimatize
W,acclivity
W,accolade
W,accommodate
W,accommodating
W,accommodation
W,accompanied
W,accompaniment
W,accompanist
W,accompany
W,accomplice
W,accomplish
W,accomplished
W,accomplishment
W,accord
W,accordance
W,accordant
W,according
W,accordion
W,accordionist
W,accost
W,account
W,accountability
W,accountable
W,accountancy
W,accountant
W,accounted
W,accounting
W,accouter
W,accouterments
W,accredit
W,accreditation
W,accredited
W,accretion
W,accrual
W,accrue
W,acct
W,acculturate
W,acculturation
W,accumulate
W,accumulation
W,accumulator
W,accuracy
W,accurate
W,accurateness
W,accursed
W,accursedness
W,accusation
W,accusative
W,accusatory
W,accuse
W,accuser
W,accusing
W,accustom
W,accustomed
W,ace
W,acerbate
W,acerbic
W,acerbically
W,acerbity
W,acetaminophen
W,acetate
W,acetic
W,acetone
W,acetonic
W,acetylene
W,ache
W,achene
W,achieve
W,achievement
W,achiever
W,aching
W,achoo
W,achromatic
W,achy
W,acid
W,acidic
W,acidify
W,acidity
W,acidosis
W,acidulous
W,acknowledge
W,acknowledged
W,acknowledgment
W,acme
W,acne
W,acolyte
W,aconite
W,acorn
W,acoustic
W,acoustical
W,acoustics
W,acquaint
W,acquaintance
W,acquaintanceship
W,acquainted
W,acquiesce
W,acquiescence
W,acquiescent
W,acquire
W,acquirement
W,acquisition
W,acquisitive
W,acquisitiveness
W,acquit
W,acquittal
W,acquitted
W,acquitting
W,acre
W,acreage
W,acrid
W,acridity
W,acridness
W,acrimonious
W,acrimoniousness
W,acrimony
W,acrobat
W,acrobatic
W,acrobatically
W,acrobatics
W,acronym
W,acrophobia
W,acropolis
W,across
W,acrostic
W,acrylic
W,act
W,act
W,acting
W,actinium
W,action
W,actionable
W,activate
W,activation
W,activator
W,active
W,active
W,activeness
W,actives
W,activism
W,activist
W,activities
W,activity
W,actor
W,actress
W,actual
W,actuality
W,actualization
W,actualize
W,actuarial
W,actuary
W,actuate
W,actuation
W,actuator
W,acuity
W,acumen
W,acupressure
W,acupuncture
W,acupuncturist
W,acute
W,acuteness
W,acyclovir
W,ad
W,adage
W,adagio
W,adamant
W,adapt
W,adaptability
W,adaptation
W,adapter
W,adaption
W,add
W,addend
W,addenda
W,addendum
W,adder
W,addict
W,addiction
W,addition
W,additional
W,additive
W,addle
W,address
W,address
W,addressable
W,addressed
W,addressee
W,adduce
W,adenine
W,adenoid
W,adenoidal
W,adept
W,adeptness
W,adequacy
W,adequate
W,adequateness
W,adhere
W,adherence
W,adherent
W,adhesion
W,adhesive
W,adhesiveness
W,adiabatic
W,adieu
W,adios
W,adipose
W,adj
W,adjacency
W,adjacent
W,adjectival
W,adjective
W,adjoin
W,adjourn
W,adjournment
W,adjudge
W,adjudicate
W,adjudication
W,adjudicator
W,adjudicatory
W,adjunct
W,adjuration
W,adjure
W,adjust
W,adjustable
W,adjuster
W,adjustment
W,adjutant
W,adman
W,admen
W,admin
W,administer
W,administrate
W,administration
W,administrative
W,administrator
W,admirably
W,admiral
W,admiralty
W,admiration
W,admire
W,admirer
W,admiring
W,admissibility
W,admissible
W,admissibly
W,admission
W,admissions
W,admit
W,admittance
W,admitted
W,admitting
W,admix
W,admixture
W,admonish
W,admonishment
W,admonition
W,admonitory
L,ado,0
W,ado
L,ado,1
W,adobe
L,adobe,1
W,adolescence
W,adolescent
W,adopt
W,adoptable
W,adopter
W,adoption
W,adorableness
W,adorably
W,adoration
W,adore
W,adorer
W,adoring
W,adorn
L,ado,1
L,adorn,1
W,adorned
W,adornment
L,abdominal,1
A,abc
A,abet,abet,1,abetted,1,abetting,1,abettor,1'''
rslt = runTest(str_spec5)
if (rslt):
print('Test 5 PASSED')
else:
print('Test 5 FAILED')
Insert: a
Insert: aah
Insert: aardvark
Insert: ab
Lookup: abdomen
Insert: aback
Insert: abacus
Insert: abaft
Insert: abalone
Insert: abandon
Insert: abandonment
Insert: abase
Insert: abasement
Insert: abash
Insert: abashed
Insert: abashment
Insert: abate
Insert: abated
Insert: abatement
Insert: abattoir
Insert: abbe
Insert: abbess
Insert: abbey
Insert: abbot
Insert: abbr
Insert: abbrev
Insert: abbreviate
Insert: abbreviation
Insert: abdicate
Insert: abdication
Insert: abdomen
Insert: abdominal
Insert: abduct
Insert: abductee
Insert: abduction
Insert: abductor
Insert: abeam
Insert: aberrant
Insert: aberration
Insert: aberrational
Insert: abet
Insert: abetted
Insert: abetting
Insert: abettor
Insert: abeyance
Insert: abhor
Insert: abhorred
Insert: abhorrence
Insert: abhorrent
Insert: abhorring
Insert: abidance
Insert: abide
Insert: abiding
Insert: ability
Insert: abject
Insert: abjection
Insert: abjectness
Insert: abjuration
Insert: abjuratory
Insert: abjure
Insert: abjurer
Insert: ablate
Insert: ablation
Insert: ablative
Insert: ablaze
Insert: able
Insert: abler
Insert: abloom
Insert: ablution
Insert: abnegate
Insert: abnegation
Insert: abnormal
Insert: abnormality
Insert: aboard
Insert: abode
Insert: abolish
Insert: abolition
Insert: abolitionism
Insert: abolitionist
Insert: abominable
Insert: abominably
Insert: abominate
Insert: abomination
Insert: aboriginal
Insert: aborigine
Insert: aborning
Insert: abort
Insert: abortion
Insert: abortionist
Insert: abortive
Insert: abound
Insert: about
Insert: above
Insert: aboveboard
Insert: abracadabra
Insert: abrade
Insert: abrasion
Insert: abrasive
Insert: abrasiveness
Insert: abreast
Insert: abridge
Insert: abridgment
Insert: abroad
Insert: abrogate
Insert: abrogation
Insert: abrogator
Insert: abrupt
Insert: abruptness
Insert: abs
Insert: abscess
Insert: abscissa
Insert: abscission
Insert: abscond
Insert: absconder
Insert: abseil
Insert: absence
Insert: absent
Insert: absentee
Insert: absenteeism
Insert: absentminded
Insert: absentmindedness
Insert: absinthe
Insert: absolute
Insert: absoluteness
Insert: absolution
Insert: absolutism
Insert: absolutist
Insert: absolve
Insert: absorb
Insert: absorbency
Insert: absorbent
Insert: absorbing
Insert: absorption
Insert: absorptive
Insert: abstain
Insert: abstainer
Insert: abstemious
Insert: abstemiousness
Insert: abstention
Insert: abstinence
Insert: abstinent
Insert: abstract
Insert: abstracted
Insert: abstractedness
Insert: abstraction
Insert: abstractness
Insert: abstruse
Insert: abstruseness
Insert: absurd
Insert: absurdity
Insert: absurdness
Insert: abundance
Insert: abundant
Insert: abuse
Insert: abuse
Insert: abuser
Insert: abusive
Insert: abusiveness
Insert: abut
Insert: abutment
Insert: abutted
Insert: abutting
Insert: abuzz
Insert: abysmal
Insert: abyss
Insert: abyssal
Insert: ac
Insert: acacia
Insert: academe
Insert: academia
Insert: academic
Insert: academical
Insert: academician
Insert: academy
Insert: acanthus
Insert: accede
Insert: accelerate
Insert: acceleration
Insert: accelerator
Insert: accent
Insert: accented
Insert: accentual
Insert: accentuate
Insert: accentuation
Insert: accept
Insert: acceptability
Insert: acceptableness
Insert: acceptably
Insert: acceptance
Insert: acceptation
Insert: accepted
Insert: access
Insert: accessibility
Insert: accessible
Insert: accessibly
Insert: accession
Insert: accessorize
Insert: accessory
Insert: accident
Insert: accidental
Insert: acclaim
Insert: acclamation
Insert: acclimate
Insert: acclimation
Insert: acclimatization
Insert: acclimatize
Insert: acclivity
Insert: accolade
Insert: accommodate
Insert: accommodating
Insert: accommodation
Insert: accompanied
Insert: accompaniment
Insert: accompanist
Insert: accompany
Insert: accomplice
Insert: accomplish
Insert: accomplished
Insert: accomplishment
Insert: accord
Insert: accordance
Insert: accordant
Insert: according
Insert: accordion
Insert: accordionist
Insert: accost
Insert: account
Insert: accountability
Insert: accountable
Insert: accountancy
Insert: accountant
Insert: accounted
Insert: accounting
Insert: accouter
Insert: accouterments
Insert: accredit
Insert: accreditation
Insert: accredited
Insert: accretion
Insert: accrual
Insert: accrue
Insert: acct
Insert: acculturate
Insert: acculturation
Insert: accumulate
Insert: accumulation
Insert: accumulator
Insert: accuracy
Insert: accurate
Insert: accurateness
Insert: accursed
Insert: accursedness
Insert: accusation
Insert: accusative
Insert: accusatory
Insert: accuse
Insert: accuser
Insert: accusing
Insert: accustom
Insert: accustomed
Insert: ace
Insert: acerbate
Insert: acerbic
Insert: acerbically
Insert: acerbity
Insert: acetaminophen
Insert: acetate
Insert: acetic
Insert: acetone
Insert: acetonic
Insert: acetylene
Insert: ache
Insert: achene
Insert: achieve
Insert: achievement
Insert: achiever
Insert: aching
Insert: achoo
Insert: achromatic
Insert: achy
Insert: acid
Insert: acidic
Insert: acidify
Insert: acidity
Insert: acidosis
Insert: acidulous
Insert: acknowledge
Insert: acknowledged
Insert: acknowledgment
Insert: acme
Insert: acne
Insert: acolyte
Insert: aconite
Insert: acorn
Insert: acoustic
Insert: acoustical
Insert: acoustics
Insert: acquaint
Insert: acquaintance
Insert: acquaintanceship
Insert: acquainted
Insert: acquiesce
Insert: acquiescence
Insert: acquiescent
Insert: acquire
Insert: acquirement
Insert: acquisition
Insert: acquisitive
Insert: acquisitiveness
Insert: acquit
Insert: acquittal
Insert: acquitted
Insert: acquitting
Insert: acre
Insert: acreage
Insert: acrid
Insert: acridity
Insert: acridness
Insert: acrimonious
Insert: acrimoniousness
Insert: acrimony
Insert: acrobat
Insert: acrobatic
Insert: acrobatically
Insert: acrobatics
Insert: acronym
Insert: acrophobia
Insert: acropolis
Insert: across
Insert: acrostic
Insert: acrylic
Insert: act
Insert: act
Insert: acting
Insert: actinium
Insert: action
Insert: actionable
Insert: activate
Insert: activation
Insert: activator
Insert: active
Insert: active
Insert: activeness
Insert: actives
Insert: activism
Insert: activist
Insert: activities
Insert: activity
Insert: actor
Insert: actress
Insert: actual
Insert: actuality
Insert: actualization
Insert: actualize
Insert: actuarial
Insert: actuary
Insert: actuate
Insert: actuation
Insert: actuator
Insert: acuity
Insert: acumen
Insert: acupressure
Insert: acupuncture
Insert: acupuncturist
Insert: acute
Insert: acuteness
Insert: acyclovir
Insert: ad
Insert: adage
Insert: adagio
Insert: adamant
Insert: adapt
Insert: adaptability
Insert: adaptation
Insert: adapter
Insert: adaption
Insert: add
Insert: addend
Insert: addenda
Insert: addendum
Insert: adder
Insert: addict
Insert: addiction
Insert: addition
Insert: additional
Insert: additive
Insert: addle
Insert: address
Insert: address
Insert: addressable
Insert: addressed
Insert: addressee
Insert: adduce
Insert: adenine
Insert: adenoid
Insert: adenoidal
Insert: adept
Insert: adeptness
Insert: adequacy
Insert: adequate
Insert: adequateness
Insert: adhere
Insert: adherence
Insert: adherent
Insert: adhesion
Insert: adhesive
Insert: adhesiveness
Insert: adiabatic
Insert: adieu
Insert: adios
Insert: adipose
Insert: adj
Insert: adjacency
Insert: adjacent
Insert: adjectival
Insert: adjective
Insert: adjoin
Insert: adjourn
Insert: adjournment
Insert: adjudge
Insert: adjudicate
Insert: adjudication
Insert: adjudicator
Insert: adjudicatory
Insert: adjunct
Insert: adjuration
Insert: adjure
Insert: adjust
Insert: adjustable
Insert: adjuster
Insert: adjustment
Insert: adjutant
Insert: adman
Insert: admen
Insert: admin
Insert: administer
Insert: administrate
Insert: administration
Insert: administrative
Insert: administrator
Insert: admirably
Insert: admiral
Insert: admiralty
Insert: admiration
Insert: admire
Insert: admirer
Insert: admiring
Insert: admissibility
Insert: admissible
Insert: admissibly
Insert: admission
Insert: admissions
Insert: admit
Insert: admittance
Insert: admitted
Insert: admitting
Insert: admix
Insert: admixture
Insert: admonish
Insert: admonishment
Insert: admonition
Insert: admonitory
Lookup: ado
Insert: ado
Lookup: ado
Failed --> expected : 1, got 0
Insert: adobe
Lookup: adobe
Failed --> expected : 1, got 0
Insert: adolescence
Insert: adolescent
Insert: adopt
Insert: adoptable
Insert: adopter
Insert: adoption
Insert: adorableness
Insert: adorably
Insert: adoration
Insert: adore
Insert: adorer
Insert: adoring
Insert: adorn
Lookup: ado
Failed --> expected : 1, got 0
Lookup: adorn
Failed --> expected : 1, got 0
Insert: adorned
Insert: adornment
Lookup: abdominal
Failed --> expected : 1, got 0
Autocomplete: abc
autoComplete("abc") failed
Expected: []
Got: [('Greenland', 2), ('Mitty', 2), ('To', 4), ('Walter', 1), ('Went', 3)]
Autocomplete: abet
autoComplete("abet") failed
Expected: [('abet', 1), ('abetted', 1), ('abetting', 1), ('abettor', 1)]
Got: [('Greenland', 2), ('Mitty', 2), ('To', 4), ('Walter', 1), ('Went', 3)]
Test 5 FAILED
