strgroup

STRGROUP: match strings based on their Levenshtein edit distance


Overview:

strgroup is a Stata command that performs a fuzzy string match using the following algorithm:

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

  2. Normalize the edit distance. The default is to divide the edit distance by the length of the shorter string in the pair.

  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.

The Levenshtein edit distance is defined as the minimum number of insertions, deletions, or substitutions necessary to change one string into the other. For example, the Levenshtein edit distance between “mitten” and “fitting” is 3, since the following three edits change one into the other, and it is impossible to do it with fewer than three edits:

  1. mitten -> fitten (substitution of ‘f’ for ‘m’)

  2. fitten -> fittin (substitution of ‘i’ for ‘e’)

  3. fittin -> fitting (insert ‘g’ at the end)

For more details, see the Stata help file included in this package.

Installation:

Type which strgroup at the Stata prompt to determine which version you have installed. To install the most recent version, copy and paste the following line of code:

net install strgroup, from("https://raw.githubusercontent.com/reifjulian/strgroup/master") replace

To install the version that was uploaded to SSC (may be older than the GitHub version), copy and paste the following line of code:

ssc install strgroup, replace

After installing, type help strgroup to learn the syntax.

strgroup is implemented as a C plugin in order to minimize memory requirements and to maximize speed. Plugins are specific to the hardware architecture and software framework of your computer. 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 (Apple Silicon/Intel) MacOSX

A 32-bit Windows plugin is included but has not been tested. Other platforms (e.g., 32-bit Unix) are not supported.

Compiling:

The C source code for strgroup is available in /src/c. It must be compiled separately for different machine types.

PC Windows 32-bit (legacy, requires older Cygwin with -mno-cygwin support):

gcc -shared -mno-cygwin stplugin.c strgroup.c -O3 -funroll-loops -o strgroup.windows32.plugin

PC Windows 64-bit (needs Cygwin and mingw compiler):

x86_64-w64-mingw32-gcc -shared stplugin.c strgroup.c -O3 -funroll-loops -o "strgroup.windows64.plugin"

Unix 64-bit:

gcc -shared -fPIC -DSYSTEM=OPUNIX stplugin.c strgroup.c -O3 -funroll-loops -o "strgroup.unix.plugin"

macOS (Apple Silicon and Intel):

clang -bundle -o strgroup.macosx.x86_64 stplugin.c strgroup.c -DSYSTEM=APPLEMAC -target x86_64-apple-macos10.11
clang -bundle -o strgroup.macosx.arm64 stplugin.c strgroup.c -DSYSTEM=APPLEMAC -target arm64-apple-macos11
lipo -create -output strgroup.macosx.plugin strgroup.macosx.x86_64 strgroup.macosx.arm64

Update History:

Author:

Julian Reif
University of Illinois
jreif@illinois.edu