Python での実装を試す
トライは、文字列を格納するために使用するデータ構造です。 それらを使用すると、可能な限り最も効率的な方法でテキスト文字列を検索できます。
この記事では、Python で Trie を実装する方法について説明します。
Python でのデータ構造のトライ
Trie は、各ノードが文字で構成される ツリー と見なすことができます。 各ノードには、それが文字列の内部文字であるか最後の文字であるかに応じて、1つ以上の子があります。
文字列の最後の文字を表すノードには子がなく、文字列の終わりを示します。 文字列の終わりをマークするために、クラス定義にフラグ変数を含めます。
トライの各ノードは、小文字の英字のみで構成される文字列を格納する場合、最大 26 個の子を持つことができます。 文字列にアルファベット以外の文字が含まれている場合、特定のノードの子の最大数は、個別の文字の総数と等しくなります。
次の例に示すように、Python で Node クラスを定義して、Trie のノードを実装できます。
class Node:
def __init__(self):
self.children = []
for i in range(26):
self.children.append(None)
self.isLeafNode = False
ここでは、キャラクターが現在のノードの子であるかどうかを定義するために使用される children という名前のリストを作成しました。 26 文字を考慮したため、リストを 26 個の None 値で初期化しました。
キャラクターが現在のノードの子でない場合、その位置には値 None が含まれます。 それ以外の場合、その文字に対応する位置にその文字のノードが格納されます。
children リストに文字を挿入する際、文字のアルファベット順に子ノードを保存します。 つまり、文字 a の子ノードはインデックス 0 に格納され、文字 b の子ノードはインデックス 1 に格納されます。
ノードを作成したら、Trie を定義するクラスを作成する必要があります。 このクラスでは、英語のアルファベットの 26 文字を表す 26 個の None 値を含むリストを持つ空のノードを定義します。
空のノードをルートノードと呼びます。
class Trie:
def __init__(self):
self.root = Node()
文字列が Trie に挿入されるたびに、文字列の最初の文字を表すノードが root ノードの子になります。 文字列の次の文字を含むノードを、その位置に従ってリスト要素として保存することに注意してください。
root ノードを作成した後、次のセクションで Trie に単語を挿入し、Trie で単語を検索するメソッドを実装します。
Python で Tri に文字列を挿入する
Trie に文字を挿入するには、まず挿入する文字列の長さを確認します。 その後、Trie の root ノードから Trie のクロールを開始します。
以下は、Trie に文字列を挿入するアルゴリズムです。
- Trie に挿入する文字列の長さを計算します。 変数
strLenに格納します。 - 変数
crawlerを取り、Trie のrootノードを変数に割り当てます。 - レベル
nにいる場合は、文字列の n 番目の文字がトライのそのレベルに存在するかどうかを確認します。 はいの場合、その位置を変数positionのchildrenリストに格納します。 次に、5に進みます。それ以外の場合は、4に進みます。 - Trie の新しいノードを作成し、それを
crawlerのインデックスpositionに割り当てます。 クローラーを次のレベルに移動します。- 文字列の最後に到達したかどうかを確認します。 はいの場合は、
7に進みます。そうでない場合は、3に進みます。 - 現在のノードを文字列の末尾としてマークします。
アルゴリズムについて説明したので、このアルゴリズムを実装して、Python の Trie に文字列を挿入しましょう。
def insert(self, input_str):
strLen = len(input_str)
crawler = self.root
for level in range(strLen):
character = input_str[level]
position = ord(character) - ord('a')
if crawler.children[position] is None:
crawler.children[position] = Node()
crawler = crawler.children[position]
crawler.isLeafNode = True
Python で Tri 内の要素を検索する
文字列がトライに存在するかどうかを検索するには、次のアルゴリズムを使用します。
- 変数
crawlerを初期化し、トライのrootノードを変数に割り当てます。 - トライで検索する文字列の長さを計算します。 変数
strLenに格納します。 - レベル
nで、文字列の n 番目の文字がchildrenリストにあるかどうかを調べます。 はいの場合は、4に進みます。 それ以外の場合は、Falseを返します。 - 現在のノードがリーフ ノードかどうかを確認します。 はいの場合、
Trueを返します。 それ以外の場合、nをインクリメントして3に進みます。
Trie 内の文字列を検索するためのアルゴリズムを定義しました。 Pythonで実装してみましょう。
def search(self, input_str):
crawler = self.root
strLen = len(input_str)
for level in range(strLen):
character = input_str[level]
position = ord(character) - ord('a')
if crawler.children[position] is None:
return False
crawler = crawler.children[position]
return crawler.isLeafNode
Python での実装を試す
Python の Trie で検索操作と挿入操作のメソッドを実装したので、いくつかの操作例を使用してコードを実行してみましょう。
class Node:
def __init__(self):
self.children = []
for i in range(26):
self.children.append(None)
self.isLeafNode = False
class Trie:
def __init__(self):
self.root = Node()
def insert(self, input_str):
strLen = len(input_str)
crawler = self.roothave
for level in range(strLen):
character = input_str[level]
position = ord(character) - ord("a")
if crawler.children[position] is None:
crawler.children[position] = Node()
crawler = crawler.children[position]
crawler.isLeafNode = True
def search(self, input_str):
crawler = self.root
strLen = len(input_str)
for level in range(strLen):
character = input_str[level]
position = ord(character) - ord("a")
if crawler.children[position] is None:
return False
crawler = crawler.children[position]
return crawler.isLeafNode
x = Trie()
myStr = "aditya"
print("Inserting the string:", myStr)
x.insert(myStr)
myStr = "delftstack"
print("Inserting the string:", myStr)
x.insert(myStr)
myStr = "aaditya"
print("Inserting the string:", myStr)
x.insert(myStr)
print("aditya is present in the trie:", x.search("aditya"))
print("delftstack is present in the trie:", x.search("delftstack"))
print("python is present in the trie:", x.search("python"))
出力：
Inserting the string: aditya
Inserting the string: delftstack
Inserting the string: aaditya
aditya is present in the trie: True
delftstack is present in the trie: True
python is present in the trie: False
最初に、この例で説明したアルゴリズムを使用して、Python で Trie を実装しました。 その後、aditya、delftstack、aaditya の 3つの文字列を Trie に挿入しました。
次に、トライで検索操作を実行して、文字列aditya、delftstack、およびpythonがトライに存在するかどうかを確認しました。 例で出力を確認できます。
Aditya Raj is a highly skilled technical professional with a background in IT and business, holding an Integrated B.Tech (IT) and MBA (IT) from the Indian Institute of Information Technology Allahabad. With a solid foundation in data analytics, programming languages (C, Java, Python), and software environments, Aditya has excelled in various roles. He has significant experience as a Technical Content Writer for Python on multiple platforms and has interned in data analytics at Apollo Clinics. His projects demonstrate a keen interest in cutting-edge technology and problem-solving, showcasing his proficiency in areas like data mining and software development. Aditya's achievements include securing a top position in a project demonstration competition and gaining certifications in Python, SQL, and digital marketing fundamentals.
GitHub