Python에서 Trie 구현
시도는 문자열을 저장하는 데 사용하는 데이터 구조입니다. 이를 통해 가장 효율적인 방식으로 텍스트 문자열을 검색할 수 있습니다.
이 기사에서는 Python에서 Trie를 구현하는 방법에 대해 설명합니다.
Python의 Trie 데이터 구조
Trie는 각 노드가 문자로 구성된 트리로 간주할 수 있습니다. 각 노드는 문자열의 내부 문자인지 마지막 문자인지에 따라 하나 이상의 자식을 갖습니다.
문자열의 마지막 문자를 나타내는 노드에는 자식이 없으며 문자열의 끝을 표시합니다. 문자열의 끝을 표시하기 위해 클래스 정의에 플래그 변수를 포함합니다.
Trie의 각 노드는 영어 소문자로만 구성된 문자열을 저장하는 경우 최대 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 값으로 목록을 초기화했습니다.
캐릭터가 현재 노드의 자식이 아닌 경우 해당 위치에는 없음 값이 포함됩니다. 그렇지 않으면 해당 문자에 해당하는 위치에 해당 문자의 노드가 저장됩니다.
자식 목록에 문자를 삽입하는 동안 문자의 알파벳 순서로 자식 노드를 저장합니다. 즉, 문자 a의 자식 노드는 인덱스 0에 저장되고 문자 b의 자식 노드는 인덱스 1에 저장됩니다.
노드를 생성한 후 Trie를 정의하기 위한 클래스를 생성해야 합니다. 클래스에서 영어 알파벳의 26자를 나타내는 26개의 None 값을 포함하는 목록이 있는 빈 노드를 정의합니다.
빈 노드를 루트 노드라고 합니다.
class Trie:
def __init__(self):
self.root = Node()
문자열이 Trie에 삽입될 때마다 문자열의 첫 번째 문자를 나타내는 노드는 root 노드의 자식이 됩니다. 위치에 따라 문자열의 다음 문자를 포함하는 노드를 목록 요소로 저장합니다.
root 노드를 만든 후 다음 섹션에서 Trie에 단어를 삽입하고 Trie에서 단어를 검색하는 메서드를 구현합니다.
Python의 Trie에 문자열 삽입
Trie에 문자를 삽입하려면 먼저 삽입할 문자열의 길이를 찾아야 합니다. 그런 다음 Trie의 루트 노드에서 Trie 크롤링을 시작합니다.
다음은 Trie에 문자열을 삽입하는 알고리즘입니다.
- Trie에 삽입할 문자열의 길이를 계산합니다. 변수
strLen에 저장합니다. 크롤러변수를 가져오고 Trie의루트노드를 변수에 할당합니다.- 레벨
n에 있는 경우 문자열의 n번째 문자가 Trie의 해당 레벨에 있는지 확인합니다. 그렇다면자식목록의 위치를position변수에 저장하십시오. 그런 다음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에서 Trie의 요소 검색
문자열이 Trie에 있는지 여부를 검색하기 위해 다음 알고리즘을 사용합니다.
crawler변수를 초기화하고 Trie의root노드를 변수에 할당합니다.- Trie에서 검색할 문자열의 길이를 계산합니다. 변수
strLen에 저장합니다. n수준에서 문자열의 n번째 문자가children목록에 있는지 확인합니다. 그렇다면4로 이동하십시오. 그렇지 않으면False를 반환합니다.- 현재 노드가 리프 노드인지 확인합니다. 예인 경우
True를 반환합니다. 그렇지 않으면n을 증가시키고3으로 이동합니다.
Trie에서 문자열을 검색하는 알고리즘을 정의했습니다. 파이썬으로 구현해 봅시다.
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에서 Trie 구현
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라는 세 개의 문자열을 Trie에 삽입했습니다.
그런 다음 Trie에서 검색 작업을 수행하여 aditya, delftstack 및 python 문자열이 Trie에 있는지 여부를 확인했습니다. 예제에서 출력을 관찰할 수 있습니다.
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