Hogyan Működnek Az Algoritmusok
Chapter 6 Strings

6. fejezet: Karakterláncok az algoritmusokban

A karakterláncok (stringek) alapvető adattípusok a számítástudományban, amelyek karakterek sorozatát reprezentálják. A karakterláncok feldolgozására szolgáló algoritmusok és adatszerkezetek tanulmányozása a számítástudományi tananyag fontos része. Ebben a fejezetben több fontos karakterlánc-feldolgozó algoritmust vizsgálunk meg, beleértve a karakterlánc-rendezé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 számos gyakorlati alkalmazással rendelkeznek, a szövegszerkesztéstől és dokumentum-visszakereséstől kezdve a bioinformatikáig és a természetes nyelvfeldolgozásig.

Karakterlánc-rendezés

A rendezés alapvető művelet a számítástudományban, és a karakterláncok rendezése gyakori feladat számos alkalmazásban. Bár az általános célú rendezési algoritmusok, mint a gyorsrendezés és az egyesítéses rendezés, használhatók karakterláncok rendezésére, vannak hatékonyabb algoritmusok, amelyek kihasználják a karakterláncok speciális tulajdonságait.

Kulcs-indexelt számlálás

A kulcs-indexelt számlálás egy egyszerű és hatékony algoritmus karakterláncok rendezésére, amikor a karakterláncok egy kis halmaz különböző karaktereiből állnak. Az alapötlet az, hogy megszámoljuk az egyes karakterek előfordulásait, majd ezeket a számokat használjuk fel a karakterláncok rendezett sorrendjének meghatározására.

Íme egy példa a kulcs-indexelt számlálás működésére:

Bemenet:  ["dab", "cab", "fad", "bad", "dad", "ebb", "ace"]
Kimenet: ["ace", "bad", "cab", "dab", "dad", "ebb", "fad"]

Az algoritmus a következőképpen működik:

  1. Megszámoljuk az egyes karakterek előfordulásait a karakterláncokban.
  2. Kiszámítjuk az egyes karakterek kezdőindexét a rendezett tömbben.
  3. Átmásoljuk a karakterláncokat a rendezett tömbbe, felhasználva a számolási eredményeket a pozíciók meghatározásához.

A kulcs-indexelt számlálás O(n + R) időben fut, ahol n a karakterláncokban lévő összes karakter száma, R pedig az ábécé mérete (a különböző karakterek száma). Ez nagyon hatékony algoritmus olyan karakterláncok rendezésére, amelyek kis ábécéből állnak.

LSD radix rendezés

A legkisebb értékű számjegy szerinti (LSD) radix rendezés a kulcs-indexelt számlálás egy kiterjesztése.Itt a magyar fordítás:

Olyan számlálás, amely egyenlő hosszúságú karakterláncokat tud rendezni nagy ábécé felett. Az alapötlet az, hogy a karakterláncokat karakterenként rendezzük, kezdve az utolsó karaktertől és haladva az első felé.

Itt egy példa az LSD radix rendezésre:

Bemenet:  ["4PGC938", "2IYE230", "3CIO720", "1ICK750", "1OHV845", "4JZY524", "1ICK750", "3CIO720", "1OHV845", "1OHV845", "2RLA629", "2RLA629", "3ATW723"]
Kimenet: ["1ICK750", "1ICK750", "1OHV845", "1OHV845", "1OHV845", "2IYE230", "2RLA629", "2RLA629", "3ATW723", "3CIO720", "3CIO720", "4JZY524", "4PGC938"]

Az algoritmus a következőképpen működik:

  1. Rendezd a karakterláncokat az utolsó karakter alapján kulcs-indexelt számlálással.
  2. Ismételd meg az 1. lépést minden karakterre, haladva az első felé.

Az LSD radix rendezés O(w * n) időben fut, ahol w a karakterláncok hossza és n a karakterláncok száma. Ez hatékony választás fix hosszúságú karakterláncok rendezésére.

MSD Radix Rendezés

A legjelentősebb számjegy szerint először (MSD) radix rendezés a radix rendezés rekurzív változata, amely különböző hosszúságú karakterláncokat is kezelni tud. Hasonlóan a gyorsrendezéshez, az MSD radix rendezés részhalmazokra bontja a tömböt, amelyek függetlenül rendezhetők.

Itt egy példa az MSD radix rendezésre:

Bemenet:  ["she", "sells", "seashells", "by", "the", "sea", "shore", "the", "shells", "she", "sells", "are", "surely", "seashells"]
Kimenet: ["are", "by", "sea", "seashells", "seashells", "sells", "sells", "she", "she", "shells", "shore", "surely", "the", "the"]

Az algoritmus a következőképpen működik:

  1. Oszd fel a tömböt részhalmazokra az első karakter alapján.
  2. Rekurzívan rendezd az egyes részhalmazokat.

Az MSD radix rendezés legrosszabb esetben O(n * w) futási idővel rendelkezik, de a gyakorlatban gyakran gyorsabb, mint az LSD radix rendezés, ha a karakterláncok hossza változó.

Trie-k

A trie (ejtsd: "tráj") egy fa-szerű adatszerkezet karakterláncok tárolására, amely lehetővé teszi a hatékony előtag-illesztést és karakterlánc-keresést. Minden csomópont egy karaktert reprezentál, és a gyökértől a csomópontig vezető út egy előtagot jelent aItt van a markdown fájl magyar fordítása. A kódban lévő kommentárokat fordítottam le, a kódot nem.

A következő példa egy trie-t mutat, amely a "sea", "sells", "she", "shells" és "shore" szavakat tárolja:

     (gyökér)
    /  |  \
   s   h   o
  / \     / \
 e   h   r   t
 |   |   |   |
 a   e   e   h
     |       |
     l       e
     |       |
     l       r
     |
     s

A trie-k a következő műveleteket támogatják:

  • Egy szó beszúrása a trie-ba.
  • Egy szó keresése a trie-ban.
  • Egy szó törlése a trie-ból.
  • Minden olyan szó megtalálása, amely egy adott előtaggal kezdődik.

Ezen műveletek időbonyolultsága O(w), ahol w a beszúrandó, keresendő vagy törlendő szó hossza. Ez nagyon hatékony adatszerkezetet tesz a szöveggel kapcsolatos feladatokhoz.

Részszöveg keresés

A részszöveg keresés annak a problémája, hogy egy adott mintaszöveget megtaláljunk egy nagyobb szövegben. Ez egy alapvető probléma a szövegfeldolgozásban, és alkalmazásai vannak a szövegszerkesztésben, a bioinformatikában és sok más területen.

Brute-Force keresés

A részszöveg keresés legegyszerűbb megközelítése a brute-force algoritmus, amely minden lehetséges pozíciót ellenőriz a szövegben, hogy megtalálja-e a mintát.

Itt egy példa a brute-force keresésre:

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

A brute-force algoritmus legrosszabb esetben O(n * m) futási idővel rendelkezik, ahol n a szöveg hossza és m a minta hossza. Bár egyszerű megvalósítani, ez lehet hatékontalan nagy szövegek és minták esetén.

Knuth-Morris-Pratt algoritmus

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

A hiba függvény megmondja nekünk a minta leghosszabb valódi előtagjának a hosszát, amely egyben a minta eddig egyező 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.

Itt egy példa a KMP algoritmuson:

Szöveg:   "abacadabrabr
```Itt a magyar fordítás a megadott markdown fájlhoz. A kódhoz tartozó kommenteket fordítottam le, a kódot nem.

"acabracadabrabrabracad"
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 részkereső algoritmus, amely a minta előfeldolgozásán alapul. Ellentétben a KMP-vel, amely az elején kezdi az összehasonlítást, a Boyer-Moore a végétől indul és visszafelé halad.

A Boyer-Moore algoritmus kulcsötlete két előre kiszámított függvény használata: a "jó utótag" függvény és a "rossz karakter" függvény. Ezek a függvények lehetővé teszik, hogy átugorjunk a szövegben, amikor eltérést találunk, hasonlóan a KMP-hez.

Itt egy példa a Boyer-Moore algoritmuson:

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), de a gyakorlatban gyakran a leggyorsabb részkereső algoritmus nagy ábécék esetén.

Reguláris kifejezések

A reguláris kifejezések egy hatékony eszköz 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ára.

A 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" szöveget illeszti. Azonban a reguláris kifejezések speciális karaktereket és konstrukciókat is tartalmaznak, amelyek lehetővé teszik a komplexebb minták leírását:

  • . (pont) bármely egyetlen karaktert illeszti.
  • * (csillag) a megelőző karakter vagy csoport nulla vagy több előfordulását illeszti.
  • + (plusz) a megelőző karakter vagy csoport egy vagy több előfordulását illeszti.
  • ? (kérdőjel) a megelőző karakter vagy csoport nulla vagy egy előfordulását illeszti.
  • ^ (kalap) a sor elejét illeszti.
  • $ (dollár) a sor végét illeszti.
  • [] (szögletes zárójelek) egy karakterosztályt határoznak meg, amely a benne szereplő bármely egyetlen karaktert illeszti.

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

- `a.b` illeszkedik bármely olyan három karakteres sztringre, 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 sztringre, amely nulla vagy több "a" karakterből áll, majd egy "b" karakter következik, például "b", "ab", "aab" vagy "aaab".
- `a+b` illeszkedik bármely olyan sztringre, amely egy vagy több "a" karakterből áll, majd egy "b" karakter következik, például "ab", "aab" vagy "aaab", de nem "b".
- `a?b` illeszkedik vagy "ab"-re, vagy "b"-re.
- `^a` illeszkedik bármely olyan sztringre, amely "a"-val kezdődik.
- `a$` illeszkedik bármely olyan sztringre, amely "a"-val végződik.
- `[aeiou]` illeszkedik bármely egyes magánhangzó karakterre.

A reguláris kifejezéseket sok programozási nyelv és eszköz támogatja, beleértve a Java-t, a Python-t és a Unix segédprogramokat, mint a grep és a sed. Széles körben használják 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 adatokat tökéletesen rekonstruálni lehessen 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 szimbólum-előfordulással és a szimbólum ismétlődésének 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 valójában növelheti 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 azok gyakorisága alapján.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 adatban található szimbólumok gyakoriságának kódolása. A gyakoribb szimbólumokhoz rövidebb kódokat, a ritkább szimbólumokhoz hosszabb kódokat rendelünk.

A algoritmus egy bináris fát, úgynevezett Huffman-fát épít fel alulról felfelé. Minden levélcsomópont egy szimbólumot és annak gyakoriságát jelöli, míg minden belső csomópont a gyermekei gyakoriságának összegét. A fát úgy építjük fel, hogy ismételten összevonjuk 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 a gyökértől a megfelelő levélcsomópontig vezető út alapján határozható meg, ahol a bal ág "0"-t, a jobb ág "1"-et jelent.

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 "111". A tömörített kimenet úgy kapható meg, hogy minden szimbólumot a megfelelő kódjával helyettesítünk.

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

### LZW-tömörítés

A Lempel-Ziv-Welch (LZW) tömörítés egy szótár alapú 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 benne található karakterláncokból. Az LZW-t széles körben használják fájltömörítő eszközökben, és a GIF-képformátumban is alkalmazták.

Az LZW lényege, hogy a karakterláncokat egyetlen kóddal helyettesíti. Karakter-karakter alapján olvassa be a bemenetet, és a karakterláncokat tömör reprezentációjukkal kódolja. Minél hosszabb a karakterlánc, annál több hely takarítható meg a kódolással.

Itt egyItt a magyar fordítás a megadott markdown fájlhoz. A kódhoz tartozó megjegyzéseket fordítottam le, a kódot nem.

1. Inicializáld a szótárat, hogy az összes egyetlen karakterből álló karakterláncot tartalmazza.
2. Találd meg a szótárban a leghosszabb W karakterláncot, amely megegyezik a jelenlegi bemeneti adattal.
3. Írd ki a W karakterlánc szótári indexét a kimenetbe, és távolítsd el a W-t a bemeneti adatból.
4. Adj hozzá a szótárhoz egy új karakterláncot, amely a W-ből és a következő szimbólumból áll.
5. Menj vissza a 2. lépéshez.

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

1. Inicializáld a szótárat, hogy az "A" és "B" karakterláncokat tartalmazza.
2. A leghosszabb egyező karakterlánc az "A". Írd ki az indexét (0) és távolítsd el a bemeneti adatból. A szótár most az "A", "B" és "AB" karakterláncokat tartalmazza.
3. A leghosszabb egyező karakterlánc a "B". Írd ki az indexét (1) és távolítsd el a bemeneti adatból. A szótár most az "A", "B", "AB" és "BA" karakterláncokat tartalmazza.
4. A leghosszabb egyező karakterlánc az "AB". Írd ki az indexét (2) és távolítsd el a bemeneti adatból. A szótár most az "A", "B", "AB", "BA" és "ABA" karakterláncokat tartalmazza.
5. A leghosszabb egyező karakterlánc az "ABA". Írd ki az indexét (4) és távolítsd el a bemeneti adatból. A szótár most az "A", "B", "AB", "BA", "ABA" és "ABAB" karakterláncokat tartalmazza.
6. A leghosszabb egyező karakterlánc a "BA". Írd ki az indexét (3). A bemeneti adat most üres.

Az "ABABABABA" tömörített reprezentációja tehát az [1] indexek sorozata, amely kevesebb bitet igényel, mint az eredeti ASCII reprezentáció.

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

1. Inicializáld a szótárat, hogy az összes egyetlen karakterből álló karakterláncot tartalmazza.
2. Olvass be egy X kódot a bemenetről.
3. Írd ki az X kódhoz tartozó karakterláncot a szótárból.
4. Ha az előző kód létezik, add hozzá a szótárhoz az előző karakterlánc és az X kódhoz tartozó karakterlánc első karakterének összefűzését.
5. Menj vissza a 2. lépéshez.

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 sok memóriát fogyaszt. 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 kis fájlok esetén.

Ezek a korlátozások ellenére az LZW tömörítés hasznos eszköz lehet sok alkalmazásban.Itt a magyar fordítás a megadott markdown fájlhoz. A kódhoz tartozó megjegyzéseket fordítottam le, a kódot nem.

## Következtetés

Ebben a fejezetben több fontos szövegfeldolgozó 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 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.

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 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. Megvizsgáltuk a reguláris kifejezések alapvető szintaxisát, és 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 az adattömörítési algoritmusokat tanulmányoztuk, 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ó algoritmusok és adatszerkezetek megértése kulcsfontosságú minden olyan személy számára, aki szöveges adatokkal dolgozik. Ahogy a strukturálatlan adatok mennyisége folyamatosan növekszik, a szöveges adatok hatékony manipulálásának, kereséséneHere is the Hungarian translation of the provided text, with the code comments translated:

A nyomtatott szövegek egyre értékesebbek lesznek. Ennek a fejezetnek a technikáinak elsajátításával jól fel lesz készülve, hogy széles körű szövegfeldolgozási kihívásokkal birkózzon meg saját projektjeiben és alkalmazásaiban.

```python
# Egy szöveg hosszának meghatározása
length = len("Hello, World!")
print(length)  # Kimenet: 13

# Egy karakter elérése a szövegben
char = "Hello, World!"[7]
print(char)  # Kimenet: W

# Részszöveg kivágása
substring = "Hello, World!"[7:12]
print(substring)  # Kimenet: World

# Szöveg összefűzése
greeting = "Hello" + ", " + "World!"
print(greeting)  # Kimenet: Hello, World!

# Szöveg ismétlése
repeated_text = "Ha" * 3
print(repeated_text)  # Kimenet: HaHaHa

# Szöveg formázása
formatted_text = "The answer is: {}"
print(formatted_text.format(42))  # Kimenet: The answer is: 42

# Szöveg átalakítása kisbetűssé/nagybetűssé
uppercase_text = "hello, world!".upper()
lowercase_text = "HELLO, WORLD!".lower()
print(uppercase_text)  # Kimenet: HELLO, WORLD!
print(lowercase_text)  # Kimenet: hello, world!

# Szöveg elválasztása
text = "apple,banana,cherry"
fruits = text.split(",")
print(fruits)  # Kimenet: ['apple', 'banana', 'cherry']

# Szöveg cseréje
replaced_text = text.replace("banana", "orange")
print(replaced_text)  # Kimenet: apple,orange,cherry