![String Variable Diagram Middle Aspect Ratio](https://upload.wikimedia.org/wikipedia/commons/4/45/String_Variable_Diagram_Middle_Aspect_Ratio.png)
In
computer programming
Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as ana ...
, a string is traditionally a
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
of characters, either as a
literal constant or as some kind of
variable
Variable may refer to:
* Variable (computer science), a symbolic name associated with a value and whose associated value may be changed
* Variable (mathematics), a symbol that represents a quantity in a mathematical expression, as used in many ...
. The latter may allow its elements to be mutated and the length changed, or it may be fixed (after creation). A string is generally considered as a
data type
In computer science and computer programming, a data type (or simply type) is a set of possible values and a set of allowed operations on it. A data type tells the compiler or interpreter how the programmer intends to use the data. Most progra ...
and is often implemented as an
array data structure
In computer science, an array is a data structure consisting of a collection of ''elements'' (values or variables), each identified by at least one ''array index'' or ''key''. An array is stored such that the position of each element can be co ...
of
byte
The byte is a unit of digital information that most commonly consists of eight bits. Historically, the byte was the number of bits used to encode a single character of text in a computer and for this reason it is the smallest addressable unit ...
s (or
word
A word is a basic element of language that carries an semantics, objective or pragmatics, practical semantics, meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of w ...
s) that stores a sequence of elements, typically characters, using some
character encoding
Character encoding is the process of assigning numbers to Graphics, graphical character (computing), characters, especially the written characters of Language, human language, allowing them to be Data storage, stored, Data communication, transmi ...
. ''String'' may also denote more general
arrays
An array is a systematic arrangement of similar objects, usually in rows and columns.
Things called an array include:
{{TOC right
Music
* In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
or other sequence (or
list
A ''list'' is any set of items in a row. List or lists may also refer to:
People
* List (surname)
Organizations
* List College, an undergraduate division of the Jewish Theological Seminary of America
* SC Germania List, German rugby union ...
) data types and structures.
Depending on the programming language and precise data type used, a
variable
Variable may refer to:
* Variable (computer science), a symbolic name associated with a value and whose associated value may be changed
* Variable (mathematics), a symbol that represents a quantity in a mathematical expression, as used in many ...
declared to be a string may either cause storage in memory to be statically allocated for a predetermined maximum length or employ
dynamic allocation
In computer science, manual memory management refers to the usage of manual instructions by the programmer to identify and deallocate unused objects, or garbage. Up until the mid-1990s, the majority of programming languages used in industry supp ...
to allow it to hold a variable number of elements.
When a string appears literally in
source code
In computing, source code, or simply code, is any collection of code, with or without comments, written using a human-readable programming language, usually as plain text. The source code of a program is specially designed to facilitate the wo ...
, it is known as a
string literal
A string literal (computer programming), literal or anonymous string is a String (computer science), string value in the source code of a computer program. Modern Computer programming, programming languages commonly use a quoted sequence of charact ...
or an anonymous string.
In
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
s, which are used in
mathematical logic
Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...
and
theoretical computer science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumsc ...
, a string is a finite sequence of
symbol
A symbol is a mark, sign, or word that indicates, signifies, or is understood as representing an idea, object, or relationship. Symbols allow people to go beyond what is known or seen by creating linkages between otherwise very different conc ...
s that are chosen from a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
called an
alphabet
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syll ...
.
String datatypes
A string datatype is a datatype modeled on the idea of a formal string. Strings are such an important and useful datatype that they are implemented in nearly every
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
. In some languages they are available as
primitive type
In computer science, primitive data types are a set of basic data types from which all other data types are constructed. Specifically it often refers to the limited set of data representations in use by a particular processor, which all compiled p ...
s and in others as
composite type
In computer science, a composite data type or compound data type is any data type which can be constructed in a program using the programming language's primitive data types and other composite types. It is sometimes called a structure or aggrega ...
s. The
syntax
In linguistics, syntax () is the study of how words and morphemes combine to form larger units such as phrases and sentences. Central concerns of syntax include word order, grammatical relations, hierarchical sentence structure ( constituency) ...
of most high-level programming languages allows for a string, usually quoted in some way, to represent an instance of a string datatype; such a meta-string is called a ''literal'' or ''string literal''.
String length
Although formal strings can have an arbitrary finite length, the length of strings in real languages is often constrained to an artificial maximum. In general, there are two types of string datatypes: ''fixed-length strings'', which have a fixed maximum length to be determined at
compile time
In computer science, compile time (or compile-time) describes the time window during which a computer program is compiled.
The term is used as an adjective to describe concepts related to the context of program compilation, as opposed to concept ...
and which use the same amount of memory whether this maximum is needed or not, and ''variable-length strings'', whose length is not arbitrarily fixed and which can use varying amounts of memory depending on the actual requirements at run time (see
Memory management
Memory management is a form of resource management applied to computer memory. The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their request, and free it for reuse when ...
). Most strings in modern
programming languages
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
are variable-length strings. Of course, even variable-length strings are limited in length – by the size of available
computer memory
In computing, memory is a device or system that is used to store information for immediate use in a computer or related computer hardware and digital electronic devices. The term ''memory'' is often synonymous with the term ''primary storage ...
. The string length can be stored as a separate integer (which may put another artificial limit on the length) or implicitly through a termination character, usually a character value with all bits zero such as in C programming language. See also "
Null-terminated" below.
Character encoding
String datatypes have historically allocated one byte per character, and, although the exact character set varied by region, character encodings were similar enough that programmers could often get away with ignoring this, since characters a program treated specially (such as period and space and comma) were in the same place in all the encodings a program would encounter. These character sets were typically based on
ASCII
ASCII ( ), abbreviated from American Standard Code for Information Interchange, is a character encoding standard for electronic communication. ASCII codes represent text in computers, telecommunications equipment, and other devices. Because of ...
or
EBCDIC
Extended Binary Coded Decimal Interchange Code (EBCDIC; ) is an eight-bit character encoding used mainly on IBM mainframe and IBM midrange computer operating systems. It descended from the code used with punched cards and the corresponding six- ...
. If text in one encoding was displayed on a system using a different encoding, text was often
mangled, though often somewhat readable and some computer users learned to read the mangled text.
Logograph
In a written language, a logogram, logograph, or lexigraph is a written character that represents a word or morpheme. Chinese characters (pronounced '' hanzi'' in Mandarin, ''kanji'' in Japanese, ''hanja'' in Korean) are generally logograms, ...
ic languages such as
Chinese
Chinese can refer to:
* Something related to China
* Chinese people, people of Chinese nationality, citizenship, and/or ethnicity
**''Zhonghua minzu'', the supra-ethnic concept of the Chinese nation
** List of ethnic groups in China, people of va ...
,
Japanese
Japanese may refer to:
* Something from or related to Japan, an island country in East Asia
* Japanese language, spoken mainly in Japan
* Japanese people, the ethnic group that identifies with Japan through ancestry or culture
** Japanese diaspor ...
, and
Korean
Korean may refer to:
People and culture
* Koreans, ethnic group originating in the Korean Peninsula
* Korean cuisine
* Korean culture
* Korean language
**Korean alphabet, known as Hangul or Chosŏn'gŭl
**Korean dialects and the Jeju language
** ...
(known collectively as
CJK) need far more than 256 characters (the limit of a one 8-bit byte per-character encoding) for reasonable representation. The normal solutions involved keeping single-byte representations for ASCII and using two-byte representations for CJK
ideographs
An ideogram or ideograph (from Greek "idea" and "to write") is a graphic symbol that represents an idea or concept, independent of any particular language, and specific words or phrases. Some ideograms are comprehensible only by familiari ...
. Use of these with existing code led to problems with matching and cutting of strings, the severity of which depended on how the character encoding was designed. Some encodings such as the
EUC family guarantee that a byte value in the ASCII range will represent only that ASCII character, making the encoding safe for systems that use those characters as field separators. Other encodings such as
ISO-2022
ISO/IEC 2022 ''Information technology—Character code structure and extension techniques'', is an ISO/IEC standard (equivalent to the ECMA standard ECMA-35, the ANSI standard ANSI X3.41 and the Japanese Industrial Standard JIS X 0202) in the f ...
and
Shift-JIS do not make such guarantees, making matching on byte codes unsafe. These encodings also were not "self-synchronizing", so that locating character boundaries required backing up to the start of a string, and pasting two strings together could result in corruption of the second string.
Unicode
Unicode, formally The Unicode Standard,The formal version reference is is an information technology Technical standard, standard for the consistent character encoding, encoding, representation, and handling of Character (computing), text expre ...
has simplified the picture somewhat. Most programming languages now have a datatype for Unicode strings. Unicode's preferred byte stream format
UTF-8
UTF-8 is a variable-width encoding, variable-length character encoding used for electronic communication. Defined by the Unicode Standard, the name is derived from ''Unicode'' (or ''Universal Coded Character Set'') ''Transformation Format 8-bit'' ...
is designed not to have the problems described above for older multibyte encodings. UTF-8, UTF-16 and
UTF-32
UTF-32 (32-bit Unicode transformation format, Unicode Transformation Format) is a fixed-length Character encoding, encoding used to encode Unicode code points that uses exactly 32 bits (four bytes) per code point (but a number of leading bits must ...
require the programmer to know that the fixed-size code units are different than the "characters", the main difficulty currently is incorrectly designed APIs that attempt to hide this difference (UTF-32 does make ''code points'' fixed-sized, but these are not "characters" due to composing codes).
Implementations
Some languages, such as
C++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
,
Perl
Perl is a family of two high-level, general-purpose, interpreted, dynamic programming languages. "Perl" refers to Perl 5, but from 2000 to 2019 it also referred to its redesigned "sister language", Perl 6, before the latter's name was offici ...
and
Ruby
A ruby is a pinkish red to blood-red colored gemstone, a variety of the mineral corundum ( aluminium oxide). Ruby is one of the most popular traditional jewelry gems and is very durable. Other varieties of gem-quality corundum are called sa ...
, normally allow the contents of a string to be changed after it has been created; these are termed ''mutable'' strings. In other languages, such as
Java
Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's List ...
,
JavaScript
JavaScript (), often abbreviated as JS, is a programming language that is one of the core technologies of the World Wide Web, alongside HTML and CSS. As of 2022, 98% of Website, websites use JavaScript on the Client (computing), client side ...
,
Lua
Lua or LUA may refer to:
Science and technology
* Lua (programming language)
* Latvia University of Agriculture
* Last universal ancestor, in evolution
Ethnicity and language
* Lua people, of Laos
* Lawa people, of Thailand sometimes referred t ...
,
Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
, and
Go, the value is fixed and a new string must be created if any alteration is to be made; these are termed ''immutable'' strings. Some of these languages with immutable strings also provide another type that is mutable, such as Java and
.NET's , the thread-safe Java , and the
Cocoa
Cocoa may refer to:
Chocolate
* Chocolate
* ''Theobroma cacao'', the cocoa tree
* Cocoa bean, seed of ''Theobroma cacao''
* Chocolate liquor, or cocoa liquor, pure, liquid chocolate extracted from the cocoa bean, including both cocoa butter and ...
NSMutableString
. There are both advantages and disadvantages to immutability: although immutable strings may require inefficiently creating many copies, they are simpler and completely
thread-safe Thread safety is a computer programming concept applicable to multi-threaded code. Thread-safe code only manipulates shared data structures in a manner that ensures that all threads behave properly and fulfill their design specifications without uni ...
.
Strings are typically implemented as
arrays
An array is a systematic arrangement of similar objects, usually in rows and columns.
Things called an array include:
{{TOC right
Music
* In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
of bytes, characters, or code units, in order to allow fast access to individual units or substrings—including characters when they have a fixed length. A few languages such as
Haskell
Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lang ...
implement them as
linked list
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whic ...
s instead.
Some languages, such as
Prolog
Prolog is a logic programming language associated with artificial intelligence and computational linguistics.
Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is intended primarily ...
and
Erlang, avoid implementing a dedicated string datatype at all, instead adopting the convention of representing strings as lists of character codes.
Representations
Representations of strings depend heavily on the choice of character repertoire and the method of character encoding. Older string implementations were designed to work with repertoire and encoding defined by ASCII, or more recent extensions like the
ISO 8859
ISO/IEC 8859 is a joint ISO and IEC series of standards for 8-bit character encodings. The series of standards consists of numbered parts, such as ISO/IEC 8859-1, ISO/IEC 8859-2, etc. There are 15 parts, excluding the abandoned ISO/IEC 8859-12 ...
series. Modern implementations often use the extensive repertoire defined by Unicode along with a variety of complex encodings such as UTF-8 and UTF-16.
The term ''byte string'' usually indicates a general-purpose string of bytes, rather than strings of only (readable) characters, strings of bits, or such. Byte strings often imply that bytes can take any value and any data can be stored as-is, meaning that there should be no value interpreted as a termination value.
Most string implementations are very similar to variable-length
array
An array is a systematic arrangement of similar objects, usually in rows and columns.
Things called an array include:
{{TOC right
Music
* In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
s with the entries storing the
character code
Character encoding is the process of assigning numbers to graphical characters, especially the written characters of human language, allowing them to be stored, transmitted, and transformed using digital computers. The numerical values that ...
s of corresponding characters. The principal difference is that, with certain encodings, a single logical character may take up more than one entry in the array. This happens for example with UTF-8, where single codes (
UCS code points) can take anywhere from one to four bytes, and single characters can take an arbitrary number of codes. In these cases, the logical length of the string (number of characters) differs from the physical length of the array (number of bytes in use).
UTF-32
UTF-32 (32-bit Unicode transformation format, Unicode Transformation Format) is a fixed-length Character encoding, encoding used to encode Unicode code points that uses exactly 32 bits (four bytes) per code point (but a number of leading bits must ...
avoids the first part of the problem.
Null-terminated
The length of a string can be stored implicitly by using a special terminating character; often this is the
null character
The null character (also null terminator) is a control character with the value zero.
It is present in many character sets, including those defined by the Baudot and ITA2 codes, ISO/IEC 646 (or ASCII), the C0 control code, the Universal Coded Ch ...
(NUL), which has all bits zero, a convention used and perpetuated by the popular
C programming language
''The C Programming Language'' (sometimes termed ''K&R'', after its authors' initials) is a computer programming book written by Brian Kernighan and Dennis Ritchie, the latter of whom originally designed and implemented the language, as well as ...
. Hence, this representation is commonly referred to as a C string. This representation of an ''n''-character string takes ''n'' + 1 space (1 for the terminator), and is thus an
implicit data structure In computer science, an implicit data structure or space-efficient data structure is a data structure that stores very little information other than the main or required data: a data structure that requires low overhead. They are called "implicit" ...
.
In terminated strings, the terminating code is not an allowable character in any string. Strings with ''length'' field do not have this limitation and can also store arbitrary
binary data
Binary data is data whose unit can take on only two possible states. These are often labelled as 0 and 1 in accordance with the binary numeral system and Boolean algebra.
Binary data occurs in many different technical and scientific fields, wher ...
.
An example of a ''null-terminated string'' stored in a 10-byte
buffer
Buffer may refer to:
Science
* Buffer gas, an inert or nonflammable gas
* Buffer solution, a solution used to prevent changes in pH
* Buffering agent, the weak acid or base in a buffer solution
* Lysis buffer, in cell biology
* Metal ion buffer
* ...
, along with its
ASCII
ASCII ( ), abbreviated from American Standard Code for Information Interchange, is a character encoding standard for electronic communication. ASCII codes represent text in computers, telecommunications equipment, and other devices. Because of ...
(or more modern
UTF-8
UTF-8 is a variable-width encoding, variable-length character encoding used for electronic communication. Defined by the Unicode Standard, the name is derived from ''Unicode'' (or ''Universal Coded Character Set'') ''Transformation Format 8-bit'' ...
) representation as 8-bit
hexadecimal number
In mathematics and computing, the hexadecimal (also base-16 or simply hex) numeral system is a Numeral system#Positional systems in detail, positional numeral system that represents numbers using a radix (base) of 16. Unlike the decimal system ...
s is:
The length of the string in the above example, "
FRANK
", is 5 characters, but it occupies 6 bytes. Characters after the terminator do not form part of the representation; they may be either part of other data or just garbage. (Strings of this form are sometimes called ''ASCIZ strings'', after the original
assembly language
In computer programming, assembly language (or assembler language, or symbolic machine code), often referred to simply as Assembly and commonly abbreviated as ASM or asm, is any low-level programming language with a very strong correspondence be ...
directive used to declare them.)
Byte- and bit-terminated
Using a special byte other than null for terminating strings has historically appeared in both hardware and software, though sometimes with a value that was also a printing character.
$
was used by many assembler systems,
:
used by
CDC
The Centers for Disease Control and Prevention (CDC) is the national public health agency of the United States. It is a United States federal agency, under the Department of Health and Human Services, and is headquartered in Atlanta, Georgi ...
systems (this character had a value of zero), and the
ZX80
The Sinclair ZX80 is a home computer launched on 29 January 1980 by Science of Cambridge Ltd. (later to be better known as Sinclair Research). It is notable for being one of the first computers available in the United Kingdom for less than a h ...
used
"
since this was the string delimiter in its BASIC language.
Somewhat similar, "data processing" machines like the
IBM 1401
The IBM 1401 is a variable-wordlength decimal computer that was announced by IBM on October 5, 1959. The first member of the highly successful IBM 1400 series, it was aimed at replacing unit record equipment for processing data stored on pu ...
used a special
word mark bit to delimit strings at the left, where the operation would start at the right. This bit had to be clear in all other parts of the string. This meant that, while the IBM 1401 had a seven-bit word, almost no-one ever thought to use this as a feature, and override the assignment of the seventh bit to (for example) handle ASCII codes.
Early microcomputer software relied upon the fact that ASCII codes do not use the high-order bit, and set it to indicate the end of a string. It must be reset to 0 prior to output.
Length-prefixed
The length of a string can also be stored explicitly, for example by prefixing the string with the length as a byte value. This convention is used in many
Pascal
Pascal, Pascal's or PASCAL may refer to:
People and fictional characters
* Pascal (given name), including a list of people with the name
* Pascal (surname), including a list of people and fictional characters with the name
** Blaise Pascal, Fren ...
dialects; as a consequence, some people call such a string a Pascal string or P-string. Storing the string length as byte limits the maximum string length to 255. To avoid such limitations, improved implementations of P-strings use 16-, 32-, or 64-bit
words
A word is a basic element of language that carries an objective or practical meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no consen ...
to store the string length. When the ''length'' field covers the
address space
In computing, an address space defines a range of discrete addresses, each of which may correspond to a network host, peripheral device, disk sector, a memory cell or other logical or physical entity.
For software programs to save and retrieve st ...
, strings are limited only by the
available memory.
If the length is bounded, then it can be encoded in constant space, typically a machine word, thus leading to an
implicit data structure In computer science, an implicit data structure or space-efficient data structure is a data structure that stores very little information other than the main or required data: a data structure that requires low overhead. They are called "implicit" ...
, taking ''n'' + ''k'' space, where ''k'' is the number of characters in a word (8 for 8-bit ASCII on a 64-bit machine, 1 for 32-bit UTF-32/UCS-4 on a 32-bit machine, etc.).
If the length is not bounded, encoding a length ''n'' takes log(''n'') space (see
fixed-length code A prefix code is a type of code system distinguished by its possession of the "prefix property", which requires that there is no whole code word in the system that is a prefix (initial segment) of any other code word in the system. It is trivially ...
), so length-prefixed strings are a
succinct data structure In computer science, a succinct data structure is a data structure which uses an amount of space that is "close" to the information-theoretic lower bound, but (unlike other compressed representations) still allows for efficient query operations. Th ...
, encoding a string of length ''n'' in log(''n'') + ''n'' space.
In the latter case, the length-prefix field itself doesn't have fixed length, therefore the actual string data needs to be moved when the string grows such that the length field needs to be increased.
Here is a Pascal string stored in a 10-byte buffer, along with its ASCII / UTF-8 representation:
Strings as records
Many languages, including object-oriented ones, implement strings as
records with an internal structure like:
class string ;
However, since the implementation is usually
hidden, the string must be accessed and modified through member functions.
text
is a pointer to a dynamically allocated memory area, which might be expanded as needed. See also
string (C++)
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
.
Other representations
Both character termination and length codes limit strings: For example, C character arrays that contain null (NUL) characters cannot be handled directly by
C string
C, or c, is the third letter in the Latin alphabet, used in the modern English alphabet, the alphabets of other western European languages and others worldwide. Its name in English is ''cee'' (pronounced ), plural ''cees''.
History
"C" ...
library functions: Strings using a length code are limited to the maximum value of the length code.
Both of these limitations can be overcome by clever programming.
It is possible to create data structures and functions that manipulate them that do not have the problems associated with character termination and can in principle overcome length code bounds. It is also possible to optimize the string represented using techniques from
run length encoding
Run-length encoding (RLE) is a form of lossless data compression in which ''runs'' of data (sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original ...
(replacing repeated characters by the character value and a length) and
Hamming encoding.
While these representations are common, others are possible. Using
rope
A rope is a group of yarns, plies, fibres, or strands that are twisted or braided together into a larger and stronger form. Ropes have tensile strength and so can be used for dragging and lifting. Rope is thicker and stronger than similarly ...
s makes certain string operations, such as insertions, deletions, and concatenations more efficient.
The core data structure in a
text editor
A text editor is a type of computer program that edits plain text. Such programs are sometimes known as "notepad" software (e.g. Windows Notepad). Text editors are provided with operating systems and software development packages, and can be us ...
is the one that manages the string (sequence of characters) that represents the current state of the file being edited.
While that state could be stored in a single long consecutive array of characters, a typical text editor instead uses an alternative representation as its sequence data structure—a
gap buffer
A gap buffer in computer science is a dynamic array that allows efficient insertion and deletion operations clustered near the same location. Gap buffers are especially common in text editors, where most changes to the text occur at or near the cur ...
, a
linked list
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whic ...
of lines, a
piece table In computing, a piece table is a data structure typically used to represent a text document while it is edited in a text editor. Initially a reference (or 'span') to the whole of the original file is created, which represents the as yet unchanged ...
, or a
rope
A rope is a group of yarns, plies, fibres, or strands that are twisted or braided together into a larger and stronger form. Ropes have tensile strength and so can be used for dragging and lifting. Rope is thicker and stronger than similarly ...
—which makes certain string operations, such as insertions, deletions, and undoing previous edits, more efficient.
Security concerns
The differing memory layout and storage requirements of strings can affect the security of the program accessing the string data. String representations requiring a terminating character are commonly susceptible to
buffer overflow
In information security and programming, a buffer overflow, or buffer overrun, is an anomaly whereby a program, while writing data to a buffer, overruns the buffer's boundary and overwrites adjacent memory locations.
Buffers are areas of memory ...
problems if the terminating character is not present, caused by a coding error or an
attacker
In some team sports, an attacker is a specific type of player, usually involved in aggressive play. Heavy attackers are, usually, placed up front: their goal is to score the most possible points for the team. In association football, attackers a ...
deliberately altering the data. String representations adopting a separate length field are also susceptible if the length can be manipulated. In such cases, program code accessing the string data requires
bounds checking
In computer programming, bounds checking is any method of detecting whether a variable is within some bounds before it is used. It is usually used to ensure that a number fits into a given type (range checking), or that a variable being used as a ...
to ensure that it does not inadvertently access or change data outside of the string memory limits.
String data is frequently obtained from user input to a program. As such, it is the responsibility of the program to validate the string to ensure that it represents the expected format. Performing
limited or no validation of user input can cause a program to be vulnerable to
code injection
Code injection is the exploitation of a computer bug that is caused by processing invalid data. The injection is used by an attacker to introduce (or "inject") code into a vulnerable computer program and change the course of execution. The res ...
attacks.
Literal strings
Sometimes, strings need to be embedded inside a text file that is both human-readable and intended for consumption by a machine. This is needed in, for example, source code of programming languages, or in configuration files. In this case, the NUL character doesn't work well as a terminator since it is normally invisible (non-printable) and is difficult to input via a keyboard. Storing the string length would also be inconvenient as manual computation and tracking of the length is tedious and error-prone.
Two common representations are:
* Surrounded by
quotation mark
Quotation marks (also known as quotes, quote marks, speech marks, inverted commas, or talking marks) are punctuation marks used in pairs in various writing systems to set off direct speech, a quotation, or a phrase. The pair consists of an ...
s (ASCII
0x22 double quote
"str"
or ASCII 0x27 single quote
'str'
), used by most programming languages. To be able to include special characters such as the quotation mark itself, newline characters, or non-printable characters,
escape sequence
In computer science, an escape sequence is a combination of characters that has a meaning other than the literal characters contained therein; it is marked by one or more preceding (and possibly terminating) characters.
Examples
* In C and man ...
s are often available, usually prefixed with the
backslash
The backslash is a typographical mark used mainly in computing and mathematics. It is the mirror image of the common slash . It is a relatively recent mark, first documented in the 1930s.
History
, efforts to identify either the origin o ...
character (ASCII 0x5C).
* Terminated by a
newline
Newline (frequently called line ending, end of line (EOL), next line (NEL) or line break) is a control character or sequence of control characters in character encoding specifications such as ASCII, EBCDIC, Unicode, etc. This character, or a ...
sequence, for example in Windows
INI files.
Non-text strings
While character strings are very common uses of strings, a string in computer science may refer generically to any sequence of homogeneously typed data. A
bit string
A bit array (also known as bitmask, bit map, bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level pa ...
or
byte string
In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable. The latter may allow its elements to be mutated and the length changed, or it may be fixed (after creation). ...
, for example, may be used to represent non-textual
binary data
Binary data is data whose unit can take on only two possible states. These are often labelled as 0 and 1 in accordance with the binary numeral system and Boolean algebra.
Binary data occurs in many different technical and scientific fields, wher ...
retrieved from a communications medium. This data may or may not be represented by a string-specific datatype, depending on the needs of the application, the desire of the programmer, and the capabilities of the programming language being used. If the programming language's string implementation is not
8-bit clean
''8-bit clean'' is an attribute of computer systems, communication channels, and other devices and software, that handle 8-bit character encodings correctly. Such encoding include the ISO 8859 series and the UTF-8 encoding of Unicode.
History
...
, data corruption may ensue.
C programmers draw a sharp distinction between a "string", aka a "string of characters", which by definition is always null terminated, vs. a "byte string" or "pseudo string" which may be stored in the same array but is often not null terminated.
Using
C string handling
The C programming language has a set of functions implementing operations on strings (character strings and byte strings) in its standard library. Various operations, such as copying, concatenation, tokenization and searching are supported. ...
functions on such a "byte string" often seems to work, but later leads to
security problems.
String processing algorithms
There are many
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
s for processing strings, each with various trade-offs. Competing algorithms can be
analyzed with respect to run time, storage requirements, and so forth. The name stringology was coined in 1984 by computer scientist
Zvi Galil
Zvi Galil ( he, צבי גליל; born June 26, 1947) is an Israeli-American computer scientist and mathematician. Galil served as the President of Tel Aviv University from 2007 through 2009. From 2010 to 2019, he was the dean of the Georgia Instit ...
for the theory of algorithms and data structures used for string processing.
Some categories of algorithms include:
*
String searching algorithm
In computer science, string-searching algorithms, sometimes called string-matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string ...
s for finding a given substring or pattern
*
String manipulation algorithm
String Function (computer science), functions are used in computer programming languages to manipulate a String (computer science), string or query information about a string (some do both).
Most programming languages that have a string datatyp ...
s
*
Sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a List (computing), list into an Total order, order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. ...
s
*
Regular expression
A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...
algorithms
*
Parsing
Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. The term ''parsing'' comes from Lati ...
a string
*
Sequence mining
Sequential pattern mining is a topic of data mining concerned with finding statistically relevant patterns between data examples where the values are delivered in a sequence. It is usually presumed that the values are discrete, and thus time serie ...
Advanced string algorithms often employ complex mechanisms and data structures, among them
suffix tree
In computer science, a suffix tree (also called PAT tree or, in an earlier form, position tree) is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values. Suffix trees allow particu ...
s and
finite-state machine
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
s.
Character string-oriented languages and utilities
Character strings are such a useful datatype that several languages have been designed in order to make string processing applications easy to write. Examples include the following languages:
*
awk
AWK (''awk'') is a domain-specific language designed for text processing and typically used as a data extraction and reporting tool. Like sed and grep, it is a filter, and is a standard feature of most Unix-like operating systems.
The AWK langu ...
*
Icon
An icon () is a religious work of art, most commonly a painting, in the cultures of the Eastern Orthodox, Oriental Orthodox, and Catholic churches. They are not simply artworks; "an icon is a sacred image used in religious devotion". The most ...
*
MUMPS
MUMPS ("Massachusetts General Hospital Utility Multi-Programming System"), or M, is an imperative, high-level programming language with an integrated transaction processing key–value database. It was originally developed at Massachusetts Gener ...
*
Perl
Perl is a family of two high-level, general-purpose, interpreted, dynamic programming languages. "Perl" refers to Perl 5, but from 2000 to 2019 it also referred to its redesigned "sister language", Perl 6, before the latter's name was offici ...
*
Rexx
Rexx (Restructured Extended Executor) is a programming language that can be interpreted or compiled. It was developed at IBM by Mike Cowlishaw. It is a structured, high-level programming language designed for ease of learning and reading. ...
*
Ruby
A ruby is a pinkish red to blood-red colored gemstone, a variety of the mineral corundum ( aluminium oxide). Ruby is one of the most popular traditional jewelry gems and is very durable. Other varieties of gem-quality corundum are called sa ...
*
sed
sed ("stream editor") is a Unix utility that parses and transforms text, using a simple, compact programming language. It was developed from 1973 to 1974 by Lee E. McMahon of Bell Labs,
and is available today for most operating systems.
sed wa ...
*
SNOBOL
SNOBOL ("StriNg Oriented and symBOlic Language") is a series of programming languages developed between 1962 and 1967 at AT&T Bell Laboratories by David J. Farber, Ralph E. Griswold and Ivan P. Polonsky, culminating in SNOBOL4. It was one of ...
*
Tcl
TCL or Tcl or TCLs may refer to:
Business
* TCL Technology, a Chinese consumer electronics and appliance company
**TCL Electronics, a subsidiary of TCL Technology
* Texas Collegiate League, a collegiate baseball league
* Trade Centre Limited ...
*
TTM
Many
Unix
Unix (; trademarked as UNIX) is a family of multitasking, multiuser computer operating systems that derive from the original AT&T Unix, whose development started in 1969 at the Bell Labs research center by Ken Thompson, Dennis Ritchie, and ot ...
utilities perform simple string manipulations and can be used to easily program some powerful string processing algorithms. Files and finite streams may be viewed as strings.
Some
API
An application programming interface (API) is a way for two or more computer programs to communicate with each other. It is a type of software Interface (computing), interface, offering a service to other pieces of software. A document or standa ...
s like
Multimedia Control Interface,
embedded SQL
Embedded SQL is a method of combining the computing power of a programming language and the database Data Manipulation Language, manipulation capabilities of SQL. Embedded SQL statement (programming), statements are SQL statements written inline wi ...
or
printf
The printf format string is a control parameter used by a class of functions in the input/output libraries of C and many other programming languages. The string is written in a simple template language: characters are usually copied literal ...
use strings to hold commands that will be interpreted.
Many
scripting programming language
A scripting language or script language is a programming language that is used to manipulate, customize, and automate the facilities of an existing system. Scripting languages are usually interpreted at runtime rather than compiled.
A scripting ...
s, including Perl,
Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
, Ruby, and Tcl employ
regular expression
A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...
s to facilitate text operations. Perl is particularly noted for its regular expression use, and many other languages and applications implement
Perl compatible regular expressions.
Some languages such as Perl and Ruby support
string interpolation
In computer programming, string interpolation (or variable interpolation, variable substitution, or variable expansion) is the process of evaluating a string literal containing one or more placeholders, yielding a result in which the placeholders ...
, which permits arbitrary expressions to be evaluated and included in string literals.
Character string functions
String function
String Function (computer science), functions are used in computer programming languages to manipulate a String (computer science), string or query information about a string (some do both).
Most programming languages that have a string datatyp ...
s are used to create strings or change the contents of a mutable string. They also are used to query information about a string. The set of functions and their names varies depending on the
computer programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming la ...
.
The most basic example of a string function is the
string length
In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable. The latter may allow its elements to be mutated and the length changed, or it may be fixed (after creation). ...
function – the function that returns the length of a string (not counting any terminator characters or any of the string's internal structural information) and does not modify the string. This function is often named
length
Length is a measure of distance. In the International System of Quantities, length is a quantity with dimension distance. In most systems of measurement a base unit for length is chosen, from which all other units are derived. In the Interna ...
or
len
. For example,
length("hello world")
would return 11. Another common function is
concatenation
In formal language, formal language theory and computer programming, string concatenation is the operation of joining character string (computer science), character strings wikt:end-to-end, end-to-end. For example, the concatenation of "sno ...
, where a new string is created by appending two strings, often this is the + addition operator.
Some
microprocessor
A microprocessor is a computer processor where the data processing logic and control is included on a single integrated circuit, or a small number of integrated circuits. The microprocessor contains the arithmetic, logic, and control circu ...
's
instruction set architecture
In computer science, an instruction set architecture (ISA), also called computer architecture, is an abstract model of a computer. A device that executes instructions described by that ISA, such as a central processing unit (CPU), is called an ' ...
s contain direct support for string operations, such as block copy (e.g. In
intel x86
x86 (also known as 80x86 or the 8086 family) is a family of complex instruction set computer (CISC) instruction set architectures initially developed by Intel based on the Intel 8086 microprocessor and its 8088 variant. The 8086 was introd ...
m
REPNZ MOVSB
).
Formal theory
Let Σ be a
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. Th ...
of symbols (alternatively called characters), called the
alphabet
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syll ...
. No assumption is made about the nature of the symbols. A string (or word) over Σ is any finite
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
of symbols from Σ.
For example, if Σ = , then ''01011'' is a string over Σ.
The ''
length
Length is a measure of distance. In the International System of Quantities, length is a quantity with dimension distance. In most systems of measurement a base unit for length is chosen, from which all other units are derived. In the Interna ...
'' of a string ''s'' is the number of symbols in ''s'' (the length of the sequence) and can be any
non-negative integer
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal n ...
; it is often denoted as , ''s'', . The ''
empty string
In formal language theory, the empty string, or empty word, is the unique string of length zero.
Formal theory
Formally, a string is a finite, ordered sequence of characters such as letters, digits or spaces. The empty string is the special cas ...
'' is the unique string over Σ of length 0, and is denoted ''ε'' or ''λ''.
[ Here: sect.1.1, p.1]
The set of all strings over Σ of length ''n'' is denoted Σ
''n''. For example, if Σ = , then Σ
2 = . Note that Σ
0 = for any alphabet Σ.
The set of all strings over Σ of any length is the
Kleene closure
In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics,
it is more commonly known as the free monoid ...
of Σ and is denoted Σ
*. In terms of Σ
''n'',
:
For example, if Σ = , then Σ
* = . Although the set Σ
* itself is
countably infinite
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
, each element of Σ
* is a string of finite length.
A set of strings over Σ (i.e. any
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
of Σ
*) is called a ''
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
'' over Σ. For example, if Σ = , the set of strings with an even number of zeros, , is a formal language over Σ.
Concatenation and substrings
''
Concatenation
In formal language, formal language theory and computer programming, string concatenation is the operation of joining character string (computer science), character strings wikt:end-to-end, end-to-end. For example, the concatenation of "sno ...
'' is an important
binary operation
In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two.
More specifically, an internal binary op ...
on Σ
*. For any two strings ''s'' and ''t'' in Σ
*, their concatenation is defined as the sequence of symbols in ''s'' followed by the sequence of characters in ''t'', and is denoted ''st''. For example, if Σ = , ''s'' = , and ''t'' = , then ''st'' = and ''ts'' = .
String concatenation is an
associative
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...
, but non-
commutative
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name o ...
operation. The empty string ε serves as the
identity element
In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
; for any string ''s'', ε''s'' = ''s''ε = ''s''. Therefore, the set Σ
* and the concatenation operation form a
monoid
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
Monoids ...
, the
free monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero eleme ...
generated by Σ. In addition, the length function defines a
monoid homomorphism
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
Monoids a ...
from Σ
* to the non-negative integers (that is, a function
, such that
).
A string ''s'' is said to be a ''
substring
In formal language theory and computer science, a substring is a contiguous sequence of characters within a string. For instance, "''the best of''" is a substring of "''It was the best of times''". In contrast, "''Itwastimes''" is a subsequence ...
'' or ''factor'' of ''t'' if there exist (possibly empty) strings ''u'' and ''v'' such that ''t'' = ''usv''. The
relation
Relation or relations may refer to:
General uses
*International relations, the study of interconnection of politics, economics, and law on a global level
*Interpersonal relationship, association or acquaintance between two or more people
*Public ...
"is a substring of" defines a
partial order
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
on Σ
*, the
least element
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined dually, that is, it is an eleme ...
of which is the empty string.
Prefixes and suffixes
A string ''s'' is said to be a
prefix
A prefix is an affix which is placed before the Word stem, stem of a word. Adding it to the beginning of one word changes it into another word. For example, when the prefix ''un-'' is added to the word ''happy'', it creates the word ''unhappy'' ...
of ''t'' if there exists a string ''u'' such that ''t'' = ''su''. If ''u'' is nonempty, ''s'' is said to be a ''proper'' prefix of ''t''. Symmetrically, a string ''s'' is said to be a
suffix
In linguistics, a suffix is an affix which is placed after the stem of a word. Common examples are case endings, which indicate the grammatical case of nouns, adjectives, and verb endings, which form the conjugation of verbs. Suffixes can carry ...
of ''t'' if there exists a string ''u'' such that ''t'' = ''us''. If ''u'' is nonempty, ''s'' is said to be a ''proper'' suffix of ''t''. Suffixes and prefixes are substrings of ''t''. Both the relations "is a prefix of" and "is a suffix of" are
prefix order In mathematics, especially order theory, a prefix ordered set generalizes the intuitive concept of a tree by introducing the possibility of continuous progress and continuous branching. Natural prefix orders often occur when considering dynamical sy ...
s.
Reversal
The reverse of a string is a string with the same symbols but in reverse order. For example, if ''s'' = abc (where a, b, and c are symbols of the alphabet), then the reverse of ''s'' is cba. A string that is the reverse of itself (e.g., ''s'' = madam) is called a
palindrome
A palindrome is a word, number, phrase, or other sequence of symbols that reads the same backwards as forwards, such as the words ''madam'' or ''racecar'', the date and time ''11/11/11 11:11,'' and the sentence: "A man, a plan, a canal – Panam ...
, which also includes the empty string and all strings of length 1.
Rotations
A string ''s'' = ''uv'' is said to be a rotation of ''t'' if ''t'' = ''vu''. For example, if Σ = the string 0011001 is a rotation of 0100110, where ''u'' = 00110 and ''v'' = 01. As another example, the string abc has three different rotations, viz. abc itself (with ''u''=abc, ''v''=ε), bca (with ''u''=bc, ''v''=a), and cab (with ''u''=c, ''v''=ab).
Lexicographical ordering
It is often useful to define an
ordering
Order, ORDER or Orders may refer to:
* Categorization, the process in which ideas and objects are recognized, differentiated, and understood
* Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of d ...
on a set of strings. If the alphabet Σ has a
total order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...
(cf.
alphabetical order
Alphabetical order is a system whereby character strings are placed in order based on the position of the characters in the conventional ordering of an alphabet. It is one of the methods of collation. In mathematics, a lexicographical order is t ...
) one can define a total order on Σ
* called
lexicographical order
In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a ...
. For example, if Σ = and 0 < 1, then the lexicographical order on Σ
* includes the relationships ε < 0 < 00 < 000 < ... < 0001 < 001 < 01 < 010 < 011 < 0110 < 01111 < 1 < 10 < 100 < 101 < 111 < 1111 < 11111 ... The lexicographical order is
total
Total may refer to:
Mathematics
* Total, the summation of a set of numbers
* Total order, a partial order without incomparable pairs
* Total relation, which may also mean
** connected relation (a binary relation in which any two elements are comp ...
if the alphabetical order is, but isn't
well-founded
In mathematics, a binary relation ''R'' is called well-founded (or wellfounded) on a class ''X'' if every non-empty subset ''S'' ⊆ ''X'' has a minimal element with respect to ''R'', that is, an element ''m'' not related by ''s& ...
for any nontrivial alphabet, even if the alphabetical order is.
See
Shortlex In mathematics, and particularly in the theory of formal languages, shortlex is a total ordering for finite sequences of objects that can themselves be totally ordered. In the shortlex ordering, sequences are primarily sorted by cardinality (leng ...
for an alternative string ordering that preserves well-foundedness.
String operations
A number of additional operations on strings commonly occur in the formal theory. These are given in the article on
string operations In computer science, in the area of formal language theory, frequent use is made of a variety of string functions; however, the notation used is different from that used for computer programming, and some commonly used functions in the theoretical ...
.
Topology
![Hamming distance 3 bit binary](https://upload.wikimedia.org/wikipedia/commons/b/b4/Hamming_distance_3_bit_binary.svg)
Strings admit the following interpretation as nodes on a graph, where ''k'' is the number of symbols in Σ:
* Fixed-length strings of length ''n'' can be viewed as the integer locations in an ''n''-dimensional
hypercube
In geometry, a hypercube is an ''n''-dimensional analogue of a square () and a cube (). It is a closed, compact, convex figure whose 1- skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, ...
with sides of length ''k''-1.
* Variable-length strings (of finite length) can be viewed as nodes on a
perfect ''k''-ary tree.
*
Infinite string
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called t ...
s (otherwise not considered here) can be viewed as infinite paths on a ''k''-node
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...
.
The natural topology on the set of fixed-length strings or variable-length strings is the discrete topology, but the natural topology on the set of infinite strings is the
limit topology
In mathematics, the inverse limit (also called the projective limit) is a construction that allows one to "glue together" several related objects, the precise gluing process being specified by morphisms between the objects. Thus, inverse limits can ...
, viewing the set of infinite strings as the
inverse limit
In mathematics, the inverse limit (also called the projective limit) is a construction that allows one to "glue together" several related objects, the precise gluing process being specified by morphisms between the objects. Thus, inverse limits can ...
of the sets of finite strings. This is the construction used for the
''p''-adic numbers and some constructions of the
Cantor set
In mathematics, the Cantor set is a set of points lying on a single line segment that has a number of unintuitive properties. It was discovered in 1874 by Henry John Stephen Smith and introduced by German mathematician Georg Cantor in 1883.
Thr ...
, and yields the same topology.
Isomorphism
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
s between string representations of topologies can be found by normalizing according to the
lexicographically minimal string rotation In computer science, the lexicographically minimal string rotation or lexicographically least circular substring is the problem of finding the rotation of a string possessing the lowest lexicographical order of all such rotations. For example, the ...
.
See also
*
Binary-safe
A binary-safe function is one that treats its input as a raw stream of bytes and ignores every textual aspect it may have. The term is mainly used in the PHP programming language to describe expected behaviour when passing binary data into fun ...
— a property of string manipulating functions treating their input as raw data stream
*
Bit array
A bit array (also known as bitmask, bit map, bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level p ...
— a string of binary digits
*
C string handling
The C programming language has a set of functions implementing operations on strings (character strings and byte strings) in its standard library. Various operations, such as copying, concatenation, tokenization and searching are supported. ...
— overview of C string handling
*
C++ string handling
The C programming language has a set of functions implementing operations on strings (character strings and byte strings) in its standard library. Various operations, such as copying, concatenation, tokenization and searching are supported. F ...
— overview of C++ string handling
*
Comparison of programming languages (string functions)
*
Connection string In computing, a connection string is a string that specifies information about a data source and the means of connecting to it. It is passed in code to an underlying driver or provider in order to initiate the connection. Whilst commonly used for ...
— passed to a driver to initiate a connection (e.g., to a database)
*
Empty string
In formal language theory, the empty string, or empty word, is the unique string of length zero.
Formal theory
Formally, a string is a finite, ordered sequence of characters such as letters, digits or spaces. The empty string is the special cas ...
— its properties and representation in programming languages
*
Incompressible string
An incompressible string is a string with Kolmogorov complexity equal to its length, so that it has no shorter encodings.V. Chandru and M.R.Rao, '' Algorithms and Theory of Computation Handbook'', CRC Press 1999, p29-30.
Example
Suppose we hav ...
— a string that cannot be compressed by any algorithm
*
Rope (data structure)
In computer programming, a rope, or cord, is a data structure composed of smaller strings that is used to efficiently store and manipulate a very long string. For example, a text editing program may use a rope to represent the text being edited, ...
— a data structure for efficiently manipulating long strings
*
String metric
In mathematics and computer science, a string metric (also known as a string similarity metric or string distance function) is a metric that measures distance ("inverse similarity") between two text strings for approximate string matching or com ...
— notions of similarity between strings
References
{{Formal languages and grammars , state=collapsed
Character encoding
Data types
Formal languages
Combinatorics on words
Primitive types
Syntactic entities
Algorithms on strings