Brief #03 · Backend
Search Autocomplete Service
Medium⏱ 10-14 ঘণ্টাশীঘ্রই
দশ লাখ product এর নামের ওপর autocomplete: ২০ ms এর কম সময়ে suggestion, ভালো ranking, আর বানান ভুল ক্ষমা করে।
Outline free · tracking সহ বানাতে Pro লাগবে
SBriefTeam এর পক্ষ থেকে
আমাদের search box প্রতিটা key চাপায় একটা LIKE '%term%' query চালায়, আর প্রতি সন্ধ্যায় database হাঁপিয়ে ওঠে। User 'samsng' লিখলে কিছুই পায় না। এমন একটা autocomplete service বানাও, যেটা মানুষের লেখার গতিতে উত্তর দেয় আর তবুও তারা যা বোঝাতে চেয়েছে সেটা খুঁজে পায়।
যা বানাবে
- 1দশ লাখ নাম (বানিয়ে নাও বা public dataset থেকে) memory তে একটা trie তে তোলো।
- 2একটা prefix এর জন্য জনপ্রিয়তা অনুযায়ী সেরা ১০টা completion ফেরত দাও।
- 3প্রতিটা node এ top-k জমিয়ে রাখো, যাতে query কখনো পুরো subtree না ঘোরে।
- 4প্রতিটা query ধীর না করে typo tolerance (edit distance 1) যোগ করো।
- 5একটা ছোট frontend, debounce করা input সহ, যেটা API ডাকে।
ধাপে ধাপে walkthrough
Walkthrough শীঘ্রই আসছে
এই project এর ধাপে ধাপে walkthrough, প্রতিটা ধাপে আসল output সহ, এখনো লেখা হচ্ছে। ততক্ষণ brief পড়ে নিজে চেষ্টা করতে পারো; walkthrough তৈরি হলে tracking চালু হবে।
শেষ হবে যখন
- দশ লাখ entry তে prefix query এর p95 ২০ ms এর নিচে।
- 'samsng' লিখলে Samsung এর product suggest করে।
- কতটা memory লাগছে, মেপে লিখে রাখা।
- Unit test এ খালি prefix, unicode আর অনেক long input ধরা আছে।
আরো এগোতে চাইলে
- Downtime ছাড়াই নতুন data থেকে index আবার বানাও।
- বাংলা নাম সমর্থন করো, আর কী কী বদলাতে হলো তা ব্যাখ্যা করো।