Python spell checker using a trie

Question

I am trying to implement a spell checker using a trie data structure. I currently have the following outline for a Node:

class Node:
    def __init__(self):
        self.next = {}
        self.word_marker = False

    def add_item(self, string):
        #if the length of the string is 0 then return. When the end of the word 
        #comes set the word_marker to true
        if len(string) == 0:
            self.word_marker = True
            return
        #set the key to the first letter of the string and reformat the string to reflect the first letter taken out
        #ultimately going to store the letters for each node as the key
        key = string[0]
        string = string[1:]

        #if there is a key in the dictionary, then recursively call add_item with new string
        if key in self.next:
            self.next[key].add_item(string)

        else:
            node = Node()
            self.next[key] = node
            node.add_item(string)

The next thing that I want to do is write the function to search for a string and then return a suggested spelling. (def correct(self, string)). How would I go through this trie to implement the search? Assume that I already added a list of words to the trie by defining a root node root, then using add_item for each of the words in the list.

`d.has_key(k)` is really old hat; use `k in d` – John Machin Oct 19 '11 at 06:49 — John Machin, Oct 19 '11 at 06:49
cool thanks will make the change – locoboy Oct 19 '11 at 16:01 — locoboy, Oct 19 '11 at 16:01

score 4 · Answer 1 · answered Oct 19 '11 at 06:25

4

If you haven't already, you might want to check out Norvig's 'How to Write a Spelling Corrector'

answered Oct 19 '11 at 06:25

CSkau

625
6
10

Yeah saw this but I don't want to depend on probability. I'd like to be able to solve ability to filter aaaappppllleee = > apple and jella => jello. The first is distinguishing between repeating letters and the second is replacing vowels. – locoboy Oct 19 '11 at 06:36
1

cfarm54, read the part about *edit distance*. It sounds like that is what you're looking for. Secondly, don't be scared off by the use of probability theory. Norvig knows what he is doing, and uses it for a reason. If you want a good general-use spelling corrector, then that is the way to go. Hand-woven heuristics will only get you so far.. – CSkau Oct 19 '11 at 07:14
I saw this, however I'd like to try to go through each of the cases to see if there's something we can do programmatically. – locoboy Oct 19 '11 at 15:45
1

Why does `jella` map to `jello`? What's special about vowels? The letter `a` is next to `s` on a qwerty keyboard, so surely `jells` is a more likely candidate. – ekhumoro Oct 19 '11 at 16:31
I think there are many situations that need to be covered but i'd just like to understand one at a time. vowels, then consonants, then keyboard distance. obviously this can get complicated very quickly, so i want to do the simple ones first. – locoboy Oct 19 '11 at 16:48

score 2 · Answer 2 · edited May 23 '17 at 11:48

2

There's an answer to related to your question here: https://stackoverflow.com/a/11016430/793956 .

Also consider using libraries such as https://github.com/kmike/marisa-trie#readme or https://github.com/kmike/datrie#readme

edited May 23 '17 at 11:48

Community

1
1

answered Dec 07 '12 at 15:43

Jeff

1,232
1
13
22

score 0 · Answer 3 · answered Jul 12 '13 at 16:30

Though not a direct answer, you might want to start with a more developed Trie implementation like this:

class Trie:

    def __init__(self):
        self.__final = False
        self.__nodes = {}

    def __repr__(self):
        return 'Trie<len={}, final={}>'.format(len(self), self.__final)

    def __getstate__(self):
        return self.__final, self.__nodes

    def __setstate__(self, state):
        self.__final, self.__nodes = state

    def __len__(self):
        return len(self.__nodes)

    def __bool__(self):
        return self.__final

    def __contains__(self, array):
        try:
            return self[array]
        except KeyError:
            return False

    def __iter__(self):
        yield self
        for node in self.__nodes.values():
            yield from node

    def __getitem__(self, array):
        return self.__get(array, False)

    def create(self, array):
        self.__get(array, True).__final = True

    def read(self):
        yield from self.__read([])

    def update(self, array):
        self[array].__final = True

    def delete(self, array):
        self[array].__final = False

    def prune(self):
        for key, value in tuple(self.__nodes.items()):
            if not value.prune():
                del self.__nodes[key]
        if not len(self):
            self.delete([])
        return self

    def __get(self, array, create):
        if array:
            head, *tail = array
            if create and head not in self.__nodes:
                self.__nodes[head] = Trie()
            return self.__nodes[head].__get(tail, create)
        return self

    def __read(self, name):
        if self.__final:
            yield name
        for key, value in self.__nodes.items():
            yield from value.__read(name + [key])

Python spell checker using a trie

3 Answers3

Linked