В информатике, строковый тип (англ. 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 можно использовать как признак конца строки), но приводит к невозможности прямой адресации символа в памяти по номеру его позиции в строке.

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

• Расстояние Дамерау — Левенштейна
• Расстояние Левенштейна
• Расстояние Хэмминга
• Сходство Джаро — Винклера

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

В статье не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (20 октября 2024)