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

Az ezeknek az objektumoknak a tárolására szolgáló adattípust szintén stringnek nevezik; ez ebben az esetben tetszés szerinti, változó hosszúságú, bináris adatok sorozata. Egy karakterstring általában helyettesíthető a forráskódjával, amelyet gyakran meghatározott elválasztó jelek határolnak – többnyire idézőjelek, általában ' vagy " –, és amely leírható a használatos billentyűzetekkel. Néhány esetben a bináris string kifejezést használják bitek tetszés szerinti hosszúságú sorozatára.

String adattípusok

A string adattípus ideális formális stringet modellez. A stringek a legfontosabb és leggyakrabban használt adattípusok között vannak, 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é tartoznak, más nyelvek az összetett típusok közé sorolják ezeket. 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 megjelenésének tekinti; a metastringre viszont gyakran a 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ú, ez a hossz a megvalósított nyelvekben gyakran mesterségesen maximalizált. Általánosságban a string adattípus két fajtája létezik:

• fix hosszúságú string: függetlenül attól, hogy elemeinek a száma eléri-e a maximumot, mindig ugyanakkora memóriaterületet foglal le a tárolása;
• változó hosszúságú string: csak az aktuális, nem fix hossza szerinti helyet foglalja el a memóriában.

A modern programozási nyelvekben a legtöbb string változó hosszúságú, de ezek hossza is korlátozott: gyakorlatilag a rendelkezésre álló számítógépmemória mértékétől függ.

Történetileg a string adattípus esetében egy byte tartozott egy-egy karakterhez; annak ellenére, hogy a karakterkódtáblák régiónként változtak, a tényleges tartalom gyakorlatilag a programozóktól függött. Később azonos régiók is több kódtáblát használtak, í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 az EBCDIC kódolást használta a nagyszámítógépein.

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 2 byte-os kódokat a CJK szóképek esetén. Ez a megoldás azonban több szempontból is problematikus: nem lehet összehasonlítani és darabolni a stringeket, csak ha pontosan ismert, milyen a tárolás kódja, de ebben az esetben az összehasonlítás, valamint a rendezés is kérdéses a különböző kódolású stringek között. 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 a 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, és 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 az adott string milyen kódolású.

Néhány nyelv, mint például a C++, template-ként használja a stringeket, azaz létezik azokban elemi adattípusuk, de ezek inkább kivételt képeznek, mint szabályt.

Megvalósítása

Egy string megvalósítása erősen függ attól, hogy a megvalósítás környezete milyen karakterkészletet használ, és milyen kódolást támogat. A régebbi stringmegvalósításokat úgy tervezték, hogy azok az ASCII-karakterekre támaszkodtak, míg az újabbak 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 stringmegvaló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 karakterkó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 1–4 byte 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: itt a string hossza – számszerűen – nincsen tárolva, a string végét egyértelműen felismerhető elválasztó/lezáró karakter jelzi. Erre a megvalósításra gyakran hivatkoznak C-stringként. Más esetben a string hosszát is számszerűen tárolják: a string karaktereit általában megelőzi a byte-okban megadott hossza. Ezt a konvenciót használja a Pascal, ezért néhányan P-stringnek nevezik ezt.

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 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-ek a buffer előző, esetünkben nem lényeges tartalmát jelölik, ugyanis az 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”. (Az ebben a formában tárolt stringeket gyakran nevezik ASCIZ-stringeknek, mert a tárolás az assembly programozási nyelv egy direktívája alapján történik így.)

A következő példa a fenti string Pascal-string szerinti tárolása, szintén 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ó az 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 stringműveletek, mint a beszúrás, a törlés és az egyesítés, sokkal hatékonyabbak.

Vektorok

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

Stringalgoritmusok

A stringfeldolgozás területén számtalan formában valósítottak meg algoritmusokat, amelyek a következő csoportokba sorolhatók:

• stringkeresési algoritmusok egy adott string vagy minta megtalálására;
• stringkezelő algoritmusok;
• rendező algoritmusok;
• szabályos kifejezést feldolgozó algoritmusok;
• stringelemző parsingok.

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

Karakterstring-orientált nyelvek és segédprogramok

A karakterstring az egyik leghasznosabb adattípus, amelyet gyakorlatilag minden nyelv használ. Emellett vannak olyanok, amelyeket arra fejlesztettek ki, hogy egyszerű formában leírhatóan kezeljenek stringeket, illetve olyan segédprogramok, 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 stringműveletek végrehajtására, és egyszerű programozás segítségével hatékony stringkezelő eszközt biztosítanak. A segítségükkel fájlok és véges karakterfolyamok stringként ábrázolhatók és kezelhetők.

Több stringkezelő 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 stringkönyvtár
• A Vstr stringkö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ő ábécének. Ennek az elemeit nevezik karaktereknek. Egy string (vagy szó) a Σ felett, annak karaktereiből álló, véges sorozat. A definíció nem engedi meg a végtelen sorozatokat.

Nagyon fontos tulajdonságú string az olyan sorozat, amelyet egy karakter sem alkot. Ezt nevezik üres stringnek vagy empty stringnek. 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 a Σ Kleene-lezárása, amit Σ* jelöl. Az összekapcsolás bináris művelete határozható meg erre. Ha s is, és t is string, akkor az összekapcsolásukat st-vel jelöljük, és meghatározás szerint ez az s karaktereinek sorozata, amit a 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. Vagy u, vagy v lehet üres, és mindkettő is lehet az. A „substringja” reláció részleges rendezést határoz meg Σ*-on, aminek utolsó eleme 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 jól definiált jól rendezettséget jelent a Σ*-on, amelyet lexikografikus rendezésnek neveznek. Meg kell jegyezni, hogy ha Σ véges, akkor mindig lehet találni 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észhalmazát) nevezik Σ feletti formális nyelvnek.

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

Karakterstring-műveletek

Stringmű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 a stringekről. Általában a különböző programozási nyelvek használják a stringműveleteket.

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

Például a length("hello world") 11-et ad eredményül.

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