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

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

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

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

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

Цель

Основная цель строк — хранить удобочитаемый текст, например слова и предложения. Строки используются для передачи информации из компьютерной программы пользователю программы. ^{[ 2 ]} Программа также может принимать строковые данные от своего пользователя. Кроме того, строки могут хранить данные, выраженные в виде символов, но не предназначенные для чтения человеком.

Примеры строк и их назначение:

Сообщение типа " file upload complete" — это строка, которую программное обеспечение показывает конечным пользователям программы . В исходном коде это сообщение, скорее всего, будет отображаться как строковый литерал .
Введенный пользователем текст, например " I got a new job today" как обновление статуса в службе социальных сетей . Вместо строкового литерала программа, скорее всего, сохранит эту строку в базе данных .
Алфавитные данные, например " AGATGCCGT«представляющие последовательности нуклеиновых кислот ДНК . ^{[ 3 ]}
Настройки или параметры компьютера, например « ?action=edit" в виде строки запроса URL-адреса . Часто они предназначены для удобочитаемости, хотя их основная цель — общение с компьютерами.

Термин «строка» может также обозначать последовательность данных или компьютерных записей, отличных от символов, например «строку битов », но при использовании без уточнений он относится к строкам символов. ^{[ 4 ]}

История

Использование слова «строка» для обозначения любых предметов, расположенных в линию, серию или последовательность, восходит к столетиям. ^{[ 5 ]}^{[ 6 ]} В наборе текста XIX века наборщики использовали термин «строка» для обозначения длины шрифта, напечатанного на бумаге; строка будет измеряться для определения заработной платы наборщика. ^{[ 7 ]}^{[ 4 ]}^{[ 8 ]}

Использование слова «строка» для обозначения «последовательности символов или лингвистических элементов в определенном порядке» возникло из математики, символической логики и лингвистической теории , чтобы говорить о формальном поведении символических систем, игнорируя значение символов. ^{[ 4 ]}

Например, логик К.И. Льюис писал в 1918 году: ^{[ 9 ]}

Математическая система — это любой набор строк распознаваемых знаков, в котором некоторые строки взяты изначально, а остальные получены из них посредством операций, выполняемых в соответствии с правилами, независимыми от какого-либо значения, присвоенного знакам. То, что система должна состоять из «знаков», а не из звуков или запахов, не имеет значения.

По словам Джин Э. Саммет , «первым реалистичным языком обработки строк и сопоставления с образцом» для компьютеров был COMIT в 1950-х годах, за ним последовал язык SNOBOL в начале 1960-х. ^{[ 10 ]}

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

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

Длина строки

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

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

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

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

Юникод несколько упростил картину. Большинство языков программирования теперь имеют тип данных для строк Юникода. Предпочтительный формат потока байтов 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и какао NSMutableString. У неизменности есть как преимущества, так и недостатки: хотя для неизменяемых строк может потребоваться неэффективное создание множества копий, они проще и полностью потокобезопасны .

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

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

Представительства

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

`F`	`R`	`A`	`N`	`K`	НУЛЕВОЙ	`k`	`e`	`f`	`w`
46 ₁₆	52 ₁₆	41 ₁₆	4Э ₁₆	4B_4Б16	00 ₁₆	6Б ₁₆	65 ₁₆	66 ₁₆	77 ₁₆

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

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

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

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

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

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

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

длина	`F`	`R`	`A`	`N`	`K`	`k`	`e`	`f`	`w`
05 ₁₆	46 ₁₆	52 ₁₆	41 ₁₆	4Э ₁₆	4B_4Б16	6Б ₁₆	65 ₁₆	66 ₁₆	77 ₁₆

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

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

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

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

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

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

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

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

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

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

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

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

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

Литеральные строки

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

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

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

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

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

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

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

Существует множество алгоритмов обработки строк, каждый из которых имеет свои компромиссы. Конкурирующие алгоритмы можно анализировать с точки зрения времени выполнения, требований к памяти и т. д. Название «стрингология» было придумано в 1984 году ученым-компьютерщиком Цви Галилом для теории алгоритмов и структур данных, используемых для обработки строк. ^{[ 18 ]}^{[ 19 ]}^{[ 20 ]}

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

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

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

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

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

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

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

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

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

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

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

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

содержат прямую некоторых микропроцессоров Архитектуры набора команд поддержку строковых операций, таких как копирование блоков (например, в Intel x86m REPNZ MOVSB). ^{[ 22 ]}

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

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

Длина — это строки s количество символов в s (длина последовательности) и может быть любым неотрицательным целым числом ; его часто обозначают как | с |. — Пустая строка это уникальная строка над Σ длины 0 и обозначается ε или λ . ^{[ 25 ]}^{[ 26 ]}

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

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

\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 = bear, и т = hug, тогда ст = bearhug и ц = hugbear.

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

Строка 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 < ... < 1111 < ... < 11111 ... Применительно к этому упорядочение, например, бесконечное множество { 1, 01, 001, 0001, 00001, 000001, ... } не имеет минимального элемента.

См. Shortlex для альтернативного порядка строк, сохраняющего обоснованность. Для примера алфавита порядок шортлекса следующий: ε <0 <1 <00 <01 < 10 < 11 < 000 < 001 < 010 < 011 < 100 < 101 < 0110 < 111 < 0000 < 0001 < 0010 < 0011 < ... < 1111 < 00000 < 00001 ...

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

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

Топология

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

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

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

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

См. также

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

Ссылки

^ «Введение в Java – MFC 158 G» . Архивировано из оригинала 3 марта 2016 г. Строковые литералы (или константы) называются «анонимными строками».
^ де Сен-Жермен, Х. Джеймс. «Струны» . Университет Юты, Школа вычислительной техники Калерта .
^ Фрэнсис, Дэвид М.; Мерк, Хизер Л. (14 ноября 2019 г.). «ДНК как биохимическая сущность и строка данных» .
^ Jump up to: ^а ^б ^с Берчфилд, RW (1986). "нить". Дополнение к Оксфордскому словарю английского языка . Оксфорд в Clarendon Press.
^ "нить". Оксфордский словарь английского языка . Том. X. Оксфорд в Clarendon Press. 1933 год.
^ «строка (сущ.)» . Интернет-словарь этимологии .
^ Уитни, Уильям Дуайт ; Смит, Бенджамин Э. «Струна». Словарь века . Нью-Йорк: Компания Century. п. 5994.
^ «Распад Старого Союза». Милуоки Сентинел . 11 января 1898 г. с. 3.
^ Льюис, CI (1918). Обзор символической логики . Беркли: Издательство Калифорнийского университета. п. 355.
^ Саммет, Жан Э. (июль 1972 г.). «Языки программирования: история и будущее» (PDF) . Коммуникации АКМ . 15 (7). дои : 10.1145/361454.361485 . S2CID 2003242 .
^ Брайант, Рэндал Э .; Дэвид, О'Халларон (2003), Компьютерные системы: взгляд программиста (изд. 2003 г.), Аппер-Сэддл-Ривер, Нью-Джерси: Pearson Education, с. 40, ISBN 0-13-034074-Х , заархивировано из оригинала 6 августа 2007 г.
^ Уэрмут, Джефф. «Сборочный лист ПЗУ Sinclair ZX80» . Архивировано из оригинала 15 августа 2015 года. {{cite web}}: CS1 maint: неподходящий URL ( ссылка )
^ Эллисон, Деннис. «Заметки по проектированию Tiny BASIC» . Архивировано из оригинала 10 апреля 2017 г.
^ Чарльз Кроули. «Структуры данных для текстовых последовательностей». Архивировано 4 марта 2016 г. на Wayback Machine . Раздел «Введение». Архивировано 4 апреля 2016 г. на Wayback Machine .
^ «strlcpy и strlcat — согласованное, безопасное копирование и конкатенация строк». Архивировано 13 марта 2016 г. в Wayback Machine.
^ «Разглагольствования о strcpy, strncpy и strlcpy». Архивировано 29 февраля 2016 г. в Wayback Machine.
^ Кейт Томпсон. «Нет, strncpy() не является «более безопасной» функцией strcpy()». 2012.
^ «Пражский стрингологический клуб» . Stringology.org . Архивировано из оригинала 1 июня 2015 года . Проверено 23 мая 2015 г.
^ Эвартс, Холли (18 марта 2021 г.). «Бывший декан Цви Галил вошел в десятку самых влиятельных ученых-компьютерщиков за последнее десятилетие» . Колумбия Инжиниринг . Он изобрел термин «стрингология», которая является подразделом строковых алгоритмов.
^ Крошмор, Максим (2002). Жемчужины стрингологии . Сингапур. п. ISBN против 981-02-4782-6 . Термин «стрингология» — популярное прозвище для строковых алгоритмов, а также для текстовых алгоритмов. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ «Основной Perl» . Архивировано из оригинала 21 апреля 2012 г. Самая известная сила Perl заключается в манипулировании строками с помощью регулярных выражений.
^ «Строковые инструкции x86» . Архивировано из оригинала 27 марта 2015 г.
^ Флетчер, Питер; Хойл, Хьюз; Пэтти, К. Уэйн (1991). Основы дискретной математики . PWS-Кент. п. 114. ИСБН 0-53492-373-9 . Пусть Σ — алфавит. Непустое слово над Σ — это конечная последовательность с областью определения I _n (для некоторого n ∈ ℕ) и кодобластью Σ.
^ Шенфилд, Джозеф Р. (2010) [1967]. Математическая логика (переиздание). ЦРК Пресс. п. 2. ISBN 978-156881135-2 . Любая конечная последовательность символов языка называется выражением этого языка.
^ Jump up to: ^а ^б Барбара Х. Парти; Алиса тер Мейлен ; Роберт Э. Уолл (1990). Математические методы в лингвистике . Клювер.
^ Джон Э. Хопкрофт, Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. ISBN 0-201-02988-Х . Здесь: разд.1.1, п.1

[1] «Введение в Java – MFC 158 G» . Архивировано из оригинала 3 марта 2016 г. Строковые литералы (или константы) называются «анонимными строками».

[2] де Сен-Жермен, Х. Джеймс. «Струны» . Университет Юты, Школа вычислительной техники Калерта .

[3] Фрэнсис, Дэвид М.; Мерк, Хизер Л. (14 ноября 2019 г.). «ДНК как биохимическая сущность и строка данных» .

[Burchfield1986-4] Jump up to: ^а ^б ^с Берчфилд, RW (1986). "нить". Дополнение к Оксфордскому словарю английского языка . Оксфорд в Clarendon Press.

[5] "нить". Оксфордский словарь английского языка . Том. X. Оксфорд в Clarendon Press. 1933 год.

[6] «строка (сущ.)» . Интернет-словарь этимологии .

[7] Уитни, Уильям Дуайт ; Смит, Бенджамин Э. «Струна». Словарь века . Нью-Йорк: Компания Century. п. 5994.

[8] «Распад Старого Союза». Милуоки Сентинел . 11 января 1898 г. с. 3.

[9] Льюис, CI (1918). Обзор символической логики . Беркли: Издательство Калифорнийского университета. п. 355.

[10] Саммет, Жан Э. (июль 1972 г.). «Языки программирования: история и будущее» (PDF) . Коммуникации АКМ . 15 (7). дои : 10.1145/361454.361485 . S2CID 2003242 .

[11] Брайант, Рэндал Э .; Дэвид, О'Халларон (2003), Компьютерные системы: взгляд программиста (изд. 2003 г.), Аппер-Сэддл-Ривер, Нью-Джерси: Pearson Education, с. 40, ISBN 0-13-034074-Х , заархивировано из оригинала 6 августа 2007 г.

[asm-12] Уэрмут, Джефф. «Сборочный лист ПЗУ Sinclair ZX80» . Архивировано из оригинала 15 августа 2015 года. {{cite web}}: CS1 maint: неподходящий URL ( ссылка )

[13] Эллисон, Деннис. «Заметки по проектированию Tiny BASIC» . Архивировано из оригинала 10 апреля 2017 г.

[14] Чарльз Кроули. «Структуры данных для текстовых последовательностей». Архивировано 4 марта 2016 г. на Wayback Machine . Раздел «Введение». Архивировано 4 апреля 2016 г. на Wayback Machine .

[15] «strlcpy и strlcat — согласованное, безопасное копирование и конкатенация строк». Архивировано 13 марта 2016 г. в Wayback Machine.

[16] «Разглагольствования о strcpy, strncpy и strlcpy». Архивировано 29 февраля 2016 г. в Wayback Machine.

[17] Кейт Томпсон. «Нет, strncpy() не является «более безопасной» функцией strcpy()». 2012.

[18] «Пражский стрингологический клуб» . Stringology.org . Архивировано из оригинала 1 июня 2015 года . Проверено 23 мая 2015 г.

[19] Эвартс, Холли (18 марта 2021 г.). «Бывший декан Цви Галил вошел в десятку самых влиятельных ученых-компьютерщиков за последнее десятилетие» . Колумбия Инжиниринг . Он изобрел термин «стрингология», которая является подразделом строковых алгоритмов.

[20] Крошмор, Максим (2002). Жемчужины стрингологии . Сингапур. п. ISBN против 981-02-4782-6 . Термин «стрингология» — популярное прозвище для строковых алгоритмов, а также для текстовых алгоритмов. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[21] «Основной Perl» . Архивировано из оригинала 21 апреля 2012 г. Самая известная сила Perl заключается в манипулировании строками с помощью регулярных выражений.

[22] «Строковые инструкции x86» . Архивировано из оригинала 27 марта 2015 г.

[23] Флетчер, Питер; Хойл, Хьюз; Пэтти, К. Уэйн (1991). Основы дискретной математики . PWS-Кент. п. 114. ИСБН 0-53492-373-9 . Пусть Σ — алфавит. Непустое слово над Σ — это конечная последовательность с областью определения I _n (для некоторого n ∈ ℕ) и кодобластью Σ.

[24] Шенфилд, Джозеф Р. (2010) [1967]. Математическая логика (переиздание). ЦРК Пресс. п. 2. ISBN 978-156881135-2 . Любая конечная последовательность символов языка называется выражением этого языка.

[partee-25] Jump up to: ^а ^б Барбара Х. Парти; Алиса тер Мейлен ; Роберт Э. Уолл (1990). Математические методы в лингвистике . Клювер.

[26] Джон Э. Хопкрофт, Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. ISBN 0-201-02988-Х . Здесь: разд.1.1, п.1

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

v т и Струны
Строковая метрика	Примерное соответствие строк Алгоритм битап Расстояние Дамерау – Левенштейна Изменить расстояние Сопоставление гештальт-образцов Расстояние Хэмминга Расстояние Яро – Винклера Расстояние Ли Автомат Левенштейна Расстояние Левенштейна Алгоритм Вагнера-Фишера
Алгоритм поиска строк	Алгоритм Апостола – Джанкарло Алгоритм поиска строк Бойера – Мура Алгоритм Бойера – Мура – Хорспула Алгоритм Кнута – Морриса – Пратта Алгоритм Рабина – Карпа Алгоритм Райта Триграммный поиск Алгоритм двустороннего сопоставления строк Алгоритм сопоставления строк Чжу – Такаока
Поиск нескольких строк	Ахо – Корасик Алгоритм Комментца-Вальтера
Регулярное выражение	Сравнение механизмов регулярных выражений Регулярная грамматика Конструкция Томпсона Недетерминированный конечный автомат
Sequence alignment	BLAST Hirschberg's algorithm Needleman–Wunsch algorithm Smith–Waterman algorithm
Data structure	DAFSA Suffix array Suffix automaton Suffix tree Generalized suffix tree Rope Ternary search tree Trie
Other	Parsing Pattern matching Compressed pattern matching Longest common subsequence Longest common substring Sequential pattern mining Sorting String rewriting systems String operations

v т и Типы данных
Uninterpreted	Bit Byte Trit Tryte Word Bit array
Numeric	Arbitrary-precision or bignum Complex Decimal Fixed point Floating point Reduced precision Minifloat Half precision bfloat16 Single precision Double precision Quadruple precision Octuple precision Extended precision Long double Integer signedness Interval Rational
Указатель	Адрес физический виртуальный Ссылка
Текст	Характер Нить завершающийся нулем
Композитный	Алгебраический тип данных обобщенный Множество Ассоциативный массив Сорт Зависимый Равенство Индуктивный Пересечение Список Объект метаобъект Тип опции Продукт Запись или структура Уточнение Набор Союз отмеченный
Другой	логическое значение Нижний тип Коллекция Перечислимый тип Исключение Тип функции Непрозрачный тип данных Рекурсивный тип данных Семафор Транслировать Строго типизированный идентификатор Тип верха Тип класса Пустой тип Тип устройства Пустота
Связанный темы	Абстрактный тип данных Бокс Структура данных Общий Добрый метакласс Параметрический полиморфизм Примитивный тип данных Интерфейс Подтипирование Тип конструктора Преобразование типов Типовая система Теория типов Переменная