В компьютерном программировании строка традиционно является последовательностью символов , либо как литеральная константа , либо как некоторая переменная . Последнее может позволять изменять ее элементы и изменять длину, или она может быть фиксированной (после создания). Строка обычно рассматривается как тип данных и часто реализуется как структура данных массива байтов (или слов ) , которая хранит последовательность элементов, как правило, символов, используя некоторую кодировку символов . Строка может также обозначать более общие массивы или другие типы данных и структуры последовательностей (или списков ).
В зависимости от языка программирования и точного типа используемых данных переменная , объявленная как строка, может либо привести к статическому выделению памяти на заранее определенную максимальную длину, либо использовать динамическое выделение , чтобы позволить ей хранить переменное количество элементов.
Когда строка появляется в исходном коде буквально , она называется строковым литералом или анонимной строкой. [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 ∈ ℕ) и областью значений Σ.
Любая конечная последовательность символов языка называется выражением этого языка.