Hogyan Működnek Az Algoritmusok
Chapter 8 Algorithm Analysis Techniques

8. fejezet: Algoritmus-elemzési technikák

Az előző fejezetekben számos alapvető algoritmust és adatszerkezetet vizsgáltunk meg, többek között a rendezés, keresés, gráfok, szövegek és különféle alkalmazások témaköreit. Bár ezen algoritmusok megvalósítása és megértése kulcsfontosságú, ugyanilyen fontos az is, hogy elemezzük teljesítményjellemzőiket, hogy tájékozott döntéseket hozhassunk az egyes problémákhoz leginkább illő algoritmusok kiválasztásakor. Ebben a fejezetben az algoritmusok elemzésére és értékelésére használt technikákba mélyedünk el, a matematikai modellek, empirikus vizsgálatok és algoritmus-vizualizáció területére fókuszálva.

Matematikai modellek és elemzés

A matematikai elemzés hatékony eszköz az algoritmusok viselkedésének és teljesítményének megértéséhez. Olyan matematikai modellek kidolgozásával, amelyek megragadják az algoritmus lényegi jellemzőit, következtetéseket vonhatunk le annak hatékonyságáról és skálázhatóságáról. Ezek a modellek lehetővé teszik, hogy előrejelzéseket tegyünk az algoritmus futási idejéről, memóriahasználatáról és egyéb teljesítménymutatóiról, ami segít összehasonlítani a különböző algoritmusokat, és kiválasztani a legmegfelelőbbet egy adott feladathoz.

Big-O jelölés

Az algoritmusok teljesítményének leírására leggyakrabban használt jelölés a big-O jelölés. A big-O jelölés felső korlátot ad meg egy függvény növekedési ütemére, lehetővé téve, hogy jellemezzük az algoritmus futási idejének vagy memóriaigényének legrosszabb esetét.

A big-O jelölésben az algoritmus teljesítményét az input méretének (jellemzően n) függvényében fejezzük ki. Például vegyük a következő egyszerű függvényt, amely kiszámítja az első n pozitív egész szám összegét:

public static int sum(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

Ennek a függvénynek a futási ideje lineárisan növekszik az n input mérettel. Ezt big-O jelöléssel O(n)-nek írhatjuk, ami azt jelenti, hogy a futási idő arányos az input méretével. Ez azt jelenti, hogy ahogy az input mérete nő, a futási idő is lineárisan növekszik.Kérem, itt a magyar fordítás a megadott markdown fájlhoz. A kódhoz tartozó megjegyzéseket fordítottam le, a kódot nem.

A bemeneti méret növekedésével az algoritmus futási ideje legfeljebb lineárisan növekszik.

A Big-O jelölés lehetővé teszi, hogy figyelmen kívül hagyjuk a konstans tényezőket és az alacsonyabb rendű tagokat, és a függvény növekedési ütemét meghatározó domináns tagra összpontosítsunk. Például vegyük a következő függvényt:

public static int sumOfSquares(int n) {
    // Összeg inicializálása
    int sum = 0;
    // Ciklus 1-től n-ig
    for (int i = 1; i <= n; i++) {
        // Ciklus 1-től i-ig
        for (int j = 1; j <= i; j++) {
            // Összeg növelése j-vel
            sum += j;
        }
    }
    // Összeg visszaadása
    return sum;
}

Ennek a függvénynek a futási ideje arányos n négyzetével. Pontosabban, a "sum += j" utasítás végrehajtásának száma 1 + 2 + ... + N ~ N^2/2.

Általánosságban kifejezhetjük egy program futási idejét a bemeneti méret függvényében a Big-O jelöléssel. Ez lehetővé teszi, hogy elhagyjuk a vezető együtthatókat és az alacsonyabb rendű tagokat, és a futási idő növekedési ütemének lényegére összpontosítsunk.

Knuth-Morris-Pratt-algoritmus

A Knuth-Morris-Pratt (KMP) algoritmus egy hatékony alstringsearch-algoritmus, amely egy előre kiszámított "hiba-függvényt" használ a szükségtelen összehasonlítások elkerülésére.

A hiba-függvény megmutatja nekünk a minta leghosszabb megfelelő előtagjának a hosszát, amely egyben a minta eddig egyeztetett részének utótagja is. Ez lehetővé teszi, hogy "előreugorjunk" a szövegben, amikor eltérést találunk, ahelyett, hogy visszalépnénk.

Íme egy példa a KMP-algoritmusra:

Szöveg:   "abacadabrabracabracadabrabrabracad"
Minta:    "abracadabra"
Kimenet:  [13]

A KMP-algoritmus futási ideje O(n + m), ami sokkal hatékonyabb, mint a brute-force megközelítés nagy szövegek és minták esetén.

Boyer-Moore-algoritmus

A Boyer-Moore-algoritmus egy másik hatékony alstringsearch-algoritmus, amely a minta előfeldolgozásán alapul. Ellentétben a KMP-vel, amely az minta elejétől kezdi az összehasonlításokat, a Boyer-Moore a végétől indul és visszafelé halad.

A Boyer-Moore kulcsötlete két előre kiszámított függvény használata: a "jó utótag" és a "rossz karakter" függvények.Itt a magyar fordítás a megadott markdown fájlhoz. A kódban csak a megjegyzéseket fordítottam le, a kódot nem.

Függvény és a "rossz karakter" függvény. Ezek a függvények lehetővé teszik, hogy előreugorjunk a szövegben, amikor eltérést találunk, hasonlóan a KMP-hez.

Itt egy példa a Boyer-Moore algoritmusra:

Szöveg: "abacadabrabracabracadabrabrabracad" Minta: "abracadabra" Kimenet: [13]


A Boyer-Moore algoritmus legjobb esetben O(n/m) futási idővel rendelkezik, a legrosszabb esetben pedig O(n * m) futási idővel, de a gyakorlatban gyakran a leggyorsabb részlánc-keresési algoritmus nagy ábécék esetén.

## Reguláris kifejezések

A reguláris kifejezések hatalmas eszközt jelentenek a szövegekben található minták leírására. Tömör és rugalmas jelölést biztosítanak a szöveg illesztésére, kereséséhez és manipulálásához.

Egy reguláris kifejezés egy karaktersorozat, amely egy keresési mintát határoz meg. A legegyszerűbb reguláris kifejezés egy literális karakterlánc, mint például a "hello", amely pontosan a "hello" karakterláncot illeszti. Azonban a reguláris kifejezések speciális karaktereket és konstrukciókat is tartalmaznak, amelyek lehetővé teszik a bonyolultabb minták leírását:

- `.` (pont) illeszkedik bármely egyetlen karakterre.
- `*` (csillag) illeszkedik a megelőző karakter vagy csoport nulla vagy több előfordulására.
- `+` (plusz) illeszkedik a megelőző karakter vagy csoport egy vagy több előfordulására.
- `?` (kérdőjel) illeszkedik a megelőző karakter vagy csoport nulla vagy egy előfordulására.
- `^` (kalap) illeszkedik a sor elejére.
- `$` (dollár) illeszkedik a sor végére.
- `[]` (szögletes zárójelek) egy karakterosztályt határoznak meg, amely illeszkedik a zárójeleken belüli bármely egyetlen karakterre.

Íme néhány példa reguláris kifejezésekre és az általuk illesztett mintákra:

- `a.b` illeszkedik bármely három karakterből álló karakterláncra, amely "a"-val kezdődik és "b"-vel végződik, például "acb", "a5b" vagy "a b".
- `a*b` illeszkedik bármely olyan karakterláncra, amely nulla vagy több "a" karakterből áll, majd egy "b" karakterből, például "b", "ab", "aab" vagy "aaab".
- `a+b` illeszkedik bármely olyan karakterláncra, amely egy vagy több "a" karakterből áll, majd egy "b" karakterből, például "ab", "aab" vagy "aaab", de nem "b".
- `a?b` illeszkedik akár "ab"-re, akár "b"-re.
- `^a` illeszkedik bármely olyan karakterláncra, amely "a"-val kezdődik.Itt a magyar fordítás a megadott markdown fájlhoz. A kódban nem fordítottam le a kódot, csak a megjegyzéseket.

- `a$` egyezik bármely olyan karakterlánchoz, amely "a" betűvel végződik.
- `[aeiou]` egyezik bármely egyes magánhangzó karakterrel.

A reguláris kifejezések sok programozási nyelv és eszköz által támogatottak, beleértve a Javát, a Pythont és a Unix segédprogramokat, mint a grep és a sed. Széles körben használatosak adatérvényesítésre, szövegfeldolgozásra és naplóelemzésre.

## Adattömörítés

Az adattömörítés az információ kódolásának folyamata, amely kevesebb bitet használ, mint az eredeti ábrázolás. Ez hasznos a tárolási követelmények és az átviteli idők csökkentésére. Két fő típusa van a tömörítésnek: veszteségmentes és veszteséges. A veszteségmentes tömörítés lehetővé teszi, hogy az eredeti adatok tökéletesen rekonstruálhatók legyenek a tömörített adatokból, míg a veszteséges tömörítés lehetővé teszi az információ bizonyos mértékű elvesztését cserébe a nagyobb tömörítési arányokért.

### Futáshossz-kódolás

A futáshossz-kódolás (RLE) egy egyszerű veszteségmentes tömörítési technika, amely az azonos szimbólumok ismétlődő sorozatait (futásokat) egyetlen példánnyal és a megismétlődések számával helyettesíti.

Itt egy példa az RLE-re:

Bemenet: "AAAABBBCCCDDDEEE" Kimenet: "4A3B3C3D3E"


Az RLE hatékony olyan adatok esetén, amelyekben sok hosszú futás van, mint például az egyszerű grafikus képek. Azonban akár növelheti is az adatok méretét, ha kevés vagy egyáltalán nincsenek futások.

### Huffman-kódolás

A Huffman-kódolás egy veszteségmentes tömörítési algoritmus, amely változó hosszúságú kódokat rendel a szimbólumokhoz az input adatok gyakoriságai alapján. A gyakoribb szimbólumokhoz rövidebb kódok, a ritkább szimbólumokhoz pedig hosszabb kódok rendelődnek.

Az algoritmus úgy működik, hogy alulról felfelé építi fel a bináris fát, amelyet Huffman-fának nevezünk. Minden levélcsomópont egy szimbólumot és annak gyakoriságát jelöli, míg minden belső csomópont a gyermekei gyakoriságainak összegét. A fát úgy építjük fel, hogy ismételten egyesítjük a két legkisebb gyakoriságú csomópontot, amíg csak egy csomópont marad.

Miután a fa felépült, minden szimbólum kódja meghatározható a gyökértől a levélcsomópontig vezető útvonal alapján.Itt a magyar fordítás a megadott markdown fájlhoz. A kódnál csak a kommenteket fordítottam le, a kódot nem.

A megfelelő levélcsomópont, ahol a bal ág "0"-t, a jobb ág "1"-et jelöl.

Itt egy példa a Huffman-kódolásra:

Bemenet: "AAAABBBCCCDDDEEE"
Kimenet: "000010011001011100101"

Huffman-fa:
      (15)
     /    \
   (7)    (8)
   / \    / \
 (4) (3) (3) (5)
 /\  /\  /\  /\
A B  C D E

Ebben a példában az "A" kódja "00", a "B" kódja "01", a "C" kódja "10", a "D" kódja "110", az "E" kódja pedig "111". A tömörített kimenet úgy kapható meg, hogy minden szimbólumot a megfelelő kóddal helyettesítünk.

A Huffman-kódolás optimális előtag-kód, ami azt jelenti, hogy egy kód sem előtagja egy másik kódnak. Ez lehetővé teszi a tömörített adat egyértelmű dekódolását. A Huffman-kódolást széles körben használják különféle fájlformátumokban és tömörítő eszközökben, mint például a JPEG, MP3 és ZIP.

Lempel-Ziv-Welch (LZW) tömörítés

A Lempel-Ziv-Welch (LZW) tömörítés egy szótáralapú tömörítési algoritmus, amely a bemenet tömörítése közben építi fel a szótárat (vagy kódkönyvet) a karakterláncokból. Az LZW-t széles körben használják fájltömörítő segédprogramokban, és a GIF-képformátumban is alkalmazták.

Az LZW lényegi ötlete, hogy a karakterláncokat egyetlen kóddal helyettesíti. Karakter-karakter után olvassa be a bemeneti karakterláncot, és tömör ábrázolásba kódolja azt, úgy, hogy a rögzített hosszúságú kódokat változó hosszúságú kódokra cseréli. Minél hosszabb a karakterlánc, annál több hely takarítható meg a számmal való kódolással.

Íme, lépésről lépésre, hogyan működik az LZW-tömörítés:

  1. Inicializáld a szótárat, hogy az összes egyetlen karakterből álló karakterláncot tartalmazza.
  2. Keresd meg a szótárban a jelenlegi bemenettel egyező leghosszabb karakterláncot.
  3. Írd ki a szótár indexét a kimenetbe, és töröld a karakterláncot a bemenetből.
  4. Vedd fel a szótárba a karakterláncot, amit az előző lépésben kiírtál, plusz a következő szimbólumot.
  5. Menj vissza a 2. lépésre.

Nézzünk egy példát. Tegyük fel, hogy a "ABABABABA" karakterláncot szeretnénk LZW-vel tömöríteni.

  1. Inicializáld a szótárat "A" és "B" karakterláncokkal.
  2. A leghosszabb egyező karakterlánc "A". Írd ki az indexét a kimenetbe, és töröld a bemenetből.
  3. Vedd fel a szótárba az "A" karakterláncot, plusz a következő szimbólumot, ami ebben az esetben szintén "A".
  4. Menj vissza a 2. lépésre.Itt a magyar fordítás a megadott markdown fájlhoz. A kódban nem fordítottam le a kódot, csak a megjegyzéseket.

LZW Adattömörítés

  1. A leghosszabb egyezés "A". Kibocsátjuk az indexét (0) és eltávolítjuk a bemeneti adatból. A szótár most "A", "B" és "AB" elemeket tartalmaz.
  2. A leghosszabb egyezés "B". Kibocsátjuk az indexét (1) és eltávolítjuk a bemeneti adatból. A szótár most "A", "B", "AB" és "BA" elemeket tartalmaz.
  3. A leghosszabb egyezés "AB". Kibocsátjuk az indexét (2) és eltávolítjuk a bemeneti adatból. A szótár most "A", "B", "AB", "BA" és "ABA" elemeket tartalmaz.
  4. A leghosszabb egyezés "ABA". Kibocsátjuk az indexét (4) és eltávolítjuk a bemeneti adatból. A szótár most "A", "B", "AB", "BA", "ABA" és "ABAB" elemeket tartalmaz.
  5. A leghosszabb egyezés "BA". Kibocsátjuk az indexét (3). A bemeneti adat most üres.

Az "ABABABABA" tömörített ábrázolása így az [1] indexek sorozata, amely kevesebb bitet igényel, mint az eredeti ASCII ábrázolás.

A dekompresszió hasonlóan működik, de fordított sorrendben:

  1. Inicializáljuk a szótárat, hogy az összes egykarakteres karakterláncot tartalmazza.
  2. Olvassunk be egy X kódot a bemenetről.
  3. Írjuk ki az X karakterláncot a szótárból.
  4. Ha az előző kód létezik, adjuk hozzá az előző karakterlánc és az X karakterlánc első karakterének összefűzését a szótárhoz.
  5. Ugrás a 2. lépésre.

Az LZW tömörítés egyszerű és gyors, ezért sok alkalmazásban jó választás. Azonban vannak korlátai is. A szótár mérete jelentősen megnőhet, ami jelentős memóriafelhasználást eredményez. Ezen kívül a szótár minden bemeneti blokk után alaphelyzetbe áll, ami csökkentheti a tömörítési arányt a kis fájlok esetén.

Ezek a korlátozások ellenére az LZW népszerű és hatékony tömörítési algoritmus, különösen olyan alkalmazásokban, ahol a sebesség fontosabb, mint a lehető legmagasabb tömörítési arány elérése.

Következtetés

Ebben a fejezetben több fontos szövegfeldolgozási algoritmust is megvizsgáltunk, beleértve a szövegrendezést, a trie-kat, a részlánc-keresést, a reguláris kifejezéseket és az adattömörítést. Ezek az algoritmusok sok valós alkalmazás alapját képezik, és nélkülözhetetlenek minden olyan programozó számára, aki szöveges adatokkal dolgozik.

A szövegrendezéssel kezdtük, amely a legtöbb szövegfeldolgozási alkalmazás alapja. Ezt követően a trie-kat és a részlánc-keresést tárgyaltuk, amelyek hatékony módszereket biztosítanak a szöveges adatok tárolására és keresésére.Itt a magyar fordítás a megadott markdown fájlhoz. A kódhoz tartozó kommentárokat fordítottam le, a kódot nem.

Optimalizált rendezési algoritmusok, amelyek kihasználják a karakterláncok speciális tulajdonságait. A kulcs-indexelt számlálás, az LSD radix rendezés és az MSD radix rendezés hatékony módszereket biztosítanak a karakterláncok egyedi karakterek alapján történő rendezésére.

Ezután megvizsgáltuk a trie-kat, egy fa-szerű adatszerkezetet a karakterláncok tárolására és visszakeresésére. A trie-k lehetővé teszik a gyors előtag-illesztést, és gyakran használják őket olyan alkalmazásokban, mint az automatikus kiegészítés és az IP-útválasztási táblázatok.

A szubsztring-keresési algoritmusok, mint a Knuth-Morris-Pratt és a Boyer-Moore algoritmusok, lehetővé teszik, hogy hatékonyan keressünk mintákat nagyobb karakterláncokban. Ezeknek az algoritmusoknak számos alkalmazása van a szövegszerkesztésben, a számítógépes biológiában és az információ-visszakeresésben.

A reguláris kifejezések hatékony és rugalmas módot biztosítanak a karakterlánc-minták leírására. Megvitattuk a reguláris kifejezések alapvető szintaxisát, és hogy hogyan használhatók mintaillesztésre és karakterlánc-manipulációra különböző programozási nyelvekben és eszközökben.

Végül megvizsgáltuk az adattömörítési algoritmusokat, amelyek csökkentik az adatok méretét a bemeneti adatokban lévő redundanciák és minták kihasználásával. Foglalkoztunk a hosszúság-kódolással, a Huffman-kódolással és a Lempel-Ziv-Welch-tömörítéssel, amelyeknek mindegyiknek megvannak a saját erősségei és alkalmazásai.

A karakterlánc-feldolgozási algoritmusok és adatszerkezetek megértése kulcsfontosságú mindazok számára, akik szöveges adatokkal dolgoznak. Ahogy a strukturálatlan adatok mennyisége tovább növekszik, a karakterláncok hatékony manipulálása, keresése és tömörítése egyre értékesebbé válik. A fejezetben tárgyalt technikák elsajátításával jól fel leszel készülve a karakterlánc-feldolgozási kihívások széles körének kezelésére saját projektjeidben és alkalmazásaidban.

Chapter 7 ContextChapter 9 Algorithm Design Paradigms Divide and Conquer