Строка (информатика) - String (computer science)

Схема строковых данных в вычислениях.  Показывает предложение "Это строка!"  с каждой буквой в отдельном ящике.  Слово «String» находится выше, относящееся ко всему предложению.  Ярлык «Персонаж» находится ниже и указывает на отдельные поля.
Строки часто состоят из символов . Они полезны для хранения данных удобочитаемых, как и предложения, или списки буквенных данных, как кислотные последовательности нуклеиновых из ДНК .

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

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

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

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

Строковые типы данных

Строка тип данных является типом данных по образцу идеи формальной строки. Строки - это такой важный и полезный тип данных, что они реализованы почти во всех языках программирования . В некоторых языках они доступны как примитивные типы, а в других - как составные типы . Синтаксис большинства языков программирования высокого уровня позволяет строки, как правило , цитируемый в некотором роде, чтобы представить экземпляр строки типа данных; такая мета-строка называется литералом или строковым литералом .

Длина строки

Хотя формальные строки могут иметь произвольную конечную длину, длина строк в реальных языках часто ограничивается искусственным максимумом. В общем, существует два типа строковых типов данных: строки фиксированной длины , которые имеют фиксированную максимальную длину, определяемую во время компиляции, и которые используют один и тот же объем памяти независимо от того, нужен этот максимум или нет, и строки переменной длины , длина которых не является произвольно фиксированной и которые могут использовать различные объемы памяти в зависимости от фактических требований во время выполнения (см. Управление памятью ). Большинство строк в современных языках программирования - это строки переменной длины. Конечно, даже строки переменной длины ограничены по длине - размером доступной памяти компьютера . Длина строки может быть сохранена как отдельное целое число (что может наложить другое искусственное ограничение на длину) или неявно через символ завершения, обычно это символьное значение со всеми нулевыми битами, например, в языке программирования C. См. Также « Завершение с нулевым завершением » ниже.

Кодировка символов

Для строковых типов данных исторически выделялся один байт на символ, и, хотя точный набор символов варьировался в зависимости от региона, кодировки символов были достаточно похожи, поэтому программисты часто могли игнорировать это, поскольку символы, которые программа обрабатывала особым образом (например, точка, пробел и запятая) ) были в одном месте во всех кодировках, с которыми могла столкнуться программа. Эти наборы символов обычно основывались на ASCII или EBCDIC . Если текст в одной кодировке отображался в системе с использованием другой кодировки, текст часто искажался , хотя часто несколько читался, и некоторые пользователи компьютеров учились читать искаженный текст.

Логографические языки, такие как китайский , японский и корейский (известные под общим названием CJK ), требуют гораздо более 256 символов (ограничение в один 8-битный байт на символьную кодировку) для разумного представления. Обычные решения заключались в сохранении однобайтовых представлений для ASCII и использовании двухбайтовых представлений для идеографов CJK . Их использование с существующим кодом приводило к проблемам с сопоставлением и обрезкой строк, серьезность которых зависела от того, как была разработана кодировка символов. Некоторые кодировки, такие как семейство EUC, гарантируют, что значение байта в диапазоне ASCII будет представлять только этот символ ASCII, что делает кодирование безопасным для систем, которые используют эти символы в качестве разделителей полей. Другие кодировки, такие как ISO-2022 и Shift-JIS , не дают таких гарантий, что делает сопоставление байтовых кодов небезопасным. Эти кодировки также не были «самосинхронизирующимися», поэтому для определения границ символов требовалось резервное копирование до начала строки, а вставка двух строк вместе могла привести к повреждению второй строки.

Юникод несколько упростил картину. Большинство языков программирования теперь имеют тип данных для строк Unicode. Предпочтительный формат байтового потока Unicode UTF-8 разработан, чтобы не иметь проблем, описанных выше для более старых многобайтовых кодировок. UTF-8, UTF-16 и UTF-32 требуют, чтобы программист знал, что единицы кода фиксированного размера отличаются от «символов», основная трудность в настоящее время заключается в неверно разработанных API-интерфейсах, которые пытаются скрыть эту разницу (UTF-32 действительно сделать кодовые точки фиксированного размера, но они не являются «символами» из-за составления кодов).

Реализации

Некоторые языки, такие как C ++ и Ruby , обычно позволяют изменять содержимое строки после ее создания; они называются изменяемыми строками. В других языках, таких как Java и Python , значение фиксировано, и необходимо создать новую строку, если необходимо внести какие-либо изменения; они называются неизменяемыми строками (некоторые из этих языков также предоставляют другой изменяемый тип, такой как Java и .NET StringBuilder , потокобезопасная Java StringBufferи Какао NSMutableString ).

Строки обычно реализуются как массивы байтов, символов или единиц кода, чтобы обеспечить быстрый доступ к отдельным единицам или подстрокам, включая символы, если они имеют фиксированную длину. Некоторые языки, такие как Haskell, реализуют их в виде связанных списков .

Некоторые языки, такие как Prolog и Erlang , вообще избегают реализации выделенного строкового типа данных, вместо этого принимая соглашение о представлении строк в виде списков кодов символов.

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

Представления строк сильно зависят от выбора репертуара символов и метода кодирования символов. Старые строковые реализации были разработаны для работы с репертуаром и кодировкой, определенными ASCII, или более поздними расширениями, такими как серия ISO 8859 . Современные реализации часто используют обширный репертуар, определенный Unicode, вместе с множеством сложных кодировок, таких как UTF-8 и UTF-16.

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

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

С нулевым завершением

Длина строки может быть сохранена неявно с помощью специального символа завершения; часто это нулевой символ (NUL), которая имеет все биты нуль, условность используется и увековечен популярным языком программирования Си . Следовательно, это представление , что обычно называют как строки C . Это представление строки из n символов занимает n + 1 пробел (1 для терминатора) и, таким образом, является неявной структурой данных .

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

Пример строки с завершающим нулем, хранящейся в 10-байтовом буфере , вместе с ее представлением ASCII (или более современным UTF-8 ) в виде 8-битных шестнадцатеричных чисел :

F R A N K NUL k e f w
46 16 52 16 41 16 16 16 00 16 16 65 16 66 16 77 16

Длина строки "" в приведенном выше примере FRANKсоставляет 5 символов, но занимает 6 байтов. Знаки после терминатора не являются частью изображения; они могут быть частью других данных или просто мусором. (Строки этой формы иногда называют строками ASCIZ после исходной директивы языка ассемблера, используемой для их объявления.)

Байт- и битовое завершение

Использование специального байта, отличного от нуля, для завершения строки исторически появлялось как в аппаратном, так и в программном обеспечении, хотя иногда со значением, которое также было печатным символом. $использовался многими системами ассемблера, :используемыми системами CDC (этот символ имел нулевое значение), и ZX80 использовался, "поскольку это был разделитель строк в его языке BASIC.

В чем-то похожем, машины для «обработки данных», такие как IBM 1401, использовали специальный бит словарной метки для разграничения строк слева, где операция начиналась бы справа. Этот бит должен быть очищен во всех остальных частях строки. Это означало, что, хотя в IBM 1401 было семибитное слово, почти никто никогда не думал использовать его как функцию и отменять назначение седьмого бита (например) для обработки кодов ASCII.

Раннее программное обеспечение для микрокомпьютеров основывалось на том факте, что коды ASCII не используют бит старшего разряда, и устанавливали его для обозначения конца строки. Перед выводом он должен быть сброшен на 0.

С префиксом длины

Длина строки также может быть сохранена явно, например, путем добавления к строке префикса длины в качестве байтового значения. Это соглашение используется во многих диалектах Паскаля ; как следствие, некоторые люди называют такую ​​строку строкой Паскаля или P-строкой . Сохранение длины строки в байтах ограничивает максимальную длину строки 255. Чтобы избежать таких ограничений, улучшенные реализации P-строк используют 16-, 32- или 64-битные слова для хранения длины строки. Когда поле длины покрывает адресное пространство , строки ограничиваются только доступной памятью .

Если длина ограничена, то ее можно закодировать в постоянном пространстве, обычно в машинном слове, что приводит к неявной структуре данных , занимающей пространство n + k , где k - количество символов в слове (8 для 8-битных ASCII на 64-битной машине, 1 для 32-битной UTF-32 / UCS-4 на 32-битной машине и т. Д.). Если длина не ограничена, кодирование длины n занимает пространство журнала ( n ) (см. Код фиксированной длины ), поэтому строки с префиксом длины представляют собой сжатую структуру данных , кодирующую строку длины n в log ( n ) + n пробел. .

В последнем случае само поле префикса длины не имеет фиксированной длины, поэтому фактические строковые данные необходимо перемещать, когда строка растет, так что поле длины необходимо увеличивать.

Вот строка Паскаля, хранящаяся в 10-байтовом буфере, вместе с ее представлением ASCII / UTF-8:

длина F R A N K k e f w
05 16 46 16 52 16 41 16 16 16 16 65 16 66 16 77 16

Строки как записи

Многие языки, в том числе объектно-ориентированные, реализуют строки как записи с внутренней структурой, например:

class string {
  size_t length;
  char *text;
};

Однако, поскольку реализация обычно скрыта , к строке необходимо обращаться и изменять ее через функции-члены. text- указатель на динамически выделяемую область памяти, которая может быть расширена по мере необходимости. См. Также строку (C ++) .

Другие представления

И завершение символа, и коды длины ограничивают строки: например, символьные массивы C, содержащие нулевые (NUL) символы, не могут обрабатываться напрямую функциями библиотеки строк C : строки, использующие код длины, ограничены максимальным значением кода длины.

Оба эти ограничения можно преодолеть с помощью грамотного программирования.

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

Хотя эти представления обычны, возможны и другие. Использование веревок делает некоторые строковые операции, такие как вставки, удаления и конкатенации, более эффективными.

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

Проблемы безопасности

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

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

Буквальные строки

Иногда строки необходимо встраивать в текстовый файл, который удобен для чтения и предназначен для использования машиной. Это необходимо, например, в исходном коде языков программирования или в файлах конфигурации. В этом случае символ NUL не работает как терминатор, поскольку обычно он невидим (не печатается) и его трудно вводить с клавиатуры. Сохранение длины строки также будет неудобным, поскольку ручное вычисление и отслеживание длины утомительно и подвержено ошибкам.

Два распространенных представления:

  • Окруженные кавычки (ASCII 0x22 двойные кавычки или ASCII 0x27 апостроф), используемых большинством языков программирования. Чтобы иметь возможность включать специальные символы, такие как кавычки, символы новой строки или непечатаемые символы, часто доступны escape-последовательности , обычно с префиксом обратной косой черты (ASCII 0x5C).
  • Отменено с помощью новой строки последовательности, например , в Windows , INI - файлах .

Нетекстовые строки

В то время как символьные строки - очень распространенное использование строк, строка в информатике может относиться к любой последовательности однородно типизированных данных. Например, битовая строка или байтовая строка может использоваться для представления нетекстовых двоичных данных, извлеченных из коммуникационной среды. Эти данные могут или не могут быть представлены типом данных, зависящим от строки, в зависимости от потребностей приложения, желания программиста и возможностей используемого языка программирования. Если строковая реализация языка программирования не является 8-битной чистой , может произойти повреждение данных.

Программисты на C проводят резкое различие между «строкой», также известной как «строка символов», которая по определению всегда заканчивается нулем, и «байтовой строкой» или «псевдострочкой», которые могут храниться в том же массиве, но являются часто не завершается нулевым символом. Использование функций обработки строки C в такой «байтовой строке» часто кажется эффективным, но позже приводит к проблемам с безопасностью .

Алгоритмы обработки строк

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

Некоторые категории алгоритмов включают:

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

Название стрингология было придумано в 1984 году компьютерным ученым Цви Галилом для проблемы алгоритмов и структур данных, используемых для обработки строк.

Языки и утилиты, ориентированные на символьные строки

Символьные строки являются настолько полезным типом данных, что было разработано несколько языков, чтобы упростить написание приложений для обработки строк. Примеры включают следующие языки:

Многие утилиты Unix выполняют простые операции со строками и могут использоваться для простого программирования некоторых мощных алгоритмов обработки строк. Файлы и конечные потоки можно рассматривать как строки.

Некоторые API, такие как интерфейс управления мультимедиа , встроенный SQL или printf, используют строки для хранения команд, которые будут интерпретироваться.

Последние языки программирования сценариев , включая Perl, Python , Ruby и Tcl, используют регулярные выражения для облегчения текстовых операций. Perl особенно известен использованием регулярных выражений, и многие другие языки и приложения реализуют совместимые с Perl регулярные выражения .

Некоторые языки, такие как Perl и Ruby, поддерживают строковую интерполяцию , которая позволяет вычислять произвольные выражения и включать их в строковые литералы.

Функции символьных строк

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

Самый простой пример строковой функции - это функция длины строки - функция, которая возвращает длину строки (без учета каких-либо символов-ограничителей или какой-либо внутренней структурной информации строки) и не изменяет строку. Эта функция часто называется lengthили len. Например, length("hello world")вернет 11. Другой распространенной функцией является конкатенация , когда новая строка создается путем добавления двух строк, часто это оператор сложения +.

Некоторый микропроцессорных «сек набора команд архитектуры содержат прямую поддержку строковых операций, таких как блок - копии (например , в интел x86m REPNZ MOVSB ).

Формальная теория

Пусть Σ - конечный набор символов (также называемых символами), называемый алфавитом . Никаких предположений о природе символов не делается. Строка (или слово ) над Й является любой конечной последовательностью символов из Е. Например, если Σ = {0, 1}, то 01011 - это строка над Σ.

Длина строки s это количество символов в сек (длина последовательности) и может быть любым неотрицательным целым числом ; его часто обозначают как | с |, Пустая строка уникальная строка над пространством длиной 0, и обозначается й или Л .

Множество всех строк над пространством длины п обозначается Е п . Например, если Σ = {0, 1}, то Σ 2 = {00, 01, 10, 11}. Обратите внимание, что Σ 0 = {ε} для любого алфавита Σ.

Множество всех строк над Σ любой длины является замыканием Клини над Σ и обозначается Σ * . С точки зрения Е п ,

Например, если Σ = {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 . Следовательно, множество Σ * и операция конкатенации образуют моноид , свободный моноид, порожденный Σ. Кроме того, функция длины определяет гомоморфизм моноида из Σ * в неотрицательные целые числа (то есть функцию , такую ​​что ).

Строка , сек , как говорят , быть подстроку или фактор из т , если существуют (возможно , пустой) строки U и V такие , что т = USV . Отношение «является» подстрокой определяет частичный порядок на Е * , тем не менее элемент из которых является пустой строкой.

Префиксы и суффиксы

Строка , сек , как говорят, является префиксом из т , если существует строка ¯u таким образом, что т = су . Если u не пусто, s называется собственным префиксом t . Симметрично, строка сек есть называется суффикс из т , если существует последовательность у такой , что т = нам . Если 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 <1111 <11111 ... Лексикографический порядок является полным, если есть алфавитный порядок, но не является обоснованным для любого нетривиального алфавита, даже если алфавитный порядок равен.

См. В Shortlex альтернативный порядок строк, сохраняющий обоснованность.

Строковые операции

В формальной теории обычно встречается ряд дополнительных операций со строками. Они приведены в статье о строковых операциях .

Топология

(Гипер) куб двоичных строк длины 3

Строки допускают следующую интерпретацию как узлы на графе, где k - количество символов в Σ:

  • Строки фиксированной длины длины n можно рассматривать как целочисленные местоположения в n- мерном гиперкубе со сторонами длиной k -1.
  • Строки переменной длины (конечной длины) можно рассматривать как узлы совершенного k -арного дерева .
  • Бесконечные строки (иначе не рассматриваемые здесь) можно рассматривать как бесконечные пути на k- узловом полном графе .

Естественная топология на множестве строк фиксированной длины или строк переменной длины - это дискретная топология, но естественная топология на множестве бесконечных строк - это предельная топология , рассматривающая набор бесконечных строк как обратный предел множеств конечные строки. Эта конструкция используется для p -адических чисел и некоторых конструкций множества Кантора , и дает ту же топологию.

Изоморфизмы между строковыми представлениями топологий могут быть найдены путем нормализации в соответствии с лексикографически минимальным вращением строки .

Смотрите также

использованная литература