CS161_HW3 (1).pdf
text_file_path = "google-10000-english-no-swears.txt"
valid_words = []
with open(text_file_path) as file:
for line in file:
XXXXXXXXXXvalid_words.append(line.rstrip())
class Node:
def __init__(self, value):
XXXXXXXXXXself.left_child = None
XXXXXXXXXXself.middle_child = None
XXXXXXXXXXself.right_child = None
XXXXXXXXXXself.value = value
XXXXXXXXXXself.is_end = False
class TernarySearchTree:
def __init__(self):
XXXXXXXXXXself.root_node = None
def insert(self, word, node=None):
""" Inserts the provided word into the ternary search tree.
XXXXXXXXXXNote: While you can implement this function however you like, we
XXXXXXXXXXthink you might have the easiest time writing this funcion recursively.
XXXXXXXXXXTo facilitate this, we have included a parameter to indicate the
XXXXXXXXXXcu
ent node being compared against.
XXXXXXXXXXThe worst-case runtime of this function should be O(k(n + k)), where
XXXXXXXXXXn is the number of words in the tree and k is the number of characters
XXXXXXXXXXin the word.
XXXXXXXXXXParameters
------------
XXXXXXXXXXword : st
XXXXXXXXXXThe word to be inserted.
XXXXXXXXXXnode : Node
XXXXXXXXXXThe cu
ent node being compared against.
"""
### TODO: YOUR CODE HERE ###
XXXXXXXXXXpass
def contains(self, word, node=None):
""" Returns True if the provided word is in the ternary search tree
XXXXXXXXXXand False otherwise.
XXXXXXXXXXNote: While you can implement this function however you like, we
XXXXXXXXXXthink you might have the easiest time writing this funcion recursively.
XXXXXXXXXXTo facilitate this, we have included a parameter to indicate the
XXXXXXXXXXcu
ent node being compared against.
XXXXXXXXXXThe worst-case runtime of this function should be O(k(n + k)), where
XXXXXXXXXXn is the number of words in the tree and k is the number of characters
XXXXXXXXXXin the word.
XXXXXXXXXXParameters
------------
XXXXXXXXXXword : st
XXXXXXXXXXThe word we are searching for.
XXXXXXXXXXnode : Node
XXXXXXXXXXThe cu
ent node being compared against.
XXXXXXXXXXReturns
------------
XXXXXXXXXXboolean : True if the word was found. False otherwise.
"""
### TODO: YOUR CODE HERE ###
XXXXXXXXXXpass
class Spellchecker:
def __init__(self, valid_words):
""" Creates a ternary search tree and stores the provided list of
XXXXXXXXXXvalid words in the tree.
XXXXXXXXXXParameters
-----------
XXXXXXXXXXvalid_words : list[str]
XXXXXXXXXXThe list of valid words.
"""
### TODO: YOUR CODE HERE ###
XXXXXXXXXXpass
def getNea
yStrings(self, word):
"""Takes in an input word and returns a list of strings which are an edit
XXXXXXXXXXdistance of 1 from the input word. Note that the strings in this list
XXXXXXXXXXwill not necessarily be in the valid_words list.
* Thanks to Peter Norvig for this function! He has a great essay on
XXXXXXXXXXspelling co
ection here: https:
norvig.com/spell-co
ect.html. *
XXXXXXXXXXParameters
-----------
XXXXXXXXXXword : st
XXXXXXXXXXThe input word.
XXXXXXXXXXReturns
-----------
XXXXXXXXXXlist[str] : A list of strings which are an edit distance of 1 from the
XXXXXXXXXXinput word.
"""
XXXXXXXXXXletters = 'abcdefghijklmnopqrstuvwxyz'
XXXXXXXXXXsplits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
XXXXXXXXXXdeletes = [L + R[1:] XXXXXXXXXXfor L, R in splits if R]
XXXXXXXXXXtransposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R)>1]
XXXXXXXXXXreplaces = [L + c + R[1:] XXXXXXXXXXfor L, R in splits if R for c in letters]
XXXXXXXXXXinserts = [L + c + R XXXXXXXXXXfor L, R in splits for c in letters]
XXXXXXXXXXreturn list(set(deletes + transposes + replaces + inserts))
def make_suggestions(self, word):
"""Takes in an input word and searches for words which are an
XXXXXXXXXXedit distance of 1 from the input word in the ternary search tree.
XXXXXXXXXXReturns this list of words.
XXXXXXXXXXSome key points:
XXXXXXXXXXYou can assume that words wil consist only of lowercase alphabetic
XXXXXXXXXXcharacters. This means you do not need to consider uppercase characters,
XXXXXXXXXXspaces, punctuation, numbers, etc.
XXXXXXXXXXYou should not return any words which are not in the "valid_words" list.
XXXXXXXXXXYou do not need to consider whether the input word is spelled co
ectly.
XXXXXXXXXXYour function should still return words which are an edit distance of 1
XXXXXXXXXXaway from the input word regardless.
XXXXXXXXXXParameters
-----------
XXXXXXXXXXword : st
XXXXXXXXXXThe input word.
XXXXXXXXXXReturns
-----------
XXXXXXXXXXlist[str] : A list of words from the "valid_words" list which are an edit
XXXXXXXXXXdistance of 1 from the input word.
"""
### TODO: YOUR CODE HERE ###
XXXXXXXXXXpass
spellchecker = Spellchecker(valid_words)
output = spellchecker.make_suggestions(input())
output.sort()
for word in output:
print(word)
the
of
and
to
a
in
fo
is
on
that
y
this
with
i
you
it
not
o
e
are
from
at
as
you
all
have
new
more
an
was
we
will
home
can
us
about
if
page
my
has
search
free
ut
ou
one
othe
do
no
information
time
they
site
he
up
may
what
which
thei
news
out
use
any
there
see
only
so
his
when
contact
here
usiness
who
we
also
now
help
get
pm
view
online
c
e
first
am
een
would
how
were
me
s
services
some
these
click
its
like
service
x
than
find
price
date
ack
top
people
had
list
name
just
ove
state
yea
day
into
email
two
health
n
world
e
next
used
go
work
last
most
products
music
uy
data
make
them
should
product
system
post
he
city
t
add
policy
numbe
such
please
available
copyright
support
message
afte
est
software
then
jan
good
video
well
d
where
info
ights
public
ooks
high
school
through
m
each
links
she
eview
years
orde
very
privacy
ook
items
company
ead
group
need
many
use
said
de
does
set
unde
general
esearch
university
january
mail
full
map
eviews
program
life
know
games
way
days
management
p
part
could
great
united
hotel
eal
f
item
international
cente
ebay
must
store
travel
comments
made
development
eport
off
membe
details
line
terms
efore
hotels
did
send
ight
type
ecause
local
those
using
esults
office
education
national
ca
design
take
posted
internet
address
community
within
states
area
want
phone
dvd
shipping
eserved
subject
etween
forum
family
l
long
ased
w
code
show
o
even
lack
check
special
prices
website
index
eing
women
much
sign
file
link
open
today
technology
south
case
project
same
pages
uk
version
section
own
found
sports
house
elated
security
oth
g
county
american
photo
game
members
powe
while
care
network
down
compute
systems
three
total
place
end
following
download
h
him
without
pe
access
think
north
esources
cu
ent
posts
ig
media
law
control
wate
history
pictures
size
art
personal
since
including
guide
shop
directory
oard
location
change
white
text
small