Строка (информатика)

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Поиск источников:  "String" Computer science  -  новости  · газеты  · книги  · ученый  · JSTOR ( март 2015 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

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

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

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

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

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

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

Длина строки [ править ]

Хотя формальные строки могут иметь произвольную конечную длину, длина строк в реальных языках часто ограничивается искусственным максимумом. В общем, существует два типа строковых типов данных: строки фиксированной длины , которые имеют фиксированную максимальную длину, определяемую во время компиляции, и которые используют один и тот же объем памяти независимо от того, нужен этот максимум или нет, и строки переменной длины , длина которого не является произвольно фиксированной и которые могут использовать различные объемы памяти в зависимости от фактических требований во время выполнения (см. Управление памятью ). Большинство строк в современных языках программирования - это строки переменной длины. Конечно, даже строки переменной длины ограничены по длине - размером доступногопамять компьютера . Длина строки может быть сохранена как отдельное целое число (что может наложить другое искусственное ограничение на длину) или неявно через символ завершения, обычно это символьное значение со всеми нулевыми битами, например, в языке программирования 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), которая имеет все биты нуль, условность используется и увековечен популярным языком программирования Си . ^[2] Таким образом, это представление , что обычно называют как строки C . Это представление строки из n символов занимает n + 1 пробел (1 для терминатора) и, таким образом, является неявной структурой данных .

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

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

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

Завершение байтом и битом [ править ]

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

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

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

С префиксом длины [ править ]

Длину строки также можно сохранить явно, например, поставив перед строкой длину в качестве байтового значения. Это соглашение используется во многих диалектах Паскаля ; как следствие, некоторые люди называют такую ​​строку строкой Паскаля или 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:

Строки как записи [ править ]

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

 строка  класса {  size_t  length ;  char  * текст ; };

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

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

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

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

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

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

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

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

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

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

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

Формальная теория [ править ]

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

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

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

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

${\ displaystyle \ Sigma ^ {*} = \ bigcup _ {n \ in \ 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 и t в Σ ^* их конкатенация определяется как последовательность символов в s, за которой следует последовательность символов в t , и обозначается st . Например, если Σ = {a, b, ..., z}, s = медведь и t = обнимать , то st = медведь и ts = обниматься .

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

Строка , сек , как говорят , быть подстроку или фактор из т , если существуют (возможно , пустой) строки 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 для альтернативного порядка строк, сохраняющего обоснованность.

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

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

Топология [ править ]

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

Викискладе есть медиафайлы по теме строк .