prefix-fa
Kiejtés
- IPA: [ ˈprɛfiksfɒ]
Főnév
Trie (Prefix-fa)
A trie (vagy prefix-fa) egy speciális fa adatszerkezet, amelyet hatékonyan használnak szavak, karakterláncok és prefixek tárolására és keresésére. Minden csomópont egy karaktert reprezentál, és egy szót vagy karakterláncot a gyökértől a levélig vezető út jelöl.
Tulajdonságai
- Hatékony tárolás:
- A közös prefixeket csak egyszer tárolja.
- Gyors keresés:
- A szavak keresése (O(m)) időbonyolultsággal történik, ahol (m) a keresett szó hossza.
- Alkalmazások:
- Automatikus kiegészítés (autocomplete).
- Szavak szűrése és keresése.
- Szótár implementációja.
- DNS keresések.
Alapvető műveletek
1. Beszúrás
- Egy karakterláncot karakterenként adunk hozzá a fához.
- Ha egy karakter nem létezik, új csomópontot hozunk létre.
2. Keresés
- Egy karakterláncot karakterenként keresünk a fában.
- Ha az összes karakter megtalálható, és a végén egy “vége” jelző igaz, akkor a karakterlánc létezik.
3. Prefix keresés
- Ellenőrzi, hogy egy adott prefix létezik-e a fában.
Pszeudokód
Trie csomópont
class TrieNode: gyerekek = {} # A csomópont gyermekei vége = False # Jelzi, hogy ez egy szó vége
Beszúrás
function insert(root, word): node = root for char in word: if char not in node.gyerekek: node.gyerekek[char] = TrieNode() node = node.gyerekek[char] node.vége = True
Keresés
function search(root, word): node = root for char in word: if char not in node.gyerekek: return False node = node.gyerekek[char] return node.vége
Prefix ellenőrzés
function startsWith(root, prefix): node = root for char in prefix: if char not in node.gyerekek: return False node = node.gyerekek[char] return True
Python implementáció
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
# Példa használat
trie = Trie()
trie.insert("apple")
trie.insert("app")
trie.insert("bat")
# Keresések
print(trie.search("app")) # True
print(trie.search("apple")) # True
print(trie.search("bat")) # True
print(trie.search("batman")) # False
print(trie.starts_with("ap")) # True
print(trie.starts_with("ba")) # True
print(trie.starts_with("cat")) # False
Kimenet:
True True True False True True False
C++ implementáció
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
class TrieNode {
public:
unordered_map<char, TrieNode*> children;
bool is_end_of_word;
TrieNode() {
is_end_of_word = false;
}
};
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(const string& word) {
TrieNode* node = root;
for (char c : word) {
if (node->children.find(c) == node->children.end()) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->is_end_of_word = true;
}
bool search(const string& word) {
TrieNode* node = root;
for (char c : word) {
if (node->children.find(c) == node->children.end()) {
return false;
}
node = node->children[c];
}
return node->is_end_of_word;
}
bool starts_with(const string& prefix) {
TrieNode* node = root;
for (char c : prefix) {
if (node->children.find(c) == node->children.end()) {
return false;
}
node = node->children[c];
}
return true;
}
};
int main() {
Trie trie;
trie.insert("apple");
trie.insert("app");
trie.insert("bat");
// Keresések
cout << trie.search("app") << endl; // 1
cout << trie.search("apple") << endl; // 1
cout << trie.search("bat") << endl; // 1
cout << trie.search("batman") << endl; // 0
cout << trie.starts_with("ap") << endl; // 1
cout << trie.starts_with("ba") << endl; // 1
cout << trie.starts_with("cat") << endl; // 0
return 0;
}
Kimenet:
1 1 1 0 1 1 0
Előnyök
- Hatékony keresés: (O(m)), ahol (m) a szó hossza.
- Közös prefixek tömör tárolása.
- Könnyű prefix-alapú keresések, például automatikus kiegészítés.
Hátrányok
- Nagy memóriaigény: Minden csomópont tárolja a gyermekek mutatóit.
- Nem hatékony ritka vagy kis számú szó esetén.
Felhasználási területek
- Automatikus kiegészítés (autocomplete).
- Szóellenőrzés és helyesírás-javítás.
- Szöveganalízis és keresés.
- DNS-címek gyors keresése.
A Trie adatszerkezet ideális olyan alkalmazásokhoz, ahol a karakterláncok gyors keresése és tárolása a cél, különösen akkor, ha közös prefixeket tartalmazó adatokkal dolgozunk.