Implement the Jaccard similarity function which, given two strings s and t, and given a Tokenizer instance tokens, returns the jaccard similarity between tokens(s) and tokens(t).

Here a tokenizer is a function which transforms a string into a set (or a multiset). The Jaccard similarity between two sets A and B is defined as |A and B|/|A or B|

Edit-based distances can have their different operations (transposition, substitution, deletion, or insertion) be weighted to allow more flexibility. It would be nice to provide this functionality to the package.

We need to keep in mind that users might want to be able to learn these weights from data. So tuning these parameters should bring as little computational overhead as possible.

It would be best to wait working on this issue until we have a working case study for which we want to implement string distance learning.

dev branch is currently used for active development and can break often. Need to make a new release and instruct users to install from that branch.

https://en.wikipedia.org/wiki/Levenshtein_automaton

The check for null case should be done at the token bag level rather than the string level:

I would recommend refactoring jaccard.py as follows:

1. Have the jacard() function take two token sets as arguments and compute their jaccard similarity (overlap percentage). Checking for empty token bags should be done here.
2. Have the compare() function deal with the tokenization and anything else (e.g. transforming the distance to a similarity).

Create an examples folder structured as follows:

examples/
├─ 1-getting-started.ipynb
├─ 2-interesting-use-case.ipynb
└─ ...

Each python notebook should be numbered and contain a working example of StringCompare's features and usage.

The first notebook, 1-getting-started.ipynb, should walk the user through the installation of the package, the logical structure of the package, and simple examples (kind of like the package README does, but in a bit more detail).

Following notebooks should introduce more advanced features and use cases. For instance, we could cover how to learn the parameters of string comparison functions from data, how to do blocking to speed-up finding close matches, or how to feed string comparisons to a machine learning algorithm for fuzzy string matching. Any working example would be suitable here.

Ideas for specific user examples can be proposed by opening separate Github Issues.

The goal of user examples

There are three main goals to providing user examples in this way:

1. It provides users with a guide to working with the package and working code as a starting point.
2. It provides us (the developers) with motivating use cases and a playground on which to experiment with new functionality.
3. It provides us with a way to test end-to-end workflows involving the use of StringCompare. Formal tests are as simple as using pytest and the testbook package to automatically check that all notebooks run without error.

Currently, every list passed to a StringCompare function is copied before operations are applied. This is due to the use of stl containers as input types and implicit conversions done by pybind11 (see https://pybind11.readthedocs.io/en/stable/advanced/cast/stl.html).

It would be best to have StringCompare vectorized functions take buffer protocol objects as arguments, to avoid any copying and improve efficiency.

Add a user example (see #2) which provides a fair and exhaustive benchmark of StringCompare against other string comparison libraries.

Currently, the package uses the C++ code by default and leaves the use of the pure Python implementation to the discretion of the user.

It might be better to more clearly separate the Python and C++ implementation. Some ideas:

• provide separate "strincompare" and "cstringcompare" packages,
• at package load time, try using C++ implementation and fall back on the pure Python implementation if loading fails.

There are also some issues with having all C++ code in headers. Compilation is still very quick but I'm not sure how it will scale as the package grows. It would also be nice to be able to provide the C++ code as a C++ library which is independent of the Python implementation...

We'll see what refactoring is needed as the package grows.

Hamming distance is defined here: https://en.wikipedia.org/wiki/Hamming_distance

Add doctests throughout.

Create a class to tokenize strings.

It should be able to tokenize strings into both sets and multisets.

Make installation process robust to C++ symbol not found errors and to the error where the stringcompare.distance._distance module is not found.

Implement min-hashing as an approximation to the Jaccard similarity.

Create a user example (see #2) which shows how StringCompare can be used to match business names.

That is, suppose we have a long list L of business names. Given another business name provided by a user, we want to be able to find the name in L which most closely matches it.

We can address this problem in a few steps:

1. Identify an open dataset to work with for the case study.
2. Identify a string comparison function which works best to match similar business names.
3. Implement the brute force solution which computes all distances and returns the closest match.
4. Try to speed up computation using indexing/blocking.
5. Try to speed up computation using B-trees.
6. Try to find quick approximate solutions using locality sensitive hashing.

Steps 1-3 are the most important. Steps 4-6 can be explored if they seem interesting.

References

• https://corpus.ulaval.ca/jspui/bitstream/20.500.11794/67747/1/36572.pdf

Describe the bug

When we try to import packages in Jaccard, we get "Import Error: attempted relative import with no known parent package". We specifically have issues with
"from .comparator import StringComparator
from ..preprocessing.tokenizer import Tokenizer, WhitespaceTokenizer"
and the dots before comparator and preprocessing.

When we remove the dots the code runs but with the dots there the code doesn't run.

Here is our code so far:

from .comparator import StringComparator
from ..preprocessing tokenizer import Tokenizer, WhitespaceTokenizer
`
def jaccard(s, t, token):
s_token = token(s)
t_token = token(t)

intersection = [value for value in s_token if value in t_token]
len_intersection = len(intersection)
return len_intersection / (len(s_token) + len(t_token) - len_intersection)

class Jaccard(StringComparator):
def init(self, similarity = True, tokenizer = WhitespaceTokenizer()):
self.similarity = similarity
self.tokenizer = tokenizer

def compare(self, s, t):
    if self.similarity:
        return jaccard(s, t, self.tokenizer)
    else:
        return 1 - jaccard(s, t, self.tokenizer)

'
We think that the issue has to do with relative paths somehow, as .comparator gives us the error above, but comparator gives us no errors. We could not get ..preprocessing to import unless we brought tokenizer into our local directory and imported that file directly, but obviously this doesn't solve the problem. We tried on both mac and linux systems using PyCharm and a cloud-based service called repl.it.