The R Project SVN R

% File src/library/utils/man/adist.Rd

% Part of the R package, https://www.R-project.org

% Copyright 2011-2015 R Core Team

% Distributed under GPL 2 or later

\name{adist}

\alias{adist}

\title{Approximate String Distances}

\description{

  Compute the approximate string distance between character vectors.

  The distance is a generalized Levenshtein (edit) distance, giving the

  minimal possibly weighted number of insertions, deletions and

  substitutions needed to transform one string into another.

}

\usage{

adist(x, y = NULL, costs = NULL, counts = FALSE, fixed = TRUE,

      partial = !fixed, ignore.case = FALSE, useBytes = FALSE)

}

\arguments{

  \item{x}{a character vector.  \link{Long vectors} are not supported.}

  \item{y}{a character vector, or \code{NULL} (default) indicating

    taking \code{x} as \code{y}.}

  \item{costs}{a numeric vector or list with names partially matching

    \samp{insertions}, \samp{deletions} and \samp{substitutions} giving

    the respective costs for computing the Levenshtein distance, or

    \code{NULL} (default) indicating using unit cost for all three

    possible transformations.}

  \item{counts}{a logical indicating whether to optionally return the

    transformation counts (numbers of insertions, deletions and

    substitutions) as the \code{"counts"} attribute of the return

    value.}

  \item{fixed}{a logical.  If \code{TRUE} (default), the \code{x}

    elements are used as string literals.  Otherwise, they are taken as

    regular expressions and \code{partial = TRUE} is implied

    (corresponding to the approximate string distance used by

    \code{\link{agrep}} with \code{fixed = FALSE}).}

  \item{partial}{a logical indicating whether the transformed \code{x}

    elements must exactly match the complete \code{y} elements, or only

    substrings of these.  The latter corresponds to the approximate

    string distance used by \code{\link{agrep}} (by default).}

  \item{ignore.case}{a logical.  If \code{TRUE}, case is ignored for

    computing the distances.}

  \item{useBytes}{a logical.  If \code{TRUE} distance computations are

    done byte-by-byte rather than character-by-character.}

}

\value{

  A matrix with the approximate string distances of the elements of

  \code{x} and \code{y}, with rows and columns corresponding to \code{x}

  and \code{y}, respectively.

  If \code{counts} is \code{TRUE}, the transformation counts are

  returned as the \code{"counts"} attribute of this matrix, as a

  3-dimensional array with dimensions corresponding to the elements of

  \code{x}, the elements of \code{y}, and the type of transformation

  (insertions, deletions and substitutions), respectively.

  Additionally, if \code{partial = FALSE}, the transformation sequences

  are returned as the \code{"trafos"} attribute of the return value, as

  character strings with elements \samp{M}, \samp{I}, \samp{D} and

  \samp{S} indicating a match, insertion, deletion and substitution,

  respectively.  If \code{partial = TRUE}, the offsets (positions of

  the first and last element) of the matched substrings are returned as

  the \code{"offsets"} attribute of the return value (with both offsets

  \eqn{-1} in case of no match).

}

\details{

  The (generalized) Levenshtein (or edit) distance between two strings

  \var{s} and \var{t} is the minimal possibly weighted number of

  insertions, deletions and substitutions needed to transform \var{s}

  into \var{t} (so that the transformation exactly matches \var{t}).

  This distance is computed for \code{partial = FALSE}, currently using

  a dynamic programming algorithm (see, e.g.,

  \url{https://en.wikipedia.org/wiki/Levenshtein_distance}) with space

  and time complexity \eqn{O(mn)}, where \eqn{m} and \eqn{n} are the

  lengths of \var{s} and \var{t}, respectively.  Additionally computing

  the transformation sequence and counts is \eqn{O(\max(m, n))}.

  The generalized Levenshtein distance can also be used for approximate

  (fuzzy) string matching, in which case one finds the substring of

  \var{t} with minimal distance to the pattern \var{s} (which could be

  taken as a regular expression, in which case the principle of using

  the leftmost and longest match applies), see, e.g.,

  \url{https://en.wikipedia.org/wiki/Approximate_string_matching}.  This

  distance is computed for \code{partial = TRUE} using \samp{tre} by

  Ville Laurikari (\url{http://laurikari.net/tre/}) and

  corresponds to the distance used by \code{\link{agrep}}.  In this

  case, the given cost values are coerced to integer.

  Note that the costs for insertions and deletions can be different, in

  which case the distance between \var{s} and \var{t} can be different

  from the distance between \var{t} and \var{s}.

}

\seealso{

  \code{\link{agrep}} for approximate string matching (fuzzy matching)

  using the generalized Levenshtein distance.

}

\examples{

## Cf. https://en.wikipedia.org/wiki/Levenshtein_distance

adist("kitten", "sitting")

## To see the transformation counts for the Levenshtein distance:

drop(attr(adist("kitten", "sitting", counts = TRUE), "counts"))

## To see the transformation sequences:

attr(adist(c("kitten", "sitting"), counts = TRUE), "trafos")

## Cf. the examples for agrep:

adist("lasy", "1 lazy 2")

## For a "partial approximate match" (as used for agrep):

adist("lasy", "1 lazy 2", partial = TRUE)

}

\keyword{character}