Строковый тип
Материал из Википедии — свободной энциклопедии
Строковый тип (в программировании) — тип данных, значениями которого является произвольная последовательность символов алфавита. Каждая переменная такого типа может быть представлен фиксированным количеством байтов или иметь произвольную длину.
Содержание |
[править] Представление в памяти
Некоторые языки программирования накладывают ограничения на максимальную длину строки, но в большинстве языков подобные ограничения отсутствуют.
Основные проблемы в машинном представлении строкового типа:
- строки могут иметь достаточно существенный размер (до нескольких десятков мегабайтов);
- изменяющийся со временем размер — возникают трудности с добавлением и удалением символов.
В представлении строк в памяти компьютера существует два принципиально разных подхода.
[править] Представление массивом символов
В этом подходе строки представляются массивом символов; при этом размер массива хранится в отдельной (служебной) области. От названия языка Pascal, где этот метод был впервые реализован, данный метод получил название Pascal Strings.
[править] Преимущества
- программа в каждый момент времени «знает» о размере строки, и операции добавления символов в конец, копирования и получения размера строки выполняются достаточно быстро;
- строка может содержать любые данные;
- возможно на программном уровне следить за выходом за границы строки при её обработке;
- возможно быстрое выполнение операции вида «взятие N-ого символа с конца строки».
[править] Недостатки
- проблемы с хранением и обработкой символов произвольной длины;
- увеличение затрат на хранение строк — значение «длина строки» также занимает место и в случае большого количества строк маленького размера может существенно увеличить требования алгоритма к оперативной памяти;
- ограничение максимального размера строки. В современных языках программирования это ограничение скорее теоретическое, так как обычно размер строки хранится в 32-битовом поле, что даёт максимальный размер строки в 2 147 483 647 байт (2 гигабайта).
[править] Метод «завершающего байта»
Второй метод заключается в использовании «завершающего байта». Одно из возможных значений символов алфавита (как правило, это символ с кодом 0) выбирается в качестве признака конца строки, и строка хранится как последовательность байтов от начала до конца. Есть системы, в которых в качестве признака конца строки используется не символ 0, а байт 0xFF (255) или код символа «$».
Метод имеет три названия — ASCIIZ (символы в кодировке ASCII с нулевым завершающим байтом), C-strings (наибольшее распространение метод получил именно в языке Си) и метод нуль-терминированных строк.
[править] Преимущества
- отсутствие дополнительной служебной информации о строке (кроме завершающего байта);
- возможность представления строки без создания отдельного типа данных;
- отсутствие ограничения на максимальный размер строки;
- экономное использование памяти;
- простота получения суффикса строки;
- возможность использовать алфавит с произвольным размером символа (например, UTF-8).
[править] Недостатки
- долгое выполнение операций получения длины и конкатенации строк;
- отсутствие средств контроля за выходом за пределы строки, в случае повреждения завершающего байта возможность повреждения больших областей памяти, что может привести к непредсказуемым последствиям — потере данных, краху программы и даже всей системы;
- невозможность использовать символ завершающего байта в качестве элемента строки.
[править] Использование обоих методов
В таких языках, как Глагол, строка размещается в массиве символов определённой длины, причём её конец обозначается нулевым символом. По умолчанию, весь массив заполнен нулевыми символами. Такой способ позволяет объединить многие преимущества обоих подходов, а также избежать большинство их недостатков.
[править] Реализация в языках программирования
- В первых языках программирования вообще не было строкового типа; программист должен был сам строить функции для работы со строками того или другого типа.
- В Си используются нуль-терминированные строки с полным ручным контролем со стороны программиста.
- В стандартном Паскале строка выглядит как массив из 256 байтов; первый байт хранил длину строки, в остальных хранится её тело. Таким образом, длина строки не может превышать 255 символов. В Borland Pascal 7.0 также появились строки «а-ля Си» — очевидно, из-за того, что в число поддерживаемых платформ вошла Windows.
- В Object Pascal строка является «чёрным ящиком», в котором выделение/высвобождение памяти происходит автоматически — без участия программиста. При создании строки память выделяется автоматически; как только на строку не останется ни одной ссылки, память возвращается системе. Преимущество этого метода в том, что программист не задумывается над работой строк. С другой стороны, программист имеет недостаточный контроль над работой программы в критичных к скорости участках; также трудно реализуется передача таких строк в качестве параметра в DLL. Также Object Pascal автоматически следит, чтобы в конце строки был символ с кодом 0. Поэтому если функция требует на входе нуль-терминированную строку, для конвертации надо просто написать
PAnsiChar(строковая_переменная)илиPWideChar(строковая_переменная). - В Java и других языках со «сборкой мусора» строка является неизменяемым объектом; если строку нужно модифицировать, создаётся другой объект. Этот метод медленный и расходует немало временной памяти, но хорошо сочетается с концепцией сборки мусора. Преимуществом этого метода в том, что при присваивании происходит быстро и без дублирования строк. Также имеется некоторый ручной контроль над конструированием строк (в Java, например, через класс
StringBuffer) — это позволяет уменьшить количество выделений и высвобождений памяти и, соответственно, увеличить скорость.
[править] Операции
[править] Простейшие операции со строками
- получение символа по номеру позиции (индексу) — в большинстве языков это тривиальная операция;
- конкатенация (соединение) строк.
[править] Производные операции
- получение подстроки по индексам начала и конца;
- проверка вхождения одной строки в другую (поиск подстроки в строке);
- проверка на совпадение строк (с учётом или без учёта регистра символов);
- получение длины строки;
- замена подстроки в строке.
[править] Операции при трактовке строк как списков
- свёртка;
- отображение одного списка на другой;
- фильтрация списка по критерию.
[править] Более сложные операции
- Нахождение минимальной надстроки, содержащей все указанные строки;
- Поиск в двух массивах строк совпадающих последовательностей (задача о плагиате).
[править] Возможные задачи для строк на естественном языке
- Сравнение на близость указанных строк по заданному критерию;
- Определение языка и кодировки текста на основании вероятностей символов и слогов.
[править] Представление символов строки
До последнего времени один символ всегда кодировался одним байтом (8 двоичных битов; применялись также кодировки с 7 битами на символ), что позволяло представлять 256 (128 при семибитной кодировке) возможных значений. Однако для полноценного представления символов алфавитов нескольких языков (многоязыковых документов, типографских символов — несколько видов кавычек, тире, нескольких видов пробелов и для написания текстов на иероглифических языках — китайском, японском и корейском) 256 символов недостаточно. Для решения этой проблемы существует несколько методов:
- Переключение языка управляющими кодами. Метод не стандартизирован и лишает текст самостоятельности (то есть последовательность символов без управляющего кода в начале теряет смысл); использовался в некоторых ранних русификациях ZX-Spectrum и БК.
- Использование двух или более байт для представления каждого символа (UTF-16, UTF-32). Главным недостатком этого метода является потеря совместимости с предыдущими библиотеками для работы с текстом при представлении строки как ASCIIZ. Например, концом строки должен считаться уже не байт со значением 0, а два или четыре подряд идущих нулевых байта, в то время как одиночный байт «0» может встречаться в середине строки, что сбивает библиотеку «с толку».
- Использование кодировки с переменным размером символа. Например, в UTF-8 часть символов представляется одним байтом, часть двумя, тремя или четырьмя. Этот метод позволяет сохранить частичную совместимость со старыми библиотеками (нет символов 0 внутри строки и поэтому 0 можно использовать как признак конца строки), но приводит к невозможности прямой адресации символа в памяти по номеру его позиции в строке.
[править] См. также
- Нуль-терминированная строка
- Свободная полугруппа
- Лексикографический порядок
- Алгоритмы на строках
- Unicode
- Слово (математика)
 |
Это незавершённая статья о компьютерном программном обеспечении. Вы можете помочь проекту, исправив и дополнив её. |
