String (computer science)
 |
This article needs additional citations for verification. Please help improve this article by adding reliable references. Unsourced material may be challenged and removed. (January 2010) |
In mathematical logic, more precisely in the theory of formal languages, and in computer science, a string is a sequence of symbols that are chosen from a set or alphabet.
In computer programming, a string is, essentially, a sequence of characters. A string is generally understood as a data type storing a sequence of data values, usually bytes, in which elements usually stand for characters according to a character encoding, which differentiates it from the more general array data type. In this context, the terms binary string and byte string are used to suggest strings in which the stored data does not (necessarily) represent text.
A variable declared to have a string data type usually causes storage to be allocated in memory that is capable of holding some predetermined number of symbols. When a string appears literally in source code, it is known as a string literal and has a representation that denotes it as such.
Contents |
[edit] Formal theory
- See also: Tuple
Let Σ be an alphabet, a non-empty finite set. Elements of Σ are called symbols or characters. A string (or word) over Σ is any finite sequence of characters from Σ. For example, if Σ = {0, 1}, then 0101 is a string over Σ.
The length of a string is the number of characters in the string (the length of the sequence) and can be any non-negative integer. The empty string is the unique string over Σ of length 0, and is denoted ε or λ.
The set of all strings over Σ of length n is denoted Σn. For example, if Σ = {0, 1}, then Σ2 = {00, 01, 10, 11}. Note that Σ0 = {ε} for any 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}, Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, …}. Although Σ* itself is countably infinite, all elements of Σ* have finite length.
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 Σ.
[edit] 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 characters 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 associative, but non-commutative operation. The empty string serves as the identity element; for any string s, εs = sε = s. Therefore, the set Σ* and the concatenation operation form a monoid, the free monoid generated by Σ. In addition, the length function defines a monoid homomorphism from Σ* to the non-negative integers.
A string s is said to be a substring or factor of t if there exist (possibly empty) strings u and v such that t = usv. The relation "is a substring of" defines a partial order on Σ*, the least element of which is the empty string.
[edit] Lexicographical ordering
It is often necessary to define an ordering on the set of strings. If the alphabet Σ has a total order (cf. alphabetical order) one can define a total order on Σ* called lexicographical order. Note that since Σ is finite, it is always possible to define a well ordering on Σ and thus on Σ*. For example, if Σ = {0, 1} and 0 < 1, then the lexicographical ordering of Σ* is ε < 0 < 00 < 000 < … < 011 < 0110 < … < 01111 < … < 1 < 10 < 100 < … < 101 < … < 111 …
[edit] String operations
A number of additional operations on strings commonly occur in the formal theory. These are given in the article on string operations.
[edit] Topology
Strings admit the following interpretation as nodes on a graph:
- Fixed length strings can be viewed as nodes on a hypercube;
- Variable length strings (of finite length) can be viewed as nodes on the k-ary tree, where k is the number of symbols in Σ;
- Infinite strings can be viewed as infinite paths on the k-ary tree.
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, viewing the set of infinite strings as the inverse limit of the sets of finite strings. This is the construction used for the p-adic numbers and some constructions of the Cantor set, and yields the same topology.
[edit] 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. In some languages they are available as primitive types and in others as composite types. The syntax 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.
[edit] String length
Although formal strings can have an arbitrary (but 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 and which use the same amount of memory whether this maximum is reached or not, and variable length strings whose length is not arbitrarily fixed and which use varying amounts of memory depending on their actual size. Most strings in modern programming languages are variable length strings. Despite the name, even variable length strings are limited in length; although, generally, the limit depends only on the amount of memory available.
[edit] Character encoding
Historically, string datatypes allocated one byte per character, and although the exact character set varied by region, character encodings were similar enough that programmers could generally get away with ignoring this — groups of character sets used by the same system in different regions usually either had a character in the same place, or did not have it at all. These character sets were typically based on ASCII or EBCDIC.
Logographic languages such as Chinese, Japanese, and Korean (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. 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 only represent that ASCII character, making the encoding safe for systems that use those characters as field separators. Other encodings such as ISO-2022 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 (these problems were much less with EUC as any ASCII character did synchronize the encoding).
Unicode has simplified the picture somewhat. Most programming languages have a datatype for Unicode strings (usually UTF-16 as it was usually added before Unicode supplemental planes were introduced). Unicode's preferred byte stream format UTF-8 is designed not to have the problems described above for older multibyte encodings. Both UTF-8 and UTF-16 require the programmer to know that the fixed-size code units are different than the "characters", the main difficulty currently is incorrectly designed API's that attempt to hide this difference. Strings which use UTF-32 encoded characters do not have this problem since the fixed-size code units are "characters".
[edit] Implementations
Some languages like C++ implement strings as templates that can be used with any datatype, but this is the exception, not the rule.
Some languages, such as C++ 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 and Python, the value is fixed and a new string must be created if any alteration is to be made; these are termed immutable strings.
Strings are typically implemented as arrays of characters, in order to allow fast access to individual characters. A few languages such as Haskell implement them as linked lists instead.
Some languages, such as Prolog and Erlang, avoid implementing a dedicated string datatype at all, instead adopting the convention of representing strings as lists of character codes.
[edit] 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 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.
Most string implementations are very similar to variable-length arrays with the entries storing the character codes 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 characters can take anywhere from one to four bytes. In these cases, the logical length of the string (number of characters) differs from the logical length of the array (number of bytes in use).
The length of a string can be stored implicitly by using a special terminating character; often this is the null character having value zero, a convention used and perpetuated by the popular C programming language[1]. Hence, this representation is commonly referred to as C string. The length of a string can also be stored explicitly, for example by prefixing the string with the length as a byte value — a convention used in many Pascal dialects; consequently some people call it a 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 to store the string length. When the length field covers the address space strings are only limited by the available memory.
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.
The term bytestring 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.
Here is an example of a null-terminated string stored in a 10-byte buffer, along with its ASCII representation:
| F | R | A | N | K | NUL | k | e | f | w |
| 46 | 52 | 41 | 4E | 4B | 00 | 6B | 66 | 66 | 77 |
The length of a string in the above example 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 another string or just garbage. (Strings of this form are sometimes called ASCIZ strings, after the original assembly language directive used to declare them.)
Here is the equivalent (old style) Pascal string stored in a 10-byte buffer, along with its ASCII representation:
| length | F | R | A | N | K | k | e | f | w |
| 05 | 46 | 52 | 41 | 4E | 4B | 6B | 66 | 66 | 77 |
Both character termination and length codes limit strings: for example, C character arrays that contain 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, of course, but such workarounds are by definition not standard.
Historically, rough equivalents of the C termination method appear in both hardware and software. For example "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 meant that while the IBM 1401 had a seven-bit word in "reality", 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.
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 (replacing repeated characters by the character value and a length) and Hamming encoding.
While these representations are common, others are possible. Using ropes makes certain string operations, such as insertions, deletions, and concatenations more efficient.
[edit] Vectors
While character strings are very common uses of strings, a string in computer science may refer generically to any vector of homogenously typed data. A string of bits or bytes, for example, may be used to represent data 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.
[edit] String processing algorithms
There are many algorithms for processing strings, each with various trade-offs. Some categories of algorithms include:
- String searching algorithms for finding a given substring or pattern
- String manipulation algorithms
- Sorting algorithms
- Regular expression algorithms
- Parsing a string
Advanced string algorithms often employ complex mechanisms and data structures, among them suffix trees and finite state machines.
[edit] 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 APIs like Multimedia Control Interface, embedded SQL or printf use strings to hold commands that will be interpreted.
Recent scripting programming languages, including Perl, Python, Ruby, and Tcl employ regular expressions to facilitate text operations.
Some languages such as Perl and Ruby support string interpolation, which permits arbitrary expressions to be evaluated and included in string literals.
[edit] Character string functions
String functions are used to manipulate a string or change or edit the contents of a string. They also are used to query information about a string. They are usually used within the context of a computer programming language.
The most basic example of a string function is the length(string) function, which 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. For example, length("hello world") returns 11.
There are many string functions which exist in other languages with similar or exactly the same syntax or parameters. For example in many languages the length function is usually represented as len(string). Even though string functions are very useful to a computer programmer, a computer programmer using these functions should be mindful that a string function in one language could in another language behave differently or have a similar or completely different function name, parameters, syntax, and results.
[edit] See also
[edit] References
- ^ Bryant, Randal E.; David, O'Hallaron (2003), Computer Systems: A Programmer's Perspective (2003 ed.), Upper Saddle River, NJ: Pearson Education, p. 40, ISBN 0-13-034074-X, http://csapp.cs.cmu.edu/
|
|||||||||||||||||||||||
