String (computer science)
|
|
In computer programming and some branches of mathematics , strings are sequences of various simple objects. These are selected from a predetermined set each entry of which is usually allocated a code. Most commonly these simple objects will be printable characters and the control codes that are used with them. The data types in which these are stored are also called strings and it is fairly common to use these types to store arbitrary variable length lumps of binary data. Generally a string can be placed directly in the code usually by surrounding it with some form of quote marks (usually ' or " as these are typeable on a standard US keyboard and most others). Sometimes the term binary string is used to refer to an arbitrary sequence of bits.
| Contents |
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.
Although formal strings can have an arbitrary (but finite) length, strings in real languages have limited length. In general, there are two types of string datatypes: fixed length strings which have a fixed maximum length, and variable length strings whose length is not arbitrarily fixed. 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.
Historically string datatypes had one byte for each character and although the exact character set varied by region the character sets were close enough that programmers could generally get away with ignoring this (mostly groups of character sets used by the same system in different regions either had a character in the same place or did not have it at all). Mostly these character sets were based on ASCII though IBMs mainframe systems went their own way and used EBCDIC.
Ideographic languages such as Chinese, Japanese and Korean (known collectively as CJK) need far more than 256 characters 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 charactor encoding was designed. Some encodings such as the EUC family gaurantee that a byte value in the ASCII range will only represent that ASCII charactor making the encoding safe for systems that use those charactors as field separators of similar. Others such as ISO-2022 and shift-jis do not make such gaurantees making matching on ascii codes unsafe. Another issue is that if the beginning of a string is cut off important instructions fo the decoder or imformation on position in a multibyte sequence may be lost. The final issue is that if strings are joined together (especially after having their ends truncated by code not aware of the encoding) the first string may not leave the encoder in a state suitable for dealing with the second string.
Unicode has complicated the picture somewhat. Most languages have a datatype for Unicode strings (usually UTF-16 as it was usually added before Unicode supplemental planes were introduced). Converting between Unicode and local encodings requires an understanding of the local encoding which may be problematic for existing systems where strings of various encodings are being transmitted together with no real marking as to what encoding they are in.
Some languages like C++ implement strings as templates that can be used with any primitive type but this is the exception not the rule.
Representations
Representations of strings depend heavily on the choice of character set (such as an alphabet) and the method of character encoding. Older string implementations were designed to work with the character set and encoding defined by ASCII, or more recent extensions like the ISO 8859 series. Modern implementations often use the extensive character set 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 differs from the logical length of the array.
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. 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 integer value (convention used in Pascal, consequently some people call it a P-string). Note that with terminated strings the terminating character is not an allowable character in any string.
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 | 65 | 66 | 77 |
The length of a string in the above example is 5 characters, but note that 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.
Here is the equivalent (old style) Pascal string:
| length | F | R | A | N | K | k | f | f | w |
| 05 | 46 | 52 | 41 | 4E | 4B | 6B | 66 | 66 | 77 |
While these representations are common, others are possible. Using ropes makes certain string operations, such as insertions, deletions, and concatenations more efficient.
Memory management
There are several serious memory management issues with strings.
- Making sure memory for strings that are no longer in use gets freed
- Making sure strings that are still in use do not get freed.
- Making sure that a write to a memory block allocated to a string does not go past the end of the string. (Buffer overflow)
- Making sure when a string is altered it does not have an unwanted/unexpected effect on other code.
Different languages deal with the issue of strings and their memory management in different ways:
- C simply offers pointers to characters and forces the programmer to deal with these things themselves. This often leads to bugs when they get it wrong. In many cases these bugs have led to security holes (usually the famous buffer overflow attack). However, manual coding can often lead to better performance than code generated by compilers for higher-level languages.
- Old style Borland Pascal uses fixed-size arrays with a length byte at the beginning. This makes string assignment and passing strings by-value expensive as the entire string has to be copied. On the other hand it does not involve the heap manager and therefore cannot cause a memory leak problem and since string lengths are fixed at compile time it is easy for the compiler to generate code that enforces them. Also due to the fact it only uses a single byte for length, the maximum string size that can be declared is 255 characters. This often forces coders to use character pointers to do things by hand like in C.
- Delphi 2 upwards (and freepascal in Delphi mode) uses reference counts maintained by the compiler. If an attempt is made to modify a string that has a reference count other than one, the string is copied first. Therefore, to the programmer, it looks like the string is being passed by-value but the huge overhead of copying the string on every assignment is removed. Unfortunately it also requires generation of what is effectively a try-finally block to ensure that the reference count is decreased when a procedure is exited by an exception.
- Garbage-collected languages like Microsoft .NET and Java usually make strings an immutable class and let the garbage collector deal with strings that are no longer needed. This works well enough but can make string manipulation difficult and expensive so these languages usually have a second mutable class for doing string manipulation. (StringBuffer in Java, StringBuilder in .NET, etc.)
- The C++ STL makes use of advanced language features such as copy constructors and destructors for non reference objects to allow a string template and class to be implemented that has the feel of a primitive type.
String algorithms
There are many algorithms for processing strings, each with various tradeoffs. Some categories of algorithms include:
- string searching algorithms for finding a given substring or pattern
- 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.
String oriented languages and utilities
Strings are such a useful datatype that several languages have been designed in order to make string processing applications easy to write. Examples include:
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.
Formal theory
One starts with a non-empty finite set Σ called an alphabet. Elements of this alphabet are called characters. A string (or word) over Σ is any finite sequence of characters from Σ.
A particularly important string is the sequence of no characters, called the empty string. The empty string is often denoted ε or λ. Note that one does not allow infinite sequences of characters.
For example, if Σ = {0, 1}, strings over Σ are of the form
- ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, …
The set of all strings over Σ is denoted Σ*. One can define a binary operation on Σ* called string concatenation. If s and t are two strings, their concatenation, denoted st, is defined as the sequence of characters in s followed by the sequence of characters in t.
For example, if 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. In algebraic terms, the set Σ* forms a monoid under string concatenation. In fact, Σ* is the free monoid generated by Σ.
The length of a string is the number of characters in the string. The length can be any natural number. The length of the empty string is 0. Algebraically speaking, the length function defines a monoid homomorphism from Σ* to N (Non-negative integers with addition).
A string s is said to be a substring of t if there exist two strings u and v such that t = usv. One, or both, of u and v can be empty. The relation "is a substring of" defines a partial order on Σ*, the least element of which is the empty string.
More often, especially in computing applications, one is interested in a different kind of ordering on the set of strings. If the alphabet Σ is well-ordered (cf. alphabetical order) one can define a well-ordering on Σ* called lexicographical order. The empty string is also the least element with respect to this ordering.
A set of strings over Σ (i.e. a subset of Σ*) is called a formal language over Σ. Note that while the alphabet is a finite set and every string has finite length, a language may very well have infinitely many member strings. In fact, Σ* itself is always an infinite language. Important examples of formal languages include regular expressions and formal grammars.
See also
de:Zeichenkette fr:Chane de caractres it:Stringa (informatica) pl:String ru:Строка (тип данных) zh:字符串