String Matching
Name matching is one case of a broader need: deciding whether two strings are close, or finding a pattern inside a lot of text fast. The page starts with fuzzy matching tools built on edit distance and sequence comparison, then moves to regex engines, their speed, and the keyword-extraction alternatives that skip regex altogether.
The same notes are in Name Matching and SIMILARITY.
Tools
The simplest notion of "close" is edit distance. Fuzzy string matching library - fuzzywuzzy - using edit-distance is Susan Li's NLP for fuzzy string matching with Python. The standard library has its own tool: Difflib provides classes and functions for comparing sequences, mostly sequences of text lines, and difflib-2 is the Python Module of the Week walkthrough of comparing sequences with it.
The figure is from Susan Li's fuzzy wuzzy string matching post on medium.com.
REGEX
Fuzzy matching compares two strings; regex searches for a pattern, and at scale the question becomes which engine is fast enough. Why re is slow is "Regular Expression Matching Can Be Simple And Fast", the explanation of why backtracking engines lose. The numbers come next: Benchmark is a simple regex benchmark of different programming languages, comparisons is the Rust Leipzig Users' comparison of regex engines, more is the Stack Overflow question on regular expression library benchmarks beyond the browser, and many more asks for an up-to-date benchmark of re2, pcre with jit, and other contemporary libraries.
Two practical regex notes sit beside the benchmarks. Split on separator but keep the separator is Per's Python post on splitting a file's lines while keeping the separator. Semantic versioning is a pattern on RegExr, the online tool to learn, build, and test regular expressions.
When the standard engine is too slow, two libraries are the usual replacements:
Hyperscan — Hyperscan (paper) is a high-performance multiple regex matching library. It follows the regular expression syntax of the commonly-used libpcre library, but is a standalone library with its own C API. The paper frames regex matching as the performance bottleneck of network security applications, since every byte of packet payload has to be scanned.
The comparison above puts those libraries side by side. Sometimes the pattern is really a token rule or a keyword list, and then regex is the wrong tool. Spacy’s Matcher & “regex” is spaCy's rule-based matching, which finds phrases and tokens and matches entities. Flashtext— This module can be used to replace keywords in sentences or extract keywords from sentences. It is based on the FlashText algorithm, described in the paper "Replace or Retrieve Keywords In Documents at Scale".
The fuzzywuzzy post from the tools section is also linked at its older address: Fuzzy string matching library - fuzzywuzzy - using edit-distance https://towardsdatascience.com/natural-language-processing-for-fuzzy-string-matching-with-python-6632b7824c49
Deprecated links
These links and images no longer work. The original wording is kept here. A same-resource copy, when one was checked, is used above.
Re2 This address no longer opens: https://github.com/google/re2/tree/abseil/python
Last updated
Was this helpful?