Tip șir

• executarea îndelungată a operațiunilor de obținere a lungimii și concatenării șirurilor;
• lipsa mijloacelor de control al ieșirii liniei, în caz de deteriorare a octetului final, posibilitatea de a deteriora suprafețe mari de memorie, ceea ce poate duce la consecințe imprevizibile - pierderea datelor, blocarea programului și chiar a întregului sistem;
• incapacitatea de a utiliza caracterul octet final ca element șir.
• incapacitatea de a utiliza unele codificări cu o dimensiune a caracterelor de mai mulți octeți (de exemplu, UTF-16), deoarece în multe astfel de caractere, de exemplu  (0x0100), unul dintre octeți este zero (în același timp, UTF- codificarea 8 este lipsită de acest dezavantaj).

Folosind ambele metode

În limbi precum, de exemplu, Oberon , un șir este plasat într-o matrice de caractere de o anumită lungime, iar sfârșitul său este indicat printr-un caracter nul. În mod implicit, întreaga matrice este umplută cu caractere nule. Această metodă vă permite să combinați multe dintre avantajele ambelor abordări, precum și să evitați majoritatea dezavantajelor acestora.

Vizualizare listă

Limbile Erlang [3] , Haskell [4] , Prolog [5] folosesc o listă de caractere pentru tipul șirului . Această metodă face limbajul mai „teoretic elegant” prin respectarea ortogonalității în sistemul de tipări , dar aduce o penalizare semnificativă de performanță.

Implementare în limbaje de programare

• Primele limbaje de programare nu aveau deloc un tip de șir; programatorul trebuia să construiască funcții pentru lucrul cu șiruri de un tip sau altul.
• C folosește șiruri terminate nul cu control manual complet de către programator.
• În Pascal standard , un șir arată ca o matrice de 256 de octeți; primul octet a stocat lungimea șirului, restul și-a stocat corpul. Astfel, lungimea șirului nu poate depăși 255 de caractere. Borland Pascal 7.0 a introdus și linii „a la C ”, aparent datorită faptului că Windows a fost inclus printre platformele suportate .
• În Object Pascal și C++ STL , un șir este o „cutie neagră” în care alocarea/dealocarea memoriei are loc automat - fără participarea programatorului . Când este creat un șir, memoria este alocată automat; de îndată ce nu mai există nicio referință la șir, memoria este returnată sistemului. Avantajul acestei metode este că programatorul nu trebuie să se gândească la modul în care funcționează șirurile. Pe de altă parte, programatorul are un control insuficient asupra funcționării programului în zonele critice pentru viteză; de asemenea, este dificil să treci astfel de șiruri ca parametru unui DLL . De asemenea, Object Pascal se asigură automat că la sfârșitul șirului există un caracter cu codul 0. Prin urmare, dacă funcția necesită un șir terminat cu nul ca intrare , trebuie doar să scrieți sau (pentru Pascal), (pentru Builder /STL) pentru a converti.PAnsiChar(строковая_переменная)PWideChar(строковая_переменная)переменная.c_str()
• În C# și în alte limbaje colectate de gunoi , un șir este un obiect imuabil; dacă șirul trebuie modificat, se creează un alt obiect. Această metodă este lentă și irosește multă memorie temporară, dar merge bine cu conceptul de colectare a gunoiului. Avantajul acestei metode este că atribuirea este rapidă și fără rânduri duplicat. Există, de asemenea, un anumit control manual asupra construcției șirurilor de caractere (în Java , de exemplu, prin clase StringBuffer и StringBuilder) - acest lucru vă permite să reduceți numărul de alocări și ediții de memorie și, în consecință, să creșteți viteza.
  • În unele limbi (de exemplu, Standard ML ), în plus, există un modul suplimentar pentru a oferi o eficiență și mai mare - „substring” (SubString). Utilizarea acestuia vă permite să efectuați operații pe șiruri fără a copia corpurile acestora prin manipularea indicilor începutului și sfârșitului subșirului; copierea fizică are loc numai atunci când este necesară convertirea subșirurilor în șiruri.

Operațiuni

• obținerea unui caracter după numărul de poziție (index) - în majoritatea limbilor, aceasta este o operațiune banală;
• concatenare (conectare) de șiruri.

• obținerea unui subșir de indici de început și de sfârșit;
• verificarea apariției unui șir în altul ( căutarea unui subșir într-un șir);
• verificați dacă există șiruri de caractere care se potrivesc (se face distincție între majuscule sau minuscule );
• obținerea lungimii șirului;
• înlocuirea unui subșir într-un șir.

• convoluție ;
• cartografierea de la o listă la alta;
• filtrarea listei după criterii.

• găsirea superșirului minim care conține toate șirurile specificate;
• caută în două matrice de șiruri de caractere pentru secvențe potrivite ( problema plagiatului ) .

• comparație pentru proximitatea șirurilor specificate după un criteriu dat;
• determinarea limbajului şi codificarea textului pe baza probabilităţilor caracterelor şi silabelor.

Reprezentarea caracterelor unui șir

Până de curând, un caracter era întotdeauna codificat ca un octet (8 biți binari; se foloseau și codificări cu 7 biți pe caracter), ceea ce făcea posibilă reprezentarea a 256 (128 cu o codare pe șapte biți) de valori posibile. Cu toate acestea, pentru o reprezentare completă a caracterelor alfabetelor mai multor limbi​​(documente în mai multe limbi, caractere tipografice - mai multe tipuri de ghilimele , liniuțe , mai multe tipuri de spații și pentru scrierea textelor în limbi hieroglifice - chineză , japoneză și coreeană ) 256 de caractere nu sunt suficiente. Există mai multe metode pentru a rezolva această problemă:

• Schimbarea limbii prin coduri de control. Metoda nu este standardizată și privează textul de independență (adică o succesiune de caractere fără cod de control la început își pierde sensul); folosit în unele rusificări timpurii ale ZX-Spectrum și BK .
• Folosind doi sau mai mulți octeți pentru a reprezenta fiecare caracter ( UTF-16 , UTF-32 ). Principalul dezavantaj al acestei metode este pierderea compatibilității cu bibliotecile de text anterioare atunci când reprezintă un șir ca ASCIIZ. De exemplu, sfârșitul unui șir nu mai trebuie considerat un octet cu valoarea 0, ci doi sau patru zero octeți consecutivi, în timp ce un singur octet „0” poate apărea în mijlocul unui șir, ceea ce derutează biblioteca.
• Folosind o codificare cu o dimensiune variabilă a caracterelor. De exemplu, în UTF-8, unele caractere sunt reprezentate de un octet, altele de doi, trei sau patru. Această metodă vă permite să păstrați compatibilitatea parțială cu bibliotecile vechi (nu există caractere 0 în interiorul șirului și, prin urmare, 0 poate fi folosit ca semn al sfârșitului șirului), dar duce la imposibilitatea de a adresa direct un caracter în memorie prin numărul său de poziție în șir.

Analiză lexicală

Pentru a verifica conformitatea tuturor formelor de cuvinte în timpul analizei lexicale (semantice), sunt utilizate măsuri de similaritate simbol:

• Distanța de la Damerau la Loewenstein
• Distanța Levenshtein
• Distanța de Hamming
• Asemănări Jaro-Winkler

Vezi și

• Șir terminat nul
• Linie goală
• Date text
• Semigrup liber
• Ordinea lexicografică
• Algoritmi pe șiruri
• Cuvânt (matematică)
• Simbol larg

Note

1. ↑ Cea mai scumpă greșeală de un octet - Coada ACM . Consultat la 17 septembrie 2016. Arhivat din original pe 19 septembrie 2016. (nedefinit)
2. ↑ Joel despre software - Înapoi la elementele de bază . Consultat la 17 septembrie 2016. Arhivat din original la 16 septembrie 2016. (nedefinit)
3. ↑ Simon St. Laurent. Vă prezentăm Erlang . - O'Reilly Media, Inc., 2013. - P.  62 . — 185p. - ISBN 978-1-449-33176-4 .
4. ↑ Bryan O'Sullivan, Don Stewart, John Goerzen, Lumea Reală Haskell. Anexa B. Caractere, șiruri și reguli de evadare Arhivat 26 ianuarie 2012 la Wayback Machine
5. ↑ SWI-Prolog Manual: 5.2.2 Reprezentarea textului: șiruri de caractere, atomi și liste de coduri Arhivat 17 iulie 2014 la Wayback Machine