В компьютерном программировании строка традиционно является последовательностью символов , либо как литеральная константа , либо как некоторая переменная . Последнее может позволять изменять ее элементы и изменять длину, или она может быть фиксированной (после создания). Строка обычно рассматривается как тип данных и часто реализуется как структура данных массива байтов (или слов ) , которая хранит последовательность элементов, как правило, символов, используя некоторую кодировку символов . Строка может также обозначать более общие массивы или другие типы данных и структуры последовательностей (или списков ).
В зависимости от языка программирования и точного типа используемых данных переменная , объявленная как строка, может либо привести к статическому выделению памяти на заранее определенную максимальную длину, либо использовать динамическое выделение , чтобы позволить ей хранить переменное количество элементов.
Когда строка появляется в исходном коде буквально , она называется строковым литералом или анонимной строкой. [1]
В формальных языках , используемых в математической логике и теоретической информатике , строка представляет собой конечную последовательность символов , выбранных из набора, называемого алфавитом .
Основная цель строк — хранить текст, читаемый человеком, например, слова и предложения. Строки используются для передачи информации от компьютерной программы пользователю программы. [2] Программа также может принимать строковый ввод от пользователя. Кроме того, строки могут хранить данные, выраженные в виде символов, но не предназначенные для чтения человеком.
Примеры строк и их назначение:
file upload complete" — это строка, которую программное обеспечение показывает конечным пользователям . В исходном коде программы это сообщение, скорее всего, будет отображаться как строковый литерал .I got a new job today" как обновление статуса в социальной сети . Вместо строкового литерала программное обеспечение, скорее всего, сохранит эту строку в базе данных .AGATGCCGT", представляющие последовательности нуклеиновых кислот ДНК . [3]?action=edit URL . Часто они предназначены для того, чтобы быть в некоторой степени читаемыми человеком, хотя их основная цель — общаться с компьютерами.Термин «строка» может также обозначать последовательность данных или компьютерных записей, отличных от символов, например «строку битов », но при использовании без уточнения он относится к строкам символов. [4]
Использование слова «строка» для обозначения любых элементов, расположенных в линию, ряд или последовательность, восходит к векам. [5] [6] В наборном деле 19-го века наборщики использовали термин «строка» для обозначения длины шрифта, напечатанного на бумаге; строка измерялась для определения оплаты труда наборщика. [7] [4] [8]
Использование слова «строка» для обозначения «последовательности символов или языковых элементов в определенном порядке» возникло в математике, символической логике и лингвистической теории , чтобы говорить о формальном поведении символических систем, оставляя в стороне значение символов. [4]
Например, логик К. И. Льюис писал в 1918 году: [9]
Математическая система — это любой набор строк узнаваемых знаков, в котором некоторые строки берутся изначально, а остальные выводятся из них с помощью операций, выполняемых в соответствии с правилами, которые не зависят от какого-либо значения, приписываемого знакам. То, что система должна состоять из «знаков», а не звуков или запахов, несущественно.
По словам Жана Э. Саммета , «первым реалистичным языком обработки строк и сопоставления с образцом» для компьютеров был COMIT в 1950-х годах, за которым в начале 1960-х годов последовал язык SNOBOL . [10]
Строковый тип данных — это тип данных, смоделированный на основе идеи формальной строки. Строки — настолько важный и полезный тип данных, что они реализованы практически в каждом языке программирования . В некоторых языках они доступны как примитивные типы , а в других — как составные типы . Синтаксис большинства языков программирования высокого уровня позволяет строке, обычно заключенной в кавычки, представлять экземпляр строкового типа данных; такая метастрока называется литералом или строковым литералом .
Хотя формальные строки могут иметь произвольную конечную длину, длина строк в реальных языках часто ограничена искусственным максимумом. В общем, существует два типа строковых типов данных: строки фиксированной длины , которые имеют фиксированную максимальную длину, определяемую во время компиляции , и которые используют тот же объем памяти, нужен этот максимум или нет, и строки переменной длины , длина которых произвольно не фиксирована и которые могут использовать различные объемы памяти в зависимости от фактических требований во время выполнения (см. Управление памятью ). Большинство строк в современных языках программирования являются строками переменной длины. Конечно, даже строки переменной длины ограничены по длине — размером доступной памяти компьютера . Длина строки может храниться как отдельное целое число (что может накладывать еще одно искусственное ограничение на длину) или неявно через символ завершения, обычно символьное значение со всеми нулевыми битами, как в языке программирования C. См. также «Null-terminated» ниже.
Строковые типы данных исторически выделяли один байт на символ, и, хотя точный набор символов различался в зависимости от региона, кодировки символов были достаточно похожи, чтобы программисты могли часто игнорировать это, поскольку символы, которые программа обрабатывала особым образом (например, точка, пробел и запятая), находились в одном и том же месте во всех кодировках, с которыми могла столкнуться программа. Эти наборы символов обычно основывались на ASCII или EBCDIC . Если текст в одной кодировке отображался в системе, использующей другую кодировку, текст часто искажался , хотя часто был несколько читаемым, и некоторые пользователи компьютеров научились читать искалеченный текст.
Логографическим языкам, таким как китайский , японский и корейский (известные под общим названием CJK ), для разумного представления требуется гораздо больше, чем 256 символов (ограничение в один 8-битный байт на символ кодировки). Обычные решения включали сохранение однобайтовых представлений для ASCII и использование двухбайтовых представлений для идеограмм CJK . Использование их с существующим кодом приводило к проблемам с сопоставлением и разрезанием строк, серьезность которых зависела от того, как была разработана кодировка символов. Некоторые кодировки, такие как семейство EUC, гарантируют, что байтовое значение в диапазоне ASCII будет представлять только этот символ ASCII, что делает кодировку безопасной для систем, использующих эти символы в качестве разделителей полей. Другие кодировки, такие как ISO-2022 и Shift-JIS, не дают таких гарантий, что делает сопоставление по байтовым кодам небезопасным. Эти кодировки также не были «самосинхронизирующимися», поэтому для определения границ символов требовалось вернуться к началу строки, а склеивание двух строк могло привести к повреждению второй строки.
Unicode несколько упростил картину. В большинстве языков программирования теперь есть тип данных для строк Unicode. Предпочтительный формат потока байтов Unicode UTF-8 разработан так, чтобы не иметь проблем, описанных выше для старых многобайтовых кодировок. UTF-8, UTF-16 и UTF-32 требуют, чтобы программист знал, что кодовые единицы фиксированного размера отличаются от «символов», основная трудность в настоящее время заключается в неправильно спроектированных API, которые пытаются скрыть это различие (UTF-32 делает кодовые точки фиксированного размера, но они не являются «символами» из-за составных кодов).
Некоторые языки, такие как C++ , Perl и Ruby , обычно позволяют изменять содержимое строки после ее создания; такие строки называются изменяемыми . В других языках, таких как Java , JavaScript , Lua , Python и Go , значение фиксировано, и для внесения каких-либо изменений необходимо создать новую строку; такие строки называются неизменяемыми . Некоторые из этих языков с неизменяемыми строками также предоставляют другой тип, который является изменяемыми, например Java и .NET , StringBuilderпотокобезопасный Java StringBufferи Cocoa NSMutableString . У неизменяемости есть как преимущества, так и недостатки: хотя неизменяемые строки могут потребовать неэффективного создания множества копий, они проще и полностью потокобезопасны .
Строки обычно реализуются как массивы байтов, символов или кодовых единиц, чтобы обеспечить быстрый доступ к отдельным единицам или подстрокам, включая символы, когда они имеют фиксированную длину. Некоторые языки, такие как Haskell, реализуют их как связанные списки .
Некоторые языки, такие как Prolog и Erlang , вообще избегают реализации специального строкового типа данных, принимая вместо этого соглашение о представлении строк в виде списков кодов символов.
Представления строк сильно зависят от выбора набора символов и метода кодирования символов. Более старые реализации строк были разработаны для работы с набором и кодировкой, определенными ASCII или более поздними расширениями, такими как серия ISO 8859. Современные реализации часто используют обширный набор, определенный Unicode, вместе с различными сложными кодировками, такими как UTF-8 и UTF-16.
Термин строка байтов обычно указывает на строку байтов общего назначения, а не на строки только (читаемых) символов, строки битов и т. п. Строки байтов часто подразумевают, что байты могут принимать любое значение и любые данные могут храниться как есть, то есть не должно быть значения, интерпретируемого как конечное значение.
Большинство реализаций строк очень похожи на массивы переменной длины , в записях которых хранятся коды соответствующих символов. Главное отличие состоит в том, что в некоторых кодировках один логический символ может занимать более одной записи в массиве. Это происходит, например, с UTF-8, где одиночные коды ( кодовые точки UCS ) могут занимать от одного до четырех байтов, а одиночные символы могут занимать произвольное количество кодов. В этих случаях логическая длина строки (количество символов) отличается от физической длины массива (количество используемых байтов). UTF-32 избегает первой части проблемы.
Длина строки может быть сохранена неявно с помощью специального завершающего символа; часто это нулевой символ (NUL), все биты которого равны нулю, соглашение, используемое и увековеченное популярным языком программирования C. [ 11] Следовательно, это представление обычно называют строкой C. Это представление строки из n символов занимает n + 1 место (1 для завершающего символа) и, таким образом, является неявной структурой данных .
В терминированных строках терминальный код не является допустимым символом в любой строке. Строки с полем длины не имеют этого ограничения и также могут хранить произвольные двоичные данные .
Пример строки с завершающим нулем, сохраненной в 10-байтовом буфере , вместе с ее представлением ASCII (или более современным UTF-8 ) в виде 8-битных шестнадцатеричных чисел :
Длина строки в приведенном выше примере, " FRANK", составляет 5 символов, но она занимает 6 байт. Символы после терминатора не являются частью представления; они могут быть либо частью других данных, либо просто мусором. (Строки такой формы иногда называют строками ASCIZ , по названию исходной директивы языка ассемблера , используемой для их объявления.)
Использование специального байта, отличного от нуля, для завершения строк исторически появлялось как в аппаратном, так и в программном обеспечении, хотя иногда со значением, которое также было печатным символом. $использовался многими ассемблерными системами, :использовался системами CDC (этот символ имел значение ноль), а ZX80 использовал "[12] , поскольку это был разделитель строк в его языке BASIC.
Несколько похожие машины «обработки данных», такие как IBM 1401, использовали специальный бит -маркер слова для разграничения строк слева, где операция начиналась справа. Этот бит должен был быть очищен во всех других частях строки. Это означало, что, хотя у IBM 1401 было семибитное слово, почти никто никогда не думал использовать это как функцию и переопределять назначение седьмого бита для (например) обработки кодов ASCII.
Раннее программное обеспечение микрокомпьютеров полагалось на тот факт, что коды ASCII не используют старший бит, и устанавливало его для указания конца строки. Он должен быть сброшен на 0 перед выводом. [13]
Длина строки также может храниться явно, например, путем добавления к строке префикса длины в виде байтового значения. Это соглашение используется во многих диалектах Pascal ; как следствие, некоторые называют такую строку строкой Pascal или P-строкой . Сохранение длины строки в виде байта ограничивает максимальную длину строки до 255. Чтобы избежать таких ограничений, улучшенные реализации P-строк используют 16-, 32- или 64-битные слова для хранения длины строки. Когда поле длины охватывает адресное пространство , строки ограничены только доступной памятью .
Если длина ограничена, то ее можно закодировать в постоянном пространстве, обычно машинном слове, что приводит к неявной структуре данных , занимающей n + k пространства, где k — количество символов в слове (8 для 8-битного ASCII на 64-битной машине, 1 для 32-битного UTF-32/UCS-4 на 32-битной машине и т. д.). Если длина не ограничена, кодирование длины n занимает log( n ) пространства (см. код фиксированной длины ), поэтому строки с префиксом длины являются краткой структурой данных , кодирующей строку длины n в log( n ) + n пространства.
В последнем случае само поле префикса длины не имеет фиксированной длины, поэтому фактические данные строки необходимо перемещать, когда строка увеличивается настолько, что требуется увеличить поле длины.
Вот строка Pascal, сохраненная в 10-байтовом буфере, вместе с ее представлением ASCII / UTF-8:
Во многих языках, включая объектно-ориентированные, строки реализуются как записи с внутренней структурой, подобной:
класс строка { size_t длина ; символ * текст ; }; Однако, поскольку реализация обычно скрыта , доступ к строке и ее изменение должны осуществляться через функции-члены. text— это указатель на динамически выделенную область памяти, которая может быть расширена по мере необходимости. См. также string (C++) .
Строки ограничиваются как кодами завершения символа, так и кодами длины: например, массивы символов C, содержащие нулевые (NUL) символы, не могут обрабатываться напрямую функциями библиотеки строк C : строки, использующие код длины, ограничены максимальным значением кода длины.
Оба эти ограничения можно преодолеть с помощью грамотного программирования.
Можно создавать структуры данных и функции, которые ими манипулируют, не имеющие проблем, связанных с завершением символов, и в принципе способные преодолеть ограничения длины кода. Также можно оптимизировать строку, представленную с помощью методов кодирования длины серии (замена повторяющихся символов на значение символа и длину) и кодирования Хэмминга [ требуется разъяснение ] .
Хотя эти представления являются общими, возможны и другие. Использование веревок делает некоторые операции со строками, такие как вставки, удаления и конкатенации, более эффективными.
Основная структура данных в текстовом редакторе — это та, которая управляет строкой (последовательностью символов), которая представляет текущее состояние редактируемого файла. Хотя это состояние может храниться в одном длинном последовательном массиве символов, типичный текстовый редактор вместо этого использует альтернативное представление в качестве своей структуры данных последовательности — буфер пробелов , связанный список строк, таблицу частей или веревку — что делает определенные операции со строками, такие как вставки, удаления и отмена предыдущих правок, более эффективными. [14]
Различная структура памяти и требования к хранению строк могут повлиять на безопасность программы, обращающейся к строковым данным. Строковые представления, требующие завершающего символа, обычно подвержены проблемам переполнения буфера , если завершающий символ отсутствует, что вызвано ошибкой кодирования или злоумышленником, намеренно изменяющим данные. Строковые представления, принимающие отдельное поле длины, также подвержены проблемам, если длину можно изменить. В таких случаях программный код, обращающийся к строковым данным, требует проверки границ , чтобы гарантировать, что он непреднамеренно не получит доступ или не изменит данные за пределами границ памяти строки.
Строковые данные часто получаются из пользовательского ввода в программу. Таким образом, программа несет ответственность за проверку строки, чтобы убедиться, что она представляет ожидаемый формат. Выполнение ограниченной проверки или отсутствие проверки пользовательского ввода может сделать программу уязвимой для атак с внедрением кода .
Иногда строки необходимо встроить в текстовый файл, который одновременно понятен человеку и предназначен для использования машиной. Это необходимо, например, в исходном коде языков программирования или в файлах конфигурации. В этом случае символ NUL не очень хорошо подходит в качестве терминатора, поскольку он обычно невидим (непечатаем) и его трудно ввести с клавиатуры. Хранение длины строки также было бы неудобным, поскольку ручное вычисление и отслеживание длины утомительно и подвержено ошибкам.
Два распространенных представления:
"str" или одинарные кавычки ASCII 0x27 'str'), используемые большинством языков программирования. Чтобы иметь возможность включать специальные символы, такие как сами кавычки, символы новой строки или непечатаемые символы, часто доступны управляющие последовательности , обычно с префиксом в виде символа обратной косой черты (ASCII 0x5C).Хотя строки символов являются очень распространенным использованием строк, строка в информатике может ссылаться на любую последовательность однородно типизированных данных. Например, битовая строка или байтовая строка могут использоваться для представления нетекстовых двоичных данных, извлеченных из среды связи. Эти данные могут быть представлены или не представлены строковым типом данных в зависимости от потребностей приложения, желания программиста и возможностей используемого языка программирования. Если реализация строки языка программирования не является 8-битной , может произойти повреждение данных.
Программисты на C проводят четкое различие между «строкой», также известной как «строка символов», которая по определению всегда заканчивается нулем, и «байтовой строкой» или «псевдострокой», которая может храниться в том же массиве, но часто не заканчивается нулем. Использование функций обработки строк C на такой «байтовой строке» часто, кажется, работает, но позже приводит к проблемам безопасности. [15] [16] [17]
Существует множество алгоритмов обработки строк, каждый из которых имеет различные компромиссы. Конкурирующие алгоритмы можно анализировать с точки зрения времени выполнения, требований к хранению и т. д. Название «стрингология» было придумано в 1984 году ученым-компьютерщиком Цви Галилом для теории алгоритмов и структур данных, используемых для обработки строк. [18] [19] [20]
Некоторые категории алгоритмов включают в себя:
Расширенные строковые алгоритмы часто используют сложные механизмы и структуры данных, среди которых суффиксные деревья и конечные автоматы .
Строки символов являются настолько полезным типом данных, что было разработано несколько языков, чтобы сделать приложения для обработки строк простыми в написании. Примерами могут служить следующие языки:
Многие утилиты Unix выполняют простые манипуляции со строками и могут быть использованы для простого программирования некоторых мощных алгоритмов обработки строк. Файлы и конечные потоки могут рассматриваться как строки.
Некоторые API, такие как Multimedia Control Interface , встроенный SQL или printf, используют строки для хранения команд, которые будут интерпретироваться.
Многие языки программирования сценариев , включая Perl, Python , Ruby и Tcl, используют регулярные выражения для упрощения текстовых операций. Perl особенно известен своим использованием регулярных выражений, [21] и многие другие языки и приложения реализуют совместимые с Perl регулярные выражения .
Некоторые языки, такие как Perl и Ruby, поддерживают интерполяцию строк , что позволяет вычислять произвольные выражения и включать их в строковые литералы.
Строковые функции используются для создания строк или изменения содержимого изменяемой строки. Они также используются для запроса информации о строке. Набор функций и их имена различаются в зависимости от языка программирования .
Самый простой пример строковой функции — функция длины строки — функция, которая возвращает длину строки (не считая никаких терминирующих символов или какой-либо внутренней структурной информации строки) и не изменяет строку. Эта функция часто называется lengthили len. Например, length("hello world")вернет 11. Другая распространенная функция — конкатенация , где новая строка создается путем присоединения двух строк, часто это оператор сложения +.
Некоторые архитектуры набора инструкций микропроцессоров содержат прямую поддержку строковых операций, таких как копирование блоков (например, в Intel x86m ). [22] REPNZ MOVSB
Пусть Σ — конечный набор различных, однозначных символов (иначе называемых знаками), называемый алфавитом . Строка (или слово [23] или выражение [24] ) над Σ — это любая конечная последовательность символов из Σ. [25] Например, если Σ = {0, 1}, то 01011 — это строка над Σ.
Длина строки s — это количество символов в s (длина последовательности) и может быть любым неотрицательным целым числом ; она часто обозначается как | s |. Пустая строка — это уникальная строка над Σ длины 0 и обозначается ε или λ . [25] [26]
Множество всех строк над Σ длины n обозначается Σ n . Например, если Σ = {0, 1}, то Σ 2 = {00, 01, 10, 11}. Для каждого алфавита Σ имеем Σ 0 = {ε}.
Множество всех строк над Σ любой длины является замыканием Клини Σ и обозначается Σ * . В терминах Σ n ,
Например, если Σ = {0, 1}, то Σ * = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}. Хотя само множество Σ * счетно бесконечно , каждый элемент Σ * представляет собой строку конечной длины.
Множество строк над Σ (т. е. любое подмножество Σ * ) называется формальным языком над Σ. Например, если Σ = {0, 1}, то множество строк с четным числом нулей, {ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, ...}, является формальным языком над Σ.
Конкатенация — важная бинарная операция на Σ * . Для любых двух строк s и t в Σ * их конкатенация определяется как последовательность символов в s, за которой следует последовательность символов в t , и обозначается st . Например, если Σ = {a, b, ..., z}, s = bear, и t = hug, то st = bearhugи ts = hugbear.
Конкатенация строк является ассоциативной , но некоммутативной операцией . Пустая строка ε служит элементом тождества ; для любой строки s , ε s = s ε = s . Таким образом, множество Σ * и операция конкатенации образуют моноид , свободный моноид, порожденный Σ. Кроме того, функция длины определяет гомоморфизм моноида из Σ * в неотрицательные целые числа (то есть функцию , такую, что ).
Говорят, что строка s является подстрокой или фактором t , если существуют (возможно, пустые) строки u и v , такие что t = usv . Отношение «является подстрокой» определяет частичный порядок на Σ * , наименьшим элементом которого является пустая строка.
Строка s называется префиксом t , если существует строка u, такая что t = su . Если u непусто, то s называется собственным префиксом t . Симметрично, строка s называется суффиксом t , если существует строка u, такая что t = us . Если u непусто, то s называется собственным суффиксом t . Суффиксы и префиксы являются подстроками t . Оба отношения «является префиксом» и «является суффиксом» являются порядками префиксов .
Обратной строкой называется строка с теми же символами, но в обратном порядке. Например, если s = abc (где a, b и c — символы алфавита), то обратной строкой s будет cba. Строка, которая является обратной самой себе (например, s = madam), называется палиндромом , который также включает пустую строку и все строки длины 1.
Говорят, что строка s = uv является поворотом t, если t = vu . Например, если Σ = {0, 1}, то строка 0011001 является поворотом 0100110, где u = 00110 и v = 01. В качестве другого примера, строка abc имеет три различных поворота, а именно: сама abc (с u = abc, v = ε), bca (с u = bc, v = a) и cab (с u = c, v = ab).
Часто бывает полезно определить порядок на множестве строк. Если алфавит Σ имеет полный порядок (ср. алфавитный порядок ), можно определить полный порядок на Σ *, называемый лексикографическим порядком . Лексикографический порядок является полным, если алфавитный порядок является, но не является обоснованным для любого нетривиального алфавита, даже если алфавитный порядок является. Например, если Σ = {0, 1} и 0 < 1, то лексикографический порядок на Σ * включает отношения ε < 0 < 00 < 000 < ... < 0001 < ... < 001 < ... < 01 < 010 < ... < 011 < 0110 < ... < 01111 < ... < 1 < 10 < 100 < ... < 101 < ... < 111 < ... < 11111 < ... < 11111 ... Относительно этого порядка, например, бесконечное множество { 1, 01, 001, 0001, 00001, 000001, ... } не имеет минимального элемента.
Альтернативный порядок строк, сохраняющий обоснованность, см. в Shortlex. Для примера алфавита порядок shortlex будет следующим: ε < 0 < 1 < 00 < 01 < 10 < 11 < 000 < 001 < 010 < 011 < 100 < 101 < 0110 < 111 < 0000 < 0001 < 0010 < 0011 < ... < 1111 < 00000 < 00001 ...
В формальной теории часто встречается ряд дополнительных операций над строками. Они приведены в статье об операциях над строками .
Строки допускают следующую интерпретацию как узлов на графе, где k — количество символов в Σ:
Естественная топология на множестве строк фиксированной длины или строк переменной длины — это дискретная топология, но естественная топология на множестве бесконечных строк — это предельная топология , рассматривающая множество бесконечных строк как обратный предел множеств конечных строк. Это конструкция, используемая для p -адических чисел и некоторых конструкций множества Кантора , и она дает ту же самую топологию.
Изоморфизмы между строковыми представлениями топологий можно найти путем нормализации в соответствии с лексикографически минимальным строковым вращением .
Строковые литералы (или константы) называются "анонимными строками"
{{cite web}}: CS1 maint: неподходящий URL ( ссылка )Он изобрел термин «стрингология», который является подразделом строковых алгоритмов,
«стрингология» — популярное название строковых алгоритмов, а также текстовых алгоритмов.
{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )Самая известная сила Perl — это манипуляция строками с помощью регулярных выражений.
Пусть Σ — алфавит. Непустое слово над Σ — это конечная последовательность с областью значений I n (для некоторого n ∈ ℕ) и областью значений Σ.
Любая конечная последовательность символов языка называется выражением этого языка.