String (informatyka) - String (computer science)

Schemat danych String w informatyce.  Wyświetla zdanie „To jest ciąg!”  z każdą literą w osobnym pudełku.  Słowo „String” znajduje się powyżej i odnosi się do całego zdania.  Etykieta „Znak” znajduje się poniżej i wskazuje na poszczególne pola.
Ciągi często składają się ze znaków . Są one użyteczne do przechowywania danych czytelnych dla człowieka, takie jak kar lub listach danych literowego, tak jak kwasów nukleinowych sekwencji z DNA .

W programowaniu komputerowym , wykorzystując ciąg jest tradycyjnie sekwencja z postaciami , w postaci dosłownej stałej lub jako pewnego rodzaju zmiennej . Ten ostatni może umożliwiać mutację jego elementów i zmianę długości lub może być naprawiony (po utworzeniu). Ciąg jest powszechnie uważany jako typ danych i często jest zaimplementowany jako struktury danych array of bajtów (lub słowa ), który przechowuje ciąg elementów, zwykle znaków, przy użyciu jakiegoś kodowania znaków . Łańcuch może również oznaczać bardziej ogólne tablice lub inne sekwencje (lub list ) typy i struktury danych.

W zależności od używanego języka programowania i precyzyjnego typu danych zmienna zadeklarowana jako łańcuch może albo spowodować, że pamięć w pamięci zostanie statycznie przydzielona na z góry określoną maksymalną długość, albo zastosować alokację dynamiczną, aby umożliwić przechowywanie zmiennej liczby elementów.

Gdy ciąg pojawia się dosłownie w kodzie źródłowym , jest znany jako literał ciągu lub anonimowy ciąg.

W językach formalnych , używanych w logice matematycznej i informatyce teoretycznej , ciąg znaków jest skończoną sekwencją symboli wybranych ze zbioru zwanego alfabetem .

Ciągowe typy danych

Typ danych łańcuchowych to typ danych wzorowany na idei łańcucha formalnego. Łańcuchy są tak ważnym i użytecznym typem danych, że są implementowane w prawie każdym języku programowania . W niektórych językach są one dostępne jako typy pierwotne, aw innych jako typy złożone . Składnia większości języków programowania wysokiego poziomu pozwala na sznurku, najczęściej cytowany w jakiś sposób reprezentuje instancję typu danych string; taki meta-ciąg nazywany jest literałem lub literałem ciągu .

Długość łańcucha

Chociaż formalne łańcuchy mogą mieć dowolną skończoną długość, długość łańcuchów w rzeczywistych językach jest często ograniczona do sztucznego maksimum. Ogólnie rzecz biorąc, istnieją dwa typy typów danych łańcuchowych: łańcuchy o stałej długości , które mają stałą maksymalną długość do określenia w czasie kompilacji i które wykorzystują tę samą ilość pamięci, niezależnie od tego, czy to maksimum jest potrzebne, czy nie, oraz łańcuchy o zmiennej długości , których długość nie jest arbitralnie ustalona i które mogą wykorzystywać różne ilości pamięci w zależności od rzeczywistych wymagań w czasie wykonywania (patrz Zarządzanie pamięcią ). Większość ciągów we współczesnych językach programowania to ciągi o zmiennej długości. Oczywiście nawet stringi o zmiennej długości mają ograniczoną długość – przez wielkość dostępnej pamięci komputera . Długość łańcucha może być przechowywana jako oddzielna liczba całkowita (która może wprowadzić kolejne sztuczne ograniczenie długości) lub pośrednio przez znak kończący, zwykle wartość znakową z wszystkimi bitami zero, tak jak w języku programowania C. Zobacz także „ Zakończone znakiem zerowym ” poniżej.

Kodowanie znaków

Typy danych łańcuchowych historycznie przydzielały jeden bajt na znak i chociaż dokładny zestaw znaków różnił się w zależności od regionu, kodowanie znaków było na tyle podobne, że programiści często mogli to zignorować, ponieważ znaki były traktowane przez program specjalnie (takie jak kropka, spacja i przecinek ) znajdowały się w tym samym miejscu we wszystkich kodowaniach, jakie napotka program. Te zestawy znaków były zazwyczaj oparte na ASCII lub EBCDIC . Jeśli tekst w jednym kodowaniu był wyświetlany w systemie przy użyciu innego kodowania, tekst był często zniekształcony , choć często nieco czytelny, a niektórzy użytkownicy komputerów nauczyli się czytać zniekształcony tekst.

Języki logograficzne , takie jak chiński , japoński i koreański (zwane zbiorczo CJK ) wymagają znacznie więcej niż 256 znaków (ograniczenie jednego 8-bitowego kodowania na znak) dla rozsądnej reprezentacji. Normalne rozwiązania obejmowały utrzymywanie jednobajtowych reprezentacji dla ASCII i używanie dwubajtowych reprezentacji dla ideogramów CJK . Użycie ich w istniejącym kodzie powodowało problemy z dopasowywaniem i wycinaniem ciągów, których waga zależała od tego, jak zaprojektowano kodowanie znaków. Niektóre kodowania, takie jak rodzina EUC, gwarantują, że wartość bajtu z zakresu ASCII będzie reprezentować tylko ten znak ASCII, dzięki czemu kodowanie jest bezpieczne dla systemów, które używają tych znaków jako separatorów pól. Inne kodowania, takie jak ISO-2022 i Shift-JIS , nie dają takich gwarancji, przez co dopasowywanie kodów bajtowych jest niebezpieczne. Te kodowania również nie były „samosynchronizujące się”, więc zlokalizowanie granic znaków wymagało utworzenia kopii zapasowej do początku ciągu, a wklejenie dwóch ciągów razem mogło spowodować uszkodzenie drugiego ciągu.

Unicode nieco uprościł obraz. Większość języków programowania ma teraz typ danych dla ciągów Unicode. Preferowany format strumienia bajtów UTF-8 w standardzie Unicode nie ma problemów opisanych powyżej dla starszych kodowań wielobajtowych. UTF-8, UTF-16 i UTF-32 wymagają od programisty, aby wiedział, że jednostki kodu o stałym rozmiarze różnią się od „znaków”, główną trudnością jest obecnie niepoprawnie zaprojektowane API, które próbują ukryć tę różnicę (UTF-32 tworzyć punkty kodowe o stałych rozmiarach, ale nie są to „znaki” ze względu na kody tworzące).

Realizacje

Niektóre języki, takie jak C++ i Ruby , zwykle pozwalają na zmianę zawartości ciągu po jego utworzeniu; są to tak zwane ciągi zmienne . W innych językach, takich jak Java i Python , wartość jest stała i należy utworzyć nowy ciąg, jeśli ma być dokonana jakakolwiek zmiana; są one określane jako ciągi niezmienne (niektóre z tych języków zapewniają również inny typ, który jest zmienny, taki jak Java i .NET StringBuilder , Java bezpieczna wątkowo StringBufferi Cocoa NSMutableString ).

Ciągi są zwykle implementowane jako tablice bajtów, znaków lub jednostek kodu, aby umożliwić szybki dostęp do poszczególnych jednostek lub podciągów — w tym znaków, gdy mają stałą długość. Kilka języków, takich jak Haskell, implementuje je jako listy połączone .

Niektóre języki, takie jak Prolog i Erlang , w ogóle unikają implementacji dedykowanego typu danych ciągu, zamiast tego przyjmują konwencję reprezentowania ciągów jako list kodów znaków.

Reprezentacje

Reprezentacje ciągów w dużej mierze zależą od doboru repertuaru znaków i metody kodowania znaków. Starsze implementacje ciągów zostały zaprojektowane do pracy z repertuarem i kodowaniem zdefiniowanym przez ASCII lub nowszymi rozszerzeniami, takimi jak seria ISO 8859 . Nowoczesne implementacje często wykorzystują bogaty repertuar zdefiniowany przez Unicode wraz z różnymi złożonymi kodowaniami, takimi jak UTF-8 i UTF-16.

Termin ciąg bajtów zwykle oznacza ciąg bajtów ogólnego przeznaczenia, a nie ciągi tylko (czytelnych) znaków, ciągi bitów lub tym podobne. Ciągi bajtów często oznaczają, że bajty mogą przyjmować dowolną wartość, a dowolne dane mogą być przechowywane bez zmian, co oznacza, że ​​nie powinno być żadnej wartości interpretowanej jako wartość zakończenia.

Większość implementacji napisów jest bardzo podobna do tablic o zmiennej długości, w których wpisy przechowują kody znaków odpowiadających im znaków. Główna różnica polega na tym, że w przypadku niektórych kodowań pojedynczy znak logiczny może zajmować więcej niż jeden wpis w tablicy. Dzieje się tak na przykład w UTF-8, gdzie pojedyncze kody ( punkty kodowe UCS ) mogą zajmować od jednego do czterech bajtów, a pojedyncze znaki mogą przyjmować dowolną liczbę kodów. W takich przypadkach długość logiczna ciągu (liczba znaków) różni się od fizycznej długości tablicy (liczba używanych bajtów). UTF-32 pozwala uniknąć pierwszej części problemu.

Zakończone zerem

Długość ciągu można przechowywać niejawnie, używając specjalnego znaku kończącego; Często jest to znak null (NUL), który ma wszystkie bity zero, konwencja używane i utrwalona przez popularnego języka programowania C . Dlatego ta reprezentacja jest powszechnie nazywana ciągiem C . Ta reprezentacja n- znakowego ciągu zajmuje n +1 miejsca (1 dla terminatora), a zatem jest niejawną strukturą danych .

W zakończonych łańcuchach kod kończący nie jest dozwolonym znakiem w żadnym łańcuchu. Łańcuchy z polem długości nie mają tego ograniczenia i mogą również przechowywać dowolne dane binarne .

Przykładem łańcucha zakończonego znakiem null przechowywanego w 10-bajtowym buforze wraz z jego reprezentacją ASCII (lub bardziej nowoczesną UTF-8 ) jako 8-bitowe liczby szesnastkowe jest:

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ługość ciągu w powyższym przykładzie, " FRANK", to 5 znaków, ale zajmuje 6 bajtów. Znaki po terminatorze nie stanowią części reprezentacji; mogą być częścią innych danych lub po prostu śmieciem. (Ciągi w tej formie są czasami nazywane ciągami ASCIZ , po oryginalnej dyrektywie asemblerowej użytej do ich deklarowania.)

Zakończone bajtami i bitami

Używanie specjalnego bajtu innego niż null do oznaczania ciągów kończących ciągów historycznie pojawiało się zarówno w sprzęcie, jak i oprogramowaniu, chociaż czasami z wartością, która była również znakiem drukowania. $był używany przez wiele systemów asemblerowych, :używany przez systemy CDC (ten znak miał wartość zero), a ZX80 był używany, "ponieważ był to ogranicznik łańcucha w jego języku BASIC.

Nieco podobne maszyny do „przetwarzania danych”, takie jak IBM 1401, używały specjalnego bitu znaku słownego do odgraniczania ciągów po lewej stronie, gdzie operacja rozpoczynałaby się po prawej stronie. Ten fragment musiał być wyraźny we wszystkich innych częściach struny. Oznaczało to, że chociaż IBM 1401 miał słowo siedmiobitowe, prawie nikt nigdy nie pomyślał o użyciu go jako funkcji i pominięciu przypisania siódmego bitu do (na przykład) obsługi kodów ASCII.

Wczesne oprogramowanie mikrokomputerowe opierało się na fakcie, że kody ASCII nie używają bitu wyższego rzędu i ustawiały go tak, aby wskazywał koniec ciągu. Musi być zresetowany do 0 przed wyjściem.

Długość z przedrostkiem

Długość ciągu może być również przechowywana jawnie, na przykład przez poprzedzenie ciągu z długością jako wartością bajtową. Konwencja ta jest używana w wielu dialektach Pascala ; w konsekwencji niektórzy ludzie nazywają taki łańcuch łańcuchem Pascala lub P-string . Przechowywanie długości ciągu jako bajt ogranicza maksymalną długość ciągu do 255. Aby uniknąć takich ograniczeń, ulepszone implementacje P-ciągów używają 16-, 32- lub 64-bitowych słów do przechowywania długości ciągu. Gdy pole długości zakrywa przestrzeń adresową , łańcuchy są ograniczone jedynie dostępną pamięcią .

Jeśli długość jest ograniczona, to może być zakodowana w stałej przestrzeni, zazwyczaj słowie maszynowym, co prowadzi do niejawnej struktury danych , przyjmującej przestrzeń n + k , gdzie k jest liczbą znaków w słowie (8 dla 8-bitowych ASCII na maszynie 64-bitowej, 1 dla 32-bitowego UTF-32/UCS-4 na maszynie 32-bitowej itd.). Jeśli długość nie jest ograniczona, kodowanie długości n zajmuje log( n ) przestrzeni (patrz kod o stałej długości ), więc łańcuchy z przedrostkiem długości są zwięzłą strukturą danych , kodującą łańcuch o długości n w log( n ) + n spacji .

W tym drugim przypadku samo pole z prefiksem długości nie ma stałej długości, dlatego rzeczywiste dane ciągu muszą zostać przesunięte, gdy ciąg rośnie w taki sposób, że należy zwiększyć pole długości.

Oto łańcuch Pascala przechowywany w 10-bajtowym buforze, wraz z jego reprezentacją ASCII / UTF-8:

długość 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

Ciągi jako rekordy

Wiele języków, w tym zorientowanych obiektowo, implementuje łańcuchy jako rekordy o wewnętrznej strukturze, takiej jak:

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

Jednak ponieważ implementacja jest zwykle ukryta , ciąg musi być dostępny i modyfikowany za pomocą funkcji składowych. textjest wskaźnikiem do dynamicznie przydzielonego obszaru pamięci, który w razie potrzeby może zostać rozszerzony. Zobacz także string (C++) .

Inne reprezentacje

Zarówno znaki zakończenia, jak i kody długości ograniczają ciągi: Na przykład tablice znaków C, które zawierają znaki null (NUL), nie mogą być obsługiwane bezpośrednio przez funkcje biblioteki ciągów C : Ciągi używające kodu długości są ograniczone do maksymalnej wartości kodu długości.

Oba te ograniczenia można przezwyciężyć dzięki sprytnemu programowaniu.

Możliwe jest tworzenie struktur danych i funkcji, które nimi manipulują, które nie mają problemów związanych z zakończeniem znaków i mogą w zasadzie przezwyciężyć ograniczenia długości kodu. Możliwa jest również optymalizacja ciągu reprezentowanego przy użyciu technik kodowania długości przebiegu (zastępowanie powtarzających się znaków wartością znaku i długością) oraz kodowania Hamminga .

Chociaż te reprezentacje są powszechne, możliwe są inne. Korzystanie z lin sprawia, że ​​niektóre operacje na łańcuchach, takie jak wstawianie, usuwanie i łączenie, są bardziej wydajne.

Podstawową strukturą danych w edytorze tekstu jest ta, która zarządza ciągiem (sekwencją znaków) reprezentującym bieżący stan edytowanego pliku. Chociaż ten stan może być przechowywany w jednej długiej kolejnej tablicy znaków, typowy edytor tekstu zamiast tego używa alternatywnej reprezentacji jako swojej struktury danych sekwencji — bufor przerw , połączona lista wierszy, tabela kawałków lub lina — co sprawia, że niektóre operacje na ciągach, takie jak wstawianie, usuwanie i cofanie poprzednich edycji, są bardziej wydajne.

Obawy dotyczące bezpieczeństwa

Różny układ pamięci i wymagania dotyczące przechowywania ciągów mogą wpływać na bezpieczeństwo programu uzyskującego dostęp do danych ciągów. Reprezentacje ciągów wymagające znaku kończącego są zwykle podatne na problemy z przepełnieniem bufora , jeśli nie ma znaku kończącego, co jest spowodowane błędem kodowania lub celową zmianą danych przez atakującego . Reprezentacje ciągów przyjmujące oddzielne pole długości są również podatne, jeśli można manipulować długością. W takich przypadkach kod programu uzyskujący dostęp do danych ciągów wymaga sprawdzenia granic, aby upewnić się, że nie ma przypadkowego dostępu lub zmiany danych poza limitami pamięci ciągów.

Dane ciągu są często uzyskiwane z danych wejściowych użytkownika do programu. W związku z tym obowiązkiem programu jest sprawdzenie poprawności ciągu w celu upewnienia się, że reprezentuje on oczekiwany format. Wykonywanie ograniczonej lub brak walidacji danych wejściowych użytkownika może spowodować, że program będzie podatny na ataki polegające na wstrzykiwaniu kodu .

Dosłowne ciągi

Czasami ciągi znaków muszą być osadzone w pliku tekstowym, który jest zarówno czytelny dla człowieka, jak i przeznaczony do użycia przez maszynę. Jest to potrzebne np. w kodzie źródłowym języków programowania lub w plikach konfiguracyjnych. W tym przypadku znak NUL nie działa dobrze jako terminator, ponieważ jest zwykle niewidoczny (niedrukowalny) i trudno go wprowadzić za pomocą klawiatury. Przechowywanie długości łańcucha byłoby również niewygodne, ponieważ ręczne obliczanie i śledzenie długości jest żmudne i podatne na błędy.

Dwie wspólne reprezentacje to:

  • Otoczony cudzysłowami ( podwójny cudzysłów ASCII 0x22 lub pojedynczy cudzysłów ASCII 0x27), używany przez większość języków programowania. Aby móc dołączyć znaki specjalne, takie jak sam cudzysłów, znaki nowego wiersza lub znaki niedrukowalne, często dostępne są sekwencje specjalne , zwykle poprzedzone znakiem odwrotnego ukośnika (ASCII 0x5C).
  • Zakończona nowej linii sekwencji, na przykład w systemie Windows plikach INI .

Ciągi nietekstowe

Chociaż ciągi znaków są bardzo powszechnymi zastosowaniami ciągów, ciąg w informatyce może odnosić się ogólnie do dowolnej sekwencji jednorodnie wpisanych danych. Na przykład ciąg bitów lub ciąg bajtów może być używany do reprezentowania nietekstowych danych binarnych pobranych z nośnika komunikacyjnego. Te dane mogą, ale nie muszą być reprezentowane przez typ danych specyficzny dla ciągu, w zależności od potrzeb aplikacji, chęci programisty i możliwości używanego języka programowania. Jeśli implementacja ciągu w języku programowania nie jest 8-bitowa , może dojść do uszkodzenia danych.

Programiści C dokonują ostrego rozróżnienia między „ciągiem”, czyli „ciągiem znaków”, który z definicji jest zawsze zakończony zerem, a „ciągiem bajtów” lub „pseudociągiem”, który może być przechowywany w tej samej tablicy, ale jest często nie zakończone zerem. Używanie funkcji obsługi ciągów C na takim „ciągu bajtów” często wydaje się działać, ale później prowadzi do problemów z bezpieczeństwem .

Algorytmy przetwarzania ciągów

Istnieje wiele algorytmów przetwarzania ciągów, każdy z różnymi kompromisami. Konkurencyjne algorytmy można analizować pod kątem czasu działania, wymagań dotyczących pamięci i tak dalej.

Niektóre kategorie algorytmów obejmują:

Zaawansowane algorytmy łańcuchowe często wykorzystują złożone mechanizmy i struktury danych, w tym drzewa sufiksów i maszyny skończone .

Nazwa stringologia została ukuta w 1984 roku przez informatyka Zvi Galila dla zagadnienia algorytmów i struktur danych wykorzystywanych do przetwarzania łańcuchów.

Języki i narzędzia zorientowane na łańcuch znaków

Ciągi znaków są tak użytecznym typem danych, że zaprojektowano kilka języków, aby ułatwić pisanie aplikacji przetwarzających ciągi. Przykłady obejmują następujące języki:

Wiele narzędzi uniksowych wykonuje proste operacje na ciągach znaków i można ich używać do łatwego programowania potężnych algorytmów przetwarzania ciągów. Pliki i skończone strumienie mogą być postrzegane jako ciągi.

Niektóre interfejsy API, takie jak Multimedia Control Interface , wbudowany SQL lub printf używają ciągów do przechowywania poleceń, które będą interpretowane.

Najnowsze skryptowe języki programowania , w tym Perl, Python , Ruby i Tcl, wykorzystują wyrażenia regularne w celu ułatwienia operacji tekstowych. Perl jest szczególnie znany z używania wyrażeń regularnych, a wiele innych języków i aplikacji implementuje wyrażenia regularne zgodne z Perlem .

Niektóre języki, takie jak Perl i Ruby, obsługują interpolację ciągów , co pozwala na ewaluację i uwzględnienie dowolnych wyrażeń w literałach ciągów.

Funkcje ciągu znaków

Funkcje ciągów służą do tworzenia ciągów lub zmiany zawartości zmiennej ciągu. Służą również do wysyłania zapytań o informacje dotyczące ciągu. Zestaw funkcji i ich nazwy różnią się w zależności od języka programowania komputera .

Najbardziej podstawowym przykładem funkcji ciągów jest funkcja długości ciągu — funkcja, która zwraca długość ciągu (nie licząc żadnych znaków terminatora ani żadnych wewnętrznych informacji strukturalnych ciągu) i nie modyfikuje ciągu. Ta funkcja jest często nazywana lengthlub len. Na przykład length("hello world")zwróci 11. Inną powszechną funkcją jest concatenation , gdzie nowy ciąg jest tworzony przez dołączenie dwóch ciągów, często jest to operator dodawania +.

Jakiegoś mikroprocesor „s zestaw instrukcji architektury zawierać bezpośrednie wsparcie dla operacji strunowych, takich jak kopia bloku (np intel x86m REPNZ MOVSB ).

Teoria formalna

Niech Σ będzie skończonym zbiorem symboli (zwanych alternatywnie znakami), zwanymi alfabetem . Nie ma żadnych założeń co do natury symboli. Łańcuch (lub słowo ) w Ď jakikolwiek skończoną sekwencję symboli z Ď. Na przykład, jeśli Σ = {0, 1}, to 01011 jest ciągiem nad Σ.

Długość łańcucha * y oznacza liczbę symboli w s (długość sekwencji) i może być dowolna nieujemną liczbę całkowitą ; jest często oznaczany jako | s |. Pusty łańcuch jest unikalny łańcuch znaków na Ď długości 0, i jest oznaczona ε lub X .

Zbiór wszystkich łańcuchów powyżej Σ długości n oznaczamy Σ n . Na przykład, jeśli Σ = {0, 1}, to Σ 2 = {00, 01, 10, 11}. Zauważ, że Σ 0 = {ε} dla dowolnego alfabetu Σ.

Zbiór wszystkich łańcuchów powyżej Σ o dowolnej długości jest domknięciem Kleene Σ i jest oznaczony Σ * . Pod względem Σ n ,

Na przykład, jeśli Σ = {0, 1}, to Σ * = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}. Chociaż sam zbiór Σ * jest przeliczalnie nieskończony , każdy element Σ * jest łańcuchem o skończonej długości.

Zbiór łańcuchów nad Σ (tj. dowolny podzbiór Σ * ) nazywany jest językiem formalnym nad Σ. Na przykład, jeśli Σ = {0, 1}, zbiór ciągów z parzystą liczbą zer, {ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, ...} jest językiem formalnym ponad Σ.

Konkatenacja i podciągi

Konkatenacja jest ważną operacją binarną na Σ * . Dla dowolnych dwóch łańcuchów s i t w Σ * , ich konkatenacja jest zdefiniowana jako sekwencja symboli w s , po której następuje sekwencja znaków w t i jest oznaczona st . Na przykład, jeśli Σ = {a, b, ..., z}, s  = beari t  = hug, to st  = bearhugi ts  = hugbear.

Łączenie ciągów jest operacją asocjacyjną , ale nieprzemienną . Pusty łańcuch ε służy jako element tożsamości ; dla dowolnego ciągu s , ε s = s ε = s . Dlatego zbiór Σ * i operacja konkatenacji tworzą monoid , swobodny monoid generowany przez Σ. Ponadto funkcja length definiuje homomorfizm monoidu od Σ * do nieujemnych liczb całkowitych (czyli funkcję taką, że ).

STRING s mówi się, że jest podciąg lub czynnik o t jeśli istnieją (ewentualnie puste) łańcuchów u i v w taki sposób, T = USV . Związek „jest podłańcuchem” określa porządek częściowy na Ď * , a z przynajmniej elementów , z których jest pusty.

Przedrostki i przyrostki

STRING s Mówi się przedrostek z t , jeśli istnieje ciąg u tak, że t = su . Jeśli u jest niepuste, mówi się, że s jest właściwym przedrostkiem t . Symetrycznie, ciąg s Mówi się przyrostek z t , jeśli istnieje ciąg U tak, że t = nas . Jeśli u jest niepuste, mówi się, że s jest właściwym sufiksem t . Sufiksy i przedrostki są podciągami t . Obie relacje „jest prefiksem” i „jest sufiksem” są zamówieniami prefiksowymi .

Odwrócenie

Odwrotność ciągu to ciąg z tymi samymi symbolami, ale w odwrotnej kolejności. Na przykład, jeśli s = abc (gdzie a, b i c są symbolami alfabetu), to odwrotnością s jest cba. Ciąg będący odwrotnością samego siebie (np. s = madam) nazywany jest palindromem , który zawiera również pusty ciąg i wszystkie ciągi o długości 1.

Obroty

Mówi się, że struna s = uv jest obrotem t, jeśli t = vu . Na przykład, jeśli Σ = {0, 1} ciąg 0011001 jest rotacją 0100110, gdzie u = 00110 iv = 01. Jako inny przykład, ciąg abc ma trzy różne obroty, mianowicie. abc (z u =abc, v =ε), bca (z u =bc, v =a) i cab (z u =c, v =ab).

Porządkowanie leksykograficzne

Często przydatne jest zdefiniowanie kolejności na zestawie ciągów. Jeżeli alfabet Σ ma porządek całkowity (por. porządek alfabetyczny ) można określić porządek całkowity na Σ * zwany porządkiem leksykograficznym . Na przykład, jeśli Σ = {0, 1} i 0 < 1, to porządek leksykograficzny na Σ * obejmuje relacje ε < 0 < 00 < 000 < ... < 0001 < 001 < 01 < 010 < 011 < 0110 < 01111 < 1 < 10 < 100 < 101 < 111 < 1111 < 11111 ... Porządek leksykograficzny jest całkowity, jeśli porządek alfabetyczny jest taki, ale nie jest dobrze ugruntowany dla żadnego nietrywialnego alfabetu, nawet jeśli porządek alfabetyczny jest taki.

Zobacz Shortlex, aby uzyskać alternatywną kolejność ciągów, która zachowuje solidność.

Operacje na ciągach

Szereg dodatkowych operacji na strunach powszechnie występuje w teorii formalnej. Są one podane w artykule o operacjach na ciągach .

Topologia

(Hiper)sześcian ciągów binarnych o długości 3

Łańcuchy dopuszczają następującą interpretację jako węzły na grafie, gdzie k jest liczbą symboli w Σ:

  • Ciągi o stałej długości o długości n mogą być postrzegane jako położenia liczb całkowitych w n- wymiarowym hipersześcianie o bokach długości k -1.
  • Łańcuchy o zmiennej długości (o skończonej długości) mogą być postrzegane jako węzły na doskonałym k- arnym drzewie .
  • Nieskończone ciągi (inaczej nie uważane tutaj) może być postrzegana jako nieskończonych ścieżek na k -node graf pełny .

Naturalna topologia zbioru ciągów o stałej długości lub ciągów o zmiennej długości jest topologią dyskretną, ale naturalna topologia zbioru ciągów nieskończonych jest topologią graniczną , postrzegając zbiór nieskończonych ciągów jako odwrotną granicę zbiorów skończone struny. Jest to konstrukcja używana dla liczb p- adycznych i niektórych konstrukcji zbioru Cantora i daje taką samą topologię.

Izomorfizmy między łańcuchowymi reprezentacjami topologii można znaleźć, normalizując zgodnie z leksykograficznie minimalną rotacją łańcuchów .

Zobacz też

Bibliografia