stringpairfinder 1.0.0

Package designed to match strings by similarity

StringPairFinder

StringPairFinder is a Python package designed to simplify the process of finding similarities between strings.

Evaluation

Evaluation on a dataset of 1000 observations (see notebooks/1_evaluation.ipynb) :

• FuzzyWuzzy algorithm : 85.2 % of success rate
• StringPairFinder algorithm : 94.0 % of success rate

Installation

pip install stringpairfinder

Usage

Computing String Similarity

import stringpairfinder as spf

spf.get_similarity("Munich", "Munchen")

>> 0.23809523809523808

Finding the Nearest String

spf.get_nearest_string(
    string="Naples",
    string_list=["Munchen", "Napoli", "Warszawa"]
    )

>> 'Napoli'

Mapping Strings to Their Nearest Counterparts

spf.match_strings(
    source_strings=["Naples", "Munich", "Warsaw"],
    target_strings=["Munchen", "Napoli", "Warszawa"]
    )

>> {'Naples': 'Napoli',
    'Munich': 'Munchen',
    'Warsaw': 'Warszawa'}

Examples of use

• Encoding variables in datasets before a merge: It is common to want to merge datasets from different sources, but to encounter difficulties when the variables used to identify records are not coded in the same way. Using StringPairFinder to link the variables before the merge can facilitate this process.

• Detection of duplicates in databases: StringPairFinder can be used to detect duplicates in databases by matching and recoding strings that are mistakenly encoded differently.

• Searching for match between names and email addresses: StringPairFinder can be used to link names and email addresses in databases. This can be useful for contact management or mass emailing.

• Searching for product similarity in online catalogs: StringPairFinder can be used to link similar products in online catalogs. This can be used for tasks such as product recommendation or similar product search.

What is the algorithm ?

The similarity search between two strings consists of a matrix comparison of each character in those strings. Let"s assume we want to compare the strings "Munich" and "Bayern Munich".

1. The first step is to construct a table $T$ containing the first string in the column and the second in the row. The value of a cell is 1 if the character in the row is the same as the one in the column, and 0 otherwise.

2. The second step aims at highlighting the fact that several characters correspond consecutively. Thus, for each row $i$ and column $j$, if cell $T[i-1, j-1] > 0$, then $T[i, j]$ is twice the value of $T[i-1, j-1]$.

3. The third step is simply to calculate the similarity score, equal to the sum of all the cells in the $T$ divided by the size of the table.

$$ Score = \frac{\sum_{i=1}^{n_{row}}\sum_{j=1}^{n_{col}} T_{i,j}}{n_{row} * n_{col}} = \frac{1+1+2+4+8+16+32}{78} \approx 0.82 $$

In this example, we obtain a similarity score of 64.

To connect the peers two by two, StringPairFinder calculates the similarity score of all (list1, list2) combinations and returns the association between each character string in list 1 with the character string in list 2 with the highest similarity score.