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:
- Megszámoljuk az egyes karakterek előfordulásait a karakterláncokban.
- Kiszámítjuk az egyes karakterek kezdőindexét a rendezett tömbben.
- Á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:
- Rendezd a karakterláncokat az utolsó karakter alapján kulcs-indexelt számlálással.
- 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:
- Oszd fel a tömböt részhalmazokra az első karakter alapján.
- 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