Stringology

In formal languages, which are used in mathematical logic and theoretical computer science, stringology deals with algorithms and data structures used for string processing. The name was coined in 1984 by computer scientist Zvi Galil.^[1]

Formal theory

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 Σⁿ. For example, if Σ = {0, 1}, then Σ² = {00, 01, 10, 11}. Note that Σ⁰ = {ε} for any alphabet Σ.

The set of all strings over Σ of any length is the Kleene closure of Σ and is denoted Σ*. In terms of Σⁿ,

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

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.

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
• Sequence mining

Advanced string algorithms often employ complex mechanisms and data structures, among them suffix trees and finite state machines.

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

See also

References