How Fuzzy Text Search Works

In this tutorial, we explore how to make fuzzy autocomplete in Python. First using libraries like `fuzzywuzzy`, then from scratch using Levenshtein distance and the Wagner-Fischer algorithm. Finally, we look at how we can get C/C++ level of performance with Python using vectorization and NumPy. For production use, definitely prefer one of the libraries mentioned at the beginning :) If you're interested in text processing, dynamic programming, and making Python programs run fast, I hope you'll find the video useful.

Let me know in the comments what tutorial you'd like to see next!

🔴 SOURCE CODE 👇

◼️ TIMESTAMPS 🕑
00:00 Intro
00:41 Example: Fuzzy autocomplete with "rapidfuzz"
01:27 Libraries for fuzzy matching in Python
03:01 String similarity measures
04:07 Hamming distance explained
05:17 Hamming distance, implementation
05:47 Levenshtein distance explained
07:32 Levenshtein distance, implementation
08:26 Wagner-Fischer algorithm explained
13:40 Wagner-Fischer performance in Python
14:47 How to optimize it? Cython/Numba vs. vectorization
15:13 Vectorization of Wagner-Fischer algorithm
17:14 Example: Fuzzy autocomplete with vectorized Wagner-Fischer
17:53 Comparison with C implementation
18:20 Outro

◼️ REFERENCES 📚

◼️ TOPICS 🎓
#ProgrammingTutorial #TextSearch #BigPython #Python

◼️ CREDITS 🙏

[jsp]

I found this video right when i need and i have been getting back to it. Would be awesome to have more tutorials, really high quality here!

[SnekCato]

I cannot wait to be able to how to do this, i'm still a beginner but i love how you explain such cool topics.

[mohammadsheikh]

Came across this right when I needed it, thanks for the video. Would love to see a video on the Finite State Machines as well.

[RyanSteele]

Thank you for this. Really good explanation!

[robimez]

very interesting, love how you explain things, subbed.

[cvbrxdi]

Pretty nice!! Good one you and everything is explained well and nice, thanks very much!

[coxpbco]

there is any two sentence meaning nlp or algorithm is there? or not is there means can you tell which algo or nlp ?how that work

[lammelmiklos]

Very nice tutorial! I was wondering: what dev environment do you use here in the video? It seem to be some kind of Jupyter Notebook with some nice cusomization... How did you customize?

[thanhhuy]

nice video, i see O(n^2), and
i have 1 question, if input text long 500 and has 1e7 item, how much is the time run?

[andreaventurelli]

You talk about the possibility of change the weight of the (add, delete, replace) how can it is achievable?