Typ řetězce
V informatice je typ řetězce ( anglicky string "thread, string") datový typ, jehož hodnoty jsou libovolná sekvence (řetězec) znaků abecedy . Každá proměnná tohoto typu ( string variable ) může být reprezentována pevným počtem bajtů nebo může mít libovolnou délku.
Reprezentace paměti
Některé programovací jazyky ukládají omezení na maximální délku řetězce, ale většina jazyků taková omezení nemá. Při použití Unicode může každý znak typu řetězec vyžadovat dva nebo dokonce čtyři bajty, aby jej reprezentoval.
Hlavní problémy ve strojové reprezentaci typu string jsou:
- řetězce mohou mít poměrně významnou velikost (až několik desítek megabajtů);
- velikost, která se v průběhu času mění – dochází k potížím s přidáváním a odebíráním znaků.
Existují dva zásadně odlišné přístupy k reprezentaci řetězců v paměti počítače.
Reprezentace pole znaků
V tomto přístupu jsou řetězce reprezentovány polem znaků ; velikost pole je uložena v samostatné (obslužné) oblasti. Podle názvu jazyka Pascal , kde byla tato metoda poprvé implementována, se tato metoda nazývá Pascal strings .
Mírně optimalizovanou verzí této metody je tzv. c-addr u formát (z anglické adresy zarovnané se znaky + číslo bez znaménka ) používaný ve Forth . Na rozdíl od Pascalových řetězců zde není velikost pole uložena společně s řetězcovými daty, ale je součástí ukazatele na řetězec.
Výhody
- program v každém okamžiku obsahuje informace o velikosti řetězce, takže operace přidání znaků na konec, zkopírování řetězce a vlastně získání velikosti řetězce se provádějí poměrně rychle;
- řetězec může obsahovat libovolná data;
- je možné na úrovni programu sledovat výjezd z hranic linky při jejím zpracování;
- je možné rychle provést operaci jako „převzít N-tý znak z konce řetězce“.
Nevýhody
- problémy s ukládáním a zpracováním znaků libovolné délky;
- zvýšení nákladů na ukládání řetězců - hodnota "délka řetězce" také zabírá místo a v případě velkého počtu řetězců malé velikosti může výrazně zvýšit požadavky algoritmu na RAM;
- maximální limit velikosti řádku. V moderních programovacích jazycích je toto omezení spíše teoretické, protože typicky je velikost řetězce uložena v 32bitovém poli, což dává maximální velikost řetězce 4 294 967 295 bajtů (4 gigabajty);
- při použití abecedy s proměnnou velikostí znaků (například UTF-8 ), velikost neukládá počet znaků, ale velikost řetězce v bajtech, takže počet znaků se musí počítat samostatně.
Metoda ukončování bajtů
Druhou metodou je použití "koncového bytu" [1] [2] . Jedna z možných hodnot znaků abecedy (obvykle znak s kódem 0) je vybrána jako terminátor řetězce a řetězec je uložen jako sekvence bajtů od začátku do konce. Existují systémy, ve kterých se jako znak konce řádku používá bajt 0xFF (255) nebo znakový kód „$“, nikoli znak 0.
Metoda má tři názvy - ASCIIZ (neboli asciz, znaky ASCII s ukončovacím bytem null), C-řetězce (metoda je nejrozšířenější v jazyce C ) a metoda null-terminated string method .
Výhody
- absence dalších servisních informací o lince (kromě posledního bajtu);
- schopnost reprezentovat řetězec bez vytváření samostatného datového typu;
- bez omezení maximální velikosti řádku;
- ekonomické využití paměti;
- snadnost získání přípony řetězce;
- snadnost předávání řetězců funkcím (předává se ukazatel na první znak);
Nevýhody
- dlouhé provádění operací pro získání délky a zřetězení řetězců;
- nedostatek prostředků pro řízení výstupu linky, v případě poškození konečného bajtu možnost poškození velkých oblastí paměti, což může vést k nepředvídatelným následkům – ztrátě dat, pádu programu a dokonce i celého systému;
- nemožnost použít ukončovací bajtový znak jako řetězec.
- nemožnost použít některá kódování s velikostí znaků několik bajtů (například UTF-16), protože v mnoha takových znacích, například Ā (0x0100), je jeden z bajtů nula (současně UTF- 8 kódování je bez této nevýhody).
Použití obou metod
V jazycích, jako je například Oberon , je řetězec umístěn v poli znaků určité délky a jeho konec je označen znakem null. Ve výchozím nastavení je celé pole vyplněno znaky null. Tato metoda umožňuje kombinovat mnoho výhod obou přístupů a zároveň se vyhnout většině jejich nevýhod.
Zobrazit seznam
Jazyky Erlang [3] , Haskell [4] , Prolog [5] používají seznam znaků pro typ řetězce . Tato metoda činí jazyk "teoreticky elegantnějším" tím, že respektuje ortogonalitu v typovém systému , ale přináší významnou výkonnostní penalizaci.
Implementace v programovacích jazycích
- První programovací jazyky vůbec neměly typ řetězce; programátor musel sestavit funkce pro práci s řetězci toho či onoho typu.
- C používá řetězce zakončené nulou s plně ručním ovládáním programátorem.
- Ve standardním Pascalu vypadá řetězec jako pole o 256 bajtech; první bajt uložil délku řetězce, zbytek uložil jeho tělo. Délka řetězce tedy nemůže přesáhnout 255 znaků. Borland Pascal 7.0 také představil "a la C " linky, zřejmě kvůli tomu, že mezi podporované platformy byl zařazen Windows .
- V Object Pascal a C++ STL je řetězec "černá skříňka", ve které dochází k alokaci/dealokaci paměti automaticky - bez účasti programátora . Když je vytvořen řetězec, paměť je alokována automaticky; jakmile nezůstane žádný odkaz na řetězec, paměť se vrátí do systému. Výhodou této metody je, že programátor nemusí přemýšlet o tom, jak řetězce fungují. Na druhou stranu má programátor nedostatečnou kontrolu nad provozem programu v oblastech kritických pro rychlost; je také obtížné předat takové řetězce jako parametr do knihovny DLL . Object Pascal také automaticky zajistí, že na konci řetězce je znak s kódem 0. Pokud tedy funkce vyžaduje jako vstup řetězec zakončený nulou , stačí napsat nebo (pro Pascal), (pro Builder /STL) převést.PAnsiChar(строковая_переменная)PWideChar(строковая_переменная)переменная.c_str()
- V C# a dalších jazycích pro sběr odpadu je řetězec neměnným objektem; pokud je třeba řetězec upravit, vytvoří se další objekt. Tato metoda je pomalá a plýtvá velkým množstvím dočasné paměti, ale dobře se hodí ke konceptu shromažďování odpadu. Výhodou této metody je, že přiřazení je rychlé a bez duplicitních řádků. Existuje také určitá ruční kontrola nad konstrukcí řetězců (v Javě například prostřednictvím tříd StringBuffer и StringBuilder) - to vám umožní snížit počet alokací paměti a vydání a odpovídajícím způsobem zvýšit rychlost.
- V některých jazycích (například Standard ML ) navíc existuje další modul, který poskytuje ještě větší efektivitu - „podřetězec“ (SubString). Jeho použití umožňuje provádět operace s řetězci bez kopírování jejich těl manipulací s indexy začátku a konce podřetězce; k fyzickému kopírování dochází pouze tehdy, když je nutné převést podřetězce na řetězce.
Operace
Základní operace s řetězci
- získání znaku podle čísla pozice (indexu) - ve většině jazyků je to triviální operace;
- zřetězení (spojení) řetězců.
Derivační operace
Operace při zacházení s řetězci jako se
seznamy
- konvoluce ;
- mapování z jednoho seznamu do druhého;
- filtrování seznamu podle kritérií.
Složitější operace
- nalezení minimálního superřetězce obsahujícího všechny zadané řetězce;
- hledejte ve dvou polích řetězců odpovídající sekvence ( problém plagiátorství ) .
Možné úlohy pro řetězce
přirozeného jazyka
- porovnání blízkosti zadaných řetězců podle daného kritéria;
- určení jazyka a kódování textu na základě pravděpodobnosti znaků a slabik.
Znaková reprezentace řetězce
Donedávna se vždy jeden znak kódoval jako jeden bajt (8 binárních bitů; používalo se i kódování se 7 bity na znak), což umožňovalo reprezentovat 256 (128 se sedmibitovým kódováním) možných hodnot. Pro plné znázornění znaků abeced několika jazyků(vícejazyčné dokumenty, typografické znaky - několik typů uvozovek , pomlčky , několik typů mezer a pro psaní textů v hieroglyfických jazycích - čínština , japonština a korejština ) 256 znaků je málo. Existuje několik způsobů, jak tento problém vyřešit:
- Přepínání jazyků pomocí řídicích kódů. Metoda není standardizovaná a zbavuje text nezávislosti (to znamená, že sekvence znaků bez řídicího kódu na začátku ztrácí smysl); použitý v některých časných Russifications ZX-Spectrum a BK .
- Použití dvou nebo více bajtů k reprezentaci každého znaku ( UTF-16 , UTF-32 ). Hlavní nevýhodou této metody je ztráta kompatibility s předchozími textovými knihovnami při reprezentaci řetězce jako ASCIIZ. Například konec řetězce by již neměl být považován za bajt s hodnotou 0, ale za dva nebo čtyři po sobě jdoucí nula bajtů, zatímco jeden bajt "0" se může vyskytovat uprostřed řetězce, což mate knihovnu.
- Použití kódování s proměnnou velikostí znaků. Například v UTF-8 jsou některé znaky reprezentovány jedním bajtem, některé dvěma, třemi nebo čtyřmi. Tato metoda umožňuje zachovat částečnou kompatibilitu se starými knihovnami (v řetězci není 0 znaků, a proto lze 0 použít jako znak konce řetězce), ale vede k nemožnosti přímého adresování znaku v paměti pomocí číslo jeho pozice v řetězci.
Lexikální analýza
Pro kontrolu shody všech tvarů slov během lexikální (sémantické) analýzy se používají míry podobnosti tokenů:
Viz také
Poznámky
- ↑ Nejdražší jednobajtová chyba – fronta ACM . Získáno 17. září 2016. Archivováno z originálu 19. září 2016. (neurčitý)
- ↑ Joel on Software – Zpět k základům . Získáno 17. září 2016. Archivováno z originálu 16. září 2016. (neurčitý)
- ↑ Simon St. Laurent. Představujeme vám Erlang . - O'Reilly Media, Inc., 2013. - S. 62 . — 185p. - ISBN 978-1-449-33176-4 .
- ↑ Bryan O'Sullivan, Don Stewart, John Goerzen, Real World Haskell. Dodatek B. Znaky, řetězce a úniková pravidla Archivováno 26. ledna 2012 na Wayback Machine
- ↑ Manuál SWI-Prolog: 5.2.2 Reprezentující text: řetězce, atomy a seznamy kódů Archivováno 17. července 2014 na Wayback Machine