3
\$\begingroup\$

I have about 10k categories, represented by their name. I need to find a match for a category input among this list of 10k categories.

This is done through an API, and by batches: the endpoint will receive about 500 categories to match.

The process is:

-> Receive request with all categories to match

-> For each word, run fuzzy matching algorithm with the 10k categories.

-> Return match

I'm using Fuzzy Wuzzy for the algorithm, and Django for the API. Basically, this would look like this:

response = {}

for category in categories_received:
  for master_category in master_categories:
    if fuzz.ratio(category, master_category) > 95:
       response[category] = master_category

This is terribly inefficient, but I couldn't find another way to do it. I control both sides: the way data is sent to the API, and of course the way it is compared to the existing categories.

Any idea/input on how to make this code more efficient would be much appreciated

\$\endgroup\$
3
\$\begingroup\$

Fuzzy-wuzzy is poorly optimized for that kind of use.

What you can do is use fuzzy-wuzzy functions to construct your own ratio function.

The biggest boost you will get if you will use any caching for master_category tokenization. If you are on python3 you can use functions.lru_cache and if memory allows you I would suggest making it the size of len(master_categories)+1.

This is a small change and it will increase memory usage a lot, but as a result speed of calculation will also be boosted a lot.

also since you need just 1 master_category per each category, just break your loop as soon as you find one.

for category in categories_received:
  for master_category in master_categories:
    if fuzz.ratio(category, master_category) > 95:
       response[category] = master_category
       break
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.