Řetězec (počítačová věda) - String (computer science)

Schéma řetězcových dat ve výpočetní technice.  Ukazuje větu „Toto je řetězec!“  s každým písmenem v samostatném poli.  Nahoře je slovo „Řetězec“, které odkazuje na celou větu.  Štítek „Znak“ je níže a ukazuje na jednotlivá políčka.
Řetězce často tvoří postavy . Jsou užitečné pro ukládání lidských čitelné údaje, jako vět, nebo seznamů abecedních dat, stejně jako sekvence nukleové kyseliny z DNA .

V programování počítače , je řetězec je tradičně sekvence z postav , a to buď jako doslovný konstanty nebo jako nějaký druh proměnné . Ten může umožnit mutaci jeho prvků a změnu délky, nebo může být opraven (po vytvoření). Řetězec je obecně považován za typ dat a je často realizován jako datové struktury pole z bytů (nebo slova ), která ukládá sekvence prvků, typicky znaky, pomocí nějakého kódování znaků . Řetězec může také označovat obecnější pole nebo jiné sekvenční (nebo seznamové ) datové typy a struktury.

V závislosti na použitém programovacím jazyce a přesném datovém typu může proměnná deklarovaná jako řetězec buď způsobit statické přidělení úložiště v paměti na předem stanovenou maximální délku, nebo použít dynamickou alokaci, aby mohla obsahovat proměnný počet prvků.

Když se řetězec objeví doslova ve zdrojovém kódu , je znám jako řetězcový literál nebo anonymní řetězec.

Ve formálních jazycích , které se používají v matematické logice a teoretické informatice , je řetězec konečnou posloupností symbolů, které jsou vybrány ze sady zvané abeceda .

Řetězcové datové typy

Řetězec datový typ je datový typ postaven na myšlence formální řetězce. Řetězce jsou tak důležitým a užitečným datovým typem, že jsou implementovány téměř v každém programovacím jazyce . V některých jazycích jsou k dispozici jako primitivní typy a v jiných jako složené typy . Syntaxe většiny programovacích jazyků vysoké úrovně umožňuje řetězec, obvykle citoval nějakým způsobem reprezentovat instanci řetězce datový typ; takový meta-řetězec se nazývá doslovný nebo řetězcový .

Délka struny

Ačkoli formální řetězce mohou mít libovolnou konečnou délku, délka řetězců ve skutečných jazycích je často omezena na umělé maximum. Obecně existují dva typy řetězcových datových typů: řetězce s pevnou délkou , které mají pevnou maximální délku určenou v době kompilace a které používají stejné množství paměti bez ohledu na to, zda je toto maximum potřeba nebo ne, a řetězce s proměnnou délkou , jehož délka není libovolně fixována a která může využívat různá množství paměti v závislosti na skutečných požadavcích za běhu (viz Správa paměti ). Většina řetězců v moderních programovacích jazycích jsou řetězce s proměnnou délkou. Samozřejmě i řetězce s proměnnou délkou jsou omezeny délkou-velikostí dostupné počítačové paměti . Délka řetězce může být uložena jako samostatné celé číslo (což může na délku znamenat další umělý limit) nebo implicitně prostřednictvím ukončovacího znaku, obvykle znakové hodnoty se všemi bity nula, například v programovacím jazyce C. Viz také níže „ Null-terminated “.

Kódování znaků

Řetězcové datové typy historicky přidělovaly jeden bajt na znak, a přestože se přesná znaková sada lišila podle oblasti, kódování znaků bylo dostatečně podobné, že se programátorům často podařilo toto ignorovat, protože znaky program zpracovával speciálně (například tečku, mezeru a čárku) ) byly na stejném místě ve všech kódováních, se kterými se program setká. Tyto znakové sady byly obvykle založeny na ASCII nebo EBCDIC . Pokud byl text v jednom kódování zobrazen v systému pomocí jiného kódování, text byl často rozbitý , i když často poněkud čitelný a někteří uživatelé počítačů se naučili číst pokazený text.

Logologické jazyky, jako je čínština , japonština a korejština (souhrnně označované jako CJK ), vyžadují pro rozumnou reprezentaci mnohem více než 256 znaků (limit jednoho 8bitového kódování na jeden znak). Normální řešení zahrnovala zachování jednobajtových reprezentací pro ASCII a používání dvoubajtových reprezentací pro ideografy CJK . Jejich použití s ​​existujícím kódem vedlo k problémům s párováním a řezáním řetězců, jejichž závažnost závisela na tom, jak bylo navrženo kódování znaků. Některá kódování, jako je rodina EUC, zaručují, že bajtová hodnota v rozsahu ASCII bude představovat pouze tento znak ASCII, takže je kódování bezpečné pro systémy, které tyto znaky používají jako oddělovače polí. Jiná kódování, jako je ISO-2022 a Shift-JIS , takové záruky neposkytují, takže je shoda na bajtových kódech nebezpečná. Tato kódování také nebyla "samosynchronizující", takže vyhledání hranic znaků vyžadovalo zálohování až na začátek řetězce a vložení dvou řetězců dohromady by mohlo mít za následek poškození druhého řetězce.

Unicode obrázek poněkud zjednodušil. Většina programovacích jazyků má nyní datový typ pro řetězce Unicode. Preferovaný formát bajtového proudu UTF-8 Unicode je navržen tak, aby neměl problémy popsané výše u starších vícebajtových kódování. UTF-8, UTF-16 a UTF-32 vyžadují, aby programátor věděl, že kódové jednotky pevné velikosti se liší od „znaků“, přičemž hlavní obtíž v současnosti představují nesprávně navržená rozhraní API, která se pokoušejí tento rozdíl skrýt (UTF-32 ano udělejte body kódu pevné velikosti, ale nejedná se o „znaky“ kvůli skládání kódů).

Implementace

Některé jazyky, například C ++ a Ruby , obvykle umožňují změnit obsah řetězce po jeho vytvoření; tyto se nazývají proměnlivé řetězce. V jiných jazycích, jako je Java a Python , je hodnota pevná a je -li třeba provést jakoukoli změnu, je nutné vytvořit nový řetězec; tyto se nazývají neměnné řetězce (některé z těchto jazyků také poskytují jiný typ, který je měnitelný, například Java a .NET StringBuilder , Java bezpečná pro vlákna StringBuffera Cocoa NSMutableString ).

Řetězce jsou obvykle implementovány jako pole bajtů, znaků nebo kódových jednotek, aby byl umožněn rychlý přístup k jednotlivým jednotkám nebo podřetězcům - včetně znaků, pokud mají pevnou délku. Několik jazyků, jako je Haskell, je místo toho implementuje jako propojené seznamy .

Některé jazyky, například Prolog a Erlang , se vůbec vyhnou implementaci vyhrazeného datového typu řetězce, místo toho přijmou konvenci reprezentující řetězce jako seznamy znakových kódů.

Zastoupení

Reprezentace řetězců závisí do značné míry na volbě znakového repertoáru a způsobu kódování znaků. Starší implementace řetězců byly navrženy pro práci s repertoárem a kódováním definovaným ASCII nebo novějšími rozšířeními, jako je řada ISO 8859 . Moderní implementace často používají rozsáhlý repertoár definovaný Unicode spolu s řadou komplexních kódování, jako jsou UTF-8 a UTF-16.

Termín bajtový řetězec obvykle označuje univerzální řetězec bajtů, nikoli řetězce pouze (čitelných) znaků, řetězce bitů nebo podobně. Bajtové řetězce často znamenají, že bajty mohou mít jakoukoli hodnotu a jakákoli data lze ukládat tak, jak jsou, což znamená, že by neměla existovat žádná hodnota interpretovaná jako hodnota ukončení.

Většina řetězcových implementací je velmi podobná maticím s proměnnou délkou, přičemž položky ukládají kódy znaků odpovídajících znaků. Zásadní rozdíl je v tom, že při určitých kódováních může jeden logický znak zabírat více než jednu položku v poli. Stává se to například u UTF-8, kde jednotlivé kódy ( body kódu UCS ) mohou trvat od jednoho do čtyř bajtů a jednotlivé znaky mohou mít libovolný počet kódů. V těchto případech se logická délka řetězce (počet znaků) liší od fyzické délky pole (počet používaných bajtů). UTF-32 se vyhýbá první části problému.

Null-terminated

Délka řetězce může být implicitně uložena pomocí speciálního ukončovacího znaku; Často se jedná o null znak (NUL), který má všechny bity nula, konvence použité a udržovaný populární C programovací jazyk . Z tohoto důvodu je toto znázornění je běžně označována jako C řetězce . Tato reprezentace řetězce n -character zabírá n + 1 mezeru (1 pro terminátor), a je tedy implicitní datovou strukturou .

V ukončených řetězcích není ukončovací kód povoleným znakem v žádném řetězci. Řetězce s délkovým polem toto omezení nemají a mohou také ukládat libovolná binární data .

Příklad řetězce zakončeného nulou uloženého v 10bajtové vyrovnávací paměti spolu s jeho reprezentací ASCII (nebo modernější UTF-8 ) jako 8bitová hexadecimální čísla je:

F R A N K NUL k e f w
46 16 52 16 41 16 4E 16 4B 16 00 16 6B 16 65 16 66 16 77 16

Délka řetězce ve výše uvedeném příkladu „ FRANK“ je 5 znaků, ale zabírá 6 bajtů. Znaky za terminátorem nejsou součástí reprezentace; mohou být buď součástí jiných dat, nebo jen odpadky. (Řetězce tohoto formuláře se někdy nazývají řetězce ASCIZ , poté, co je k jejich deklaraci použila původní direktiva jazyka sestavení .)

Bajtové a bitové zakončení

Použití speciálního bajtu jiného než null pro ukončení řetězců se historicky objevilo v hardwaru i softwaru, i když někdy s hodnotou, která byla také tiskovým znakem. $byl používán mnoha assemblerovými systémy, :používanými systémy CDC (tento znak měl hodnotu nula) a používal ZX80," protože to byl oddělovač řetězců v jeho ZÁKLADNÍM jazyce.

Poněkud podobné stroje „na zpracování dat“, jako je IBM 1401, používaly speciální bit slovních značek k vymezení řetězců vlevo, kde by operace začínala vpravo. Tento bit musel být jasný ve všech ostatních částech řetězce. To znamenalo, že zatímco IBM 1401 mělo sedmbitové slovo, téměř nikoho nikdy nenapadlo použít tuto funkci jako funkci a přepsat přiřazení sedmého bitu (například) zpracovávat kódy ASCII.

Starší mikropočítačový software spoléhal na skutečnost, že kódy ASCII nepoužívají bit vyššího řádu, a nastavil jej tak, aby označoval konec řetězce. Před výstupem musí být resetován na 0.

Délka s předponou

Délka řetězce může být také uložena explicitně, například předponou řetězce s délkou jako bajtovou hodnotou. Tato konvence se používá v mnoha pascalských dialektech; v důsledku toho někteří lidé nazývají takový řetězec řetězcem Pascal nebo P-řetězcem . Uložení délky řetězce jako bajtu omezuje maximální délku řetězce na 255. Aby se předešlo těmto omezením, vylepšené implementace řetězců P používají k uložení délky řetězce 16-, 32- nebo 64bitová slova . Když pole délky pokrývá adresní prostor , řetězce jsou omezeny pouze dostupnou pamětí .

Pokud je délka ohraničená, lze ji zakódovat do konstantního prostoru, obvykle do strojového slova, což vede k implicitní datové struktuře , přičemž prostor je n + k , kde k je počet znaků ve slově (8 pro 8bitové ASCII na 64bitovém počítači, 1 pro 32bitový UTF-32/UCS-4 na 32bitovém počítači atd.). Pokud délka není ohraničená, kódování délky n zabere místo log ( n ) (viz kód pevné délky ), takže řetězce s předponou délky jsou stručnou datovou strukturou kódující řetězec délky n v log ( n ) + n mezera .

V druhém případě pole délky předpony samo o sobě nemá pevnou délku, proto je třeba data aktuálního řetězce přesunout, když řetězec roste tak, že je potřeba pole délky zvětšit.

Zde je řetězec Pascal uložený v 10bajtové vyrovnávací paměti spolu s jeho reprezentací ASCII / UTF-8:

délka F R A N K k e f w
05 16 46 16 52 16 41 16 4E 16 4B 16 6B 16 65 16 66 16 77 16

Řetězce jako záznamy

Mnoho jazyků, včetně objektově orientovaných, implementuje řetězce jako záznamy s vnitřní strukturou jako:

class string {
  size_t length;
  char *text;
};

Protože je však implementace obvykle skrytá , je nutné k řetězci přistupovat a upravovat ho prostřednictvím členských funkcí. textje ukazatel na dynamicky přidělenou paměťovou oblast, kterou lze podle potřeby rozšířit. Viz také řetězec (C ++) .

Jiná zobrazení

Omezení řetězců kódů ukončení i délky: Například pole znaků C, která obsahují znaky null (NUL), nelze zpracovávat přímo pomocí funkcí knihovny řetězců C : Řetězce používající kód délky jsou omezeny na maximální hodnotu kódu délky.

Obě tato omezení lze překonat chytrým programováním.

Je možné vytvářet datové struktury a funkce, které s nimi manipulují a které nemají problémy spojené s ukončováním znaků a v zásadě mohou překonat hranice kódu délky. Je také možné optimalizovat řetězec reprezentovaný pomocí technik z kódování délky běhu (nahrazení opakovaných znaků hodnotou znaku a délky) a Hammingova kódování .

I když jsou tato zobrazení běžná, jiná jsou možná. Použití lan zvyšuje efektivitu určitých řetězcových operací, jako je vkládání, odstraňování a zřetězení.

Základní datová struktura v textovém editoru je ta, která spravuje řetězec (posloupnost znaků), který představuje aktuální stav upravovaného souboru. Zatímco tento stav mohl být uložen v jedné dlouhé po sobě jdoucí řadě znaků, typický textový editor místo toho používá jako sekvenční datovou strukturu alternativní reprezentaci - mezerník , propojený seznam řádků, tabulku kusů nebo provaz - což vytváří některé řetězcové operace, jako jsou vkládání, odstraňování a vrácení předchozích úprav, efektivnější.

Bezpečnostní obavy

Rozdílné rozložení paměti a požadavky na úložiště řetězců mohou ovlivnit zabezpečení programu přistupujícího k řetězcovým datům. Řetězcové reprezentace vyžadující ukončovací znak jsou obvykle náchylné k problémům s přetečením vyrovnávací paměti, pokud koncový znak není přítomen, způsobený chybou kódování nebo útočníkem záměrně měnícím data. Řetězcové reprezentace přijímající samostatné pole délky jsou také náchylné, pokud lze s délkou manipulovat. V takových případech programový kód přistupující k řetězcovým datům vyžaduje kontrolu mezí, aby bylo zajištěno, že nedopatřením nepřistupuje ani nezmění data mimo limity paměti řetězců.

Řetězcová data jsou často získávána ze vstupu uživatele do programu. Za program je odpovědný ověřit řetězec, aby se zajistilo, že představuje očekávaný formát. Provedení omezeného nebo žádného ověření vstupu uživatele může způsobit, že program bude zranitelný vůči útokům na vkládání kódu .

Doslovné struny

Někdy je třeba řetězce vložit do textového souboru, který je čitelný pro člověka a je určen ke spotřebě strojem. To je třeba například ve zdrojovém kódu programovacích jazyků nebo v konfiguračních souborech. V tomto případě znak NUL nefunguje dobře jako terminátor, protože je normálně neviditelný (nelze jej vytisknout) a je obtížné jej zadat pomocí klávesnice. Uložení délky řetězce by bylo také nepohodlné, protože ruční výpočet a sledování délky je únavné a náchylné k chybám.

Dvě běžné reprezentace jsou:

  • Je obklopen uvozovkami ( dvojité uvozovky ASCII 0x22 nebo jednoduché uvozovky ASCII 0x27), používané většinou programovacích jazyků. Aby bylo možné zahrnout speciální znaky, jako jsou samotné uvozovky, znaky nového řádku nebo netisknutelné znaky, jsou často k dispozici únikové sekvence , obvykle s předponou zpětného lomítka (ASCII 0x5C).
  • Ukončeno sekvencí nového řádku , například v souborech Windows INI .

Netextové řetězce

Zatímco znakové řetězce jsou velmi běžným používáním řetězců, řetězec v informatice může obecně odkazovat na jakoukoli sekvenci homogenně zadaných dat. Bitový řetězec nebo byte řetězec , například, může být použit k reprezentaci netextový binární data načtená z komunikačního média. Tato data mohou, ale nemusí být reprezentována datovým typem specifickým pro řetězec, v závislosti na potřebách aplikace, přání programátora a schopnostech používaného programovacího jazyka. Pokud implementace řetězce programovacího jazyka není 8bitová , může dojít k poškození dat.

Programátoři C kreslí ostrý rozdíl mezi „řetězcem“, neboli „řetězcem znaků“, který je podle definice vždy ukončen nulou, oproti „bajtovému řetězci“ nebo „pseudo řetězci“, které mohou být uloženy ve stejném poli, ale často není null ukončeno. Použití funkcí zpracování řetězců C na takovém „bajtovém řetězci“ často vypadá, že funguje, ale později vede k problémům se zabezpečením .

Algoritmy zpracování řetězců

Existuje mnoho algoritmů pro zpracování řetězců, každý s různými kompromisy. Konkurenční algoritmy lze analyzovat s ohledem na dobu běhu, požadavky na úložiště atd.

Některé kategorie algoritmů zahrnují:

Pokročilé řetězcové algoritmy často využívají složité mechanismy a datové struktury, mezi nimi stromy přípon a stroje s konečným stavem .

Název stringologie vytvořil v roce 1984 počítačový vědec Zvi Galil pro problematiku algoritmů a datových struktur používaných pro zpracování řetězců.

Jazyky a obslužné programy orientované na znakové řetězce

Řetězce znaků jsou tak užitečným datovým typem, že bylo navrženo několik jazyků, aby se aplikace pro zpracování řetězců snadno zapisovaly. Mezi příklady patří následující jazyky:

Mnoho unixových nástrojů provádí jednoduché manipulace se řetězci a lze je použít k snadnému naprogramování některých výkonných algoritmů pro zpracování řetězců. Soubory a konečné toky lze považovat za řetězce.

Některá rozhraní API, například Multimedia Control Interface , embedded SQL nebo printf, používají řetězce k uložení příkazů, které budou interpretovány.

Nedávné skriptovací programovací jazyky , včetně Perlu, Pythonu , Ruby a Tcl, používají regulární výrazy k usnadnění textových operací. Perl je zvláště známý pro jeho použití pravidelných výrazů a mnoho dalších jazyků a aplikací implementuje regulární výrazy kompatibilní s Perlem .

Některé jazyky, jako je Perl a Ruby, podporují interpolaci řetězců , což umožňuje vyhodnocení a zahrnutí libovolných výrazů do řetězcových literálů.

Funkce řetězců znaků

Řetězcové funkce se používají k vytváření řetězců nebo změně obsahu měnitelného řetězce. Používají se také k dotazování informací o řetězci. Sada funkcí a jejich názvy se liší v závislosti na počítačovém programovacím jazyce .

Nejzákladnějším příkladem funkce řetězce je funkce délky řetězce - funkce, která vrací délku řetězce (nepočítaje žádné znaky terminátoru ani žádné vnitřní strukturní informace řetězce) a nemění řetězec. Tato funkce se často jmenuje lengthnebo len. Například length("hello world")vrátí 11. Další běžnou funkcí je zřetězení , kde je nový řetězec vytvořen připojením dvou řetězců, často je to operátor + sčítání.

Některé mikroprocesor ‚s instrukční sady architektury obsahuje přímou podporu pro řetězcové operace, jako jsou blokové kopie (např intel x86m REPNZ MOVSB ).

Formální teorie

Nechť Σ je konečný soubor symbolů (alternativně nazývaných znaky), nazývaný abeceda . O povaze symbolů se nepředpokládá žádný předpoklad. Řetězec (nebo slovo ) po? Je jakýkoliv konečný posloupnost symbolů z å. Pokud například Σ = {0, 1}, pak 01011 je řetězec nad Σ.

Délka řetězce s je počet symbolů v s (délka sekvence), a může být jakýkoli nezáporné celé číslo ; často je označován jako | s |. Prázdný řetězec je jedinečný řetězec přes å délky 0, a je označován e nebo lambda .

Množina všech řetězců nad Σ délky n je označena Σ n . Pokud například Σ = {0, 1}, pak Σ 2 = {00, 01, 10, 11}. Všimněte si, že Σ 0 = {ε} pro libovolnou abecedu Σ.

Sada všech řetězců nad Σ libovolné délky je Kleeneho uzávěrem Σ a je označena Σ * . Pokud jde o Σ n ,

Pokud například Σ = {0, 1}, pak Σ * = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}. Ačkoli je samotná sada Σ * spočitatelně nekonečná , každý prvek Σ * je řetězec konečné délky.

Sada řetězců nad Σ (tj. Jakákoli podmnožina Σ * ) se nazývá formální jazyk nad Σ. Pokud například Σ = {0, 1}, sada řetězců se sudým počtem nul, {ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, ...}, je formální jazyk.

Zřetězení a podřetězce

Zřetězení je důležitou binární operací na Σ * . Pro jakékoliv dva řetězce s jsou i t v å * , jejich zřetězení je definována jako sekvence symbolů s následnou sekvencí znaků v t , a je označován st . Pokud například Σ = {a, b, ..., z}, s  = beara t  = hug, pak st  = bearhuga ts  = hugbear.

Zřetězení řetězců je asociativní , ale nekomutativní operace. Prázdný řetězec ε slouží jako prvek identity ; pro libovolný řetězec s , ε s = s ε = s . Proto sada Σ * a operace zřetězení tvoří monoid , volný monoid generovaný Σ. Kromě toho funkce délka definuje monoidní homomorfismus od Σ * do nezáporných celých čísel (tj. Funkce , taková, že ).

Řetězec s se říká, že se dílčí řetězec , nebo faktor z t , pokud existují (případně prázdný) struny U a V takové, že t = USV . Vztah „je podřetězec“ definuje částečné uspořádání na å * , The nejmenší prvek , z nichž je prázdný řetězec.

Předpony a přípony

Řetězec s se říká, že je prefix z t , pokud existuje řetězec u tak, že t = su . Pokud u neprázdný, š se říká, že je správný předpona t . Symetricky, Řetězec s se říká, že je přípona z t , pokud existuje řetězec u tak, že t = nás . Pokud u neprázdný, š se říká, že je správná přípona t . Přípony a předpony jsou podřetězci t . Oba vztahy „jsou předponou“ a „jsou příponou“ jsou předpony .

Obrácení

Rubem řetězce je řetězec se stejnými symboly, ale v opačném pořadí. Například pokud s = abc (kde a, b, a c jsou symboly abecedy), pak je reverzní s je cba. Řetězec, který je jeho opakem (např. S = madam), se nazývá palindrom , který také obsahuje prázdný řetězec a všechny řetězce o délce 1.

Rotace

Řetězec s = uv se říká, že je rotací t, pokud t = vu . Například pokud Σ = {0, 1} řetězec 0011001 je rotací 0100110, kde u = 00110 a v = 01. Jako další příklad má řetězec abc tři různé rotace, viz. abc sám (s u = abc, v = ε), bca (s u = bc, v = a) a kabina (s u = c, v = ab).

Lexikografické řazení

Často je užitečné definovat řazení na sadě řetězců. Pokud má abeceda Σ celkové pořadí (viz abecední pořadí ), lze definovat celkové pořadí na Σ * nazývané lexikografické pořadí . Pokud například Σ = {0, 1} a 0 <1, pak lexikografické pořadí na Σ * zahrnuje vztahy ε <0 <00 <000 <... <0001 <001 <01 <010 <011 <0110 < 01111 <1 <10 <100 <101 <111 <1111 <11111 ... Lexikografické pořadí je úplné, pokud je abecední pořadí, ale není podložené žádnou netriviální abecedou, i když abecední pořadí je.

Alternativní řazení řetězců, které zachovává fundovanost, najdete v Shortlexu .

Řetězcové operace

Ve formální teorii se běžně vyskytuje řada dalších operací na řetězcích. Ty jsou uvedeny v článku o řetězcových operacích .

Topologie

(Hyper) kostka binárních řetězců o délce 3

Řetězce připouštějí následující interpretaci jako uzly v grafu, kde k je počet symbolů v Σ:

  • Řetězce s pevnou délkou délky n lze považovat za celočíselná umístění v n -rozměrné hyperkrychli se stranami o délce k -1.
  • Řetězce s proměnnou délkou (konečné délky) lze považovat za uzly dokonalého k -ary stromu .
  • Nekonečné řetězce (jinak se zde neuvažuje) lze na grafu k -uzlu zobrazit jako nekonečné cesty .

Přirozená topologie na sadě řetězců s pevnou délkou nebo řetězců s proměnnou délkou je diskrétní topologie, ale přirozená topologie na sadě nekonečných řetězců je limitní topologie , prohlížení sady nekonečných řetězců jako inverzní mez sady množin konečné řetězce. Toto je konstrukce použitá pro p -adická čísla a některé konstrukce sady Cantor a poskytuje stejnou topologii.

Izomorfismy mezi řetězcovými reprezentacemi topologií lze nalézt normalizací podle lexikograficky minimální rotace řetězce .

Viz také

Reference