Corrector ortográfico Python usando un trie

Estoy tratando de implementar un corrector ortográfico utilizando una estructura de datos trie. Actualmente tengo el siguiente esquema para un 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) 

Lo siguiente que quiero hacer es escribir la función para buscar una string y luego devolver una ortografía sugerida. ( def correct(self, string) ). ¿Cómo pasaría por este trie para implementar la búsqueda? Supongamos que ya agregué una lista de palabras al trie definiendo una raíz de nodo root , y luego uso add_item para cada una de las palabras en la lista.

Si aún no lo ha hecho, es posible que desee revisar ‘ Cómo escribir un corrector ortográfico ‘ de Norvig

Aquí hay una respuesta relacionada con su pregunta: https://stackoverflow.com/a/11016430/793956 .

También considere usar bibliotecas como https://github.com/kmike/marisa-trie#readme o https://github.com/kmike/datrie#readme

Aunque no es una respuesta directa, es posible que desee comenzar con una implementación Trie más desarrollada como esta:

 class Trie: def __init__(self): self.__final = False self.__nodes = {} def __repr__(self): return 'Trie'.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])