Рядок (програмування)

У Вікіпедії є статті про інші значення цього терміна: Рядок (значення).

Рядок (англ. String — «нитка, низка») або рядковий тип даних, також іноді стрічка[1][2], ланцюжок[3] — це тип даних, значеннями якого є довільна послідовність (рядок) символів алфавіту. Кожна змінна такого типу (рядкова змінна) може бути представлена фіксованою кількістю байтів або мати довільну довжину.

Внутрішнє представлення рядка в пам'яті[ред. | ред. код]

Деякі мови програмування накладають обмеження на максимальну довжину рядка, але в більшості мов подібні обмеження відсутні. При використанні Unicode кожен символ рядкового типу може вимагати двох або навіть чотирьох байтів для свого представлення.

Основні проблеми в машинному поданні рядкового типу:

  • рядки можуть мати досить істотний розмір (до декількох десятків мегабайтів);
  • змінюється з часом розмір — виникають труднощі з додаванням і видаленням символів.

У поданні рядків в пам'яті комп'ютера існує два принципово різних підходи.

Подання масивом символів[ред. | ред. код]

У цьому підході рядки представляються масивом символів; при цьому розмір масиву зберігається в окремій (службовій) області. Від назви мови Pascal, де цей метод був вперше реалізований, даний метод отримав назву Pascal strings.

Злегка оптимізованим варіантом цього методу є так званий формат c-addr-u (від англ. character-aligned address + unsigned number), застосовуваний в Форте. На відміну від Pascal strings, тут розмір масиву зберігається не спільно із рядковими даними, а є частиною покажчика на рядок.

Переваги[ред. | ред. код]

  • програма в кожен момент часу містить відомості про розмір рядка, тому операції додавання символів в кінець, копіювання рядка і власне отримання розміру рядка виконуються досить швидко;
  • рядок може містити будь-які дані;
  • можливо на програмному рівні стежити за виходом за межі рядка при її обробці;
  • можливо швидке виконання операції виду «взяття N-го символу з кінця рядка».

Недоліки[ред. | ред. код]

  • проблеми зі зберіганням і обробкою символів довільної довжини;
  • збільшення витрат на зберігання рядків — значення «довжина рядка» також займає місце і в разі великої кількості рядків маленького розміру може істотно збільшити вимоги алгоритму до оперативної пам'яті;
  • обмеження максимального розміру рядка. У сучасних мовах програмування це обмеження скоріше теоретичне, так як зазвичай розмір рядка зберігається в 32-бітовому полі, що дає максимальний розмір рядка в 4 294 967 295 байт (4 гігабайти);
  • при використанні алфавіту зі змінним розміром символу (наприклад, UTF-8), в розмірі зберігається не кількість символів, а саме розмір рядка в байтах, тому кількість символів необхідно вважати окремо.

Метод «завершального байту»[ред. | ред. код]

Другий метод полягає у використанні «завершального байту»[4][5]. Одне з можливих значень символів алфавіту (як правило, це символ з кодом 0) вибирається як ознака кінця рядка, і рядок зберігається як послідовність байтів від початку до кінця. Є системи, в яких роль ознаки кінця рядка виконує не символ 0, а байт 0xFF (255) або код символу «$».

Метод має три назви — ASCIIZ (або asciiz, символи в кодуванні ASCII з нульовим завершальним байтом), C-strings (найбільшого поширення метод отримав саме в мові Сі), нуль-термінований рядок (англ. null-terminated string).

Переваги[ред. | ред. код]

  • відсутність додаткової службової інформації про рядок (крім завершального байту);
  • можливість подання рядка без створення окремого типу даних;
  • відсутність обмеження на максимальний розмір рядка;
  • економне використання пам'яті;
  • простота отримання суфіксу рядка;
  • простота передачі рядків у функції (передається покажчик на перший символ);

Недоліки[ред. | ред. код]

  • значний час виконання операцій отримання довжини і конкатенації рядків;
  • відсутність засобів контролю за виходом за межі рядка, в разі пошкодження завершального байта можливість пошкодження великих областей пам'яті, що може привести до непередбачуваних наслідків — втрати даних, краху програми і навіть всієї системи;
  • неможливість використовувати символ завершального байту як елемента рядка.
  • неможливість використовувати деякі кодування з розміром символу в кілька байт (наприклад, UTF-16), тому що у багатьох таких символах, наприклад Ā (0x0100), один з байтів дорівнює нулю (в той же час, кодування UTF-8 вільне від цього недоліку).

Використання обох методів[ред. | ред. код]

У таких мовах, як, наприклад, Оберон, рядок розміщується в масиві символів певної довжини, причому її кінець позначається нульовим символом. За замовчуванням, весь масив заповнений нульовими символами. Такий спосіб дозволяє об'єднати багато переваг обох підходів, а також уникнути більшість їх недоліків.

Подання у вигляді списку[ред. | ред. код]

Мови Erlang[6], Haskell[7], Пролог[8] використовують для рядкового типу список символів. Цей метод робить мову більш «теоретично елегантною» за рахунок дотримання ортогональності в системі типів, але приносить суттєві втрати швидкодії.

Реалізація в мовах програмування[ред. | ред. код]

  • У перших мовах програмування взагалі не було рядкового типу; програміст повинен був сам будувати функції для роботи з рядками того чи іншого типу.
  • У Сі використовуються нуль-терміновані рядки з повним ручним контролем з боку програміста.
  • У стандартному Паскалі рядок виглядає як масив з 256 байтів; перший байт зберігав довжину рядка, в інших зберігається її тіло. Таким чином, довжина рядка не може перевищувати 255 символів. У Borland Pascal 7.0 також з'явилися рядки «по типу Сі» — очевидно[кому?], через те, що в число підтримуваних платформ увійшла Windows.
  • У Object Pascal та C++ STL рядок є «чорним ящиком», в якому виділення / вивільнення пам'яті відбувається автоматично — без участі програміста. При створенні рядка пам'ять виділяється автоматично; як тільки на рядок не залишиться жодного посилання, пам'ять повертається системі. Перевага цього методу в тому, що програміст не замислюється над роботою рядків. З іншого боку, програміст має недостатній контроль над роботою програми в критичних до швидкості ділянках; також важко реалізується передача таких рядків як параметр в DLL. Також Object Pascal автоматично стежить, щоб в кінці рядка був символ з кодом 0. Тому якщо функція вимагає на вході нуль-термінований рядок, для конвертації треба просто написати PAnsiChar(рядкова_змінна) або PWideChar (рядкова_змінна) (для Pascal), змінна c_str() (для Builder / STL).
  • У C # та іншими мовами із збіркою сміття рядок є незмінним об'єктом; якщо рядок потрібно модифікувати, створюється інший об'єкт. Цей метод повільний і витрачає чимало тимчасової пам'яті, але добре поєднується з концепцією збірки сміття. Перевага цього методу в тому, що присвоювання відбувається швидко і без дублювання рядків. Також є деякий ручний контроль над конструюванням рядків (в Java, наприклад, через класи StringBuffer і StringBuilder) — це дозволяє зменшити кількість виділень і вивільнень пам'яті і, відповідно, збільшити швидкість.
  • У деяких мовах (наприклад, Standard ML) крім цього, є додатковий модуль для забезпечення ще більшої ефективності — «підрядок» (англ. substring). Його використання дозволяє виконувати операції над рядками без копіювання їхніх тіл за допомогою маніпулювання індексами початку і кінця підрядка; фізичне копіювання відбувається лише при необхідності перетворення підрядків у рядки.

Операції[ред. | ред. код]

Найпростіші операції з рядками[ред. | ред. код]

  • Отримання символу за номером позиції (індексу) — в більшості мов це тривіальна операція;
  • Конкатенація (з'єднання) рядків.

Похідні операції[ред. | ред. код]

  • Отримання підрядка за індексами початку і кінця;
  • Перевірка входження одного рядка в іншу (пошук підрядка в рядку);
  • Перевірка на збіг рядків (з урахуванням або без урахування регістру символів);
  • Отримання довжини рядка;
  • Заміна підрядка в рядку.

Операції при трактуванні рядків як списків[ред. | ред. код]

  • Згортання;
  • Відображення одного списку на інший;

Складніші операції[ред. | ред. код]

  • Знаходження мінімального надрядка, що містить всі зазначені рядки;
  • Пошук в двох масивах рядків збігаються послідовностей (завдання про плагіат).

Можливі завдання для рядків на природній мові[ред. | ред. код]

  • Порівняння на близькість зазначених рядків по заданому критерію;
  • Визначення мови і кодування тексту на підставі ймовірностей символів і складів.

Подання символів рядка[ред. | ред. код]

До останнього часу[коли?] один символ завжди кодувався одним байтом (8 двійкових бітів; застосовувалися також кодування з 7 бітами на символ), що дозволяло представляти 256 (128 при семибітному кодуванні) можливих значень. Однак для повноцінного представлення символів алфавітів кількох мов (багатомовних документів, друкарських символів — кілька видів лапок, тире, кількох видів прогалин і для написання текстів на ієрогліфічних мовах — китайською, японською та корейською) 256 символів недостатньо. Для вирішення цієї проблеми існує кілька методів:

  • Перемикання мови керуючими кодами. Метод не стандартизований і позбавляє текст самостійності (тобто послідовність символів без керуючого коду на початку втрачає сенс); використовувався в деяких ранніх русифікації ZX Spectrum і БК.
  • Використання двох або більше байт для представлення кожного символу (UTF-16, UTF-32). Головним недоліком цього методу є втрата сумісності з попередніми бібліотеками для роботи з текстом при поданні рядка як ASCIIZ. Наприклад, кінцем рядка повинен вважатися вже не байт із значенням 0, а два або чотири поспіль нульових байти, в той час як одиночний байт «0» може зустрічатися в середині рядка, що збиває бібліотеку «з пантелику».
  • Використання кодування зі змінним розміром символу. Наприклад, в UTF-8 частина символів представляється одним байтом, частина двома, трьома або чотирма. Цей метод дозволяє зберегти часткову сумісність зі старими бібліотеками (немає символів 0 всередині рядка і тому 0 можна використовувати як ознака кінця рядка), але призводить до неможливості прямої адресації символу в пам'яті за номером його позиції в рядку.

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. ↑ Мейнарович, Євген (2010). Англійсько-український словник. Математика та кібернетика. Київ: Перун.
  2. ↑ Чи правильно вживати “стрічка” в значенні “рядок”?. Процитовано 12.01.2020.
  3. ↑ Глушков В.М., ред. (1973). Енциклопедія кібернетики. Київ: Гол. ред. Української радянської енциклопедії.
  4. ↑ http://queue.acm.org/detail.cfm?id=2010365
  5. ↑ Архівована копія. Архів оригіналу за 25 вересня 2016. Процитовано 11 грудня 2016.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)
  6. ↑ Simon St. Laurent. Introducing Erlang. — O'Reilly Media, Inc., 2013. — P. 62. — 185 p. — ISBN 978-1-449-33176-4.
  7. ↑ http://book.realworldhaskell.org/read/characters-strings-and-escaping-rules.html
  8. ↑ http://www.swi-prolog.org/pldoc/man?section=text-representation


Інформаційні технології Це незавершена стаття про інформаційні технології.
Ви можете допомогти проєкту, виправивши або дописавши її.
Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. Будь ласка, допоможіть удосконалити цю статтю, додавши посилання на надійні (авторитетні) джерела. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки.
Матеріал без джерел може бути піддано сумніву та вилучено. (грудень 2018)
Міри схожості рядків
Алгоритм пошуку рядка
Множинний пошук підрядків
Вирівнювання послідовностей
Строкові структури даних
Інше
Неінтерпретовувані
Числові
Вказівник
Текстові
Складені
Інші
Пов'язані теми
Отримано з https://uk.wikipedia.org/w/index.php?title=Рядок_(програмування)&oldid=35045904