Ugrás a tartalomhoz

deterministic acyclic finite state automaton

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

deterministic acyclic finite state automaton (tsz. deterministic acyclic finite state automatons)

  1. (informatika) A Deterministic Acyclic Finite State Automaton (röviden DAFSA) egy speciális típusa a véges állapotú automatának, amely:

✅ determinista, ✅ irányított körmentes gráf (acyclic), ✅ és véges számú állapotot tartalmaz.

Leggyakrabban szavak halmazának hatékony tárolására használják, például szótárak vagy nyelvi feldolgozás során.


🧠 Alapfogalmak

1. Deterministic

  • Egy állapotból egy adott bemeneti szimbólumra legfeljebb egy átmenet van.
  • Nincs több alternatíva: egyetlen út lehetséges minden bemenethez.

2. Acyclic

  • Nincsenek körök: nem lehet visszatérni egy korábbi állapothoz.
  • Ez azt jelenti, hogy a bemenet véges hosszú szavakhoz vezethet csak.

3. Finite

  • Csak véges számú állapot és átmenet van.


📚 Használati példa

A DAFSA-t gyakran használják:

  • Szókészletek tárolására (pl. szótárak),
  • Prefix-optimalizálásra,
  • Spell checking, autocomplete vagy morfémák tárolására,
  • Nyelvészeti korpuszok tömör tárolására.


🧊 Példa: Szavak tárolása

Tegyük fel, hogy az alábbi szavakat szeretnénk tárolni:

cat
car
cart
dog
dot

✅ Hagyományos trie (prefixfa)

A trie redundánsan tartalmazza a hasonló előtagokat (pl. c-a vagy d-o).

✅ DAFSA: redundancia eltávolítása

A DAFSA felismeri a közös utakat és végződéseket:

          --> t (final)
         /
c → a → r → t (final)
         \
          (final)
d → o → g (final)
       \
        t (final)
  • Az ar és at közös szülőn osztoznak
  • dog és dot ugyanazt az o → szakaszt használják


🔧 Miért hasznos a DAFSA?

Előny Leírás
🔁 Redundancia csökkentése Közös prefixek és suffixek tömörítése
📦 Memóriatakarékos Sokkal kevesebb csomópont, mint trie esetén
⚡ Gyors keresés Determinisztikus: egyszerű lekövetés
📈 Növekszik a hatékonyság, ha sok közös rész van Pl. nyelvi szótárakban vagy morfémák között


📏 Formális definíció

Egy DAFSA egy 5-tuple:

M = (Q, Σ, δ, q₀, F)
  • Q: állapotok véges halmaza
  • Σ: bemeneti ábécé (pl. betűk)
  • δ: determinisztikus átmenetfüggvény δ: Q × Σ → Q
  • q₀: kezdeti állapot
  • F ⊆ Q: végállapotok
  • A δ gráf irányított és körmentes


🛠️ Építési algoritmusok

  • Incremental construction (state merging on the fly)
  • Minimal acyclic deterministic finite automaton (MADFA) építés:
    • Szavak rendezése lexikálisan
    • Trie felépítés
    • Visszafelé haladva állapotok összevonása (minimizálás)


✅ Összefoglalás

Tulajdonság DAFSA
Determinista? ✅
Körmentes? ✅
Véges? ✅
Redundancia? ❌ Csökkentve
Használat Szókészletek, szótárak, nyelvfeldolgozás
Alternatíva Trie (prefixfa), de több memóriát igényel


További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=deterministic_acyclic_finite_state_automaton&oldid=3500299”