String - Revision history

Brian: alphabet size and complexity

2011-11-23T23:56:18Z

alphabet size and complexity

Brian at 04:29, 29 May 2011

2011-05-29T04:29:57Z

Brian at 19:21, 5 March 2011

2011-03-05T19:21:23Z

Brian: strings are a subset of sequences

2011-03-05T06:03:52Z

strings are a subset of sequences

Brian: note on total ordering

2011-03-05T06:03:08Z

note on total ordering

Brian: sp.

2011-03-02T06:48:50Z

sp.

Brian at 20:23, 17 November 2010

2010-11-17T20:23:30Z

Brian at 22:15, 16 November 2010

2010-11-16T22:15:52Z

Brian at 16:27, 16 November 2010

2010-11-16T16:27:21Z

Brian: Created page with "The '''string''' is one of the most fundamental objects in computer science. Strings are intimately familiar to us in the form of text and therefore it is no wonder that the theo..."

2010-11-16T07:05:48Z

Created page with "The '''string''' is one of the most fundamental objects in computer science. Strings are intimately familiar to us in the form of text and therefore it is no wonder that the theo..."

New page

The '''string''' is one of the most fundamental objects in computer science. Strings are intimately familiar to us in the form of text and therefore it is no wonder that the theory of strings (which is to be distinguished from the field of theoretical physics known as "string theory") is one of the most extensively studied subdisciplines of computer science.

==Definitions==
An ''alphabet'', usually denoted <math>\Sigma</math> is a finite nonempty set (whose size is denoted <math>|\Sigma|</math>). It is often assumed that the alphabet is totally ordered, but this is not always necesary. An element of this the alphabet is known as a ''character''.

The set of <math>n</math>-tuples of <math>\Sigma</math> is denoted <math>\Sigma^n</math>. A ''string of length <math>n</math>'' is an element of <math>\Sigma^n</math>. The set <math>\Sigma^*</math> is defined <math>\Sigma^0 \cup \Sigma^1 \cup ...</math>; an element of <math>\Sigma^*</math> is known simply as a ''string'' over <math>\Sigma</math>. The ''empty string'', denoted <math>\lambda</math>, is the unique element of <math>\Sigma^0</math>. Strings must have finite length, but there is no limit on the length of a string.

Examples of alphabets include:
* The binary alphabet, <math>\{0, 1\}</math>. There are two characters, usually denoted '''0''' and '''1'''. In virtually all computers ever built, data are strings over the binary alphabet, and are known as bit strings.
* The Latin alphabet, consisting of the characters '''a''', '''A''', '''b''', '''B''', ..., '''z''', '''Z'''. English words may be considered strings over the Latin alphabet.
* The Unicode character set. Text files may be considered strings over this alphabet.
* The set of integers <math>0, 1, ..., N-1</math> for some <math>N \in \mathbb{N}</math>. Here the characters are actually integers. (Recall that the definition of ''character'' is broader than the common concept of the character as the smallest, indivisible element of writing.)

@@ Line 2: / Line 2: @@
 ==Definitions==
-An '''alphabet''', usually denoted <math>\Sigma</math> is a finite nonempty set (whose size is denoted <math>|\Sigma|</math>). It is often assumed that the alphabet is totally ordered, but this is not always necessary. (Since the alphabet is finite, we can always impose a total order when it would be useful to do so, such as when constructing a [[dictionary]].) An element of this the alphabet is known as a '''character'''. The size of the alphabet can affect the asymptotic complexity of string algorithms. In particular, if <math>N</math> is the size of the input, and the alphabet size is bounded by a constant independent of <math>N</math>, then it is called a '''constant''' alphabet; if its size is <math>O(N)</math>, it is called '''integer''' alphabet; and if it is larger than this then it is called a '''general''' alphabet.
+An '''alphabet''', usually denoted <math>\Sigma</math> is a finite nonempty set (whose size is denoted <math>|\Sigma|</math>). It is often assumed that the alphabet is totally ordered, but this is not always necessary. (Since the alphabet is finite, we can always impose a total order when it would be useful to do so, such as when constructing a [[dictionary]].) An element of this the alphabet is known as a '''character'''. Unless otherwise specified, we will always assume that two characters from the same alphabet can be compared for equality in constant time.
 The set of <math>n</math>-tuples of <math>\Sigma</math> is denoted <math>\Sigma^n</math>. A '''string of length <math>n</math>''' is an element of <math>\Sigma^n</math>. The set <math>\Sigma^*</math> is defined <math>\Sigma^0 \cup \Sigma^1 \cup ...</math>; an element of <math>\Sigma^*</math> is known simply as a '''string''' over <math>\Sigma</math>. The '''empty string''', denoted <math>\epsilon</math> or <math>\lambda</math>, is the unique element of <math>\Sigma^0</math>. The length of a string <math>S</math> is denoted <math>|S|</math>. (Note that the usual definition of "string" requires strings to have finite length, although arbitrarily long strings exist.)
@@ Line 29: / Line 29: @@
 * <math>|ST| = |S|+|T|</math>
 For example, concatenating ''there'' and ''in'' gives ''therein''. So do concatenating ''the'' and ''rein'', or <math>\epsilon</math> and ''therein'', or ''therein'' and <math>\epsilon</math>. Note that in general, concatenation is not commutative.
 ==Treatment in programming languages==
@@ Line 40: / Line 50: @@
 * ''Find'' the first occurrence of a given character in a given string, or find the first occurrence of a given string as a substring of another string.
 * ''Compare'' two strings [[Lexicographic order|lexicographically]].

@@ Line 2: / Line 2: @@
 ==Definitions==
-An '''alphabet''', usually denoted <math>\Sigma</math> is a finite nonempty set (whose size is denoted <math>|\Sigma|</math>). It is often assumed that the alphabet is totally ordered, but this is not always necessary. (Since the alphabet is finite, we can always impose a total order when it would be useful to do so, such as when constructing a [[dictionary]].) An element of this the alphabet is known as a '''character'''.
+An '''alphabet''', usually denoted <math>\Sigma</math> is a finite nonempty set (whose size is denoted <math>|\Sigma|</math>). It is often assumed that the alphabet is totally ordered, but this is not always necessary. (Since the alphabet is finite, we can always impose a total order when it would be useful to do so, such as when constructing a [[dictionary]].) An element of this the alphabet is known as a '''character'''. The size of the alphabet can affect the asymptotic complexity of string algorithms. In particular, if <math>N</math> is the size of the input, and the alphabet size is bounded by a constant independent of <math>N</math>, then it is called a '''constant''' alphabet; if its size is <math>O(N)</math>, it is called '''integer''' alphabet; and if it is larger than this then it is called a '''general''' alphabet.
 The set of <math>n</math>-tuples of <math>\Sigma</math> is denoted <math>\Sigma^n</math>. A '''string of length <math>n</math>''' is an element of <math>\Sigma^n</math>. The set <math>\Sigma^*</math> is defined <math>\Sigma^0 \cup \Sigma^1 \cup ...</math>; an element of <math>\Sigma^*</math> is known simply as a '''string''' over <math>\Sigma</math>. The '''empty string''', denoted <math>\epsilon</math> or <math>\lambda</math>, is the unique element of <math>\Sigma^0</math>. The length of a string <math>S</math> is denoted <math>|S|</math>. (Note that the usual definition of "string" requires strings to have finite length, although arbitrarily long strings exist.)

@@ Line 25: / Line 25: @@
 Two strings with the same alphabet can be '''concatenated'''. To concatenate two strings is to link them together to give a new string which begins with the first and ends with the second with no overlap. Formally, the concatenation of strings <math>S</math> and <math>T</math> is denoted <math>ST</math> and has the following three properties:
-# <math>S \sqsubset ST</math>
+* <math>S \sqsubset ST</math>
-# <math>T \sqsupset ST</math>
+* <math>T \sqsupset ST</math>
-# <math>|ST| = |S|+|T|</math>
+* <math>|ST| = |S|+|T|</math>
 For example, concatenating ''there'' and ''in'' gives ''therein''. So do concatenating ''the'' and ''rein'', or <math>\epsilon</math> and ''therein'', or ''therein'' and <math>\epsilon</math>. Note that in general, concatenation is not commutative.

← Older revision		Revision as of 06:03, 5 March 2011
Line 5:		Line 5:

	The set of <math>n</math>-tuples of <math>\Sigma</math> is denoted <math>\Sigma^n</math>. A '''string of length <math>n</math>''' is an element of <math>\Sigma^n</math>. The set <math>\Sigma^</math> is defined <math>\Sigma^0 \cup \Sigma^1 \cup ...</math>; an element of <math>\Sigma^</math> is known simply as a '''string''' over <math>\Sigma</math>. The '''empty string''', denoted <math>\epsilon</math> or <math>\lambda</math>, is the unique element of <math>\Sigma^0</math>. The length of a string <math>S</math> is denoted <math>\|S\|</math>. (Note that the usual definition of "string" requires strings to have finite length, although arbitrarily long strings exist.)		The set of <math>n</math>-tuples of <math>\Sigma</math> is denoted <math>\Sigma^n</math>. A '''string of length <math>n</math>''' is an element of <math>\Sigma^n</math>. The set <math>\Sigma^</math> is defined <math>\Sigma^0 \cup \Sigma^1 \cup ...</math>; an element of <math>\Sigma^</math> is known simply as a '''string''' over <math>\Sigma</math>. The '''empty string''', denoted <math>\epsilon</math> or <math>\lambda</math>, is the unique element of <math>\Sigma^0</math>. The length of a string <math>S</math> is denoted <math>\|S\|</math>. (Note that the usual definition of "string" requires strings to have finite length, although arbitrarily long strings exist.)
		+
		+	It follows from the definition that all strings are [[sequence]]s, but not all sequences are strings.

	For ease of conceptualization, we shall usually assign a ''symbol'', a graphical representation, to each character of the alphabet and, considering a string as a sequence of characters, render it as a sequence of symbols. We shall usually do so in '''boldface''', but in this section we shall use ''italics'' to avoid confusion with terms being defined, hence, ''PEG''. On other occasions we may choose to represent them with the ordered list notation, hence, [''P'',''E'',''G'']. (This form is useful when the symbols consist of more than one glyph, as can be the case when they are integers; see below.) We will often number the characters of strings, sometimes starting from zero, sometimes starting from one.		For ease of conceptualization, we shall usually assign a ''symbol'', a graphical representation, to each character of the alphabet and, considering a string as a sequence of characters, render it as a sequence of symbols. We shall usually do so in '''boldface''', but in this section we shall use ''italics'' to avoid confusion with terms being defined, hence, ''PEG''. On other occasions we may choose to represent them with the ordered list notation, hence, [''P'',''E'',''G'']. (This form is useful when the symbols consist of more than one glyph, as can be the case when they are integers; see below.) We will often number the characters of strings, sometimes starting from zero, sometimes starting from one.

@@ Line 2: / Line 2: @@
 ==Definitions==
-An '''alphabet''', usually denoted <math>\Sigma</math> is a finite nonempty set (whose size is denoted <math>|\Sigma|</math>). It is often assumed that the alphabet is totally ordered, but this is not always necessary. An element of this the alphabet is known as a '''character'''.
+An '''alphabet''', usually denoted <math>\Sigma</math> is a finite nonempty set (whose size is denoted <math>|\Sigma|</math>). It is often assumed that the alphabet is totally ordered, but this is not always necessary. (Since the alphabet is finite, we can always impose a total order when it would be useful to do so, such as when constructing a [[dictionary]].) An element of this the alphabet is known as a '''character'''.
 The set of <math>n</math>-tuples of <math>\Sigma</math> is denoted <math>\Sigma^n</math>. A '''string of length <math>n</math>''' is an element of <math>\Sigma^n</math>. The set <math>\Sigma^*</math> is defined <math>\Sigma^0 \cup \Sigma^1 \cup ...</math>; an element of <math>\Sigma^*</math> is known simply as a '''string''' over <math>\Sigma</math>. The '''empty string''', denoted <math>\epsilon</math> or <math>\lambda</math>, is the unique element of <math>\Sigma^0</math>. The length of a string <math>S</math> is denoted <math>|S|</math>. (Note that the usual definition of "string" requires strings to have finite length, although arbitrarily long strings exist.)

@@ Line 16: / Line 16: @@
 * The set of universal proteinogenic amino acids, {''A'', ''C'', ''D'', ''E'', ''F'', ''G'', ''H'', ''I'', ''K'', ''L'', ''M'', ''N'', ''P'', ''Q'', ''R'', ''S'', ''T'', ''V'', ''W'', ''Y''} (<math>|\Sigma|=20</math>). The primary structure of a protein is represented as a string over this alphabet. This and the preceding example are important alphabets in bioinformatics.
-A '''substring''' of a string <math>S = c_1 c_2 ... c_n</math> is given by <math>s = c_i c_{i+1} ... c_j</math> for some <math>i, j \in \mathbb{N}</math> with <math>i \leq j \leq n</math>. Note that the empty string is considered a substring of all other strings. In other words, it is a series of (possibly zero) characters occurring consecutively in a string, taken in order. For example, ''the'', ''in'', ''here'', and ''therein'' are all substrings of ''therein'', as is <math>\epsilon</math>; however, ''tin'' is not (the characters are not consecutive in the original string), nor is ''rine'' (the characters do not occur in order in the original string). A '''prefix''' is a substring with <math>i = 1</math>, so that <math>\epsilon</math>, ''the'', ''there'', and ''therein'' are prefixes of ''therein''. A '''suffix''' is a substring with <math>j = n</math>, so that <math>\epsilon</math>, ''in'', ''rein'', ''herein'', and ''therein'' are suffixes of ''therein''. We write <math>s \sqsubset S</math> to indicate that <math>s</math> is a prefix of <math>S</math>. Likewise the notation <math>s \sqsupset S</math> denotes that <math>s</math> is a suffix of <math>S</math>. We say that <math>s</math> is a '''proper prefix''' of <math>S</math> when <math>s \sqsubset S</math> and <math>s \neq S</math>, with '''proper suffix''' defined analogously.
+A '''substring''' of a string <math>S = c_1 c_2 ... c_n</math> is a string with the same alphabet as <math>S</math> given by <math>s = c_i c_{i+1} ... c_j</math> for some <math>i, j \in \mathbb{N}</math> with <math>i \leq j \leq n</math>. Note that the empty string is considered a substring of all other strings. In other words, it is a series of (possibly zero) characters occurring consecutively in a string, taken in order. For example, ''the'', ''in'', ''here'', and ''therein'' are all substrings of ''therein'', as is <math>\epsilon</math>; however, ''tin'' is not (the characters are not consecutive in the original string), nor is ''rine'' (the characters do not occur in order in the original string). A '''prefix''' is a substring with <math>i = 1</math>, so that <math>\epsilon</math>, ''the'', ''there'', and ''therein'' are prefixes of ''therein''. A '''suffix''' is a substring with <math>j = n</math>, so that <math>\epsilon</math>, ''in'', ''rein'', ''herein'', and ''therein'' are suffixes of ''therein''. We write <math>s \sqsubset S</math> to indicate that <math>s</math> is a prefix of <math>S</math>. Likewise the notation <math>s \sqsupset S</math> denotes that <math>s</math> is a suffix of <math>S</math>. We say that <math>s</math> is a '''proper prefix''' of <math>S</math> when <math>s \sqsubset S</math> and <math>s \neq S</math>, with '''proper suffix''' defined analogously.
 These examples may have given the misleading impression that strings which do not represent "valid" words, such as ''ther'', are not valid strings. This is entirely untrue; ''ther'' is also a valid prefix of ''therein''. The definition of a string says nothing about the ''validity'' or ''meaning'' of a string. A '''language''' is a (possibly empty, often infinite) subset of <math>\Sigma^*</math>; an element of a language is often called a ''word'' (although this term should be used with caution). Thus, while every element of <math>\Sigma^*</math> is a valid string, not all are necessarily valid words in a language over <math>\Sigma^*</math>. For example, let <math>\Sigma</math> be defined as the Latin alphabet and <math>L \subseteq \Sigma^*</math> be the language consisting of the representations of all valid English words. (Note that we have been careful to distinguish the words themselves from their representations as strings.) Then ''ther'' is certainly a valid ''string'', being an element of <math>\Sigma^*</math>, but is not a valid ''word'' in <math>L</math>, since it does not represent an English word.
@@ Line 22: / Line 22: @@
 Thus, a string of length <math>N</math> has <math>N+1</math> prefixes, <math>N+1</math> suffixes, <math>N</math> proper prefixes, <math>N</math> proper suffixes, and <math>1+N(N+1)/2</math> substrings. (Here we consider two substrings to be distinct if they start or end at different indices, except that the empty string is counted only once; see also [[counting distinct substrings]].)
-Strings can be '''concatenated'''. To concatenate two strings is to link them together to give a new string which begins with the first and ends with the second with no overlap. Formally, the concatenation of strings <math>S</math> and <math>T</math> is denoted <math>ST</math> and has the following three properties:
+Two strings with the same alphabet can be '''concatenated'''. To concatenate two strings is to link them together to give a new string which begins with the first and ends with the second with no overlap. Formally, the concatenation of strings <math>S</math> and <math>T</math> is denoted <math>ST</math> and has the following three properties:
 # <math>S \sqsubset ST</math>
 # <math>T \sqsupset ST</math>
 # <math>|ST| = |S|+|T|</math>
 For example, concatenating ''there'' and ''in'' gives ''therein''. So do concatenating ''the'' and ''rein'', or <math>\epsilon</math> and ''therein'', or ''therein'' and <math>\epsilon</math>. Note that in general, concatenation is not commutative.

@@ Line 4: / Line 4: @@
 An '''alphabet''', usually denoted <math>\Sigma</math> is a finite nonempty set (whose size is denoted <math>|\Sigma|</math>). It is often assumed that the alphabet is totally ordered, but this is not always necesary. An element of this the alphabet is known as a '''character'''.
-The set of <math>n</math>-tuples of <math>\Sigma</math> is denoted <math>\Sigma^n</math>. A '''string of length <math>n</math>''' is an element of <math>\Sigma^n</math>. The set <math>\Sigma^*</math> is defined <math>\Sigma^0 \cup \Sigma^1 \cup ...</math>; an element of <math>\Sigma^*</math> is known simply as a '''string''' over <math>\Sigma</math>. The '''empty string''', denoted <math>\lambda</math>, is the unique element of <math>\Sigma^0</math>. (The usual definition of "string", then, requires strings to have finite but unbounded length.)
+The set of <math>n</math>-tuples of <math>\Sigma</math> is denoted <math>\Sigma^n</math>. A '''string of length <math>n</math>''' is an element of <math>\Sigma^n</math>. The set <math>\Sigma^*</math> is defined <math>\Sigma^0 \cup \Sigma^1 \cup ...</math>; an element of <math>\Sigma^*</math> is known simply as a '''string''' over <math>\Sigma</math>. The '''empty string''', denoted <math>\epsilon</math> or <math>\lambda</math>, is the unique element of <math>\Sigma^0</math>. The length of a string <math>S</math> is denoted <math>|S|</math>. (Note that the usual definition of "string" requires strings to have finite length, although arbitrarily long strings exist.)
 For ease of conceptualization, we shall usually assign a ''symbol'', a graphical representation, to each character of the alphabet and, considering a string as a sequence of characters, render it as a sequence of symbols. We shall usually do so in '''boldface''', but in this section we shall use ''italics'' to avoid confusion with terms being defined, hence, ''PEG''. On other occasions we may choose to represent them with the ordered list notation, hence, [''P'',''E'',''G'']. (This form is useful when the symbols consist of more than one glyph, as can be the case when they are integers; see below.) We will often number the characters of strings, sometimes starting from zero, sometimes starting from one.
 Examples of alphabets include:
-* The binary alphabet, with exactly two characters (<math>|\Sigma|=2</math>), usually denoted ''0'' and '''1'''. In virtually all computers ever built, data are strings over the binary alphabet, and are known as bit strings.
+* The binary alphabet, with exactly two characters (<math>|\Sigma|=2</math>), usually denoted ''0'' and ''1''. In virtually all computers ever built, data are strings over the binary alphabet, and are known as bit strings.
 * The Latin alphabet, with the characters ''a'', ''A'', ''b'', ''B'', ..., ''z'', ''Z'' (<math>|\Sigma|=52</math>). English words may be considered strings over the Latin alphabet.
 * The Unicode character set (the size of this alphabet depends somewhat on what we consider to be a valid Unicode character). Text files may be considered strings over this alphabet.
 * The set of integers <math>\Sigma = \{0, 1, ..., N-1\}</math> for some <math>N \in \mathbb{N}</math>, for which <math>|\Sigma| = N</math>. Here the characters are also integers, and their corresponding symbols might have more than one glyph when <math>N > 10</math>. (Recall that the definition of ''character'' is broader than the common concept of the character as the smallest, indivisible element of writing.)
 * The set of nitrogenous bases in DNA, {''A'', ''C'', ''G'', ''T''}, with <math>|\Sigma|=4</math>. Codons are considered members of <math>\Sigma^3</math>, and DNA sequences members of <math>\Sigma^*</math>.
-A '''substring''' of a string <math>S = c_1 c_2 ... c_n</math> is given by <math>s = c_i c_{i+1} ... c_j</math> for some <math>i, j \in \mathbb{N}</math> with <math>i \leq j \leq n</math>. Note that the empty string is considered a substring of all other strings. In other words, it is a series of (possibly zero) characters occurring consecutively in a string, taken in order. For example, ''the'', ''in'', ''here'', and ''therein'' are all substrings of ''therein'', as is <math>\lambda</math>; however, ''tin'' is not (the characters are not consecutive in the original string), nor is ''rine'' (the characters do not occur in order in the original string). A ''prefix'' is a substring with <math>i = 1</math>, so the empty string, ''the'', ''there'', and ''therein'' are prefixes of
+A '''substring''' of a string <math>S = c_1 c_2 ... c_n</math> is given by <math>s = c_i c_{i+1} ... c_j</math> for some <math>i, j \in \mathbb{N}</math> with <math>i \leq j \leq n</math>. Note that the empty string is considered a substring of all other strings. In other words, it is a series of (possibly zero) characters occurring consecutively in a string, taken in order. For example, ''the'', ''in'', ''here'', and ''therein'' are all substrings of ''therein'', as is <math>\epsilon</math>; however, ''tin'' is not (the characters are not consecutive in the original string), nor is ''rine'' (the characters do not occur in order in the original string). A '''prefix''' is a substring with <math>i = 1</math>, so that <math>\epsilon</math>, ''the'', ''there'', and ''therein'' are prefixes of ''therein''. A '''suffix''' is a substring with <math>j = n</math>, so that <math>\epsilon</math>, ''in'', ''rein'', ''herein'', and ''therein'' are suffixes of ''therein''. We write <math>s \sqsubset S</math> to indicate that <math>s</math> is a prefix of <math>S</math>. Likewise the notation <math>s \sqsupset S</math> denotes that <math>s</math> is a suffix of <math>S</math>. We say that <math>s</math> is a '''proper prefix''' of <math>S</math> when <math>s \sqsubset S</math> and <math>s \neq S</math>, with '''proper suffix''' defined analogously.
-''therein''. A ''suffix'' is a substring with <math>j = n</math>, so the empty string, ''in'', ''rein'', ''herein'', and ''therein'' are suffixes of ''therein''.
 These examples may have given the misleading impression that strings which do not represent "valid" words, such as ''ther'', are not valid strings. This is entirely untrue; ''ther'' is also a valid prefix of ''therein''. The definition of a string says nothing about the ''validity'' or ''meaning'' of a string. A '''language''' is a (possibly empty, often infinite) subset of <math>\Sigma^*</math>; an element of a language is often called a ''word'' (although this term should be used with caution). Thus, while every element of <math>\Sigma^*</math> is a valid string, not all are necessarily valid words in a language over <math>\Sigma^*</math>. For example, let <math>\Sigma</math> be defined as the Latin alphabet and <math>L \subseteq \Sigma^*</math> be the language consisting of the representations of all valid English words. (Note that we have been careful to distinguish the words themselves from their representations as strings.) Then ''ther'' is certainly a valid ''string'', being an element of <math>\Sigma^*</math>, but is not a valid ''word'' in <math>L</math>, since it does not represent an English word.