imported>DenisKrivosheev: /* Представление символов строки */ исправление

2025-11-30T11:56:32Z

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

Новая страница

В [[информатика|информатике]], '''строковый тип''' ({{lang-en|string type}}) — [[тип данных]], значениями которого является произвольная последовательность (строка) символов [[Алфавит (информатика)|алфавита]]. Каждая переменная такого типа ('''строковая переменная''') может быть представлена фиксированным количеством [[байт]]ов либо иметь произвольную длину.

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

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

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

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

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

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

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

=== Метод «завершающего байта» ===
{{main|Нуль-терминированная строка}}

Второй метод заключается в использовании ''«завершающего байта»''<ref>{{Cite web |url=http://queue.acm.org/detail.cfm?id=2010365 |title=The Most Expensive One-byte Mistake — ACM Queue |access-date=2016-09-17 |archive-date=2016-09-19 |archive-url=https://web.archive.org/web/20160919163315/http://queue.acm.org/detail.cfm?id=2010365 |url-status=live }}</ref><ref>{{Cite web |url=http://local.joelonsoftware.com/wiki/%D0%9D%D0%B0%D0%B7%D0%B0%D0%B4,_%D0%BA_%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D0%B0%D0%BC |title=Joel on Software - Назад, к основам |access-date=2016-09-17 |archive-date=2016-09-16 |archive-url=https://web.archive.org/web/20160916212518/http://local.joelonsoftware.com/wiki/%D0%9D%D0%B0%D0%B7%D0%B0%D0%B4,_%D0%BA_%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D0%B0%D0%BC |url-status=live }}</ref>. Одно из возможных значений символов алфавита (как правило, это символ с кодом 0) выбирается в качестве признака конца строки, и строка хранится как последовательность байтов от начала до конца. Есть системы, в которых в качестве признака конца строки используется не символ 0, а байт 0xFF (255) или код символа «$».

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

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

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

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

=== Представление в виде списка ===
Языки [[Erlang]]<ref>{{книга
| автор = Simon St. Laurent
| заглавие = Introducing Erlang
| ссылка = https://archive.org/details/introducingerlan00laur
| издательство = O’Reilly Media, Inc.
| год = 2013
| allpages = 185
| pages = [https://archive.org/details/introducingerlan00laur/page/n77 62]
| isbn = 978-1-449-33176-4
| ref = Simon St. Laurent
}}</ref>, [[Haskell]]<ref>Bryan O’Sullivan, Don Stewart, John Goerzen, Real World Haskell. [http://book.realworldhaskell.org/read/characters-strings-and-escaping-rules.html Appendix B. Characters, strings, and escaping rules] {{Wayback|url=http://book.realworldhaskell.org/read/characters-strings-and-escaping-rules.html |date=20120126041437 }}</ref>, [[Пролог (язык программирования)|Пролог]]<ref>SWI-Prolog Manual: [http://www.swi-prolog.org/pldoc/man?section=text-representation 5.2.2 Representing text: strings, atoms and code lists] {{Wayback|url=http://www.swi-prolog.org/pldoc/man?section=text-representation |date=20140717093340 }}</ref> используют для строкового типа [[Связный список|список]] символов. Этот метод делает язык более «теоретически элегантным» за счёт соблюдения [[ортогональность|ортогональности]] в [[система типов|системе типов]], но приносит существенные потери быстродействия.

== Реализация в языках программирования ==
* В первых языках программирования вообще не было строкового типа; программист должен был сам строить функции для работы со строками того или другого типа.
* В [[Си (язык программирования)|Си]] используются [[нуль-терминированная строка|нуль-терминированные строки]] с полным ручным контролем со стороны программиста.
* В стандартном [[Паскаль (язык программирования)|Паскале]] строка выглядит как массив из 256 байтов; первый байт хранил длину строки, в остальных хранится её тело. Таким образом, длина строки не может превышать 255 символов. В [[Borland Pascal]] 7.0 также появились строки «а-ля Си» — очевидно, из-за того, что в число поддерживаемых платформ вошла [[Windows]].
* В [[Object Pascal]] и C++ [[Стандартная библиотека шаблонов|STL]] строка является «чёрным ящиком», в котором выделение/высвобождение памяти происходит автоматически — без участия [[программист]]а. При создании строки память выделяется автоматически; как только на строку не останется ни одной ссылки, память возвращается системе. Преимущество этого метода в том, что программист не задумывается над работой строк. С другой стороны, программист имеет недостаточный контроль над работой программы в критичных к скорости участках; также трудно реализуется передача таких строк в качестве параметра в [[DLL]]. Также Object Pascal автоматически следит, чтобы в конце строки был символ с кодом 0. Поэтому если функция требует на входе [[нуль-терминированная строка|нуль-терминированную строку]], для конвертации надо просто написать <code>PAnsiChar(''строковая_переменная'')</code> или <code>PWideChar(''строковая_переменная'')</code> (для Pascal), <code>''переменная''.c_str()</code> (для Builder/STL).
* В [[C Sharp|C#]] и других языках со [[сборка мусора (программирование)|сборкой мусора]] строка является неизменяемым объектом; если строку нужно модифицировать, создаётся другой объект. Этот метод медленный и расходует немало временной памяти, но хорошо сочетается с [[концепция|концепцией]] сборки мусора. Преимущество этого метода в том, что [[присваивание]] происходит быстро и без дублирования строк. Также имеется некоторый ручной контроль над конструированием строк (в [[Java]], например, через классы <code>StringBuffer и StringBuilder</code>) — это позволяет уменьшить количество выделений и высвобождений памяти и, соответственно, увеличить скорость.
** В некоторых языках (например, [[Standard ML]]) кроме этого, есть дополнительный модуль для обеспечения ещё большей эффективности — «подстрока» (SubString). Его использование позволяет выполнять операции над строками без копирования их тел посредством манипулирования индексами начала и конца подстроки; физическое копирование происходит лишь при необходимости преобразовании подстрок в строки.

== Операции ==
'''Простейшие операции со строками:'''
* получение символа по номеру позиции (индексу) — в большинстве языков это тривиальная операция;
* [[конкатенация]] (соединение) строк.

'''Производные операции:'''
* получение [[подстрока|подстроки]] по индексам начала и конца;
* проверка вхождения одной строки в другую ([[поиск подстроки]] в строке);
* проверка на совпадение строк ([[Чувствительность к регистру символов|с учётом или без учёта регистра символов]]);
* получение длины строки;
* замена подстроки в строке.

'''Операции при трактовке строк как [[Список (информатика)|списков]]:'''
* [[Свёртка списка|свёртка]];
* отображение одного списка на другой;
* фильтрация списка по критерию.

'''Более сложные операции:'''
* нахождение минимальной [[надстрока|надстроки]], содержащей все указанные строки;
* поиск в двух массивах строк совпадающих последовательностей ''([[задача о плагиате]])''.

'''Возможные задачи для строк на [[естественный язык|естественном языке]]:'''
* сравнение на близость указанных строк по заданному критерию;
* определение языка и [[кодировка|кодировки]] текста на основании вероятностей символов и слогов.

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

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

== Лексический анализ ==
Для проверки соответствия всех словоформ при лексическом (семантическом) анализе используются меры схожести лексем:
* [[Расстояние Дамерау — Левенштейна]]
* [[Расстояние Левенштейна]]
* [[Расстояние Хэмминга]]
* [[Сходство Джаро — Винклера]]

== См. также ==
* [[Нуль-терминированная строка]]
* [[Пустая строка]]
* [[Текстовые данные]]
* [[Свободная полугруппа]]
* [[Лексикографический порядок]]
* [[Список алгоритмов#Алгоритмы на строках|Алгоритмы на строках]]
* [[Слово (математика)]]
* [[Теория последовательностей]]
* [[Широкий символ]]

== Примечания ==
{{примечания}}


{{Типы данных}}
{{Строки}}
{{Нет источников |дата=2009-11-29}}

[[Категория:Типы данных]]
[[Категория:Строковые алгоритмы|*]]
[[Категория:Примитивные типы данных]]

Строковый тип - История изменений

imported>DenisKrivosheev: /* Представление символов строки */ исправление