search

OlivierBinette / StringCompare

Efficient String Comparison Functions and Fuzzy String Matching
https://olivierbinette.github.io/StringCompare/
17 stars 2 forks source link

Address matching case study #9

Open OlivierBinette opened 2 years ago

OlivierBinette commented 2 years ago

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

OlivierBinette commented 2 years ago

Lucene could be a source of inspiration for search features: https://lucene.apache.org/core/2_9_4/queryparsersyntax.html#Fuzzy%20Searches