Hogyan Működnek Az Algoritmusok
Chapter 9 Algorithm Design Paradigms Divide and Conquer

9. fejezet: Algoritmus-tervezési paradigmák

Az előző fejezetekben számos különböző algoritmust vizsgáltunk meg, amelyek specifikus problémák megoldására szolgálnak, mint például rendezés, keresés, gráf-bejárás és szövegfeldolgozás. Bár ezek az algoritmusok sokféle alkalmazásban és megvalósításban különböznek, sok közös tervezési elvet vagy paradigmát osztanak.

Ebben a fejezetben három alapvető algoritmus-tervezési paradigmát fogunk megvizsgálni: az osztás és egyesítés, a mohó algoritmusok és a dinamikus programozás paradigmáit. Ezek a paradigmák általános problémamegoldási megközelítéseket kínálnak, amelyek adaptálhatók a legkülönbözőbb problémák megoldására. Ezen paradigmák megértésével betekintést nyerhetünk az algoritmusok szerkezetébe, és új algoritmusokat fejleszthetünk a felmerülő problémák megoldására.

Osztás és egyesítés

Az osztás és egyesítés paradigma egy hatékony és széles körben használt megközelítés hatékony algoritmusok tervezésére. Az alapötlet az, hogy a problémát kisebb részproblémákra bontjuk, rekurzívan megoldjuk ezeket a részproblémákat, majd egyesítjük a megoldásokat az eredeti probléma megoldásának érdekében.

Egy tipikus osztás és egyesítés algoritmus három lépésből áll:

  1. Osztás: Ha a probléma elég kicsi ahhoz, hogy közvetlenül megoldjuk, akkor oldjuk meg. Egyébként osszuk fel a problémát kisebb részproblémákra.
  2. Meghódítás: Rekurzívan oldjuk meg mindegyik részproblémát.
  3. Egyesítés: Egyesítsük a részproblémák megoldásait, hogy megkapjuk az eredeti probléma megoldását.

Az osztás és egyesítés algoritmusok hatékonysága abból fakad, hogy képesek a probléma méretét egy konstans tényezővel csökkenteni minden rekurzív lépésben. Ez gyakran logaritmikus vagy polilogatmikus futási időt eredményez.

Egyesítéses rendezés: Egy klasszikus osztás és egyesítés algoritmus

Az egyesítéses rendezés (mergesort) az egyik legjobban ismert példája az osztás és egyesítés algoritmusnak, amelyet részletesen tárgyaltunk a 2. fejezetben. Emlékeztetőül: az egyesítéses rendezés egy tömböt úgy rendez, hogy azt két részre osztja, rekurzívan rendezi mindkét részt, majd egyesíti a rendezett részeket.

Itt egy magas szintű leírása az egyesítéses rendezés algoritmusának:

// Megjegyzés: A kódot nem kell lefordítani
function mergeSort(array):
    if length(array) <= 1:
        return array
    
    middle = length(array) / 2
    left_half = array[0:middle]
    right_half = array[middle:]
    
    left_half = mergeSort(left_half)
    right_half = mergeSort(right_half)
    
    return merge(left_half, right_half)

function merge(left, right):
    result = []
    left_index = 0
    right_index = 0
    
    while left_index < length(left) and right_index < length(right):
        if left[left_index] <= right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1
    
    result += left[left_index:]
    result += right[right_index:]
    return result

Íme a magyar fordítás:

function mergesort(tömb):
    if tömb.hossz <= 1:
        return tömb
    else:
        közép = tömb.hossz / 2
        bal = mergesort(tömb[0:közép])
        jobb = mergesort(tömb[közép:])
        return merge(bal, jobb)

A merge függvény két rendezett tömböt egyesít egyetlen rendezett tömbben:

function merge(bal, jobb):
    eredmény = []
    while bal nem üres és jobb nem üres:
        if bal[0] <= jobb[0]:
            append bal[0] to eredmény
            remove bal[0] from bal
        else:
            append jobb[0] to eredmény
            remove jobb[0] from jobb
    append remaining elements of bal to eredmény
    append remaining elements of jobb to eredmény
    return eredmény

Az osztás és meghódítás stratégia lehetővé teszi, hogy a mergesort a legrosszabb esetben is O(n log n) futási időt érjen el, ami az egyik leghatékonyabb általános célú rendezési algoritmus.

A Mester Tétel

Sok osztás és meghódítás algoritmus futási ideje elemezhető a Mester Tétel segítségével, amely általános formulát ad a következő alakú rekurzióra:

T(n) = aT(n/b) + f(n)

Itt a a rekurzív hívások száma, n/b az egyes részproblémák mérete, és f(n) a probléma felosztásának és az eredmények kombinálásának a költsége.

A Mester Tétel szerint ennek a rekurziónak a megoldása:

  1. Ha f(n) = O(n^(log_b(a) - ε)) valamely ε > 0 konstansra, akkor T(n) = Θ(n^log_b(a)).
  2. Ha f(n) = Θ(n^log_b(a)), akkor T(n) = Θ(n^log_b(a) * log n).
  3. Ha f(n) = Ω(n^(log_b(a) + ε)) valamely ε > 0 konstansra, és af(n/b) ≤ cf(n) valamely c < 1 konstansra és elég nagy n-re, akkor T(n) = Θ(f(n)).

A mergesort esetében a = 2 (két rekurzív hívás), b = 2 (minden részprobléma fele akkora), és f(n) = Θ(n) (az egyesítés lépés lineáris időt vesz igénybe). Mivel log_2(2) = 1, a Mester Tétel 2. esetébe esünk, és a futási idő Θ(n log n).

Egyéb Osztás és Meghódítás Algoritmusok

Sok más alItt van a magyar fordítás a megadott markdown fájlhoz. A kódnál nem fordítottam le a kódot, csak a megjegyzéseket.

Divide and Conquer Algoritmusok

Az algoritmusok tervezhetők a divide and conquer (osztás és megoldás) paradigma használatával. Néhány figyelemre méltó példa:

  • Gyorsrendezés (Quicksort): Hasonlóan a egyesítéses rendezéshez (mergesort), a gyorsrendezés is egy divide and conquer rendezési algoritmus. Felosztja a tömböt egy pivot elem körül, rekurzívan rendezi a pivot bal és jobb oldali részhalmazait, majd összekapcsolja az eredményeket.

  • Bináris keresés: A bináris keresési algoritmus egy elem megtalálására egy rendezett tömbben szintén felfogható divide and conquer algoritmusként. Összehasonlítja a keresett értéket a tömb középső elemével, és rekurzívan a bal vagy jobb felében folytatja a keresést, a összehasonlítás eredményétől függően.

  • Karatsuba-féle szorzás: Ez egy divide and conquer algoritmus két n-jegyű szám szorzására O(n^log_2(3)) ≈ O(n^1.585) időben, ami gyorsabb, mint a hagyományos O(n^2) algoritmus.

  • Strassen-féle mátrixszorzás: A Strassen-algoritmus két n × n méretű mátrix szorzását O(n^log_2(7)) ≈ O(n^2.807) időben végzi, ami jobb, mint a naiv O(n^3) algoritmus.

Ezek a példák szemléltetik a divide and conquer paradigma sokoldalúságát és erejét hatékony algoritmusok tervezésében.

Mohó Algoritmusok

A mohó algoritmusok olyan algoritmusok, amelyek minden lépésben a lokálisan optimális választást teszik, abban a reményben, hogy ez globálisan optimális megoldáshoz vezet. Gyakran használják őket optimalizálási problémákra, ahol a megoldást lépésről lépésre építjük fel, minden lépésben a pillanatnyi legjobb választást megtéve.

A mohó algoritmusok fő jellemzői:

  1. Minden lépésben a lokálisan optimális választást teszik, a jövőbeli következményekkel nem törődve.
  2. Feltételezik, hogy a lokálisan optimális választás globálisan optimális megoldáshoz vezet.
  3. Soha nem vizsgálják felül a korábbi választásaikat.

A mohó algoritmusok általában egyszerűen érthetők és implementálhatók, és nagyon hatékonyak lehetnek. Azonban nem mindig adnak optimális megoldást, mivel a lokálisan optimális választások nem feltétlenül vezetnek globálisan optimális megoldáshoz.

Huffman-kódolás: Egy Mohó Algoritmus az Adattömörítéshez

HuffmanItt a magyar fordítás a megadott markdown fájlhoz. A kódhoz tartozó kommentárokat fordítottam le, a kódot nem módosítottam.

A fejezetben 5-ben tárgyalt mohó algoritmus, a Huffman-kódolás, egy optimális prefix-mentes kód létrehozására szolgál adatok tömörítéséhez. Az algoritmus alulról felfelé építi fel a bináris fát, a gyakoribb karakterekhez rövidebb bitsorozatokat rendelve.

A Huffman-kódolás algoritmusának magas szintű leírása:

  1. Hozz létre egy levélcsomópontot minden karakterhez, és add hozzá őket egy prioritási sorhoz.
  2. Amíg több mint egy csomópont van a sorban:
    • Vedd ki a két legkisebb gyakoriságú csomópontot a sorból.
    • Hozz létre egy új belső csomópontot ezekkel a két csomóponttal gyermekként, és a gyakoriságát állítsd a két csomópont gyakoriságának összegére.
    • Add az új csomópontot a prioritási sorhoz.
  3. A megmaradt csomópont a gyökércsomópont, és a fa kész.

A mohó választás a két legkisebb gyakoriságú csomópont egyesítése. Ez a lokálisan optimális választás globálisan optimális prefix-mentes kódhoz vezet.

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

Tegyük fel, hogy a következő karaktergyakoriságaink vannak:

d: 1
e: 1

Itt a Huffman-fa ehhez a példához:

      (15)
     /    \
   (7)    (8)
   / \    / \
 (4) (3) (3) (5)
 /\  /\  /\  /\
A B  C D E

Az eredményül kapott Huffman-kódok:

A: 00
B: 01
C: 10
D: 110
E: 111

Így az eredeti "AAAABBBCCCDDDEEE" sztring kódolása:

00000000010101101010110110110111111111

A Huffman-kódolás a gyakoribb szimbólumokhoz rövidebb kódokat rendelve tömörít. A kódok prefix-mentesek, azaz egyikük sem előtagja a másiknak, ami lehetővé teszi az egyértelmű dekódolást.

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 alapötlete a karakterláncok egyetlen kóddal való helyettesítése. Karakter-karakter után olvassa be a bemeneti sztringet, és a tömörített reprezentációba kódolja a karakterláncokat a szótár kódjaival helyettesítve.Itt a magyar fordítás a megadott markdown fájlhoz. A kódnál csak a megjegyzéseket fordítottam le, a kódot nem.

Változó hosszúságú kód használata. Minél hosszabb a sztring, annál több helyet takarítunk meg a számként való kódolással.

Itt a lépésenkénti leírása, hogy hogyan működik az LZW tömörítés:

  1. Inicializáljuk a szótárat, hogy tartalmazzon minden egyetlen karakterből álló sztringet.
  2. Találjuk meg a leghoszszabb W sztringet a szótárban, ami megegyezik a jelenlegi bemenettel.
  3. Kibocsátjuk a W szótári indexét a kimenethez, és eltávolítjuk W-t a bemenetből.
  4. Hozzáadjuk W-t a következő szimbólummal a szótárhoz.
  5. Ugrunk a 2. lépésre.

Nézzünk egy példát. Tegyük fel, hogy tömöríteni akarjuk az "ABABABABA" sztringet LZW-vel.

  1. Inicializáljuk a szótárat "A" és "B" tartalommal.
  2. A leghosszabb egyezés "A". Kibocsátjuk az indexét (0) és eltávolítjuk a bemenetből. A szótár most "A", "B" és "AB" tartalmú.
  3. A leghosszabb egyezés "B". Kibocsátjuk az indexét (1) és eltávolítjuk a bemenetből. A szótár most "A", "B", "AB" és "BA" tartalmú.
  4. A leghosszabb egyezés "AB". Kibocsátjuk az indexét (2) és eltávolítjuk a bemenetből. A szótár most "A", "B", "AB", "BA" és "ABA" tartalmú.
  5. A leghosszabb egyezés "ABA". Kibocsátjuk az indexét (4) és eltávolítjuk a bemenetből. A szótár most "A", "B", "AB", "BA", "ABA" és "ABAB" tartalmú.
  6. A leghosszabb egyezés "BA". Kibocsátjuk az indexét (3). A bemenet most üres.

Az "ABABABABA" tömörített reprezentációja így a [1] indexsorozat, ami kevesebb bitet igényel, mint az eredeti ASCII reprezentáció.

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

  1. Inicializáljuk a szótárat, hogy tartalmazzon minden egyetlen karakterből álló sztringet.
  2. Olvassunk be egy X kódot a bemenetből.
  3. Kiírjuk az X sztringet a szótárból.
  4. Ha az előző kód létezik, adjuk hozzá az előző sztringhez az X sztring első karakterét a szótárhoz.
  5. Ugrunk 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 elég nagyra nőhet, ami jelentős memóriafogyasztást jelent. Ezen kívül,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 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 továbbra is népszerű és hatékony tömörítési algoritmus, különösen olyan alkalmazások esetén, 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 vizsgáltunk meg, beleértve a szövegrendezést, a trie-kat, a részszöveg-keresést, a reguláris kifejezéseket és az adattömörítést. Ezek az algoritmusok számos valós alkalmazás alapját képezik, és nélkülözhetetlenek minden olyan programozó számára, aki szöveges adatokkal dolgozik.

Először a szövegrendezési algoritmusokat tárgyaltuk, amelyek a szövegek speciális tulajdonságait kihasználva optimalizált rendezési algoritmusok. 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 szövegek egyedi karakterek alapján történő rendezésére.

Ezt követően a trie-kat, egy fa-szerű adatszerkezetet vizsgáltunk meg, amely a szövegek tárolására és visszakeresésére szolgál. 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 részszöveg-keresési algoritmusok, mint a Knuth-Morris-Pratt és a Boyer-Moore algoritmusok, lehetővé teszik, hogy hatékonyan keressünk mintákat nagyobb szövegeken belül. 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 szövegminták leírására. Megvitattuk a reguláris kifejezések alapvető szintaxisát, és azt, hogy hogyan használhatók mintaillesztésre és szövegmanipulá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 a bemeneti adatok redundanciáját és mintáit kihasználva csökkentik az adatok méretét. Foglalkoztunk a hosszúság-kódolással, a Huffman-kódolással és a Lempel-Ziv-Welch-tömörítéssel, amelyek mindegyikének megvannak a maga erősségei és alkalmazási területei.

Ezen szövegfeldolgozási algoritmusok és adatszerkezetek megértése kulcsfontosságú minden olyan programozó számára, aki szöveges adatokkal dolgozik.Here is the Hungarian translation of the provided markdown file, with the code comments translated:

Hatékony munkavégzés szöveges adatokkal

Ahogy a strukturálatlan adatok mennyisége folyamatosan növekszik, a szövegek hatékony kezelése, keresése és tömörítése egyre értékesebbé válik. Ennek a fejezetnek a technikáinak elsajátításával jól fel leszel készülve, hogy megbirkózz a saját projektjeid és alkalmazásaid széles körű szövegfeldolgozási kihívásaival.

# Egy szöveg hosszának kiszámítása
len(text)
 
# Egy szöveg összes karakterének megszámlálása
len(set(text))
 
# Egy szöveg összes szavának megszámlálása
len(text.split())
 
# Egy szöveg összes betűjének megszámlálása
sum(char.isalpha() for char in text)
 
# Egy szöveg összes számjegyének megszámlálása
sum(char.isdigit() for char in text)
 
# Egy szöveg összes kisbetűjének megszámlálása
sum(char.islower() for char in text)
 
# Egy szöveg összes nagybetűjének megszámlálása
sum(char.isupper() for char in text)
 
# Egy szöveg összes szóközének megszámlálása
sum(char.isspace() for char in text)
 
# Egy szöveg összes egyedi karakterének megszámlálása
len(set(text))
 
# Egy szöveg összes egyedi szavának megszámlálása
len(set(text.split()))
Chapter 8 Algorithm Analysis TechniquesChapter 10 Intractable Problems and Approximation Algorithms