String

A Wikipédiából, a szabad enciklopédiából

A számítógép-programozásban és a matematika néhány területén a string (ejtsd: sztring) különböző egyszerű objektumok (leggyakrabban karakterek) sorozata. (Szintén helyes a kiejtés szerinti sztring írásmód, és használják még a karakterlánc és karakterfüzér elnevezéseket is.)

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áskó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.

String adattípusok[szerkesztés | forrásszöveg szerkesztése]

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 lényegében 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 összetett 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 fajtája 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 maximumot, mindig ugyanakkora memóriaterületet foglalnak 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 nagyszámítógé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/Japanese/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.

Megvalósítása[szerkesztés | forrásszöveg szerkesztése]

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ámaszkodtak, 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, illetve 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 karakter egy és négy byte közötti helyet foglal 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ó karaktert 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 – nincsen 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 C stringként. Más megvalósítás esetén a string hosszát is számszerűen tárolják, általában byte-okban megadott hossza megelőzi a string karaktereit – ezt a konvenciót használja a Pascal; ezért néhányan ezt P-stringnek nevezik.

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 stringet a fenti formában tárolják.)

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.

Vektorok[szerkesztés | forrásszöveg szerkesztése]

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 adattí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.

String algoritmusok[szerkesztés | forrásszöveg szerkesztése]

Í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övetkező csoportokba sorolhatók:

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.

Karakter string orientált nyelvek és segédprogramok[szerkesztés | forrásszöveg szerkesztése]

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

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ítanak. 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:

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.

Formális elmélet[szerkesztés | forrásszöveg szerkesztése]

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 karakter 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 (konkatenáció) asszociatív, de nem kommutatív művelet. Az üres stringet tekintjük neutrális elemnek, így a stringek halmaza (Σ*)a konkatenáció műveletével egységelemes félcsoportot (monoidot) alkot.

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

Egy s stringre akkor mondhatjuk, 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ösen 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 (például alfabetikus rendezés) akkor az egy jól definiált jól rendezettséget jelent a Σ*-n, amelyet lexikografikus 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 lexikografikus rendezés a {0,1}*-ra: ε, 0, 1, 00, 01, 10, 11, 000, 001, …

A Σ feletti stringek halmazát (például Σ* 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.

Karakter string műveletek[szerkesztés | forrásszöveg szerkesztése]

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ő strukturális információt) és nem változtatja meg a stringet.

Például 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 említett length műveletet len(string) formában használják.