help strgroup
-------------------------------------------------------------------------------
Title

    strgroup -- Match strings based on their Levenshtein edit distance.


Syntax

    strgroup varname [if] [in] , generate(newvarname) threshold(#) [first
    normalize([shorter|longer|none]) noclean force]

  by is allowed; see help by.


Description

    strgroup matches similar strings together. This can be useful when
    merging data that contain typos. For example, "widgets" will not merge
    with "widgetts" because the strings are not identical.  strgroup provides
    a way to match strings in an objective and automated manner. It employs
    the following algorithm:

        1. Calculate the Levenshtein edit distance between all pairwise
              combinations of strings in varname.

        2. Normalize the edit distance as specified by
              normalize([shorter|longer|none]). The default is to divide the
              edit distance by the length of the shorter string.

        3. Match a string pair if their normalized edit distance is less than
              or equal to the user-specified threshold.

        4. If string A is matched to string B and string B is matched to
              string C, then match A to C.

        5. Assign each group of matches a unique number and store this result
              in newvarname.

    For example, the Levenshtein edit distance between "widgets" and
    "widgetts" is 1.  The lengths of these two strings are 7 and 8,
    respectively. Assuming normalize(shorter), they are matched by strgroup
    if 1/7 <= threshold.

    strgroup is case sensitive.

    See levenshtein for an explanation of the Levenshtein edit distance.


Options

    generate(newvarname) specifies the name of a new variable to store the
        results.

    threshold(#) sets the threshold level for matching.

    first instructs strgroup to only match strings that share the same first
        character.  This typically reduces the amount of time required for
        strgroup to run by several orders of magnitude, at the cost of
        perhaps incorrectly not matching strings.  For example, "widgets" and
        "qidgets" will not be matched if you specify first because they do
        not begin with the same character.

    normalize([shorter|longer|none]) is used to define the normalization of
        the Levenshtein edit distance. With shorter all edit distances are
        divided by the length of the shorter string in the pair; this is also
        the default. longer divides the edit distance by the length of the
        longer string. none specifies that no normalization is needed.

    noclean instructs strgroup not to trim leading and trailing blanks when
        comparing string pairs. Trimming can reduce run time.

    force forces strgroup to run even if when comparing more than 10,000
        observations. This may take a while and may cause memory problems if
        your dataset is too large.


Notes

    strgroup does not match missing strings.

    As explained above, strgroup calculates the Levenshtein edit distance
    between all pairwise combinations of strings in varname.  Let N be the
    number of observations being compared.  Then the amount of memory and
    number of calculations required by strgroup is proportional to
    (N)(N-1)/2, an expression that increases with the square of N.  Thus,
    large datasets need to be divided into subsets in order to facilitate
    calculations.  The first option automates this by subsetting strings
    according to their first characters.  Alternatively, the user can run
    strgroup on subsets of the data by using the if, in and/or by options.

    strgroup is implemented as a plugin in order to minimize memory
    requirements and to maximize speed.  Unfortunately, plugins are specific
    to the hardware architecture and software framework of your computer,
    i.e., plugins are not cross-platform.  Define a platform by two
    characteristics: machine type and operating system.  Stata stores these
    characteristics in c(machine_type) and c(os), respectively. strgroup
    supports the following platforms at this time:

         Machine type                   Operating system
         PC                             Windows
         PC (64-bit x86-64)             Windows
         PC (64-bit x86-64)             Unix
         Macintosh                      MacOSX
         Macintosh (Intel 64-bit)       MacOSX


Example

    Merge two datasets together and identify potential matches that didn't
    merge.

       . sysuse auto, clear
       . tempfile t
       . keep make price
       . replace make = make + "a" in 5
       . replace make = "gibberish" in 10
       . save "`t'"
       . sysuse auto, clear
       . keep make
       . merge make using "`t'", sort
       . list if _merge!=3
       . strgroup make if _merge!=3, gen(group) threshold(0.25)
       . list if _merge!=3


Acknowledgements

    The code used to calculate the Levenshtein edit distance is based on a
    Python extension written by David Necas (Yeti).  His code is publicly
    available at
    http://code.google.com/p/pylevenshtein/source/browse/trunk/Levenshtein.c.

    Thanks to Dimitriy Masterov for compiling the 64-bit Windows version of
    the plugin.


Author

    Julian Reif, University of Chicago

    jreif@uchicago.edu


Also see

    levenshtein, regexm