I'm planning to implement autocomplete feature using trie data structure. I want to convert my trie into a JSON format.
class Trie(object):
"""Class representing the structure of trie"""
def __init__(self):
self.children={} #Links to other nodes
self.isEndOfWord=False
This is the output of my trie program
[
('Z', <search_trie.Trie object at 0x7f3350f32c50>),
('j', <search_trie.Trie object at 0x7f3353e77da0>),
('z', <search_trie.Trie object at 0x7f3350f32be0>),
('M', <search_trie.Trie object at 0x7f33538eb668>)
]
where:
'Z'-character stored in the trie node
<search_trie.Trie object at 0x7f3350f32c50> -points to other node
How can I convert this to JSON format? I don't want the object address to be present in JSON. How can I extract the nodes from the address and include it in JSON?
EDIT: This is my code. What modification should I do to avoid storing nodes as references? If I can store the actual object value instead of address, converting it into JSON will be simple.
from functools import reduce
class Trie(object):
"""Class representing the trie"""
def __init__(self):
self.children={}
self.isEndOfWord=False
def add(self,char): #Adds a character to dictionary and creates a new node
self.children[char]=Trie()
def insert(self,word): #Insert a new word to the trie
node=self
for char in word:
if char not in node.children:
node.add(char)
node=node.children[char]
node.isEndOfWord=True
def search(self, word): #Search for a particular word in a trie
node = self
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.isEndOfWord
def all_suffixes(self,prefix):
results = set()
if self.isEndOfWord:
results.add(prefix)
if not self.children:
return results
return reduce(lambda a, b: a | b, [node.all_suffixes(prefix + char) for (char, node) in self.children.items()]) | results
def autocomplete(self, prefix):
node = self
for char in prefix:
if char not in node.children:
return set()
node = node.children[char]
return list(node.all_suffixes(prefix))
