Blog: How is the Autocomplete feature implemented in real life?

[HarshCasper]

Background

Do you ever wonder how some Search Engines or Commercial Portals are able to match the entered letters to whatever words you are trying to type almost instinctively?

Are they simply attempting to match the entered letters in the Database or are using some "Intelligence" to find that out?

Turns out, that this feature, which is called "Autocomplete", can be implemented via standard Data Structures. One of the most naive methods is Linear Search and Binary Search, but they simply get inefficient with lack of Typo-Tolerance.

Other efficient Data Structures include TRIE and Ternary Search Tree but the real winner comes out to be Burkhard Keller Trees, which can optimize your Autocomplete Feature up to 40 times faster

But how does it manages to do so? BK-Trees rests its concepts on the Levenshtein distance which is a measure of minimum operations needed to translate one string to other. This makes it efficient for Nearest Neighbour Search with a Logarithmic Time Complexity and also boosts performance for Fuzzy Search.

Description

Write a blog of 1000-1500 words detailing all the methods that can be utilized for this purpose. Remember you can write or pic your own code from NeoAlgo and make PRs to the upstream for the upstream.

The Blog should:

• Be conversational in nature rather than instructional (like articles)
• Be check by Grammarly and a Google Doc shared in the PR for review over them
• Uses active diagrams and infographics to explain the idea
• Unnecessary jargons are not needed and use as plain English as possible
• Add your metadata properly to the same

[shonali2600]

I would like to work on this, It's a new thing I came across. Please assign it to me.

[HarshCasper]

I would like to work on this, It's a new thing I came across. Please assign it to me.

Good Luck with that!

No need to go hard on technical jargons. Remember you are not writing articles/documentation, but a blog. Consider as if you are explaining about all this over a Coffee chat to your friend. And be sure you do your prior research on the topic. Best of Luck !

[shonali2600]

Thanks, I'll keep this in my mind.