Encyclopedia  |   World Factbook  |   World Flags  |   Reference Tables  |   List of Lists     
   Academic Disciplines  |   Historical Timeline  |   Themed Timelines  |   Biographies  |   How-Tos     
Sponsor by The Tattoo Collection
Character string (computer science)
Main Page | See live article | Alphabetical index

Character string (computer science)

In various branches of mathematics and computer science, strings are sequences of various simple objects (symbols, tokens, characters, etc.). One may consider sequences of characterss (a character string), tokenss in a formal grammar, states in automata, representations of DNA, or bits (a binary string).

In computer science, the term string may refer to the data type used to represent strings, the data structures used to store them, or the actual data itself (e.g. a string literal).

Table of contents
1 Formal theory
2 String datatypes
3 Representations
4 String algorithms
5 String oriented languages and utilities
6 See also

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 (the natural numbers 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" defnies 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.

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.

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 arbitrarly 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.

String datatypes also differ by the alphabet over which they are defined. Some strings are designed to work over a single fixed alphabet (such as the Latin alphabet or the characters representable by ASCII) and others over an arbitrary alphabet. For example, in the C++ standard library strings are designed as templates definable over any alphabet of characters.

Representations

Representations of strings depend heavily on the choice of alphabet (also called an abstract character repertoire) and the method of character encoding. Older string implementations were designed to work with the character 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 enodings such as UTF-8 and UTF-16.

Most string implementations are very similiar to variable-length arrays with the entries storing the character codes of corresponding characters. The principal diffence being 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 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 NUL, ASCII code 0)—the C programming language uses this convention (see C string)—or explicitly, for example by prefixing the string with integer value (convention used in Pascal). 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 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 Pascal string:

lengthF R A N K k f f w
0546 52 41 4E 4B 6B 66 66 77

Of course, other representations are possible. Using trees and lists makes certain string operations, such as character insertions or deletions, more efficient.

String algorithms

There are many algorithms for processing strings, each with various tradeoffs. Some categories of algorithms include: 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.

Recent scripting languages, including Perl, Python and Ruby, employ regular expressions to facilitate text operations.

See also

See string for alternate meanings of the word.