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

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Струнная» информатика  – Новости  · газеты  · книги  · ученый  · JSTOR (Март 2015 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

Строки применяются, например. в Биоинформатика описать ДНК пряди, состоящие из азотистые основания.

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

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

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

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

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

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

Длина строки

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

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

Для строковых типов данных исторически выделялся один байт на символ, и, хотя точный набор символов варьировался в зависимости от региона, кодировки символов были достаточно похожи, чтобы программисты могли часто игнорировать это, поскольку символы, которые программа обрабатывала особым образом (например, точка, пробел и запятая ) находились в одном месте во всех кодировках, с которыми могла столкнуться программа. Эти наборы символов обычно основывались на 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 ++ и Рубин, обычно позволяют изменять содержимое строки после того, как она была создана; они называются изменчивый струны. На других языках, например Ява и Python, значение фиксировано, и необходимо создать новую строку, если необходимо внести какие-либо изменения; они называются неизменный строки (некоторые из этих языков также предоставляют другой изменяемый тип, например Java и .СЕТЬ StringBuilder, потокобезопасная Java StringBuffer, а Какао NSMutableString).

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

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

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

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

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

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

Без завершения

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

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

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

Длина строки в приведенном выше примере "ОТКРОВЕННЫЙ", составляет 5 символов, но занимает 6 байтов. Символы после терминатора не являются частью представления; они могут быть частью других данных или просто мусором. (Строки такой формы иногда называют Строки ASCIZ, после оригинала язык ассемблера директива, используемая для их объявления.)

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

Использование специального байта, отличного от нуля, для завершения строки исторически появлялось как в аппаратном, так и в программном обеспечении, хотя иногда и со значением, которое также было печатным символом. $ использовался многими ассемблерными системами, : использован CDC систем (этот символ имел нулевое значение), а ZX80 использовал "^[3] поскольку это был разделитель строк на его БЕЙСИКЕ.

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

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

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

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

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

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

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

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

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

учебный класс нить {  size_t длина;  char *текст;};

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Программисты на C проводят резкое различие между «строкой», также известной как «строка символов», которая по определению всегда заканчивается нулем, и «байтовой строкой» или «псевдострочкой», которые могут храниться в том же массиве, но часто не завершается нулевым символом. Обработка строки C функции с такой "байтовой строкой" часто кажутся работающими, но позже приводит к проблемы безопасности.^[6][7][8]

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

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

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

• Алгоритмы поиска по строкам для поиска данной подстроки или шаблона
• Алгоритмы обработки строк
• Алгоритмы сортировки
• Регулярное выражение алгоритмы
• Парсинг строка
• Последовательный майнинг

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

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

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

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

• awk
• Значок
• МАМПЫ
• Perl
• Rexx
• Рубин
• sed
• СНОБОЛ
• Tcl
• ТТМ

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

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

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

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

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

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

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

Немного микропроцессор с архитектуры наборов команд содержат прямую поддержку строковых операций, таких как копирование блока (например, In Intel x86m РЭПНЗ МОВСБ).^[11]

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

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

В длина строки s это количество символов в s (длина последовательности) и может быть любой неотрицательное целое число; его часто обозначают как |s|, В пустой строкой - единственная строка длины 0 над Σ и обозначается ε или же λ.^[12][13]

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

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

${displaystyle Sigma ^ {*} = igcup _ {nin mathbb {N} cup {0}} Sigma ^ {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 и т в Σ^*, их конкатенация определяется как последовательность символов в s за которым следует последовательность символов в т, и обозначается ул. Например, если Σ = {a, b, ..., z}, s = нести, и т = обнимать, тогда ул = медвежьи объятия и ts = hugbear.

Конкатенация строк - это ассоциативный, но некоммутативный операция. Пустая строка ε служит элемент идентичности; для любой строки s, εs = sε = s. Следовательно, множество Σ^* и операция конкатенации формирует моноид, то свободный моноид порожденный Σ. Кроме того, функция длины определяет моноидный гомоморфизм из Σ^* к неотрицательным целым числам (то есть функция ${displaystyle L: Sigma ^ {*} mapsto mathbb {N} cup {0}}$, так что ${displaystyle L (st) = L (s) + L (t) quad forall s, оловянная сигма ^ {*}}$).

Строка s считается подстрока или же фактор из т если есть (возможно, пустые) строки ты и v такой, что т = usv. В связь "является подстрокой" определяет частичный заказ на Σ^*, то наименьший элемент из которых пустая строка.

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

Строка s считается префикс из т если существует строка ты такой, что т = вс. Если ты непусто, s считается правильный префикс т. Симметрично струна s считается суффикс из т если существует строка ты такой, что т = нас. Если ты непусто, s считается правильный суффикс т. Суффиксы и префиксы - это подстроки т. Оба отношения "является префиксом" и "является суффиксом" являются префиксные заказы.

Разворот

Обратная сторона строки - это строка с такими же символами, но в обратном порядке. Например, если s = abc (где a, b и c - символы алфавита), то обратное s это cba. Строка, противоположная самой себе (например, s = мадам) называется палиндром, который также включает пустую строку и все строки длины 1.

Вращения

Строка s = УФ называется вращением т если т = ву. Например, если Σ = {0, 1} строка 0011001 представляет собой поворот 0100110, где ты = 00110 и v = 01. В качестве другого примера строка abc имеет три разных поворота, а именно. сам abc (с ты= abc, v= ε), bca (с ты= bc, v= a), и cab (с ты= 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 - количество символов в Σ:

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

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

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

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

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

Рекомендации