Kiejtés

  • IPA: [ ˈprɛfiksfɒ]

Főnév

prefix-fa

  1. (matematika)

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

  1. Hatékony tárolás:
    • A közös prefixeket csak egyszer tárolja.
  2. Gyors keresés:
    • A szavak keresése (O(m)) időbonyolultsággal történik, ahol (m) a keresett szó hossza.
  3. 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

  1. Hatékony keresés: (O(m)), ahol (m) a szó hossza.
  2. Közös prefixek tömör tárolása.
  3. Könnyű prefix-alapú keresések, például automatikus kiegészítés.

Hátrányok

  1. Nagy memóriaigény: Minden csomópont tárolja a gyermekek mutatóit.
  2. Nem hatékony ritka vagy kis számú szó esetén.

Felhasználási területek

  1. Automatikus kiegészítés (autocomplete).
  2. Szóellenőrzés és helyesírás-javítás.
  3. Szöveganalízis és keresés.
  4. 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.

Fordítások