String (bilgisayar bilimi) - String (computer science)

Hesaplamada String verilerinin diyagramı.  "Bu bir dizedir!" cümlesini gösterir.  her harf ayrı bir kutuda.  Yukarıda "Dize" kelimesi cümlenin tamamına atıfta bulunmaktadır.  "Karakter" etiketi aşağıdadır ve tek tek kutulara işaret eder.
Dizeler genellikle karakterlerden oluşur . Bunlar gibi, cümle ya da alfabetik veri listeleri gibi, insanlar tarafından okunabilir olan verileri depolamak için yararlı olan nükleik asit dizileri arasında , DNA .

Gelen bilgisayar programlama , bir dize geleneksel olarak ise sırası ait karakterleri bir olarak ister edebi sabiti veya bir tür olarak değişken . İkincisi, elemanlarının mutasyona uğramasına ve uzunluğunun değiştirilmesine izin verebilir veya sabitlenebilir (yaratıldıktan sonra). Bir dizi, genel bir şekilde kabul edilir bir veri türü ve çoğu zaman bir şekilde uygulanan bir dizi veri yapısının bir bayt (ya da kelime bazı kullanılarak, tipik olarak, elemanlar, bir karakter dizisi depolayan) karakter kodlamasını . Dize ayrıca daha genel dizileri veya diğer dizi (veya liste ) veri türlerini ve yapılarını da gösterebilir .

Kullanılan programlama diline ve kesin veri türüne bağlı olarak, bir dize olarak bildirilen bir değişken , bellekte depolamanın önceden belirlenmiş bir maksimum uzunluk için statik olarak tahsis edilmesine neden olabilir veya değişken sayıda öğeyi tutmasına izin vermek için dinamik tahsisi kullanabilir.

Bir dize kaynak kodda tam anlamıyla göründüğünde , dize değişmezi veya anonim dize olarak bilinir .

Gelen resmi dilde kullanılan, matematiksel mantık ve teorik bilgisayar bilimleri , bir dize sonlu dizisidir sembollerinden bir seçilir sette bir adlandırılan alfabe .

Dize veri türleri

Bir dize veri türü , resmi bir dize fikri üzerine modellenen bir veri türüdür. Dizeler, neredeyse her programlama dilinde uygulandıkları kadar önemli ve kullanışlı bir veri türüdür . Bazı dillerde ilkel türler olarak, diğerlerinde ise bileşik türler olarak mevcutturlar . Sözdizimi en üst düzey programlama dillerinin bir dize için, genellikle bir dize veri türü bir örneğini temsil etmek, bir şekilde alıntılanan sağlar; böyle bir meta- string'e literal veya string literal denir .

IP uzunluğu

Biçimsel diziler keyfi bir sonlu uzunluğa sahip olabilse de, gerçek dillerde dizilerin uzunluğu genellikle yapay bir maksimumla sınırlandırılır. Genel olarak, yaylı veri türleri iki tipi vardır: sabit uzunluklu dizeleri sabit bir maksimum uzunlukta tespit edilmesi gerekir, derleme zamanında ve bu maksimum gerekli olup olmadığını bellek ve aynı miktarda kullanan değişken uzunluklu dizeleri , uzunluğu keyfi olarak sabit olmayan ve çalışma zamanındaki gerçek gereksinimlere bağlı olarak değişen miktarlarda bellek kullanabilen (bkz. Bellek yönetimi ). Modern programlama dillerindeki çoğu dizi , değişken uzunluklu dizilerdir. Tabii ki, değişken uzunluktaki diziler bile uzunluk bakımından sınırlıdır – kullanılabilir bilgisayar belleğinin boyutuna göre . Dize uzunluğu ayrı bir tamsayı olarak (uzunluğa başka bir yapay sınır koyabilir) veya örtük olarak bir sonlandırma karakteri aracılığıyla, genellikle C programlama dilinde olduğu gibi tüm bitleri sıfır olan bir karakter değeri olarak saklanabilir. Ayrıca aşağıdaki " Boş sonlandırılmış " bölümüne bakın.

Karakter kodlaması

Dize veri türleri tarihsel olarak karakter başına bir bayt tahsis etmiştir ve tam karakter kümesi bölgeye göre değişse de, karakter kodlamaları programcıların bunu görmezden gelebileceği kadar benzerdi, çünkü karakterler bir program özel olarak ele alındığından (nokta, boşluk ve virgül gibi) ) bir programın karşılaşacağı tüm kodlamalarda aynı yerdeydi. Bu karakter kümeleri tipik olarak ASCII veya EBCDIC'ye dayanıyordu . Bir kodlamadaki metin, farklı bir kodlama kullanan bir sistemde görüntüleniyorsa, metin genellikle karışıktı , ancak genellikle biraz okunabilirdi ve bazı bilgisayar kullanıcıları karışık metni okumayı öğrendi.

Çince , Japonca ve Korece (topluca CJK olarak bilinir ) gibi logografik diller , makul bir temsil için 256 karakterden (karakter başına bir 8 bitlik bayt kodlama sınırı) çok daha fazlasına ihtiyaç duyar. Normal çözümler, ASCII için tek baytlık temsilleri tutmayı ve CJK ideografları için iki baytlık temsilleri kullanmayı içeriyordu . Bunların mevcut kodla kullanılması, ciddiyeti karakter kodlamasının nasıl tasarlandığına bağlı olan dizelerin eşleşmesi ve kesilmesi ile ilgili sorunlara yol açtı. EUC ailesi gibi bazı kodlamalar , ASCII aralığındaki bir bayt değerinin yalnızca o ASCII karakterini temsil edeceğini garanti ederek, bu karakterleri alan ayırıcı olarak kullanan sistemler için kodlamayı güvenli hale getirir. ISO-2022 ve Shift-JIS gibi diğer kodlamalar bu tür garantiler vermez ve bayt kodlarında eşleşmeyi güvensiz hale getirir. Bu kodlamalar ayrıca "kendi kendini senkronize eden" değildi, bu nedenle bir dizenin başlangıcına kadar yedeklenmesi gereken karakter sınırlarının bulunması ve iki dizenin birbirine yapıştırılması, ikinci dizenin bozulmasına neden olabilir.

Unicode , resmi biraz basitleştirdi. Çoğu programlama dili artık Unicode dizeleri için bir veri türüne sahiptir. Unicode'un tercih edilen bayt akışı formatı UTF-8 , daha eski çok baytlı kodlamalar için yukarıda açıklanan sorunlara sahip olmayacak şekilde tasarlanmıştır. UTF-8, UTF-16 ve UTF-32 , programcının sabit boyutlu kod birimlerinin "karakterlerden" farklı olduğunu bilmesini gerektirir, şu anda asıl zorluk bu farkı gizlemeye çalışan yanlış tasarlanmış API'lerdir (UTF-32 yapmak kod noktaları ölçekli sabit ancak bunlar oluşturan kodlara "karakterler") değildir.

Uygulamalar

C++ ve Ruby gibi bazı diller normalde bir dize içeriğinin oluşturulduktan sonra değiştirilmesine izin verir; bunlar değiştirilebilir dizeler olarak adlandırılır . Java ve Python gibi diğer dillerde, değer sabittir ve herhangi bir değişiklik yapılacaksa yeni bir dize oluşturulmalıdır; bunlar değişmez dizeler olarak adlandırılır (bu dillerden bazıları ayrıca Java ve .NET StringBuilder , iş parçacığı için güvenli Java StringBufferve Cocoa gibi değişken başka bir tür sağlar NSMutableString).

Dizeler, sabit bir uzunluğa sahip olduklarında karakterler de dahil olmak üzere, tek tek birimlere veya alt dizelere hızlı erişime izin vermek için tipik olarak bayt, karakter veya kod birimi dizileri olarak uygulanır . Haskell gibi birkaç dil, bunları bunun yerine bağlantılı listeler olarak uygular .

Prolog ve Erlang gibi bazı diller, özel bir dize veri türü uygulamaktan kaçınır, bunun yerine dizeleri karakter kodları listesi olarak gösterme kuralını benimser.

temsiller

Dizelerin temsilleri, büyük ölçüde karakter repertuarının seçimine ve karakter kodlama yöntemine bağlıdır. Daha eski dize uygulamaları, ASCII tarafından tanımlanan repertuar ve kodlamayla veya ISO 8859 serisi gibi daha yeni uzantılarla çalışmak üzere tasarlanmıştır . Modern uygulamalar genellikle UTF-8 ve UTF-16 gibi çeşitli karmaşık kodlamalarla birlikte Unicode tarafından tanımlanan kapsamlı repertuarı kullanır.

Bayt dizisi terimi , yalnızca (okunabilir) karakter dizileri, bit dizileri veya benzerlerinden ziyade genellikle genel amaçlı bir bayt dizisini belirtir. Bayt dizeleri genellikle baytların herhangi bir değeri alabileceğini ve herhangi bir verinin olduğu gibi saklanabileceğini, yani bir sonlandırma değeri olarak yorumlanan hiçbir değerin olmaması gerektiği anlamına gelir.

Çoğu dize uygulaması, karşılık gelen karakterlerin karakter kodlarını depolayan girişlerle değişken uzunluklu dizilere çok benzer . Temel fark, belirli kodlamalarda, tek bir mantıksal karakterin dizide birden fazla girdi alabilmesidir. Bu, örneğin, tek kodların ( UCS kod noktaları) bir ila dört bayt arasında herhangi bir yeri alabileceği ve tek karakterlerin rastgele sayıda kod alabileceği UTF-8 ile olur . Bu durumlarda, dizenin mantıksal uzunluğu (karakter sayısı), dizinin fiziksel uzunluğundan (kullanılan bayt sayısı) farklıdır. UTF-32 , sorunun ilk kısmından kaçınır.

boş sonlandırılmış

Bir dizenin uzunluğu, özel bir sonlandırma karakteri kullanılarak örtük olarak saklanabilir; genellikle bu, popüler C programlama dili tarafından kullanılan ve sürdürülen bir kural olan tüm bitleri sıfır olan boş karakterdir (NUL) . Bu nedenle, bu gösterime genellikle bir C dizesi denir . Bir n - karakter dizisinin bu temsili n + 1 boşluk (sonlandırıcı için 1) alır ve bu nedenle örtük bir veri yapısıdır .

Sonlandırılmış dizelerde, sonlandırma kodu herhangi bir dizede izin verilen bir karakter değildir. Uzunluk alanına sahip dizeler bu sınırlamaya sahip değildir ve ayrıca isteğe bağlı ikili verileri de depolayabilir .

8 bitlik onaltılık sayılar olarak ASCII (veya daha modern UTF-8 ) gösterimi ile birlikte 10 baytlık bir arabellekte depolanan boş sonlandırılmış bir dize örneği :

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

Yukarıdaki örnekteki " FRANK" dizesinin uzunluğu 5 karakterdir, ancak 6 bayt kaplar. Sonlandırıcıdan sonraki karakterler temsilin bir parçasını oluşturmaz; ya diğer verilerin parçası olabilirler ya da sadece çöp olabilirler. (Bu formun dizeleri , bunları bildirmek için kullanılan orijinal Assembly dili yönergesinden sonra bazen ASCIZ dizeleri olarak adlandırılır .)

Bayt ve bit sonlandırmalı

Dizeleri sonlandırmak için null dışında özel bir bayt kullanmak, bazen aynı zamanda bir baskı karakteri olan bir değerle olsa da, geçmişte hem donanım hem de yazılımda ortaya çıkmıştır. CDC sistemleri (bu karakterin sıfır değeri vardı) tarafından kullanılan $birçok montajcı sistem :tarafından kullanıldı ve ZX80 , BASIC dilinde dize sınırlayıcı olduğu için kullanıldı . "

Biraz benzer, IBM 1401 gibi "veri işleme" makineleri , işlemin sağdan başlayacağı soldaki dizeleri sınırlandırmak için özel bir kelime işareti biti kullandı. Bu bit, dizenin diğer tüm bölümlerinde açık olmak zorundaydı. Bu, IBM 1401 yedi bitlik bir kelimeye sahipken, neredeyse hiç kimsenin bunu bir özellik olarak kullanmayı ve (örneğin) ASCII kodlarını işlemek için yedinci bitin atamasını geçersiz kılmayı düşünmediği anlamına geliyordu.

İlk mikrobilgisayar yazılımı, ASCII kodlarının yüksek dereceli biti kullanmadığı ve onu bir dizgenin sonunu gösterecek şekilde ayarladığı gerçeğine dayanıyordu. Çıkıştan önce 0'a sıfırlanmalıdır.

uzunluk ön ekli

Bir dizgenin uzunluğu, örneğin, bir bayt değeri olarak uzunluk ile dizgenin önüne eklenerek, açıkça saklanabilir. Bu kural birçok Pascal lehçesinde kullanılır; sonuç olarak, bazı insanlar böyle bir dizgeyi Pascal dizgisi veya P-dizisi olarak adlandırır . Dize uzunluğunu bayt olarak depolamak, maksimum dize uzunluğunu 255 ile sınırlar. Bu tür sınırlamalardan kaçınmak için, P-dizelerinin geliştirilmiş uygulamaları , dize uzunluğunu depolamak için 16-, 32- veya 64-bit sözcükleri kullanır. Ne zaman uzunluğu alanı kaplamaktadır adres alanı , dizeleri sadece sınırlıdır kullanılabilir bellek .

Uzunluk sınırlıysa, o zaman, tipik olarak bir makine sözcüğü olan sabit uzayda kodlanabilir, böylece n + k alanı alarak örtük bir veri yapısına yol açar , burada k bir sözcükteki karakter sayısıdır (8 bit için 8). 64 bit makinede ASCII, 32 bit makinede 32 bit UTF-32/UCS-4 için 1 vb.). Uzunluk sınırlı değilse, n uzunluğunu kodlamak log( n ) alanı alır ( sabit uzunluklu koda bakın ), bu nedenle uzunluk önekli dizeler kısa bir veri yapısıdır ve log( n ) + n uzayında bir uzunluk n dizesini kodlar .

İkinci durumda, uzunluk-ön ek alanının kendisi sabit uzunluğa sahip değildir, bu nedenle, uzunluk alanının arttırılması gerektiği şekilde dize büyüdüğünde gerçek dize verilerinin taşınması gerekir.

ASCII / UTF-8 gösterimi ile birlikte 10 baytlık bir arabellekte saklanan bir Pascal dizesi:

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

Kayıt olarak dizeler

Nesne yönelimli olanlar da dahil olmak üzere birçok dil, dizeleri aşağıdaki gibi dahili bir yapıya sahip kayıtlar olarak uygular :

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

Ancak, uygulama genellikle gizli olduğundan, dizeye üye işlevler aracılığıyla erişilmeli ve değiştirilmelidir. textgerektiğinde genişletilebilen, dinamik olarak ayrılmış bir bellek alanına yönelik bir işaretçidir. Ayrıca bkz. dize (C++) .

Diğer temsiller

Hem karakter sonlandırma hem de uzunluk kodları dizeleri sınırlar: Örneğin, boş (NUL) karakterler içeren C karakter dizileri, doğrudan C dize kitaplığı işlevleri tarafından işlenemez : Bir uzunluk kodu kullanan dizeler, uzunluk kodunun maksimum değeriyle sınırlıdır.

Bu sınırlamaların her ikisi de akıllı programlama ile aşılabilir.

Karakter sonlandırma ile ilgili sorunları olmayan ve prensipte uzunluk kod sınırlarının üstesinden gelebilecek veri yapıları ve bunları işleyen işlevler yaratmak mümkündür. Çalışma uzunluğu kodlamasından (tekrarlanan karakterleri karakter değeri ve bir uzunlukla değiştirmek) ve Hamming kodlamasından teknikleri kullanarak temsil edilen dizgiyi optimize etmek de mümkündür .

Bu temsiller yaygın olmakla birlikte, diğerleri mümkündür. Halatların kullanılması , eklemeler, silmeler ve birleştirmeler gibi belirli dize işlemlerini daha verimli hale getirir.

Bir metin düzenleyicideki çekirdek veri yapısı, düzenlenmekte olan dosyanın mevcut durumunu temsil eden dizeyi (karakter dizisini) yöneten yapıdır . Bu durum tek bir uzun ardışık karakter dizisinde depolanabilse de, tipik bir metin düzenleyici bunun yerine dizi veri yapısı olarak alternatif bir temsil kullanır - bir boşluk arabelleği , bağlantılı bir satır listesi , bir parça tablosu veya bir ip - ekleme, silme ve önceki düzenlemeleri geri alma gibi belirli dize işlemleri daha verimlidir.

Güvenlik endişeleri

Dizelerin farklı bellek düzeni ve depolama gereksinimleri, dize verilerine erişen programın güvenliğini etkileyebilir. Bir sonlandırma karakteri gerektiren dize temsilleri , bir kodlama hatası veya bir saldırganın verileri kasıtlı olarak değiştirmesinden kaynaklanan, sonlandırma karakteri mevcut değilse, genellikle arabellek taşması sorunlarına karşı hassastır . Uzunluk manipüle edilebiliyorsa, ayrı bir uzunluk alanını benimseyen dize temsilleri de hassastır. Bu gibi durumlarda, dizi verilerine erişen program kodu , dizi bellek sınırlarının dışındaki verilere yanlışlıkla erişmediğinden veya bunları değiştirmediğinden emin olmak için sınır denetimi gerektirir .

Dize verileri sıklıkla bir programa kullanıcı girdisinden elde edilir. Bu nedenle, beklenen biçimi temsil ettiğinden emin olmak için dizeyi doğrulamak programın sorumluluğundadır. Sahne sınırlı ya da hiç doğrulama kullanıcı girişi bir programdır karşı savunmasız olmasına neden olabilir kod enjeksiyon saldırıları.

Değişmez dizeler

Bazen, dizelerin hem insan tarafından okunabilen hem de bir makine tarafından tüketilmesi amaçlanan bir metin dosyasının içine gömülmesi gerekir. Bu, örneğin programlama dillerinin kaynak kodunda veya yapılandırma dosyalarında gereklidir. Bu durumda, normalde görünmez (yazdırılamaz) olduğundan ve klavye aracılığıyla girilmesi zor olduğundan, NUL karakteri bir sonlandırıcı olarak iyi çalışmaz. El ile hesaplama ve uzunluğun izlenmesi sıkıcı ve hataya açık olduğundan, dize uzunluğunun saklanması da elverişsiz olacaktır.

İki yaygın temsiller şunlardır:

  • Çevrili tırnak (ASCII 0x22 çoğu programlama dilleri tarafından kullanılan çift tırnak veya ASCII 0x27 tek tırnak). Tırnak işaretinin kendisi, yeni satır karakterleri veya yazdırılamayan karakterler gibi özel karakterleri dahil edebilmek için , genellikle önüne ters eğik çizgi karakteri (ASCII 0x5C) eklenmiş kaçış dizileri kullanılabilir .
  • Örneğin Windows INI dosyalarında yeni satır dizisiyle sonlandırılır .

Metin olmayan dizeler

Karakter dizileri, dizilerin çok yaygın kullanımları olsa da, bilgisayar bilimindeki bir dizi, genel olarak homojen olarak yazılmış herhangi bir veri dizisine atıfta bulunabilir. Örneğin bir bit dizisi veya bayt dizisi , bir iletişim ortamından alınan metinsel olmayan ikili verileri temsil etmek için kullanılabilir . Bu veriler, uygulamanın gereksinimlerine, programcının isteğine ve kullanılan programlama dilinin özelliklerine bağlı olarak, dizeye özgü bir veri türüyle temsil edilebilir veya olmayabilir. Programlama dilinin dize uygulaması 8 bit temiz değilse , veri bozulması meydana gelebilir.

C programcıları, tanımı gereği her zaman boş sonlanan bir "dize", diğer bir deyişle "karakter dizisi" ile aynı dizide depolanabilen ancak genellikle boş sonlandırılmaz. Kullanılması taşıma C dize böyle bir "bayt dizesi" konulu fonksiyonları genellikle işe görünüyor, ancak daha sonra kurşunları güvenlik sorunları .

Dize işleme algoritmaları

Dizeleri işlemek için her biri çeşitli takaslara sahip birçok algoritma vardır . Rakip algoritmalar, çalışma süresi, depolama gereksinimleri vb. açısından analiz edilebilir .

Bazı algoritma kategorileri şunları içerir:

Gelişmiş dizi algoritmaları genellikle karmaşık mekanizmalar ve veri yapıları kullanır, bunların arasında sonek ağaçları ve sonlu durum makineleri bulunur .

Stringology adı , 1984 yılında bilgisayar bilimcisi Zvi Galil tarafından, dizi işleme için kullanılan algoritmalar ve veri yapıları sorunu için icat edildi .

Karakter dizisi yönelimli diller ve yardımcı programlar

Karakter dizileri o kadar kullanışlı bir veri türüdür ki, dizi işleme uygulamalarının yazılmasını kolaylaştırmak için birçok dil tasarlanmıştır. Örnekler aşağıdaki dilleri içerir:

Birçok Unix yardımcı programı, basit dizi işlemeleri gerçekleştirir ve bazı güçlü dizi işleme algoritmalarını kolayca programlamak için kullanılabilir. Dosyalar ve sonlu akışlar, dizeler olarak görüntülenebilir.

Multimedya Kontrol Arayüzü , gömülü SQL veya printf gibi bazı API'ler , yorumlanacak komutları tutmak için dizeler kullanır.

Perl, Python , Ruby ve Tcl dahil olmak üzere son komut dosyası programlama dilleri , metin işlemlerini kolaylaştırmak için düzenli ifadeler kullanır . Perl, özellikle düzenli ifade kullanımıyla tanınır ve diğer birçok dil ve uygulama, Perl uyumlu düzenli ifadeler uygular .

Perl ve Ruby gibi bazı diller , rastgele ifadelerin değerlendirilmesine ve dize değişmezlerine dahil edilmesine izin veren dize enterpolasyonunu destekler .

Karakter dizisi işlevleri

Dize işlevleri , dizeler oluşturmak veya değiştirilebilir bir dizenin içeriğini değiştirmek için kullanılır. Ayrıca bir dize hakkında bilgi sorgulamak için kullanılırlar. İşlevler kümesi ve adları, bilgisayar programlama diline göre değişir .

Bir dize işlevinin en temel örneği, dize uzunluğu işlevidir - bir dizenin uzunluğunu döndüren işlev (sonlandırıcı karakterleri veya dizenin dahili yapısal bilgilerini saymaz) ve dizeyi değiştirmez. Bu işlev genellikle lengthveya olarak adlandırılır len. Örneğin, length("hello world")11 değerini döndürür. Diğer bir yaygın işlev, iki dize ekleyerek yeni bir dizenin oluşturulduğu birleştirme işlevidir; bu genellikle + toplama operatörüdür.

Bazı mikroişlemcinin 'ın komut seti mimarisi böyle (In örneğin blok kopyası gibi string işlemleri, doğrudan destek ihtiva istihbarat x86m REPNZ MOVSB ).

biçimsel teori

Σ , alfabe adı verilen sonlu bir semboller (alternatif olarak karakter olarak adlandırılır) olsun . Sembollerin doğası hakkında herhangi bir varsayımda bulunulmaz. Σ üzerindeki bir dize (veya kelime ), Σ'den gelen herhangi bir sonlu sembol dizisidir . Örneğin, Σ = {0, 1} ise, 01011 Σ üzerinde bir dizedir.

Uzunlukta bir karakter dizisi s sembol sayısıdır s (sırası uzunluğu) ve herhangi biri olabilir , negatif olmayan bir tam sayı ; genellikle | s |. Boş dize uzunluğu 0 Σ üzerinde benzersiz bir dizedir ve gösterilir £ değenni veya X .

Uzunluğu Σ üzerindeki tüm dizeleri seti n Σ gösterilir n . Örneğin, Σ = {0, 1} ise Σ 2 = {00, 01, 10, 11}. Herhangi bir Σ alfabesi için Σ 0 = {ε} olduğuna dikkat edin .

Herhangi bir uzunluktaki Σ üzerindeki tüm dizelerin kümesi, Σ'nin Kleene kapanışıdır ve Σ * ile gösterilir . Σ n cinsinden ,

Örneğin, Σ = {0, 1} ise, Σ * = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}. Set Σ rağmen * kendisi sayılabilir sonsuz , a her eleman * sonlu uzunlukta bir dizidir.

Σ üzerindeki bir dizi dizi (yani Σ * öğesinin herhangi bir alt kümesi ) Σ üzerinde biçimsel bir dil olarak adlandırılır . Örneğin, Σ = {0, 1} ise, çift sayıda sıfır içeren diziler kümesi, {ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, ...}, Σ üzerinde resmi bir dildir.

Birleştirme ve alt dizeler

Birleştirme * üzerindeönemli bir ikili işlemdir . Σ * içindekiherhangi iki s ve t dizesi için, bunların bitiştirilmesi, s içindeki sembol dizisi veardından t içindeki karakter dizisiolarak tanımlanırve st ile gösterilir. Örneğin, Σ = {a, b, ..., z}, s  = ve t  = ise , o zaman st  = ve ts  = . bearhugbearhughugbear

Dize bitiştirme, ilişkisel ancak değişmeli olmayan bir işlemdir. Boş dizge ε kimlik öğesi olarak hizmet eder ; herhangi bir dize için s , ε s = s ε = s . Bu nedenle, set Σ * ve birleştirme işlemi oluşturan Monoid , serbest Monoid Σ tarafından oluşturulan. Ek olarak, uzunluk işlevi, Σ *' den negatif olmayan tam sayılara (yani, bir işlev , öyle ki ) bir monoid homomorfizmi tanımlar .

Bir dize s isimli bir olduğu söylenen substring veya faktör arasında t vardır (muhtemelen boş) varsa şeritler u ve v bu gibi T = usv . İlişki tanımlayan bir "de bir alt" kısmi sıralama Σ ilgili * , en elemanı boş dizge olduğu.

Önekler ve Sonekler

Bir dize s isimli bir olduğu söylenen önek arasında t bir dizi mevcutsa U öyle ki t = su . u boş değilse , s'nin t'nin uygun bir öneki olduğu söylenir . Simetrik olarak, bir dize s is a olduğu söylenen eki ait t bir dize vardır, eğer u öyle ki t = bizi . u boş değilse , s'nin t'nin uygun bir eki olduğu söylenir . Son ekler ve önekler t öğesinin alt dizeleridir . Hem "bir önektir" hem de "bir sonektir" ilişkileri önek emirleridir .

tersine çevirme

Bir dizenin tersi, aynı sembollere sahip ancak ters sırada olan bir dizedir. Örneğin, eğer s = abc (burada a, b ve c alfabenin sembolleridir), o zaman s'nin tersi cba'dır. Kendinin tersi olan bir dizgeye (örneğin, s = madam) palindrom denir ve bu dizge boş dizgiyi ve 1 uzunluğundaki tüm dizgileri de içerir.

Rotasyonlar

Bir dizi s = UV bir dönme olduğu söylenir t ise t = vu . Örneğin, Σ = {0, 1} ise, 001001 dizisi 0100110'un bir dönüşüdür, burada u = 00110 ve v = 01. Başka bir örnek olarak, abc dizisinin üç farklı dönüşü vardır, yani. abc'nin kendisi ( u =abc, v =ε ile), bca ( u =bc, v =a ile) ve cab ( u =c, v =ab ile).

sözlüksel sıralama

Bir dizi dizi üzerinde bir sıralama tanımlamak genellikle yararlıdır . Eğer Σ alfabesinin bir toplam sırası varsa (bkz. alfabetik sıra ), Σ * üzerinde sözlüksel sıra adı verilen bir toplam sıra tanımlanabilir . Örneğin, Σ = {0, 1} ve 0 < 1 ise, Σ * üzerindeki sözlük düzeni, ε < 0 < 00 < 000 < ... < 0001 < 001 < 01 < 010 < 011 < 0110 < ilişkilerini içerir. 01111 <1 <10 <100 <101 <111 <1111 <11111 ... lexicographical sırasıdır toplam alfabetik sıra ise, ancak etmeyen sağlam temelli alfabetik sıra olsa bile, herhangi bir aşikar olmayan alfabesi için.

Bkz Shortlex alternatif dize sipariş olduğunu korur gerekçelere dayandığını için.

dize işlemleri

Biçimsel teoride genellikle diziler üzerinde bir dizi ek işlem meydana gelir. Bunlar dize işlemleriyle ilgili makalede verilmiştir .

topoloji

(Hiper)küpü 3 uzunluğunda ikili diziler

Dizeler, bir grafikte düğümler olarak aşağıdaki yorumu kabul eder; burada k , Σ'deki sembollerin sayısıdır:

  • n uzunluğundaki sabit uzunluktaki diziler, kenarları k- 1 olan n boyutlu bir hiperküpte tam sayı konumları olarak görülebilir .
  • Değişken uzunluktaki diziler (sonlu uzunluktaki) mükemmel bir k -ary ağacında düğümler olarak görülebilir .
  • Sonsuz diziler (aksi takdirde burada dikkate alınmaz), bir k düğümü tam grafiğinde sonsuz yollar olarak görülebilir .

Sabit uzunluklu diziler veya değişken uzunluklu diziler kümesindeki doğal topoloji ayrık topolojidir, ancak sonsuz diziler kümesindeki doğal topoloji, sonsuz diziler kümesini aşağıdaki kümelerin ters sınırı olarak gören limit topolojisidir . sonlu dizeler. Bu, p -adic sayıları ve Cantor kümesinin bazı yapıları için kullanılan yapıdır ve aynı topolojiyi verir.

Topolojilerin dizgi temsilleri arasındaki eşbiçimlilik , sözlükbilimsel olarak minimal dizge dönüşüne göre normalize edilerek bulunabilir .

Ayrıca bakınız

Referanslar