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

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

Содержание

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

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

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

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

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

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

Преимущества метода:

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

Недостатки метода:

  • проблемы с хранением и обработкой символов произвольной длины
  • увеличение затрат на хранение строк: значение "длина строки" так же занимает место и в случае большого количества строк маленького размера может существенно увеличить требования алгоритма к оперативной памяти
  • ограничение максимального размера строки. В современных языках программирования это ограничение скорее теоретическое, обычно размер строки хранится в 32-битовом поле, что даёт приблизительный максимальный размер строки в 2 Гб.

Названия метода: Pascal Strings

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

Преимущества метода:

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

Недостатки метода:

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

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

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

  • В первых языках программирования вообще не было строкового типа; программист должен был сам строить функции для работы со строками того или другого типа.
  • В языке Си: используются нуль-терминированные строки, при этом программист сам имеет дело с отводом/высвобождением памяти. Преимущество в высокой скорости и полном контроле; недостаток в том, что этот метод чреват ошибками.
  • В стандартном Паскале: строка имеет вид массива жёстко заданной длины; первый байт задаёт длину строки. Преимущество в высокой скорости; недостаток — ограничение на длину строки в 255 символов, плюс перерасход памяти, если мы имеем дело с короткими строками.
  • В Object Pascal строка является «чёрным ящиком», в котором выделение/высвобождение памяти происходит автоматически и без участия программиста. При создании строки память автоматически выделяется; как только на строку не останется ни одной ссылки, память возвращается системе. Преимущество этого метода в том, что программист не задумывается над работой строк. С другой стороны, программист имеет недостаточный контроль над работой программы в критичных к скорости участках; также трудно реализуется передача таких строк в качестве параметра в DLL.
Object Pascal автоматически следит, чтобы в конце строки был символ с кодом 0. Поэтому если функция требует на входе нуль-терминированную строку, для конвертации надо просто написать PChar(s).
  • В Java и других языках со сборкой мусора: строка является неизменным объектом; если строку нужно модифицировать, создаётся другой объект. Этот метод медленный и расходует немало временной памяти, но хорошо сочетается с концепцией сборки мусора. Преимуществом этого метода в том, что при присваивание происходит быстро и без дублирования строк. Также есть некоторый ручной контроль над конструированием строк (в Java, например, через класс StringBuffer) — это позволит уменьшить количество выделений и высвобождений памяти и, соответственно, увеличить скорость.

Операции

Основные операции со строковыми данными:

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

Так же строки могут трактоваться как списки, и к ним могут быть применены следующие операции:

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

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

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

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

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

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

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

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

Подробнее о многобайтовых кодировках см. Unicode.

См. также

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home