String

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

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

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éppen 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, miképp 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

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 attól függően lehet string-specifikus adat típusnak tekinteni, hogy mi az alkalmazás igénye, mi a programozó szándéka, és milyen képességekkel rendelkezik a használt programnyelv.

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övetkező 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
• 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.

Karakter string orientált nyelvek és segédprogramok

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:

• 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í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:

• 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.

Formális elmélet

Egy Σ nem üres, véges halmaz tekinthető egy ábécének. Ennek 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

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.