String (computer science)
In
Depending on the programming language and precise data type used, a
When a string appears literally in source code, it is known as a string literal or an anonymous string.[1]
In
Purpose
A primary purpose of strings is to store human-readable text, like words and sentences. Strings are used to communicate information from a computer program to the user of the program.[2] A program may also accept string input from its user. Further, strings may store data expressed as characters yet not intended for human reading.
Example strings and their purposes:
- A message like "
file upload complete
" is a string that software shows to end users. In the program's source code, this message would likely appear as a string literal. - User-entered text, like "
I got a new job today
" as a status update on a social media service. Instead of a string literal, the software would likely store this string in a database. - Alphabetical data, like "
AGATGCCGT
" representing nucleic acid sequences of DNA.[3] - Computer settings or parameters, like "
?action=edit
" as a URL query string. Often these are intended to be somewhat human-readable, though their primary purpose is to communicate to computers.
The term string may also designate a sequence of data or computer records other than characters — like a "string of bits" — but when used without qualification it refers to strings of characters.[4]
History
Use of the word "string" to mean any items arranged in a line, series or succession dates back centuries.
Use of the word "string" to mean "a sequence of symbols or linguistic elements in a definite order" emerged from mathematics,
For example, logician C. I. Lewis wrote in 1918:[9]
A mathematical system is any set of strings of recognisable marks in which some of the strings are taken initially and the remainder derived from these by operations performed according to rules which are independent of any meaning assigned to the marks. That a system should consist of 'marks' instead of sounds or odours is immaterial.
According to Jean E. Sammet, "the first realistic string handling and pattern matching language" for computers was COMIT in the 1950s, followed by the SNOBOL language of the early 1960s.[10]
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
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
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 or EBCDIC. 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.
Unicode has simplified the picture somewhat. Most programming languages now have a datatype for Unicode strings. Unicode's preferred byte stream format UTF-8 is designed not to have the problems described above for older multibyte encodings. UTF-8, UTF-16 and UTF-32 require the programmer to know that the fixed-size code units are different from 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++, Perl and Ruby, 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, JavaScript, Lua, Python, 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 StringBuilder
, the thread-safe Java StringBuffer
, and the Cocoa 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.
Strings are typically implemented as
A lot of high-level languages provide strings as a primitive data type, such as JavaScript and PHP, while most others provide them as a composite data type, some with special language support in writing literals, for example, Java and C#.
Some languages, such as C, Prolog and Erlang, avoid implementing a dedicated string datatype at all, instead adopting the convention of representing strings as lists of character codes. Even in programming languages having a dedicated string type, string can usually be iterated as a sequence character codes, like lists of integers or other values.
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
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
Null-terminated
The length of a string can be stored implicitly by using a special terminating character; often this is the null character (NUL), which has all bits zero, a convention used and perpetuated by the popular C programming language.[11] 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 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.
An example of a null-terminated string stored in a 10-byte
F |
R |
A |
N |
K
|
NUL | k
|
e
|
f
|
w
|
4616 | 5216 | 4116 | 4E16 | 4B16 | 0016 | 6B16 | 6516 | 6616 | 7716 |
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 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 systems (this character had a value of zero), and the ZX80 used "
[12] since this was the string delimiter in its BASIC language.
Somewhat similar, "data processing" machines like the IBM 1401 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.[13]
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
If the length is bounded, then it can be encoded in constant space, typically a machine word, thus leading to an implicit data structure, 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
In the latter case, the length-prefix field itself does not 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:
length | F |
R |
A |
N |
K
|
k
|
e
|
f
|
w
|
0516 | 4616 | 5216 | 4116 | 4E16 | 4B16 | 6B16 | 6516 | 6616 | 7716 |
Strings as records
Many languages, including object-oriented ones, implement strings as records with an internal structure like:
class string {
size_t length;
char *text;
};
However, since the implementation is usually
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 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
While these representations are common, others are possible. Using ropes makes certain string operations, such as insertions, deletions, and concatenations more efficient.
The core data structure in a text editor 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 linked list of lines, a piece table, or a rope—which makes certain string operations, such as insertions, deletions, and undoing previous edits, more efficient.[14]
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
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 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 does not 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 marks (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 sequences are often available, usually prefixed with the backslash character (ASCII 0x5C). - Terminated by a newline 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
C programmers draw a sharp distinction between a "string", aka a "string of characters", which by definition is always null terminated, vs. a "array of characters" which may be stored in the same array but is often not null terminated. Using C string handling functions on such an array of characters often seems to work, but later leads to security problems.[15][16][17]
String processing algorithms
There are many algorithms 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 for the theory of algorithms and data structures used for string processing.[18][19][20]
Some categories of algorithms include:
- String searching algorithmsfor finding a given substring or pattern
- String manipulation algorithms
- Sorting algorithms
- Regular expression algorithms
- Parsinga string
- Sequence mining
Advanced string algorithms often employ complex mechanisms and data structures, among them suffix trees and finite-state machines.
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:
Many Unix 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
Many
Some languages such as Perl and Ruby support string interpolation, which permits arbitrary expressions to be evaluated and included in string literals.
Character string functions
The most basic example of a string function is the
length
or len
. For example, length("hello world")
would return 11. Another common function is concatenationSome
REPNZ MOVSB
).[22]Formal theory
Let Σ be a finite set of distinct, unambiguous symbols (alternatively called characters), called the alphabet. A string (or word[23] or expression[24]) over Σ is any finite sequence of symbols from Σ.[25] For example, if Σ = {0, 1}, then 01011 is a string over Σ.
The
The set of all strings over Σ of length n is denoted Σn. For example, if Σ = {0, 1}, then Σ2 = {00, 01, 10, 11}. We have Σ0 = {ε} for every alphabet Σ.
The set of all strings over Σ of any length is the Kleene closure of Σ and is denoted Σ*. In terms of Σn,
For example, if Σ = {0, 1}, then Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}. Although the set Σ* itself is
A set of strings over Σ (i.e. any subset of Σ*) is called a formal language over Σ. For example, if Σ = {0, 1}, the set of strings with an even number of zeros, {ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, ...}, is a formal language over Σ.
Concatenation and substrings
Concatenation is an important binary operation 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 Σ = {a, b, ..., z}, s = bear
, and t = hug
, then st = bearhug
and ts = hugbear
.
String concatenation is an
A string s is said to be a
Prefixes and suffixes
A string s is said to be a prefix 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 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 orders.
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, 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 Σ = {0, 1} 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
See
String operations
A number of additional operations on strings commonly occur in the formal theory. These are given in the article on string operations.
Topology
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 with sides of length k-1.
- Variable-length strings (of finite length) can be viewed as nodes on a perfect k-ary tree.
- Infinite strings (otherwise not considered here) can be viewed as infinite paths on a k-node complete graph.
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
Isomorphisms between string representations of topologies can be found by normalizing according to the lexicographically minimal string rotation.
See also
- Binary-safe — a property of string manipulating functions treating their input as raw data stream
- Bit array — a string of binary digits
- C string handling — overview of C string handling
- C++ string handling — overview of C++ string handling
- Comparison of programming languages (string functions)
- Connection string — passed to a driver to initiate a connection (e.g., to a database)
- Empty string — its properties and representation in programming languages
- Incompressible string — a string that cannot be compressed by any algorithm
- Rope (data structure) — a data structure for efficiently manipulating long strings
- String metric — notions of similarity between strings
References
- ^ "Introduction To Java – MFC 158 G". Archived from the original on 2016-03-03.
String literals (or constants) are called 'anonymous strings'
- ^ de St. Germain, H. James. "Strings". University of Utah, Kahlert School of Computing.
- ^ Francis, David M.; Merk, Heather L. (November 14, 2019). "DNA as a Biochemical Entity and Data String".
- ^ a b c Burchfield, R.W. (1986). "string". A Supplement to the Oxford English Dictionary. Oxford at the Clarendon Press.
- ^ "string". The Oxford English Dictionary. Vol. X. Oxford at the Clarendon Press. 1933.
- ^ "string (n.)". Online Etymology Dictionary.
- ^ Whitney, William Dwight; Smith, Benjamin E. "string". The Century Dictionary. New York: The Century Company. p. 5994.
- ^ "Old Union's Demise". Milwaukee Sentinel. January 11, 1898. p. 3.
- Lewis, C.I. (1918). A survey of symbolic logic. Berkeley: University of California Press. p. 355.
- S2CID 2003242.
- ^
ISBN 0-13-034074-X, archivedfrom the original on 2007-08-06
- ^ Wearmouth, Geoff. "An Assembly Listing of the ROM of the Sinclair ZX80". Archived from the original on August 15, 2015.
{{cite web}}
: CS1 maint: unfit URL (link) - ^ Allison, Dennis. "Design Notes for Tiny BASIC". Archived from the original on 2017-04-10.
- ^ Charles Crowley. "Data Structures for Text Sequences" Archived 2016-03-04 at the Wayback Machine. Section "Introduction" Archived 2016-04-04 at the Wayback Machine.
- ^ "strlcpy and strlcat - consistent, safe, string copy and concatenation." Archived 2016-03-13 at the Wayback Machine
- ^ "A rant about strcpy, strncpy and strlcpy." Archived 2016-02-29 at the Wayback Machine
- ^ Keith Thompson. "No, strncpy() is not a "safer" strcpy()". 2012.
- ^ "The Prague Stringology Club". stringology.org. Archived from the original on 1 June 2015. Retrieved 23 May 2015.
- ^ Evarts, Holly (18 March 2021). "Former Dean Zvi Galil Named a Top 10 Most Influential Computer Scientist in the Past Decade". Columbia Engineering.
He invented the terms 'stringology,' which is a subfield of string algorithms,
- ISBN 981-02-4782-6.)
The term stringology is a popular nickname for string algorithms as well as for text algorithms.
{{cite book}}
: CS1 maint: location missing publisher (link - ^ "Essential Perl". Archived from the original on 2012-04-21.
Perl's most famous strength is in string manipulation with regular expressions.
- ^ "x86 string instructions". Archived from the original on 2015-03-27.
- ISBN 0-53492-373-9.
Let Σ be an alphabet. A nonempty word over Σ is a finite sequence with domain In (for some n ∈ ℕ) and codomain Σ.
- ISBN 978-156881135-2.
Any finite sequence of symbols of a language is called an expression of that language.
- ^ a b Barbara H. Partee; Alice ter Meulen; Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer.
- ISBN 0-201-02988-X. Here: sect.1.1, p.1