В
информатике
,
строковый тип
(
англ.
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
,
Haskell
,
Пролог
используют для строкового типа
список
символов. Этот метод делает язык более «теоретически элегантным» за счёт соблюдения
ортогональности
в
системе типов
, но приносит существенные потери быстродействия.
Реализация в языках программирования
-
В первых языках программирования вообще не было строкового типа; программист должен был сам строить функции для работы со строками того или другого типа.
-
В
Си
используются
нуль-терминированные строки
с полным ручным контролем со стороны программиста.
-
В стандартном
Паскале
строка выглядит как массив из 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 можно использовать как признак конца строки), но приводит к невозможности прямой адресации символа в памяти по номеру его позиции в строке.
Лексический анализ
Для проверки соответствия всех словоформ при лексическом (семантическом) анализе используются меры схожести лексем:
См. также
Примечания
-
(неопр.)
. Дата обращения: 17 сентября 2016.
19 сентября 2016 года.
-
(неопр.)
. Дата обращения: 17 сентября 2016.
16 сентября 2016 года.
-
Simon St. Laurent.
. — O’Reilly Media, Inc., 2013. — P.
. — 185 p. —
ISBN 978-1-449-33176-4
.
-
Bryan O’Sullivan, Don Stewart, John Goerzen, Real World Haskell.
от 26 января 2012 на
Wayback Machine
-
SWI-Prolog Manual:
от 17 июля 2014 на
Wayback Machine