stringtranslate.com

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

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

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

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

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

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

Цель

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

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

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

История

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

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

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

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

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

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

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

Длина строки

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

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

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

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

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

Реализации

Некоторые языки, такие как C++ , Perl и Ruby , обычно позволяют изменять содержимое строки после ее создания; такие строки называются изменяемыми . В других языках, таких как Java , JavaScript , Lua , Python и Go , значение фиксировано, и для внесения каких-либо изменений необходимо создать новую строку; такие строки называются неизменяемыми . Некоторые из этих языков с неизменяемыми строками также предоставляют другой тип, который является изменяемыми, например Java и .NET , StringBuilderпотокобезопасный Java StringBufferи Cocoa NSMutableString . У неизменяемости есть как преимущества, так и недостатки: хотя неизменяемые строки могут потребовать неэффективного создания множества копий, они проще и полностью потокобезопасны .

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

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

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

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

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

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

Нуль-терминированный

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

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

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

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

С байтовым и битовым окончанием

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

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

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

Длина-префикс

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

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

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

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

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

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

класс строка { size_t длина ; символ * текст ; };      

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например, если Σ = {0, 1}, то Σ * = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}. Хотя само множество Σ * счетно бесконечно , каждый элемент Σ * представляет собой строку конечной длины.

Множество строк над Σ (т. е. любое подмножество Σ * ) называется формальным языком над Σ. Например, если Σ = {0, 1}, то множество строк с четным числом нулей, {ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, ...}, является формальным языком над Σ.

Конкатенация и подстроки

Конкатенация — важная бинарная операция на Σ * . Для любых двух строк s и t в Σ * их конкатенация определяется как последовательность символов в s, за которой следует последовательность символов в t , и обозначается st . Например, если Σ = {a, b, ..., z}, s  = bear, и t  = hug, то st  = bearhugи ts  = hugbear.

Конкатенация строк является ассоциативной , но некоммутативной операцией . Пустая строка ε служит элементом тождества ; для любой строки s , ε s = s ε = s . Таким образом, множество Σ * и операция конкатенации образуют моноид , свободный моноид, порожденный Σ. Кроме того, функция длины определяет гомоморфизм моноида из Σ * в неотрицательные целые числа (то есть функцию , такую, что ).

Говорят, что строка s является подстрокой или фактором t , если существуют (возможно, пустые) строки u и v , такие что t = usv . Отношение «является подстрокой» определяет частичный порядок на Σ * , наименьшим элементом которого является пустая строка.

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

Строка s называется префиксом t , если существует строка u, такая что t = su . Если u непусто, то s называется собственным префиксом t . Симметрично, строка s называется суффиксом t , если существует строка u, такая что t = us . Если u непусто, то s называется собственным суффиксом t . Суффиксы и префиксы являются подстроками t . Оба отношения «является префиксом» и «является суффиксом» являются порядками префиксов .

Обратный ход

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

Вращения

Говорят, что строка s = uv является поворотом t, если t = vu . Например, если Σ = {0, 1}, то строка 0011001 является поворотом 0100110, где u = 00110 и v = 01. В качестве другого примера, строка abc имеет три различных поворота, а именно: сама abc (с u = abc, v = ε), bca (с u = bc, v = a) и cab (с u = c, v = ab).

Лексикографический порядок

Часто бывает полезно определить порядок на множестве строк. Если алфавит Σ имеет полный порядок (ср. алфавитный порядок ), можно определить полный порядок на Σ *, называемый лексикографическим порядком . Лексикографический порядок является полным, если алфавитный порядок является, но не является обоснованным для любого нетривиального алфавита, даже если алфавитный порядок является. Например, если Σ = {0, 1} и 0 < 1, то лексикографический порядок на Σ * включает отношения ε < 0 < 00 < 000 < ... < 0001 < ... < 001 < ... < 01 < 010 < ... < 011 < 0110 < ... < 01111 < ... < 1 < 10 < 100 < ... < 101 < ... < 111 < ... < 11111 < ... < 11111 ... Относительно этого порядка, например, бесконечное множество { 1, 01, 001, 0001, 00001, 000001, ... } не имеет минимального элемента.

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

Операции со строками

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

Топология

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

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

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

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

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

Ссылки

  1. ^ "Введение в Java – MFC 158 G". Архивировано из оригинала 2016-03-03. Строковые литералы (или константы) называются "анонимными строками"
  2. ^ de St. Germain, H. James. «Струны». Университет Юты, Школа вычислений Калерта .
  3. ^ Фрэнсис, Дэвид М.; Мерк, Хизер Л. (14 ноября 2019 г.). «ДНК как биохимическая сущность и строка данных».
  4. ^ abc Burchfield, RW (1986). "string". Приложение к Оксфордскому словарю английского языка . Oxford at Clarendon Press.
  5. ^ "string". Оксфордский словарь английского языка . Том X. Оксфорд, Clarendon Press. 1933.
  6. ^ "string (сущ.)". Онлайн-словарь этимологии .
  7. ^ Уитни, Уильям Дуайт ; Смит, Бенджамин Э. "string". The Century Dictionary . Нью-Йорк: The Century Company. С. 5994.
  8. «Упадок старого Союза». Milwaukee Sentinel . 11 января 1898 г. стр. 3.
  9. ^ Льюис, CI (1918). Обзор символической логики. Беркли: Издательство Калифорнийского университета. С. 355.
  10. ^ Сэммет, Жан Э. (июль 1972 г.). «Языки программирования: история и будущее» (PDF) . Сообщения ACM . 15 (7). doi :10.1145/361454.361485. S2CID  2003242.
  11. ^ Брайант, Рэндал Э .; Дэвид, О'Халларон (2003), Компьютерные системы: точка зрения программиста (редакция 2003 г.), Аппер Сэдл Ривер, Нью-Джерси: Pearson Education, стр. 40, ISBN 0-13-034074-X, архивировано из оригинала 2007-08-06
  12. ^ Уэрмут, Джефф. "Список сборки ПЗУ Sinclair ZX80". Архивировано из оригинала 15 августа 2015 г.{{cite web}}: CS1 maint: неподходящий URL ( ссылка )
  13. ^ Эллисон, Деннис. "Design Notes for Tiny BASIC". Архивировано из оригинала 2017-04-10.
  14. ^ Чарльз Кроули. "Структуры данных для текстовых последовательностей" Архивировано 04.03.2016 на Wayback Machine . Раздел "Введение" Архивировано 04.04.2016 на Wayback Machine .
  15. ^ "strlcpy и strlcat — согласованное, безопасное копирование и конкатенация строк". Архивировано 13.03.2016 на Wayback Machine
  16. ^ "Трепет по поводу strcpy, strncpy и strlcpy." Архивировано 29.02.2016 на Wayback Machine
  17. ^ Кит Томпсон. «Нет, strncpy() не является «более безопасной» strcpy()». 2012.
  18. ^ "Пражский клуб стрингологии". stringology.org . Архивировано из оригинала 1 июня 2015 . Получено 23 мая 2015 .
  19. ^ Эвартс, Холли (18 марта 2021 г.). «Бывший декан Цви Галил назван в числе 10 самых влиятельных ученых-компьютерщиков за последнее десятилетие». Columbia Engineering . Он изобрел термин «стрингология», который является подразделом строковых алгоритмов,
  20. ^ Crochemore, Maxime (2002). Драгоценности стрингологии . Сингапур. стр. v. ISBN 981-02-4782-6Термин «стрингология» — популярное название строковых алгоритмов, а также текстовых алгоритмов.{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
  21. ^ "Essential Perl". Архивировано из оригинала 2012-04-21. Самая известная сила Perl — это манипуляция строками с помощью регулярных выражений.
  22. ^ "x86 string instructions". Архивировано из оригинала 2015-03-27.
  23. ^ Флетчер, Питер; Хойл, Хьюз; Патти, К. Уэйн (1991). Основы дискретной математики . PWS-Kent. стр. 114. ISBN 0-53492-373-9. Пусть Σ — алфавит. Непустое слово над Σ — это конечная последовательность с областью значений I n (для некоторого n ∈ ℕ) и областью значений Σ.
  24. ^ Шенфилд, Джозеф Р. (2010) [1967]. Математическая логика (переиздание). CRC Press. стр. 2. ISBN 978-156881135-2. Любая конечная последовательность символов языка называется выражением этого языка.
  25. ^ ab Барбара Х. Парти; Элис тер Мейлен ; Роберт Э. Уолл (1990). Математические методы в лингвистике . Клювер.
  26. ^ Джон Э. Хопкрофт, Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Addison-Wesley. ISBN 0-201-02988-X.Здесь: раздел 1.1, стр.1