prefix-fa

• IPA:

prefix-fa

1. (matematika)

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.

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.

• Egy karakterláncot karakterenként adunk hozzá a fához.
• Ha egy karakter nem létezik, új csomópontot hozunk létre.

• 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.

• Ellenőrzi, hogy egy adott prefix létezik-e a fában.

class TrieNode:
    gyerekek = {}  # A csomópont gyermekei
    vége = False   # Jelzi, hogy ez egy szó vége

function insert(root, word):
    node = root
    for char in word:
        if char not in node.gyerekek:
            node.gyerekek = TrieNode()
        node = node.gyerekek
    node.vége = True

function search(root, word):
    node = root
    for char in word:
        if char not in node.gyerekek:
            return False
        node = node.gyerekek
    return node.vége

function startsWith(root, prefix):
    node = root
    for char in prefix:
        if char not in node.gyerekek:
            return False
        node = node.gyerekek
    return True

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 = TrieNode()
            node = node.children
        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
        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
        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

#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 = new TrieNode();
            }
            node = node->children;
        }
        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;
        }
        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;
        }
        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

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.

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.

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.

• prefix-fa - Értelmező szótár (MEK)
• prefix-fa - Etimológiai szótár (UMIL)
• prefix-fa - Szótár.net (hu-hu)
• prefix-fa - DeepL (hu-de)
• prefix-fa - Яндекс (hu-ru)
• prefix-fa - Google (hu-en)
• prefix-fa - Helyesírási szótár (MTA)
• prefix-fa - Wikidata
• prefix-fa - Wikipédia (magyar)