字典树实现前缀匹配。

trie_pre_match.py

#! /usr/bin/env python
# -*- coding: utf-8 -*-


class Trie_tree():
    def __init__(self):
        # node = [father, child, keep_char, is_word]
        self._root = [None, [], None, False]

    def insert(self, word):
        current_word = word
        current_node = self._root
        self._insert_operation_1(current_word, current_node)

    def _insert_operation_1(self, current_word, current_node):
        if current_word != "":
            first_char = current_word[0]
            child_node = current_node[1]
            is_in_child_node = False

            for node in child_node:
                if first_char == node[2]:
                    is_in_child_node = True
                    current_word = current_word[1:]
                    current_node = node
                    self._insert_operation_1(current_word, current_node)
                    break
                else:
                    continue

            if not is_in_child_node:
                self._insert_operation_2(current_word, current_node)

        else:
            current_node[3] = True

    def _insert_operation_2(self, current_word, current_node):
        first_char = current_word[0]

        # creat a new node and insert it in the tree
        new_node = [None, [], None, False]
        new_node[2] = first_char
        new_node[0] = current_node
        current_node[1].append(new_node)

        current_word = current_word[1:]
        if current_word != "":
            current_node = new_node
            self._insert_operation_2(current_word, current_node)

        else:
            new_node[3] = True

    def find(self, word):
        current_word = word
        current_node = self._root
        return self._find_opration(current_word, current_node)

    def _find_opration(self, current_word, current_node):
        if current_word != "":
            first_char = current_word[0]
            child_node = current_node[1]

            if child_node == []:
                return False

            is_in_child_node = False
            for node in child_node:
                if first_char == node[2]:
                    is_in_child_node = True
                    current_word = current_word[1:]
                    current_node = node
                    return self._find_opration(current_word, current_node)

                else:
                    continue

            if not is_in_child_node:
                return False
        else:
            return current_node[3]

    def delete(self, word):
        current_word = word
        current_node = self._root
        return self._delete_operation(current_word, current_node)

    def _delete_operation(self, current_word, current_node):
        if current_word != "":
            first_char = current_word[0]
            child_node = current_node[1]
            if child_node == []:
                return False

            is_in_child_node = False

            for node in child_node:
                if first_char == node[2]:
                    is_in_child_node = True
                    current_word = current_word[1:]
                    current_node = node
                    return self._delete_operation(current_word, current_node)

            if not is_in_child_node:
                return False
        else:
            if current_node[1] is not None:
                current_node[3] = False
            else:
                father_node = current_word[0]
                father_node[1].remove(current_node)

            return True

    def pre_match(self, pre_str):
        current_word = pre_str
        current_node = self._root
        return self._pre_match_op(current_word, current_node)

    def _pre_match_op(self, current_word, current_node):
        if current_word != "":
            first_char = current_word[0]
            child_node = current_node[1]
            if child_node == []:
                return None

            is_in_child_node = False
            for node in child_node:
                if first_char == node[2]:
                    is_in_child_node = True
                    current_word = current_word[1:]
                    current_node = node
                    return self._pre_match_op(current_word, current_node)
                else:
                    continue

            if not is_in_child_node:
                return None
        else:
            match_word = []

            # pre_str is already a word
            if current_node[3]:
                match_word.append("")

            self._pre_match_dfs("", current_node, match_word)
            return match_word

    def _pre_match_dfs(self, keep_char, current_node, match_word):
        child_node = current_node[1]
        for child in child_node:
            word = keep_char + child[2]
            if child[3]:
                match_word.append(word)
            else:
                pass

            self._pre_match_dfs(word, child, match_word)

        return match_word

if __name__ == "__main__":
    demo_trie = Trie_tree()
    print "--------Insert dict-------- "
    with open("words.txt", "r") as word_set:
        for line in word_set:
            for word in line.split():
                demo_trie.insert(word)

    pre_str = ""
    print "------Enter pre_str-------- "
    while(pre_str != EOFError):
        try:
            pre_str = raw_input("-> ")
            words = demo_trie.pre_match(pre_str)
            if words is None:
                print "No word start with ", pre_str
            else:
                for word in words:
                    print pre_str + word
                print "Totaly ", len(words), " words"
        except EOFError:
            print "Exit......"
            break

words.txt

the
be
of
and
a
to
in
he
have
it
that
for
they
I
with
as
not
on
she
at
by
this
we
you
do
but
from
or
which
one
would
all
will
there
say
who
make
when
can
more
if
no
man
out
other
so
what
time
up
go
about
than
into
could
state
only
new
year
some
take
come
these
know
see
use
get
like
then
first
any
work
now
may
such
give
over
think
most
even
find
day
also
after
way
many
must
look
before
great
7 back
through
long
where
much
should
well
people
down
own
just
because
good
each
those
feel
seem
how
high
too
place
little
world
very
still
nation
hand
old
life
tell
write
become
here
show
house
both
between
need
mean
call
develop
under
last
right
move
thing
general
school
never
same
another
begin
while
number
part
turn
real
leave
might
want
point
form
off
child
few
small
since
against
ask
late
home
interest
large
person
end
open
public
follow
during
present
without
again
hold
govern
around
possible
head
consider
word
program
problem
however
lead
system
set
order
eye
plan
run
keep
face
fact
group
play
stand
increase
early
course
change
help
line
city
put
close
case
force
meet
once
water
upon
war
build
hear
light
unite
live
every
country
bring
center
let
side
try
provide
continue
name
certain
power
pay
result
question
study
woman
member
until
far
night
always
service
away
report
something
company
week
church
toward
start
social
room
figure
nature
though
young
less
enough
almost
read
include
president
nothing
yet
better
big
boy
cost
business
value
second
why
clear
expect
family
complete
act
sense
mind
experience
art
next
near
direct
car
law
industry
important
girl
god
several
matter
usual
rather
per
often
kind
among
white
reason
action
return
foot
care
simple
within
love
human
along
appear
doctor
believe
speak
active
student
month
drive
concern
best
door
hope
example
inform
body
ever
least
probable
understand
reach
effect
different
idea
whole
control
condition
field
pass
fall
note
special
talk
particular
today
measure
walk
teach
low
hour
type
carry
rate
remain
full
street
easy
although
record
sit
determine
level
local
sure
receive
thus
moment
spirit
train
college
religion
perhaps
music
grow
free
cause
serve
age
book
board
recent
sound
office
cut
step
class
true
history
position
above
strong
friend
necessary
add
court
deal
tax
support
party
whether
either
land
material
happen
education
death
agree
arm
mother
across
quite
anything
town
past
view
society
manage
answer
break
organize
half
fire
lose
money
stop
actual
already
effort
wait
department
able
political
learn
voice
air
together
shall
cover
common
subject
draw
short
wife
treat
limit
road
letter
color
behind
produce
send
term
total
university
rise
century
success
minute
remember
purpose
test
fight
watch
situation
south
ago
difference
stage
father
table
rest
bear
entire
market
prepare
explain
offer
plant
charge
ground
west
picture
hard
front
lie
modern
dark
surface
rule
regard
dance
peace
observe
future
wall
farm
claim
firm
operation
further
pressure
property
morning
amount
top
outside
piece
sometimes
beauty
trade
fear
demand
wonder
list
accept
judge
paint
mile
soon
responsible
allow
secretary
heart
union
slow
island
enter
drink
story
experiment
stay
paper
space
apply
decide
share
desire
spend
sign
therefore
various
visit
supply
officer
doubt
private
immediate
wish
contain
feed
raise
describe
ready
horse
son
exist
north
suggest
station
effective
food
deep
wide
alone
character
English
happy
critic
unit
product
respect
drop
nor
fill
cold
represent
sudden 572 basic
kill
fine
trouble
mark
single
press
heavy
attempt
origin
standard
everything
committee
moral
black
red
bad
earth
accord
else
mere
die
remark
basis
except
equal
east
event
employ
defense
smile
river
improve
game
detail
account
cent
sort
reduce
club
buy
attention
ship
decision
wear
inside
win
suppose
ride
operate
realize
sale
choose
park
square
vote
price
district
dead
foreign
window
beyond
direction
strike
instead
trial
practice
catch
opportunity
likely
recognize
permit
serious
attack
floor
association
spring
lot
stock
lack
hair
science
relation
profession
pattern
quick
medical
influence
occasion
machine
compare
husband
blue
international
fair
especially
indeed
imagine
surprise
average
official
temperature
difficult
sing
hit
tree
race
police
touch
relative
throw
quality
former
pull
chance
prove
argue
settle
growth
date
heat
save
performance
count
production
listen
main
pick
size
cool
army
patient
combine
summer
hall
slight
command
enjoy
length
proper
express
health
chief
evening
store
language
degree
lay
current
gun
dog
hotel
strange
separate
boat
fail
clean
dress
anyone
gain
pain
object
knowledge
depend
relate
below
dollar
advance
shape
arrange
population
yes
sell
mention
dry
check
poet
sleep
join
hot
bed
electric
dream
due
season
manner
fit
left
progress
neither
strength
notice
finish
opinion
bill
western
truth
wrong
travel
suit
bank
exact
honor
brother
quiet
marry
corner
handle
danger
hospital
pool
promise
blood
shoot
scene
literature
arrive
film
base
freedom
bar
maybe
hang
suffer
manufacture
frequent
rock
loss
burn
sun
audience
essential
glass
prevent
poem
poor
inch
song
skill
post
popular
radio
animal
conscious
worth
eat
election
faith
wave
murder
model
forget
extend
edge
distance
memory
recommend
division
staff
leg
discussion
address
fly
dependent
ball
shake
frame
extreme
engineer
thick
comfort
latter
camp
oil
discover
examine
difficulty
tooth
middle
choice
refer
enemy
practical
marriage
bridge
declare
lady
cross
daily
afternoon
attend
director
balance
wash
capital
speed
block
citizen
mouth
hill
green
please
motor
agency
encourage
governor
worry
affair
shoulder
bright
mass
sample
pretty
repeat
roll
push
trip
council
clothe
parent
forward
sharp
straight
gas
weight
discuss
fix
load
master
whatever
round
rapid
laugh
finger
spot
propose
shop
broad
replace
reply
extent
lock
employee
ahead
sight
spread
wind
approve
destroy
none
pound
fame
importance
reflect
advantage
match
regular
wage
refuse
existence
hardly
perform
title
tend
exercise
thin
coat
bit
mountain
youth
behavior
newspaper
secret
ability
sea
soft
justice
reasonable
circle
solid
page
weapon
fast
representative
search
pure
escape
crowd
stick
telephone
avoid
garden
favor
news
unless
dinner
someone
100 signal
yard
ideal
warm
miss
shelter
soldier
article
cry
captain
familiar
seat
guest
weak
excite
king
everyone
wine
hole
duty
beat
perfect
bottom
compose
battle
expense
cattle
flow
kitchen
dust
bottle
admit
tear
tire
expression
exception
application
belong
rich
failure
struggle
instrument
variety
narrow
theater
collection
rain
review
preserve
leadership
clay
daughter
fellow
swing
thank
library
fat
reserve
tour
nice
warn
ring
bitter
chair
yesterday
scientific
flower
wheel
solution
aim
gather
invite
moreover
fresh
forest
winter
box
belief
ordinary
impossible
print
gray
taste
lip
speech
reference
stain
connection
otherwise
stretch
knife
village
blow
mistake
sweet
shout
divide
guard
worse
exchange
rare
commercial
request
appoint
agent
dependence
bird
wild
motion
guess
neighbor
seed
fashion
loan
correct
plain
mail
retire
opposite
prefer
safe
evil
double
wood
empty
baby
advise
content
sport
lift
literary
curious
tie
flat
message
neck
hate
dirt
delight
trust
nobody
valley
tool
presence
cook
railroad
minister
coffee
brush
beside
collect
guide
luck
profit
lord
everybody
prison
cloud
slave
chairman
soil
distinguish
introduce
urge
blind
arise
upper
curve
membership
key
entertain
soul
neighborhood
friendly 1143 pair
stone
lean
protect
advertise
mystery
welcome
knee
jump
snake
stream
avenue
brown
disease
hat
excellent
formal
snow
sheet
somehow
unity
sky
rough
smooth
weather
steady
threaten
depth
oppose
deliver
ancient
pray
adopt
birth
appearance
universe
busy
hurry
coast
forth
smell
furnish
female
hide
wire
proposal
ought
victory
quarter
engine
customer
waste
fool
intend
intention
desk
politics
passage
lawyer
root
climb
metal
gradual
hunt
protection
satisfy
roof
branch
pleasure
witness
loose
nose
mine
band
aside
risk
tomorrow
remind
ear
fish
shore
operator
civilize
being
silent
screen
bind
earn
pack
colony
besides
slip
cousin
scale
relief
explore
stem
brain
musician
defend
bend
somebody
shadow
mix
smoke
description
fruit
guilt
yield
sensitive
salt
pale
sweep
completion
throat
agriculture
admire
gentle
dozen
particle
pleasant
bay
cup
competition
moon
terrible
strip
mechanic
shock
conversation
angle
tall
plenty
star
yellow
sick
thorough
absolute
succeed
surround
proud
dear
card
lake
breath
afraid
silence
onto
shoe
somewhere
chain
slide
copy
machinery
wake
severe
pocket
bone
honest
freeze
dictionary
calm
swim
ice
male
skin
crack
rush
wet
meat
commerce
joint
gift
host
suspect
path
uncle
afford
instant
satisfactory
height
track
confidence
grass
suggestion
favorite
breakfast
apart
chest
entrance
march
sink
northern
iron
alive
ill
bag
disturb
native
bedroom
violent
beneath
pause
tough
substance
threat
charm
absence
factory
spite
meal
universal
accident
highway
sentence
liberty
wise
noise
discovery
tube
flash
twist
fence
childhood
joy
sister
sad
efficiency
disappear
defeat
extensive
rent
comparison
possess
grace
flesh
liquid
scientist
ease
heaven
milk
sympathy
rank
restaurant
frequency
angry
shade
accuse
necessity
knock
loud
permanent
row
lovely
confuse
gold
frighten
solve
grave
salary
photograph
advice
abroad
wound
virtue
dare
queen
extra
attract
numerous
pink
gate
expensive
shut
chicken
forgive
holy
wooden
prompt
crime
sorry
republic
anger
visitor
pile
violence
steel
wing
stair
partner
delay
gentleman
pour
confusion
damage
kick
safety
burst
network
resistance
screw
pride
till
hire
verb
preach
clerk
everywhere
anyway
fan
connect
egg
efficient
grain
calculate
drag
opposition
worship
arrest
discipline
string
harbor
camera
mechanism
cow
grand
funny
insurance
reduction
strict
lesson
tight
sand
plate
qualify
elsewhere
mad
interference
pupil
fold
royal
valuable
whisper
anybody
hurt
excess
quantity
fun
mud
extension
recognition
kiss
crop
sail
attractive
habit
relieve
wisdom
persuade
certainty
cloth
eager
deserve
sympathetic
cure
trap
puzzle
powder
raw
mankind
glad
blame
whenever
anxiety
bus
tremble
sacred
fortunate
glory
golden
neat
weekend
treasury
overcome
cat
sacrifice
complain
elect
roar
sake
temple
self
compete
nurse
stuff
stomach
peculiar
repair
storm
ton
desert
allowance
servant
hunger
conscience
bread
crash
tip
strengthen
proof
generous
sir
tonight
whip
tongue
mill
merchant
coal
ruin
introduction
courage
actor
belt
stir
package
punish
reflection
breathe
anywhere
amuse
dull
fate
net
fellowship
fault
furniture
beam
pencil
border
disappoint
flame
joke
bless
corn
shell
tempt
supper
destruction
dive
anxious
shine
cheap
dish
distant
greet
flood
excuse
insect
ocean
ceremony
decrease
prize
harm
insure
verse
pot
sincere
cotton
leaf
rub
medicine
stroke
bite
lung
lonely
admission
stupid
scratch
composition
broadcast
drum
resist
neglect
absent
passenger
adventure
beg
pipe
beard
bold
meanwhile
devil
cheer
nut
split
melt
swear
sugar
bury
wipe
faint
creature
tail
wealth
earnest
translate
suspicion
noble
inquiry
journey
hesitate
extraordinary
borrow
owe
funeral
ambition
mixture
slope
criminal
seldom
map
spin
praise
spare
plow
telegraph
barrel
straighten
scarce
lunch
slavery
creep
sweat
gay
stiff
brave
seize
convenient
horizon
moderate
complicate
dig
curse
weigh
priest
excessive
quarrel
widow
modest
dine
politician
custom
educate
salesman
nail
tap
eastern
possession
satisfaction
behave
mercy
scatter
objection
silver
tent
saddle
wrap
nest
grind
spell
swell
friendship
bath
bundle
grateful
crown
boundary
nowhere
asleep
clock
boil
altogether
lend
holiday
precious
wander
ugly
reputation
ticket
pretend
dismiss
delicate
despair
awake
tea
FALSE
fortune
cap
thread
haste
bare
shirt
bargain
leather
rail
butter
dot
inquire
warmth
decisive
vessel
pity
steam
pin
bound
companion
toe
reward
forbid
wherever
tower
bathe
lodge
swallow
multiply
bow
kingdom
garage
permission
pump
prevention
urgent
aunt
zero
idle
fever
Christmas
regret
jaw
soap
pronounce
empire
bowl
outline
organ
imitation
caution
mineral
disagree
blade
trick
treasure
immense
convenience
disapprove
destructive
fork
noon
ownership
tune
polish
poison
shame
loyalty
cottage
astonish
shave
feather
sauce
lid
debt
fade
confess
classification
descend
cape
mild
clever
envelope
invention
sheep
splendid
stamp
float
brick
rice
businessman
backward
qualification
artificial
attraction
lamp
curl
shower
elder
bunch
bell
steer
flavor
spit
rob
cream
interrupt
pen
weave
orange
rescue
crush
humble
fancy
decay
polite
tribe
bleed
coin
fond
autumn
classify
omit
loyal
needle
lessen
complaint
pad
steep
skirt
curtain
calculation
laughter
solemn
grease
interfere
explode
fasten
flag
resign
postpone
patience
boast
rope
envy
airplane
rid
shield
veil
kneel
tray
explosive
brass
taxi
wax
duck
button
invent
remedy
bush
thunder
weaken
poverty
scrape
arrow
tender
cruel
soften
mouse
hay
anyhow
alike
circular
juice
shelf
bake
hatred
cautious
basket
wreck
width
confident
log
heap
suck
ladder
gap
obey
hut
axe
translation
collar
delivery
reproduce
confession
pan
prejudice
voyage
tobacco
simplicity
paste
cake
elephant
ribbon
harvest
ashamed
cave
customary
thief
damp
sew
rust
separation
waiter
pet
straw
upset
towel
refresh
essence
fur
ambitious
defendant
daylight
dip
suspicious
imaginary
ash
carriage
educator
saw
stove
rubber
rug
misery
awkward
rival
roast
deed
preference
explosion
theatrical
cultivate
collector
miserable
wrist
rabbit
accustom
tide
insult
thumb
lump
annoy
toy
heal
shallow
repetition
soup
whistle
scenery
apple
offense
cork
ripe
temper
sore
pinch
diamond
razor
imaginative
hook
copper
landlord
influential
rot
hollow
enclose
harden
wicked
stiffen
silk
upright
selfish
stripe
pig
inward
excellence
rake
purple
hasten
shorten
applause
ache
apology
knot
nephew
cushion
drown
nursery
pint
fierce
imitate
aloud
gaiety
robbery
tighten
perfection
scorn
whoever
trunk
wool
sailor
competitor
moonlight
deer
bean
everyday
drawer
disregard
nowadays
patriotic
tin
penny
cage
pardon
lately
offend
coarse
spoil
horizontal
sting
ditch
librarian
meantime
cough
deaf
sword
messenger
vain
castle
elastic
comb
rod
widen
sorrow
inventor
cliff
umbrella
interruption
merry
gallon
conquest
headache
tailor
bucket
scent
signature
cart
darken
sometime
applaud
underneath
hello
pretense
descent
conquer
framework
confidential
adoption
disgust
waist
momentary
receipt
pearl
ray
lazy
limb
grammatical
beast
monkey
jewel
persuasion
obedience
sock
vowel
hammer
inn
chimney
dissatisfaction
annoyance
ornament
honesty
outward
sharpen
handkerchief
greed
heavenly
thirst
niece
spill
loaf
wheat
worm
secrecy
rude
heighten
flatten
loosen
cheese
rivalry
royalty
discontent
complication
fright
indoor
flour
actress
congratulation
ounce
fry
everlasting
goat
ink
disappearance
reproduction
thicken
avoidance
spoon
strap
deceive
lengthen
revenge
correction
descendant
hesitation
spade
basin
weed
omission
bicycle
breadth
photography
coward
mat
rejoice
cheat
congratulate
discomfort
enclosure
attentive
paw
overflow
dissatisfy
multiplication
whichever
tidy
bribe
mend
stocking
feast
nuisance
thorn
tame
inclusive
homemade
handwriting
chalk
sour
slippery
procession
ripen
jealous
jealousy
liar
homecoming
barber
whiten
berry
lighten
pigeon
hinder
bravery
baggage
noun
amongst
grammar
cultivation
companionship
rubbish
modesty
woolen
deepen
pastry
cupboard
quart
canal
notebook
deceit
parcel
brighten
moderation
punctual
hurrah
lipstick
uppermost
fatten
conqueror
hindrance
cowardice
obedient
saucer
madden
scold
weekday
rotten
disrespect
widower
deafen
donkey
businesslike
motherhood
sadden
handshake
calculator
headdress
scissors
translator
possessor
shilling
redden
motherly
whose
cultivator
whom
homework
electrician
oar
bribery
sweeten
sow
pronunciation
beak
plural