Строковый тип

Строковый тип данных (англ. string «нить, вереница») — тип данных в области информатики, который допускает произвольный набор символов алфавита в качестве допустимых значений. Переменная, принадлежащая этому типу (строковая переменная), может быть задана с фиксированной длиной в байтах или же обладать переменной длиной.

Представление в памяти

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

Ключевые проблемы представления строкового типа на уровне машины:

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

Существует два фундаментально различающихся метода представления строк в памяти компьютера.

Представление массивом символов

В этом методе строки представлены массивом символов, причём размер самого массива указывается в отдельной (служебной) области. Отметим, что этот способ получил своё название от языка Pascal, где он впервые и был реализован, и поэтому такие строки называют Pascal strings.

Более оптимизированный вид этого метода известен как формат c-addr u (от англ. character-aligned address + unsigned number), который используется в Форте. В отличие от Pascal strings, здесь размер массива не хранится совместно с данными строки, а включён в указатель на строку.

Преимущества

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

Недостатки

• сложности с хранением и обработкой символов переменной длины;
• увеличение памяти для хранения строк: дополнительное место занимает информация о длине строки, что при большом количестве коротких строк может значительно повысить требования к оперативной памяти;
• существуют ограничения на максимальную длину строки. В современных языках программирования это ограничение в основном теоретическое, так как длина строки обычно хранится в 32-битовом поле, обеспечивающем максимум длины строки в 4 294 967 295 байт (4 гигабайта);
• если используется алфавит с переменной шириной символа (например, UTF-8), то в размере строки хранится не количество символов, а общий размер в байтах, поэтому количество символов приходится вычислять отдельно.

Метод «завершающего байта»

Второй подход основывается на применении «окончательного байта». Для обозначения конца строки в алфавите выбирается один из символов (чаще всего это символ, соответствующий коду 0), и строка хранится как непрерывная последовательность байтов от начального до конечного символа. В некоторых системах, в качестве маркера конца строки может использоваться не символ 0, а байт 0xFF (255) или знак "$".

Метод известен под тремя названиями: ASCIIZ (или asciz, символы из набора ASCII, завершающиеся нулевым байтом), C-strings (метод наиболее распространен в языке Си) и метод нуль-терминированных строк.

Преимущества

Этот метод обладает следующими достоинствами:

• Эффективность в использовании памяти. Так как строки оканчиваются одиночным символом, это позволяет экономить место, по сравнению с методами, требующими дополнительные служебные байты для хранения длины строки.
• Простота и универсальность. Сама по себе идея нуль-терминированной строки достаточно проста и широко применима в различных языках программирования и операционных системах, что делает её стандартом де-факто в программировании.
• Легкость обработки. Благодаря тому, что строки завершаются нулевым байтом, многие функции стандартных библиотек могут легко манипулировать строками, избегая сложных операций по отслеживанию их длины.
• Совместимость с множеством стандартов и инструментов. Такие строки хорошо интегрируются с разнообразными средствами и стандартами, уже существующими в экосистеме разработки программного обеспечения.
• Удобство в реализации. Многие языки программирования, включая Си, имеют встроенные функции и библиотеки, непосредственно работающие с таким методом хранения строк, что упрощает задачу для программистов.
• отсутствие дополнительных метаданных о строке (за исключением завершающего байта);
• возможность представления строки без необходимости создавать специальный тип данных;
• отсутствие ограничений на длину строки;
• эффективное использование памяти;
• легкость получения суффикса строки;
• удобство передачи строк в функции (через указатель на первый символ строки).

Недостатки

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

Использование обоих методов

В языках программирования, таких как Оберон, строки хранятся в фиксированных массивах символов, где конец строки помечается нулем. Изначально весь массив заполняется нулями. Этот метод объединяет преимущества обоих подходов, при этом минимизируя их недостатки.

Erlang

В языке Erlang строки, как правило, представлены в виде списков кодов символов, каждый из которых представляет собой Unicode-значение. Подобный подход обеспечивает лучшую интеграцию с функциональным стилем программирования, а также гибкость при обработке строковых данных, позволяя применять мощные паттерны кода. Haskell и Пролог применяют списки символов для строкового типа данных. Этот подход делает язык более «теоретически элегантным» благодаря поддержанию ортогональности в системе типов, однако сопровождается значительным снижением производительности.

Реализация в языках программирования

• В первых программных языках строчного типа данных не существовало; программист сам разрабатывал функции для работы с различными типами строк.
• В Си применяются нуль-терминированные строки, предоставляя программисту полный контроль над ними.
• В стандартном Паскале строка представлена как массив из 256 байтов; начальный байт содержит длину строки, а остальные - её содержание. Таким образом, максимальная длина строки ограничена 255 символами. В Borland Pascal 7.0 также появились строки по примеру «а-ля Си», что связано с поддержкой платформы WindowsWindows.
• В Object Pascal и C++ STL строки являются «чёрным ящиком», где память выделяется и освобождается автоматически, без вмешательства программиста. При создании строки память выделяется автоматически; как только все ссылки на строку удалены, память возвращается системе. Это упрощает работу со строками для программиста, но также снижает контроль над критичными к скорости участками программы и усложняет передачу таких строк как параметров в DLLDLL. Кроме того, в Object Pascal автоматически следят за наличием символа с кодом 0 в конце строки. Поэтому для передачи нуль-терминированной строки в функцию достаточно написать PAnsiChar(строковая_переменная) или PWideChar(строковая_переменная) (для Pascal), переменная.c_str() (для Builder/STL).
• В C# и других языках с сборкой мусора строки являются неизменяемыми объектами; для модификации строки создаётся новый объект. Этот метод замедляет процесс и требует больше временной памяти, но хорошо сочетается с концепцией сборки мусора. Преимущество в том, что присваивание строк происходит быстро и без дублирования.
• Определённый контроль над созданием строк присущ некоторым языкам программирования, как, например, в JavaJava, через использование классов StringBuffer и StringBuilder, что способствует снижению числа операций по выделению и освобождению памяти, а также ускоряет процесс.
• В нескольких языках программирования, таких как Standard ML, дополнительно присутствует модуль для повышения эффективности работы со строками под названием «подстрока» (SubString). Этот механизм позволяет проводить манипуляции над строками без их копирования, просто работая с индексами начала и конца подстроки; фактическое копирование происходит только тогда, когда требуется преобразование подстрок обратно в строки.

Операции

Базовые манипуляции со строками

• Извлечение символа по указанному индексу — в большинстве языков это простая операция;
• Конкатенация (слияние) строк.

Расширенные манипуляции

• Извлечение подстроки по начальным и конечным индексам;
• Определение наличия одной строки внутри другой (поиск подстроки) через строку;
• Сравнение строк на соответствие (с учетом или без учета регистра символов);
• Подсчет количества символов в строке;
• Замена части строки другой подстрокой.

Операции при работе со строками как с списками

• свёртка списка;
• Преобразование одного списка в другой через сопоставление;
• Отбор элементов списка по определенному критерию.

Усложненные операции

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

Возможные задачи с естественными языками

• Сравнение строк по близости по заданным параметрам;
• Определение языка и кодировки текста, основываясь на вероятности появления символов и слогов.

Представление символов строки

До принятия стандарта Unicode в 1991 году, символы кодировались обычно одним байтом (в 8 двоичных бит либо меньше — 7-битные, 6-битные). 8-битные схемы кодирования предоставляли 256 возможных значений. Однако, этого числа оказалось недостаточно для корректного отображения символов алфавитов множества языков (многоязычных документов, типографских символов — различных типов кавычек, тире, различных пробелов, а также для текста на иероглифических языках, таких как китайский, японский и корейский). В связи с этим возникли несколько решений:

• Переключение языка с использованием управляющих кодов. Этот способ не стандартизирован и делает текст зависимым (последовательность символов без управляющего кода становится бессмысленной); использовался в некоторых ранних русификациях ZX-Spectrum и БК.
• Применение для кодирования каждого символа двух или более байтов (UTF-16, UTF-32). Основной минус данного способа — потеря совместимости с существующими библиотеками, использующими кодировку ASCIIZ. Например, концом строки уже считается не просто нулевой байт, а два или четыре подряд идущих нуля, при этом одиночный нулевой байт может появляться в середине строки, что запутывает библиотеку.
• Использование кодировок с переменной длиной символов. В случае с UTF-8, некоторые символы кодируются одним байтом, другие — двумя, тремя или четырьмя. Это обеспечивает частичную совместимость с устаревшими библиотеками (внутри строки нет символов с кодом 0, что позволяет использовать нулевой байт как конец строки), но делает невозможной прямую адресацию символов по их позиции в строке.

См. также

• Нуль-терминированная строка
• Пустая строка
• Текстовые данные
• Свободная полугруппа
• Лексикографический порядок
• Алгоритмы на строках
• Слово (математика)
• Теория последовательностей
• Широкий символ