Trieを使用したオートコンプリート機能

Trieがあり、ユーザーが文字を入力するときに、一致する文字列Trieを表示する必要があります。この機能をオートコンプリートと呼びます。たとえば、Trieに "xyzzzz、" "xyz、" "xxxyyxzzz"が含まれている場合 ユーザーがxyと入力したとき 、次に xyzzzz、xyzを表示する必要があります 、など。、

結果を達成するための手順。

• 標準のTrieアルゴリズムを使用して文字列を検索します。

• 文字列が存在しない場合は、-1を返します。

• 文字列が存在し、Trieの単語の終わりである場合は、文字列を印刷します。

• 一致する文字列にノードがない場合は、戻ります。

• それ以外の場合は、すべてのノードを印刷します。

コーディングを始めましょう。

# class for Trie Node
   class TrieNode():
   def __init__(self):
# initialising trie node
   self.trie_node = {}
   self.last_node = False
   class Trie():
   def __init__(self):
# initialising the trie
   self.root = TrieNode()
# list to store the words
   self.words = []
   def create_trie(self, keys):
# creating the Trie using data
   for key in keys:
# inserting one key to the trie
   self.insert_node(key)
   def insert_node(self, key):
   node = self.root
for obj in list(key):
   if not node.trie_node.get(obj):
   # creating a TrieNode
      node.trie_node[obj] = TrieNode()
      node = node.trie_node[obj]
   # making leaf node
   node.last_node = True
   def search(self, key):
# searching for the key
   node = self.root
   is_found = True
for obj in list(key):
   if not node.trie_node.get(obj):
      is_found = False
   break
      node = node.trie_node[obj]
return node and node.last_node and is_found
   def matches(self, node, word):
if node.last_node:
   self.words.append(word)
for obj, n in node.trie_node.items():
   self.matches(n, word + obj)
   def show_auto_completion(self, key):
   node = self.root
   is_found = False
   temp = ''
for obj in list(key):
   # checking the word
if not node.trie_node.get(obj):
   is_found = True
break
   temp += obj
   node = node.trie_node[obj]
if is_found:
   return 0
elif node.last_node and not node.trie_node:
   return -1
   self.matches(node, temp)
for string in self.words:
   print(string)
return 1
   # data for the Trie
strings = ["xyz", "xyzzzz", "xyabad", "xyyy", "abc", "abbccc", "xyx", "xyxer",
a"]
   # word for auto completion
   string = "xy"
   status = ["Not found", "Found"]
# instantiating Trie class
   trie = Trie()
# creating Trie using the strings
   trie.create_trie(strings)
# getting the auto completion words for the string from strings
   result = trie.show_auto_completion(string)
if result == -1 or result == 0:
   print("No matches")

上記のコードを実行すると、次の結果が得られます。

xyz
xyzzzz
xyabad
xyyy
xyx
xyxer