String

A Wikipédiából, a szabad lexikonból.

A számítógép-programozásban és a matematika néhány területén a string különböző egyszerű objektumok sorozata. Ezeket az egyszerű objektumokat egy előre meghatározott halmazból lehet kiválasztani. Leggyakrabban ezek az egyszerű objektumok nyomtatható karakterek és vezérlő karakterek. Azt az adattípust, amelyben ezek az objektumok tárolva vannak, szintén stringnek nevezik, ami tetszés szerinti, változó hosszúságú, bináris adatok sorozata. Általában, egy karakter string helyettesíthető a forrás kódjával, amelyet gyakran meghatározott elválasztó jelek határolnak, amelyek többnyire idézőjelek — általában ' vagy ", és leírhatók a használatos billentyűzetekkel. Néhány esetben a bináris string kifejezést használják bitek egy tetszés szerinti hosszúságú sorozatára.

Használatos még a karakter fűzér elnevezés is.

Tartalomjegyzék 1 String adattípusok 1.1 Megvalósítása 2 Vektorok 3 String algoritmusok 4 Karakter string orientált nyelvek és segédprogramok 5 Formális elmélet 6 Karakter string műveletek

[szerkesztés] String adattípusok

Egy string adattípus egy olyan adattípus, amely egy ideális formális stringet modellez. A stringek az egyik legfontosabb és leggyakrabban használt adattípusok, ezért gyakorlatilag minden programozási nyelvben létezik valamilyen megvalósításuk. Néhány nyelvben az elemi típusok közé tartozik, más nyelvek az öszetett típusok közé sorolják. A legtöbb magas-szintű programozási nyelv szintaxisa megengedi a string használatát, általában valamilyen idézőjeles formában, és a string adattípus egy bizonyos megjelenéseként tekintik; a meta-stringre viszont gyakran literál vagy string literál kifejezésekkel hivatkoznak.

Annak ellenére, hogy a formális string tetszés szerinti (de véges) hosszúságú, a megvalósított nyelvekben ez a hossz gyakran mesterségesen maximalizált. Általánosságban, két adatípusa létezik a string adattípusnak:

• fix hosszúságú stringek, amikor a függetlenül attól, hogy a string elemeinek száma eléri-e a maximumumot, mindig ugyanakkora memória területet foglanak le a tárolásához,
• változó hosszúságú stringek, ahol a string hossza nem fix, és csak az aktuális hossza szerinti helyet foglal el memóriában.

A modern programozási nyelvekben a legtöbb string változó hosszúságú. Ellentétben a nevével, még a változó hosszúságú string hossza is korlátozott, gyakorlatilag a rendelkezésre álló számítógép memória mennyisége a korlát.

Történetileg, a string adattípus esetében egy byte tartozott egy-egy karakterhez, annak ellenére, hogy a különböző karakter kódtáblák régiónként változtak, a tényleges tartalom gyakorlatilag a programozóktól függött. Később több kódtáblát használtak azonos régiók, így a programozók egyre gyakrabban szegték meg az egy karakter-egy byte szabályt. Ezek a kódtáblák többnyire az ASCII kódtábla alapján készültek, azonban az IBM a nagygépein az EBCDIC kódolást használta.

A logografikus nyelvek esetében, mint például a kínai, a japán és a koreai (együttesen CJK - Chinese/Japonese/Korean néven ismertek) szükségessé vált a 256-nál nagyobb, azaz több, mint 1 byte-os kódok használata. A megoldást az jelentette, hogy a megvalósítás során 1 byte-os kódokat használtak az ASCII karakterek esetén, és két byte-os kódokat a CJK szóképek esetén. Ez a megoldás azonban több szempontból is problematikus: nem lehet a stringeket összehasonlítani és darabolni, csak ha pontosan ismert, milyen a tárolás kódja, de ebben az esetben is kérdéses az összehasonlítás a különböző kódolású stringek között, valamint a rendezés. Néhány más kódolási forma, mint például az EUC család biztosítja, hogy az ASCII tartományban csak megfelelően kódolt 1 byte-os értékek legyenek, és megszokásnak megfelelően használhatók mint mezőelválasztók. Más megoldások, mint az ISO-2022 és a shift-jis nem biztosítják ezeket a feltételeket, a karakterek összehasonlítása bizonytalan.

A Unicode csak tovább bonyolítja a helyzetet. A legtöbb nyelvben létezik adattípus Unicode stringekre (általában az UTF-16, amit a Unicode előtt használtak). A Unicode és a lokális kódolás közötti konverzióhoz alapvetően szükséges a helyi kódolás alapos ismerete, de így is gondot okozhat, ha különféle módon kódolt stringeket adatátviteli vonalon keresztül továbbítanak, olyan jelzés nélkül, hogy milyen kódolású az adott string.

Néhány nyelv, mint például a C++ a stringeket mint "template" használja, azaz létezik egy elemi adattípusa, de ez inkább kivétel, mint szabály.

[szerkesztés] Megvalósítása

Egy string megvalósítása erősen függ attól, hogy milyen karakter készletet használ és milyen kódolást támogat a megvalósítás környezete. A régebbi string megvalósításokat úgy tervezték, hogy azok az ASCII karakterekre támszkodtak, míg az újabb megvalósítások már az ISO 8859 sorozat bővítéseit is figyelembe veszik. A mai, modern megvalósítások gyakran támaszkodnak a Unicode-ra, iletve az UTF-8 és UTF-16 változatokra.

A legtöbb string megvalósítás nagyon hasonlít egy változó hosszúságú tömb megvalósításához, ahol az elemek tárolása karakter kódok segítségével történik. A fő különbség az, hogy a string esetében logikailag csak bizonyos kódolású karakterek tárolása megengedett. Tulajdonképen ez történik, ha UTF-8 kódolást használnak, ekkor egy katrakter egy és négy byte közötti helyet fogalal el. Ebben az esetben például a string hossza különbözik a tömb hosszától.

A string hossza tárolható úgy, hogy implicit módon egy speciális záró karatert használnak; ez a karakter általában a null karakter amelynek értéke nulla, ezt a konvenciót használja a népszerű C programozási nyelv. Ekkor a string hossza - számszerűen - nincen tárolva, a string végét egy egyértelműen felismerhető elválasztó/lezáró karakter jelzi. Ezért, a fenti megvalósításra gyakran hivatkoznak úgy, mint C string. Más megvalósítás eseténe a string hossza is valóban, számszerűen is tárolásra kerül, általában a byteokban megadott hossza megelőzi a string karaktereit — ezt a konvenciót használja a Pascal; ezért néhány ember ezt P-stringnek nevezi.

A karakterrel lezárt stringek esetében szabály, hogy a lezáró karakter nem lehet olyan karakter, amely előfordulhat a stringben.

Egy példa mutatja, hogy hogyan történik egy null-terminated string vagy nullával lezárt string tárolása egy 10 byte-os pufferben, ASCII kódolás használata mellett:

F	R	A	N	K	NUL	x	x	x	x
46	52	41	4E	4B	00	x	x	x	x

A "x" a buffer előző, esetünkben nem lényeges tartalmát jelöli, u.i. a puffer tartalma csak a szükséges mértékben módosul.

A fenti példában a string hossza 5 karakter, de 6 byte-ot foglal el. A lezáró karaktert követő karakterek már nem tartoznak a stringhez, azok - esetleg - egy előzőleg tárolt string maradékai, gyakorlatilag "szemetek". (Ebben a formában tárolt stringeket gyakran nevezik ASCIZ stringeknek, az assembly programozási nyelv egy direktívája alapján, amely hatására a megadott string a fenti formában kerül tárolásra.)

A következő példa a fenti string Pascal string szerinti tárolása, szintén egy 10 byte-os pufferben, ASCII kódolás mellett:

length	F	R	A	N	K	k	f	f	w
05	46	52	41	4E	4B	6B	66	66	77

Az ábrán most ASCII kódban látható ez előző tartalom is.

Míg a fenti két konvenció a legelterjedtebb, vannak egyéb lehetőségek is. A rope használatával bizonyos string műveletek, mint a beszúrás, a törlés és az egyesítés sokkal hatékonyabb.

[szerkesztés] Vektorok

Míg a karakter string a legelterjedtebb használata a stringnek, általános esetben egy string a számítástechnikában vonatkozhat bármilyen homogén adatípusú adatokból alkotott vektorra is. Egy bitekből vagy byte-okból álló string, például reprezentálhat egy kommunikációs eszközből származó adatot is. Ezt az adatot vagy lehet vagy nem lehet string-specifikus adat típusnak tekinteni, attól függően, hogy mi az alkalmazás igénye, mi a programozó óhaja, és milyen képességekkel rendelkezik a használt programnyelv.

[szerkesztés] String algoritmusok

Íme néhány algoritmus a string feldolgozás területéről, amelyek számtalan formában valósítottak meg. Az algoritmusok a követekező csoportokba sorolhatók:

• string keresési algoritmusok egy adott string vagy minta megtalálására;
• string kezelő algoritmusok;
• rendező algoritmusok;
• szabályos kifejezés feldolgozó algoritmusok; ésnd
• egy string elemzése, egy parsing segítségével.

A fejlettebb string kezelő algoritmusok gyakran komplex mechanizmusokat és adatstruktúrákat használnak, például a követő fák és a véges állapotú gépek.

[szerkesztés] Karakter string orientált nyelvek és segédprogramok

A karakter string az egyik leghasznosabb adatípus, amelyt gyakorlatilag minden nyelv használ, de vannak olyanok, amelyek arra fejlesztettek ki, hogy egyszerű formában leírhatóan stringeket kezeljenek, illetve olyan segédprogramokat alkottak, amelyek megkönyítik a karakterekből álló stringek kezelését. Néhány ezek közül:

• awk
• Icon
• Perl
• Ruby
• Tcl
• MUMPS
• Rexx
• sed
• SNOBOL

Több UNIX segédprogram képes egyszerűbb string műveletek végrehajtására, és egyszerű programozás segítségével hatékony stringkezelő eszközt biztosítnak. Segítségükkel fájlok és véges karakter folyamok stringként ábrázolhatók és kezelhetők.

Több string kezelő könyvtárt dolgoztak ki a C és C++ programozási nyelvek számára, de egyéb hatékony könyvtárak is használhatók a következők közül:

• A jobb string könyvtár
• A Vstr string könyvtár
• Perl kompatibilis szabályok kifejezések

Néhány API, mint a Multimedia Control Interface, az embedded SQL vagy a printf string formában kapják azokat a parancsokat, amelyeket értelmezniük kell.

A régebbi script programozási nyelvek, ideértve a Perl, a Python, a Ruby, és a Tcl szabályos kifejezéseket használ a megvalósított szöveges műveletekhez.

[szerkesztés] Formális elmélet

Egy Σ nem üres, véges halmaz tekinthető egy ábécének. Ennak az ábécének ez elemeit nevezik karaktereknek. Egy string (vagy szó) a Σ felett a Σ karaktereiből álló, véges sorozat. A definíció a végtelen sorozatokat nem engedi meg.

Egy nagyon fontos tulajdonságú string az olyan sorozat, amelyet nem alkot egy karater sem, ezt nevezik üres stringnek vagy empty string-nek. Az üres stringet gyakran jelöli ε vagy λ.

Például, ha Σ = {0, 1}, akkor a Σ feletti stringek a következő formájúak lehetnek :ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, …

A Σ felett lévő összes string halmaza, azaz Σ Kleene lezárása, amit Σ* jelöl. Meghatározható egy bináris művelet Σ*-ra, ez az összekapcsolás. Ha s és t két string, akkor összekapcsolásukat st-val jelöljük, és meghatározás szerint s karaktereinek sorozata, amit t karaktereinek sorozata követ.

Például, ha s = bear és t = hug akkor st = bearhug és ts = hugbear.

A string összekapcsolás asszociatív, de nem kommutatív művelet. Az üres stringet tekintjük neutrális elemnek. Algebrai kifejezéssel, a Σ* halmaz egy monoid a string összekapcsolás műveletre.

A string hossza a stringben lévő karakterek száma. Ez a hossz mármilyen természetes szám lehet. Az üres string hossza 0.

Egy s stringre akkor mondhajuk, hogy t string substringja vagy factora, ha létezik két string, u és v amelyekre igaz, hogy t = usv. u és v közül egyik vagy másik, vagy mindkettő lehet üres. A "substringje lenni" reláció meghatároz egy részleges rendezést Σ*-on, az utolsó elem az üres string.

Nagyon gyakran, különösden a számítógépes alkalmazásoknál felmerül a stringek illetve a stringek halmazainak különböző rendezése. Ha a Σ ábécé jól rendezett (pl. afabetikus rendezés) akkor az egy jól definált jól rendezettséget jelent a Σ*-n, amelyet lexografikus rendezésnek neveznek. Meg kell jegyezni, ha Σ véges, akkor mindig lehet találni egy jól rendezettséget Σ-ra és Σ*-ra. Például, a lexografikus rendezés a {0,1}*-ra: ε, 0, 1, 00, 01, 10, 11, 000, 001, ...

A Σ feletti stringek halmazát (pl. Σ* egy részhalmaza) nevezik egy Σ feletti formális nyelvnek.

Amíg az ábécé egy véges halmaz, és minden string véges hosszúságú, egy nyelv jól meghatározható több hozzá tartozó stringgel. Viszont, Σ* önmagában mindig egy végtelen nyelv. Fontos részei a formális nyelveknek a szabályos kifejezések és a formális nyelvtanok.

[szerkesztés] Karakter string műveletek

String műveleteket használnak a stringek kezeléséhez vagy a stringek tartalmának megváltoztatásához. Egyes műveletek információkat szolgáltatnak stringekről. Általában a string műveleteket a különböző programozási nyelvek használják.

A legalapvetőbb művelet a length(string). Ez a művelet eredményül a string hosszát adja, (nem értve bele a null záró elemet, és semmilyen belső struktúrális információt) és nem változtatja meg a stringet.

Pl. length("hello world") 11-et ad eredményül.

Több olyan string művelet van, amelyek több nyelvben is azonos, vagy nagyon hasonló paraméter szintaxissal rendelkeznek. Sok nyelvben az előzőekben elmlített length műveletet len(string) formában használják.