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

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

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

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

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

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

В представлении строк в памяти компьютера существует два принципиально разных подхода.

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

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

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

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

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

Недостатки

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

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

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

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

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

отсутствие дополнительной служебной информации о строке (кроме завершающего байта);
возможность представления строки без создания отдельного типа данных;
отсутствие ограничения на максимальный размер строки;
экономное использование памяти;
простота получения суффикса строки;
простота передачи строк в функции (передаётся указатель на первый символ);

Недостатки

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

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

В таких языках, как, например, Оберон, строка размещается в массиве символов определённой длины, причём её конец обозначается нулевым символом. По умолчанию, весь массив заполнен нулевыми символами. Такой способ позволяет объединить многие преимущества обоих подходов, а также избежать большинство их недостатков.

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

Языки Erlang^[3], Haskell^[4], Пролог^[5] используют для строкового типа список символов. Этот метод делает язык более «теоретически элегантным» за счёт соблюдения ортогональности в системе типов, но приносит существенные потери быстродействия.

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

В первых языках программирования вообще не было строкового типа; программист должен был сам строить функции для работы со строками того или другого типа.
В Си используются нуль-терминированные строки с полным ручным контролем со стороны программиста.
В стандартном Паскале строка выглядит как массив из 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). Его использование позволяет выполнять операции над строками без копирования их тел посредством манипулирования индексами начала и конца подстроки; физическое копирование происходит лишь при необходимости преобразовании подстрок в строки.

Операции

Простейшие операции со строками:

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

Производные операции:

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

Операции при трактовке строк как списков:

свёртка;
отображение одного списка на другой;
фильтрация списка по критерию.

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

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

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

сравнение на близость указанных строк по заданному критерию;
определение языка и кодировки текста на основании вероятностей символов и слогов.

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

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

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

Лексический анализ

Для проверки соответствия всех словоформ при лексическом (семантическом) анализе используются меры схожести лексем:

См. также

Примечания

↑ The Most Expensive One-byte Mistake — ACM Queue (неопр.). Дата обращения: 17 сентября 2016. Архивировано 19 сентября 2016 года.
↑ Joel on Software - Назад, к основам (неопр.). Дата обращения: 17 сентября 2016. Архивировано 16 сентября 2016 года.
↑ Simon St. Laurent. Introducing Erlang. — O’Reilly Media, Inc., 2013. — P. 62. — 185 p. — ISBN 978-1-449-33176-4.
↑ Bryan O’Sullivan, Don Stewart, John Goerzen, Real World Haskell. Appendix B. Characters, strings, and escaping rules Архивная копия от 26 января 2012 на Wayback Machine
↑ SWI-Prolog Manual: 5.2.2 Representing text: strings, atoms and code lists Архивная копия от 17 июля 2014 на Wayback Machine

[1] The Most Expensive One-byte Mistake — ACM Queue (неопр.). Дата обращения: 17 сентября 2016. Архивировано 19 сентября 2016 года.

[2] Joel on Software - Назад, к основам (неопр.). Дата обращения: 17 сентября 2016. Архивировано 16 сентября 2016 года.

[3] Simon St. Laurent. Introducing Erlang. — O’Reilly Media, Inc., 2013. — P. 62. — 185 p. — ISBN 978-1-449-33176-4.

[4] Bryan O’Sullivan, Don Stewart, John Goerzen, Real World Haskell. Appendix B. Characters, strings, and escaping rules Архивная копия от 26 января 2012 на Wayback Machine

[5] SWI-Prolog Manual: 5.2.2 Representing text: strings, atoms and code lists Архивная копия от 17 июля 2014 на Wayback Machine

[1]

[2]

[3]

[4]

[5]