1

I have a wlist.txt file of about 58k words of the english language, a small excerpt of which looks like this :

aardvark
aardwolf
aaron
aback
abacus
abaft
abalone
abandon
abandoned
abandonment
abandons
abase
abased
abasement

What I would like to do is have a program search through the list and see if a word is contained in the list, and if so print the word. My issue is that the code i have written will constantly return that no, the word is not in the list, when i know for sure that it is. My code looks like this, anybody notice any bugs?

match = 'aardvark'
f = 'wlist.txt'
success = False
try:
    for word in open(f):
        if word == match:
            success = True
            break
except IOError:
    print f, "not found!"
if success:
    print "The word has been found with a value of", word
else:
    print "Word not found"

Thanks in advance everyone!!

11 Answers 11

6

As others have already said, your problem stems from the fact that the newline characters are part of the words you are reading in. The best way to get rid of these is to use the strip() method of str.

In addition, your code does too much to accomplish a simple task. All you need to do is build a set from your word list and look for the occurrence of your word in the set. A set is far better for this task than a list because checking for the occurrence of an element in a set is much faster. So something like this should work.

try:
    with open('wordlist.txt', 'rU') as infile:
        wordSet = set(line.strip() for line in infile)
except IOError:
       print 'error opening file'

aWord = 'aardvark'

if aWord in wordSet:
    print 'found word', aWord
else:
    print 'word not found'

Note: if aWord in wordSet is so much faster it isn't funny. If you're looking for a word closer to the end of the word list, set is nearly 60000 times faster for a 267000 word list. And it's still marginally faster even if you're looking for the very first word.

3

Here is the code that should work

match = 'aardvark'
    f = 'wlist.txt'
    success = False
    try:
        for word in open(f):
            if word.strip() == match: # Change here 
                success = True
                break
    except IOError:
        print f, "not found!"
    if success:
        print "The word has been found with a value of", word
    else:
        print "Word not found"
3
  • Good - if the word is found it will quit early. Mar 7, 2011 at 3:40
  • 2
    This is good for a one-off search, but for multiple searches, you pay the cost of IO over and over again. For ~58k words, RAM is unlikely to be an issue, so building a set of all the words and looking in the set is going to pay off very quickly (file IO will probably take on the order of 100 ms, to read the whole file, looking in the set takes 100 ns or two orders of magnitude less). Mar 7, 2011 at 4:01
  • In addition, you never close the file. Much better to use with for opening files. Mar 7, 2011 at 4:08
3

Everyone's given you good advice about how to do this, but do you really need to use python?

grep aardvark wlist.txt

It'll almost certainly destroy any python based solution for speed. fgrep will probably be even quicker.

2
  • 2
    Not all OSs have grep, and we don't know the OP's intent. Eg. This could be a self-exercise, or a component of a larger python script.
    – winwaed
    Mar 7, 2011 at 3:42
  • 1
    Also, this should be grep "^aardvark[\\s]*$", otherwise you will also find words which contain the word you're searching for. Mar 7, 2011 at 13:13
1

Iteration on file objects includes newlines.

1
  • 3
    Could you please elaborate? How do i fix this? Mar 7, 2011 at 2:45
1

Try replacing word == match with word[0:-1] == match to remove the newline character at the end of word.

Edit: Alternately, replace word == match with word.rstrip() == match as suggested in this question.

1
  • 2
    word[0:-1] should probably be avoided unless you are always absolutely sure of exactly one trailing whitespace; .rstrip() is a much safer solution. Mar 7, 2011 at 3:38
1

Here is my very simple suggestion:

wordlist = map(str.strip, open("wlist.txt", "r").readlines())
if word in wordlist:
   print "The word has been found with a value of", word
else:
   print "Word not found"
1
  • 1
    you should use a set instead, because lookup is much faster. also, a generator expression is preferred nowadays. see Chinmay Kanchi's answer.
    – user3850
    Mar 7, 2011 at 7:37
1
file = open(f)
words = set( (line.strip() for line in file.readlines()) )
file.close()

if match in words:
    print "The word has been found with a value of", word
else:
    print "Word not found"
0
1

Your problem is much simpler to solve. You have not realized that you can read the entire list in memory at a very modest cost - your file is less than 1 MB, it fits perfectly well in memory.

The solution to your problem is to read the entire thing into an array and use standard list methods to look for membership:

# this is the only thing you need to get all the words in memory
words = [w.strip() for w in open("words.txt", "rb").readlines()]

# this is the only thing you need to find wether a word is in the list
print 'aaron' in words
# returns 'True'

# now you can go around many times and ask for membership of any word, 
# or any list of words (use a loop) - the array is already in memory 
# and will stay there until you close the program - it's only 1 mega!

It can be argued that my solution is not clever, but I think it is practical - premature optimization is the root of all evil, and by trying to write a clever loop, you are missing out in a perfectly simple approach that given your problem works perfectly well (by the way, the first call to the function takes less than a second for a 60-thousand-word text file, every search is also extremely fast).

Notice: you don't need a set (you don't care if a word is repeated - the answer is the same).

Don't solve the wrong problem!

PS. A lot of people seem to think that 58k words is "a lot" - it is (58 + average length) kB (if the words are ~10 letters each, that's 580 kB - about half a meg). When I hear people saying that you should not open that in memory, I wonder how do they open their pictures! It is a paradigm that needs to be broken. People will claim "but your program is not robust, because if the list becomes 100 million gizillion lines, it will break", and that's fair in a world where the English language will increase its vocabulary by 10 orders of magnitude. We often forget that general means general for your domain.

Edit: As per @Chinmay comments, using a set over a list has dramatic access consequences. Using a 58K word list, I ran two 1000 access exercises: list, and set (access time in microseconds):

container    min    max   mean
list           3   1646  724.4
set            1     31    1.6

So, as @Chinmay points out, the mean access time is almost three orders of magnitude smaller for a set. This can make a difference if you are accessing the words many times (which you presumably are).

So, I sand corrected and modify the code to:

# create a set of words
words = set(w.strip() for w in open('file.txt').readlines())

# test access using the `in` operator, as :
'aaron' in words
# will return True

My point remains: the solution to this problem is much simpler than creating a class to implement the membership operator.

3
  • 1
    "you don't care if a word is repeated - the answer is the same". That is precisely why you should use a set. Premature optimization does not mean you shouldn't attempt to use the right tool for the job. This is a genuinely poor answer, since you a) know that a set is better for the job and yet use a list, when using a set doesn't add complexity or reduce readability of the code and b) you've dangerously misunderstood the meaning of premature optimization. -1 Mar 7, 2011 at 10:52
  • @Chinmay: why is a set better for the job? How did I misunderstood premature optimization?
    – Escualo
    Mar 7, 2011 at 23:12
  • Checking for occurrence of a value in a set is O(1), it's O(k) for a list, where k is the index of the value. This is why set is 4-5 orders of magnitude faster in the worst case, for a large word list. The concept of premature optimization only applies when the "optimized" version takes more programmer time or is less elegant than the "unoptimized" version. When both solutions are equally readable, and take an equal amount of time to implement, and one is 60000 times faster than the other, it is criminal not to use the quicker version when one is aware of it. Mar 8, 2011 at 0:04
0
class WordMatcher(object):
    @classmethod
    def fromFile(cls, fname):
        with open(fname) as inf:
            return cls(inf)

    def __init__(self, words):
        super(WordMatcher,self).__init__()
        self.words = set(word.strip().lower() for word in words)

    def __contains__(self, word):
        return word.strip().lower() in self.words

    def goodWords(self, lst):
        _sw = self.words
        for word in lst:
            word = word.strip().lower()
            if word in _sw:
                yield word

wordlist = WordMatcher.fromFile('wordlist.txt')

'abase' in wordlist   # -> True
list(wordlist.goodWords(['Abandon', 'abased\n', 'xyzzy']))  # -> ['abandon','abased']
0

The problem in the code you posted is that iterating over an open file includes the newline characters. Other answers deal with that issue.

This answer is to point out that the strategy is very inefficient if the search is to be done often.

If the search will be performed a number of times, then it is best to to store the word list as a Trie, which enables O(m) lookups, with m being the length of the searched string, while constructing the Trie has complexity similar to searching the word list for one word. The Trie can be stored to disk (pickled?) for fast retrieval.

Looking up a word against the dictionary using the posted code takes time proportional to the size of the dictionary, which is O(n). Building the Trie is O(n+C), with a big C, which makes it worth it only if there are going to be frequent searches.

I took a look, and the Web says that there are several implementations of Trie in Python ready to try .

3
  • Python's set() uses a hash resulting in O(1) run-time. Mar 7, 2011 at 3:44
  • No need, just use set. A trie is only useful when looking for words beginning with a string. To check for occurrence, a set is much better, with searches occurring in O(1) rather than O(m). Mar 7, 2011 at 4:10
  • @Chinmay Searches in hashes are O(1) for the large, but they're still O(m*C) when you look closer. You have to hash the string searched for in O(m), and compare it to each element in the corresponding bucket at O(m*k). A Trie is the most efficient data structure when there are many updates and lookups.
    – Apalala
    Mar 9, 2011 at 21:50
0

Guess you can do it using regular expressions(re) in python. Just import library re using import re re.search(pattern,source) or re.findall(pattern,source)

with open('wordlist.txt', 'rU') as infile: for item in infile.readlines():

if re.search(r'^aardvark',item):
    print('word found')
else:
    print('word not found')

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.