Formal Regular Expressions

Put together in a set, all regular expressions together form an algebra. That is, regular expressions can be built up and combined systematically by applying a few basic operations, possibly over and over again. Each such operation yields a new and valid regular expression.

The first three rules for constructing regular expressions just introduce some notation and relate regular expressions to sets of strings.

1. Rule 1 The symbols and are regular expressions, representing, respectively, the empty string "" and the empty subset of .
2. Rule 2 If is a symbol in , then a is a regular expression representing .
3. Rule 3 If is a regular expression, then so is .

The first rule defines mathematical cases that are necessary for a complete algebraic development of regular expressions. They will not be important for our purpose. Brackets have exactly the effect one expects of them: they determine the order in which combining operations are executed, just like in normal arithmetic. The next set of rules determines how regular expressions can be operated upon.

The fourth and fifth rules introduce concatenation and ‘or’-ing of regular expressions.

1. Rule 4 If and are regular expressions, then so is .
2. Rule 5 If and are regular expressions, then so is .

The | notation indicates that a position in a string can be occupied by either of its operands. For example, the regular expression a(a|ab)a indicates the set . The set of strings defined by the concatenation of two regular expressions is the concatenation of all strings of the first with all strings of the second set. In other words, if and are the sets of strings defined by regular expressions and , then the set defined by is defined as . For example, take

Concatenating with , we get

The operations introduced thus far only allow us to define finite sets of strings. The star operator, introduced in the last rule, changes this.

1. Rule 6 If is a regular expressions, then so is .

The star operator indicates ‘repeat the preceding symbol zero or more times’. The operator was first introduced by Kleene (1951), and it is therefore often referred to as the Kleene (star) operator. For example, the regular expression a*ba*c corresponds to the set

To complete our discussion of formal regular expressions, we need to define the rules for operator precedence. That is, we need to define rules so we understand whether for example a|b* should be read as (a|b)*, as a|(b*). The rule is that the * goes first, then comes concatenation, and finally |. In other words, the expression ab|c* must be read as (ab)|(c*).

Limits of Regular Expressions

As stated before, regular expressions are finite notations indicating subsets of . In particular, the Kleene operator allows us to indicate infinite sets of strings with a regular expression of finite size. A natural question is whether every possible subset of can be denoted with a finite regular expression. The answer to this question is ‘no’. In fact, subsets of that can be defined by a regular expression are called regular.

There are several ways to prove this. One way is to show that the number of subsets of is much larger (uncountably infinite) than the number of sets that can be indicated by regular expressions (countably infinite). A second way is by giving a counterexample. For example, the set of strings defined by

cannot be denoted by a finite regular expression. The actual proof of this statement relies on automata theory and is beyond the scope of this book. It can be found in many textbooks on languages and automata theory, such as Hopcroft et al. (2007). However, the result can be made intuitively clear by attempting to build a regular expression for . For example, the expression aa*bb* fails, since this also includes strings not in , such as "abb" and "aaab". Another natural candidate would be ab|aabb|aaabbb|. However, this expression is clearly not finite and so contradicts our demand that be expressed with a finite regular expression. The main intuition here is that regular expressions lack a certain sense of memory. To be able to tell whether a string is in or not, one needs to count the number of "a"'s and then verify whether ensuing number of "b"'s is the same. Since we have no way to count the number of characters, it is not possible to define a regular expression that defines . In the next section we shall see that extended regular expressions (EREs) add behavior and operators to relieve this limitation.

Because sets of strings can be defined in many ways, there is no easy general technique or rule to determine whether an infinite set of strings is definable by a regular expression or not. Rather, there are a set of mathematical techniques that have to be applied on a case-by-case basis. An easy to remember general rule, however, is that any set of strings where for each string in the set, the structure of a string at one position depends directly on the structure of the string at another position is not regular.

Character Ranges

There are four ways to indicate that a string must have any of a range of characters at a certain position. The first we have already seen: it involves using the ‘or’ operator. Secondly, to indicate a position where any single character may occur, one uses the . (period) as a ‘wildcard’ character: it stands for any symbol from the alphabet. For example, the regular expression a.b stands for all strings starting with "a", followed by an arbitrary character, followed by "b".

Third, expressions surrounded by square brackets [ ] can be used to indicate custom character ranges. So the range [AaBb012] is equivalent to A|a|B|b|0|1|2. If the closing bracket ] is part of the range, it must be included as the first character after the opening bracket, i.g. []ABC]. A range of consecutive characters can be indicated with a dash -, so, for example, [abcd] is equivalent to [a-d]. If the dash itself is part of the range, it must be included as the final character in the range, that is, -|a|b|c|d can be expressed as [a-d-]. It is also possible to negate a range of characters. For example, to express strings that start with "a", then have any character, except [c-f] one uses the ∧ at the beginning of the range: a[∧c-f].

Finally, a number of common character classes have been given predefined names. For example, the class [:digit:] is equivalent to 0-9. Note that named character ranges have to be used within a bracketed expression, so a valid expression detecting any single digit would look like this: [[:digit:]]. An overview of named character classes is given in Table 5.1. Here, we give a few more examples.

Consider the problem of detecting a class of e-mail addresses from domains ending with .com, .org, or .net. With the operators and character classes just discussed, one may construct a regular expression like this:

5.5

This expression detects strings that start with one or more alphanumeric characters, followed by a @, followed again by one or more alphanumeric characters, a period, and then com, net, or org. Note that the period is prepended with a backslash to indicate that the period must not be interpreted as a wildcard but as a simple period.

Range symbol	ASCII range	Description
. (period)	All	Any single character
[:alpha:]	[a-zA-Z]	Letters
[:digit:]	[0-9]	Numbers
[:alnum:]	[a-zA-Z0-9]	Letters and numbers
[:lower:]	[a-z]	Lowercase letters
[:upper:]	[A-Z]	Uppercase letters
[:cntrl:]	Characters 0–31	Control characters
[:space:]	Space, horizontal and vertical tab, line and form feed, and carriage return	Space characters
	[:print:]	Printable characters
[:blank:]	Space and tab	Blank characters
[:graph:]	[:alnum:] and [:punct:]	Graphical characters
[:punct:]	! " # $ % & ' () * + , - . / : ; < = > ? @ [ ] ∧ _ { | }	Punctuation
[:xdigit:]	[0-9a-fA-F]	Hexadecimal numbers

The actual interpretation depends on the alphabet used, which in R depends on the locale settings.

Suppose, as a second example, that we want to detect filenames that end with .csv. The following regular expression detects patterns consisting of one or more arbitrary characters, followed by .csv.

5.6

Here, we also introduced the dollar as a special character. The dollar stands for ‘the end of the string’. Recall from Section 5.2.1 that R functions like grepl match any string that has a substring matching the regular expression. By appending the dollar sign we, explicitly specify that the .csv must be at the end of the string.

There are two more types of character classes that can be defined with bracketed expressions, both of them related to collation and character equivalence classes (see Section 3.2.8). For example, in one language, the "ä" may be a separate letter of the alphabet, whereas in another language it may be considered equivalent to "a". The special notation for such equivalence classes is [= =]. To indicate a particular class, one specifies a single representative from an equivalence class between [= and =]. For example, if "o", "ó","ô", and "ö" belong to a single class, then the expression [[=o=]p] is equivalent to [oóôöp].

In Section 3.2.8, we also discussed the example from the Czech alphabet, where the combination"CH" is considered a single character sorting between "H" and "I". To distinguish such cases within a bracketed expression, one places multicharacter collations between [. and .]. So, for example, in [[.CH.]abc], the "CH" is treated as a single unit.

Repetitions

The Kleene star operator adds the ability to express zero or more repetitions of a pattern in a regular expression. In the extended regular expressions of the Single Unix Specification, there are several variants that facilitate other numbers of repetitions, all of them having the same precedence order as the Kleene star. An overview is given in Table 5.2.

To demonstrate their purpose, we express the regular expressions of examples (5.5) and (5.6) more compactly as follows:

The combined use of character classes and repetitions can be very powerful. For example, to detect phone numbers consisting of 10 digits, the following regular expression will do.

Suppose we want to allow phone numbers that may have a dash between the second and third number, we might use

If we also want to include phone numbers where a blank character is used instead of a dash, we can expand the expression further.

Operator	Description
*	Zero or more
?	Zero or one
+	One or more
{}	Precisely
{,}	or more
{,}	Minimum to maximally

Recognizing the Beginning or Ending of Lines

EREs have two special characters that anchor a pattern to the beginning or ending of a line.

For formal regular expressions, such operators are not needed since they only define a precise range of strings, from beginning to end. However, programs (and R functions) such as grep recognize strings that have a substring matching a regular expression. As an example, compare the two calls to grep given here.

  x <- c("aa","baa")
  grepl("a(a|b)", x)
  ## [1] TRUE TRUE
  grepl("∧a(a|b)", x)
  ## [1]  TRUE FALSE

The first regular expression is interpreted by grep to match any string having a(a|b) as a substring. Therefore, both strings are matched. The second regular expression, ∧a(a|b), explicitly requires the string to begin with an "a".

Special Symbols and Escaping them in R

In the previous sections we introduced several characters that have a special interpretation. This means that to recognize such characters simply as themselves, we have to do something extra, that is, we need to escape their special interpretation. As a reminder, we thus far encountered the following characters with a special interpretation.

To interpret them as literal characters, in EREs, one can either precede them by a backslash or include them in a bracketed expression [ ] (but see the section on character ranges on how to properly include ] and ∧). So, for example, the expression a.b would recognize "a.b" but not "aHb" and a\b recognizes "a".

In R, however, there is a catch. Recall from Section 3.2.4 that in string literals the backslash already has a special meaning: it can be used to define characters using their Unicode code point. A double backslash indicates an actual single backslash, preventing the interpretation of "u" as a command.

  c("uf6","\uf6")
  ## [1] "ö"     "\uf6"

Observe that R prints both backslashes at the command prompt. However, one may check, for example by exporting the string to a text file or by checking the string length with nchar, that the actual string contains a single backslash. For string literals that are to be interpreted as regular expressions, a double backslash must be included to indicate a single escape character.

  # detect a.b, not a<wildcard>b
  grepl("a\.b", c("a.b", "aHb"))
  ## [1]  TRUE FALSE

To recognize a single backslash, a double backslash should be used in an ERE. In R, this means using two escaped backslashes so as to recognize the string "a", and we can do the following:

  # recognize "a" and not "ab"
  grepl("a\\b", c("a\b","ab"))
  ## [1]  TRUE FALSE

Such constructions quickly become unreadable as regular expressions get larger. A better alternative is to use bracketed expressions as follows:

  grepl("a[\]b", c("a\b","ab"))
  ## [1]  TRUE FALSE

This does not reduce the length of an expression, but it does enhance readability. More importantly, the latter statement is compatible with extended regular expressions according to the Single Unix Specification.

Finally, we note that R has an option to escape regular expressions altogether. Functions like sub, gsub, grep, and grepl have an option called fixed. This option allows one to interpret the search pattern as is and not as a regular expression.

  x <- c("a.b", "aHb", "a.b.*")
  grepl("a.b.*", x)
  ## [1] TRUE TRUE TRUE
  grepl("a.b.*", x, fixed=TRUE)
  ## [1] FALSE FALSE  TRUE

Being Lazy, Being Greedy

When a regular expression operator contains one or more of the repetition operators + or *, it is possible for a string to contain matches of varying length. For example, suppose we wish to remove the HTML tags in the following string.

  The <em>hello world</em> programme.

As a first guess, we might attempt to use the pattern <.*> to find the tags. The problem is that there are several substrings matching this pattern: "<em>", "</em>" and "<em>hello world</em>". If one is only interested in whether a substring occurs or not, this is not a problem. It does become a problem when specific substrings need to be replaced or removed.

For this reason, EREs include a syntax to specify whether the shortest (lazy) or the longest (greedy) match should be used. The default behavior is to use the greedy match. Here is a simple demonstration using R's gsub function, which replaces every occurrence of a match with a replacement string.

  s <- "The <em>hello world</em> programme"
  gsub(pattern="<.*>", replacement="", x=s)
  ## [1] "The  programme"

Here, we replace each occurrence of the pattern <.*> with the empty string "". Since the default behavior is to be greedy, the pattern matches everything from the first occurrence of "<" to the last occurrence of ">". The question mark operator introduced in Table 5.2 switches the behavior to lazy matching.

  gsub(pattern="<.*?>", replacement="", x=s)
  ## [1] "The hello world programme"

The pattern <.*?> translates to: first a "<", followed by zero or more characters, to end with ">". Since we use gsub (the g stands for global), every such occurrence is replaced.

Regular Expressions with Memory: Groups and Back Referencing

We noted in Section 5.2.1 that regular expressions are limited since they lack a sense of memory and this is true for ‘pure’ regular expressions. In EREs, this restriction is relieved by introducing the concept of groups. The idea is that the strings that match a bracketed tag are stored for later reference. For example, to replace the string

  The <em>hello world</em> programme

with

  The <b>hello world</b> programme

we can devise a regular expression that stores everything between the <em> and </em> tags and places it between <b> and </b> tags.

   s <- "the <em>hello world</em> programme"
   gsub("<em>(.*?)</em>", "<b>\1</b>", s)
  ## [1] "the <b>hello world</b> programme"

Here, the \1 refers back to the first bracketed expressions. Most regular expression engines, including R's, allow for back referencing up to nine grouped expressions in this way: 1, 2, , 9 (recall that R requires the double backslash, since the first gets processed by R prior to passing it to the regular expression engine).

A second use of groups and references is to use the reference within the search pattern. For example, to match any HTML tag that is closed properly, one can use the expression <(.*)?>.*</\1>. Here, the first group, defined by (.*?), is referenced in the closing tag.

  grepl("<(.*?)>.*?</\1>", c("<li> hello","<em>hello world</em>"))
  ## [1] FALSE  TRUE

Finally, we note that some popular regular expression formats like the Perl Compatible Regular Expressions PCRE (2015) support named groups and back references. In R, support for Perl-like syntax is available through the perl=TRUE option.

  grepl("<(?P<tag>.*?)>.*?</(?P=tag)>"
    , c("<li> hello","<em>hello world</em>")
    , perl=TRUE)
  ## [1] FALSE  TRUE

Here, we use the syntax (?:<[groupname]>[pattern]) to define a named group. The syntax (?P[groupname]) is used for back reference. Support for named groups is somewhat limited, since group names cannot be used in the replacement string of (g)sub, even when using the perl=TRUE switch.

Since any modern (read: extended) regular expression engine interprets a bracketed expression as a group to be captured, one might wonder if this capturing may be switched off. This is indeed the case, and the syntax for that is (?:[pattern]). One use of this is to avoid adding to the back-reference counter for groups that are not reused.

A Few Tips on Building and Maintaining Regular Expressions

Regular expressions are powerful tools that allow for fast text processing in a compactly defined way. In practice, regular expressions have the property of being fairly easy to build up, but they are typically also hard to decypher and debug.

When building regular expressions, it is a good idea to work step by step, setting up a simple expression, trying it out, check the cases you missed, and expand it further. When expressions get too long to read comfortably, it may be a good idea to split your job in two, applying two filters consecutively. In any case, it is a good idea to spend a few lines of comment explaining what you are trying to accomplish with a regular expression.

For many well-known patterns, such as zip codes, e-mail addresses or social security numbers, regular expressions may well already be around. There are many websites that list regular expression solutions to common pattern matching problems. We strongly advise to test regular expressions against examples that should, and should not match.

Finally, we emphasize that regular expressions should not be regarded as the answer to all text recognition problems. It was noted before that regular expressions have their limitations. For example, regardless of the example we have used, validating all possible e-mail addresses conforming to the standard that defines valid notation is notoriously hard to do with regular expressions (see, e.g., Friedl (2006)). Another example would be a regular expression that recognizes valid IPv4 addresses. Such addresses have the form where , , , and are numbers between 0 and 255. Since the possible allowed value of the second and third digit depends on the value of the first (099 is valid but 299 is not), regular expressions are not a logical choice. As an alternative, one could split the string along the periods, convert each substring to numbers, and check their ranges.

Edit-Based Distances

These distances are based on determining a sequence of basic transformations necessary to turn one string into another. The set of basic operations (‘edits’) includes one or more of the following:

• Deletion of a single character, for example, ;
• Insertion of a single character, for example, ;
• Substitution of a single character, for example, ;
• Transposition of two adjacent characters, for example, .

A distance function is defined by determining the shortest sequence of basic operations that turns one string into another and determine the length of the sequence. Alternatively, one may assign weights specific to each type of transformation and determine the sequence of least total weight. Such distances are referred to as generalized distances (Boytsov, 2011).

First note that when a too limited set of basic operations is chosen, not every pair of strings from is connected by a sequence of allowed operations. Formally, such functions are not total functions on . We will follow the same convention as Navarro (2001) and define the distance between such unconnected pairs to be infinite. The advantage of this convention is that numerical comparisons () are then valid between all computed distances.

It can be shown that unweighted edit-based distances all obey the properties of a proper distance (Eq. 5.8), see, for example, Boytsov (2011). When different weights are assigned to insertion and deletion, distances become asymmetric: walking from "abc" to "ac" requires an insertion while walking from "ac" to "abc" requires an deletion. Distance functions with weighted insertion or deletion are symmetric under simultaneous swapping of both the input strings and deletion and insertion weights.

Distance	Operation
	del	ins	sub	trn
Hamming
Longest common substring
Levenshtein
Optimal string alignment				a
Damerau–Levenshtein

^a Each character can take part in maximally a single transposition.

Table 5.4 gives an overview of commonly used edit-based string distances and their allowed operations. The distance of Hamming (1950) is the simplest and allows only for substitution of characters. Hence, it is finite only when computed between strings of the same length. For example, we have and . Since there is only one allowed operation, there is no use in defining weights. Since it is defined only on strings of equal lengths, in the context of text processing, the Hamming distance is most useful for standardized strings, such as phone numbers, product codes, or other identifying numbers.

The longest common subsequence distance (lcs distance) of Needleman and Wunsch (1970) is the simplest generalization of the Hamming distance and it replaces the substitution operation by allowing insertion and deletion of characters. This means that the distance function is a complete function on . In fact, it is easy to see that given two strings and , their distance will be largest if they have no characters in common. In that case, the distance from to is simply , the cost of deleting one by one all characters from and then inserting all characters of . As an example, consider the distance between "fu" and "foo". Using only deletion and insertion, it takes three steps to go from one to the other.

This also shows that there is not necessarily a unique shortest path from the start point to the end. Other than in Euclidean geometry, for example, we could have chosen a different path through (e.g., ) and obtained a path of the same length.

As implied by its name, the lcs distance has a second interpretation. Given two strings, we pair common characters, passing through the strings from left to right but without changing their order. The distance between the two strings is then given by the number of unpaired characters in both strings. The diagram given here demonstrates this process.

Indeed, there are three unpaired characters in the two strings. Note that a subsequence is not the same as a substring. If is a string, a substring indicates a consecutive sequence . A subsequence is a sequence of characters that preserves order () but need not be consecutive. Hence, "fbar" is a subsequence of both "fubar" and "foobar" but is not a substring. Applications of the lcs distance lie mainly outside of data cleaning, although it can be interpreted as a crude (and fast) approach for typo-detection. In principle it is possible to define a generalized lcs distance by assigning different weights to insertion and deletion but this seems not very common in practice.

The Levenshtein distance (Levenshtein, 1966) is like the longest common substring distance but it is more flexible since it also allows for direct substitution of a character, which would take two steps in the lcs distance. This extra flexibility leads to shorter minimal distances. For example, the Levenshtein distance between "fu" and "foo" equals two:

5.9

The generalized Levenshtein distance satisfies the properties of Eq. (5.8) except when the weights for insertion and deletion are different. In that case, the distance is no longer symmetric, which is easily illustrated with an example. Suppose we weigh an insertion with 0.1 and deletion and substitution with 1. We have (denoting the cost per step underneath the arrows)

giving a distance of 1.1. Going the other way around, however, we get

giving a distance of 2.

The optimal string alignment distance, which is also referred to as the restricted Damerau–Levenshtein distance, allows for insertions, deletions, substitutions, and limited transpositions of adjacent characters. The limitation lies therein that each substring may be edited only once.

The most important consequence is that optimal string alignment distance does not satisfy the triangle inequality. The following counterexample is taken from Boytsov (2011). If we take , and , the distance is given by

giving a total distance of 2. The intuitive direct path from "ab" to "bca"

5.10

However, this involves editing the subsequence "ba" twice: once by transposing "a" and "b" and once by inserting a "c" between "a" and "b". In fact, it turns out that there is no way to go from "ba" to "acb" directly in less than three steps, and so one has to resort to the sequence

The optimal string alignment distance between a string variable and a known fixed string may be interpreted as the number of typing errors made in the string variable.

The Damerau–Levenshtein distance (Lowrance and Wagner, 1975) does allow for arbitrary transpositions of characters. That is, subsequences may be edited more than once, allowing the path of Eq. (5.10).

The maximum distance between two strings and , as measured by any of the discussed distances that allows for character substitution, equals . Distances that allow for a larger number of basic operations generally yield numerically smaller distances. The given diagram summarizes the relation between edit-based distances and their limits.

5.11

Note that the maxima may be used to scale distances between 0 (exactly equal) and 1 (completely different) should a method based on a string metric require it.

Finally, some notes on the computational time it takes to compute edit-based distance. The Hamming distance can obviously be computed in time. The other edit-based distances are usually implemented using dynamic programming techniques that run in time. See Navarro (2001) or Boytsov (2011) for an overview.

The Jaro–Winkler Distance

The Jaro distance was originally developed at the US bureau of the Census as part of an application called UNIMATCH. The purpose of this program was to match records based on inexact text fields, mostly name and address data. The first description appeared in the manual of this software (Jaro, 1978), which may be a reason why it is not widely described in computer science literature. Jaro (1989), however, reports successful application of this distance for matching inexact name and address fields.

The Jaro distance is an expression based on the intuition that character mismatches and character transpositions are caused by human-typed errors and that transposition of characters that are further apart are less likely to occur. It can be expressed as follows:

5.12

Here, is the number of matching characters and the number of transpositions, counted in a way to be explained later and the are nonnegative weight parameters which are usually chosen to be 1. The distance ranges between 0 ( and are identical) and 1 (complete mismatch). It is zero if both and are the empty string and it equals 1 if there are no matches while at least one string is nonempty. Otherwise, the distance depends on a weighted sum of character matches and transpositions.

The number of matches is computed as follows. First, pair characters from and as you would for the longest common subsequence distance. It now depends on the distance between the positions of paired characters whether a pair is considered a match. In particular, if is a pair, this is considered a match only when

5.13

where indicates the floor function and each character can be included no more than one match. For example, and the number of matches .

The number of transpositions is computed as follows. First take the subsequences and of and consisting only of the matching characters. Then is the number of characters in that have to change position to turn into . For example, take and , we have and and . To turn into , we need two operations:

The term transposition here is used differently from the definition in Section 5.4.1 where it is defined for transposition of two characters. Here, it should be interpreted as transposing a single character with a substring. For example, in the first step of the abovementioned example, we may interpret the relocation of "d" as swapping with "cb".

Unfortunately, there seems to be some confusion in literature over the precise definition of the Jaro distance. Cohen et al. (2003), for example, use as an upper limit for . The definition used here, and which is also implemented in stringdist package, follows the original definition of Jaro (1978).

Winkler (1990) proposes a simple variant of the Jaro distance that rests on the observation that typing errors are less likely to occur at the beginning of a human-typed string than near the end. If differences occur at the beginning, the heuristic is that the strings are likely to be truly dissimilar. In the Jaro–Winkler distance, this phenomenon is taken advantage of by multiplying the Jaro distance with a penalty factor that depends on the number of unequal characters in the first four positions. The expression is as follows:

5.14

Here, is the length of the longest common prefix of and , up to a maximum of 4. The value of is a user-defined adjustable parameter but it must be between 0 and to ensure . The value of determines how strong the length of the common prefix weighs into the total distance and the Jaro distance emerges as a special case when . Both Winkler (1990) and Cohen et al. (2003) report good results in matching name–address data when setting .

As far as this author knows, the properties as described in Eq. (5.8) are not reported anywhere except in van der Loo (2014). They are however easily derived, so we will state them in the following observation.

-Gram-Based Distances

The edit-based distances and the Jaro–Winkler distance described are typically used for the detection of misspelling errors in fairly short strings. They are based on a precise description of what operations are allowed to turn one string into another and therefore have natural paths from to through associated with them.

Distances based on -grams, on the other hand, are computed by first deriving an integer vector (the so-called -gram profile) from strings and and defining a distance measure on the space of vectors. Well-known examples include the Manhattan distance or the cosine distance.

A -gram is a string of characters. Given a string (), the associated -gram profile is a table of size counting the occurrence of all -grams in . For example, the nonzero entries of the 2-gram profile of "banana" looks like this:

In literature on text classification, the term -gram is often used instead of -gram. Since this term is also used to indicate word sequences rather than character sequences, we follow the terminology of Ukkonen (1992) and use the term -gram to avoid confusion.

We will denote the -gram profile of a string as a vector-valued function . The range of is , the set of integer vectors whose size is the number of possible -grams allowed by the alphabet. In general, is not a complete function on . In particular, it is undefined when , and we also need to decide what to do when . Here, we adopt the following conventions:

Intuitively, this corresponds to the idea that all distances are zero as long as we are not comparing anything. In particular, it means that for any -gram-based distance.

The traditional -gram distance is computed as the Manhattan distance between two -gram profiles:

Observe that since the are counts rather than frequencies, this distance is both an expression of difference in -gram distribution as well as a difference in string lengths. It is not hard to show that the maximum -gram distance between two strings and is equal to

To accommodate for the effect of differences in string length, one can base the distance on the (cosine of the) angle between the -gram vectors.

This distance varies between 0 and 1, where 0 means complete similarity and 1 means complete dissimilarity (no overlap in occurring -grams).

A third way to compare -gram profiles is the Jaccard distance.

where returns the set of all -grams occurring in . The Jaccard distance scales from 0, indicating complete similarity to 1, indicating complete dissimilarity.

The term ‘complete similarity’ is not the same as equality. We already saw the case for , which defines all strings as equal (there is nothing to make them different when ). The fact that unequal strings have a -gram-based distance equal to zero is not, however, limited to . For example, if , the table of -gram counts is the same for two words if they are anagrams. Ukkonen (1992) has shown that one can derive transformations on strings of a certain structure that leave the -gram profile intact, for any value of . For example, the reader can check that the strings["aFOObBARa" and "bBARaFOOb"]have the same 2-gram profile.

We have seen that -gram distances do not obey the identity property of distance metrics. The other properties depend on the metric that is chosen over the positive integer vectors. The distances discussed here are all nonnegative, symmetric. Both the Jaccard and -gram distance also satisfy the triangle inequality. The cosine distance does not satisfy the triangle inequality. This is easily seen by assuming three -gram profiles, , , and with angles and . We have and . To show that the cosine distance does not satisfy the triangle inequality, we only need to find an for which . This is the case for every .

-gram profiles have been widely used as a tool for text classification. Applications and methodology have been reported where texts have been classified according to the language used (Cavnar and Trenkle, 1994), topics under discussion (Clement and Sharp, 2003), or author style and identity (Kešelj, et al. 2003), to name but a very few examples. In many cases, the use of bi- or trigrams seems an appropriate choice for natural language classification (Fürnkranz, 1998).

Distances Based on String Kernels

Just like -gram-based methods, string kernels are interesting for text categorization or clustering purposes.

A string kernel is defined by a map that assigns to each string in a real vector with nonnegative coefficients. The normalized kernel function of two strings is defined as

where ‘’ is the standard inner product on a real vector space. The right-hand side is the cosine between the angle of the feature vectors and , and thus a measure of distance can be obtained as

and a suitable map defines a sense of distance on .

Several authors have defined string kernels and tested their effectiveness. Karatzoglou and Feinerer (2007) propose two string kernels. In the first kernel (simply called the string kernel), each element of counts the number of occurrences of subsequences in .

The second kernel, called the full string kernel, is defined by concatenating the feature vectors defined by every subsequence up to length .

Lodhi et al. (2002) propose a string kernel that penalizes contributions of each subsequence by the number of positions traversed going from the first to the last character of a subsequence of .

5.15

where the sum is over every occurrence of the subsequence in , and is the length of the subsequence defined by the index vector in : .

Phonetic Algorithms

Phonetic algorithms aim to match strings that sound similar when they are pronounced. Phonetic algorithms transform a string to some kind of phonetic string that represents pronunciation features. The distance between two strings is then defined as a distance between the phonetic strings. In the simplest case, the distance is 0 when two phonetic strings are equal and 1 otherwise.

One of the most famous phonetic algorithms, called soundex, was patented for the first time in the early twentieth century (Russell, 1918 1922). It is aimed at names, written in the ASCII alphabet, pronounced in English. One widely used version of the algorithm is published by the United States National Archives and Records Administration (NARA, 2015).

The soundex algorithm encodes a string to a phonetic string consisting of a letter and three numbers. The algorithm can be summarized as follows:

For example, the names "van der loo" and de jonge map to "V536" and "D252", respectively, (after removing spaces). Phonetically similar names map to similar results. For example, "john" and "joan" both map to "J500", and similarly "ashley" and "ashly" map to "A240".

The soundex algorithm has been adapted and expanded over the years by many researchers and practitioners. Like the original algorithm, such extensions are often strongly related to a particular purpose. For example, the Metaphone algorithms by Philips (2000) started as improvement on the soundex algorithm for better matching of English names, but it has been extended to other languages including Spanish, and Brazilian Portuguese. Holmes and McCabe (2002) focus on the original purpose of English name matching, using a mix of different phonetic techniques. Mokotov (1997), and later Beider and Morse (2008) developed alternatives aimed at matching Eastern European and Ashkenazic Jewish surnames, respectively. Finally, Pinto et al. (2012) report on a soundex-like algorithm for strings typically occurring in short text messages (sms).