Autocomplete: trie ও বাংলা/Banglish suggestion

এই পাঠে যা শিখবেন

• Prefix lookup, trie ও bounded suggestions
• Unicode normalization ও curated aliases
• বাংলা/Banglish search-এর বাস্তব সীমা

সমস্যা দিয়ে শুরু

User “ডাটা” লিখে “ডেটাবেজ” খুঁজছেন, অন্যজন “database” বা “detabesh” লিখছেন। শুধু lowercase করলেই সব মিলবে না। Autocomplete দ্রুত সম্ভাব্য query/topic দেখায়; script normalization, spelling alias, ranking ও privacy requirement আলাদা ভাবে ভাবতে হয়।

সহজ করে বুঝি

Trie prefix-এর shared path অনুযায়ী characters সাজায়। Input prefix অনুসরণ করে subtree-এর bounded suggestions পাওয়া যায়। Database prefix index ছোট catalog-এ simpler alternative। Unicode normalization visually similar sequences-এর canonical form দিতে সাহায্য করে; এটি transliteration বা spelling correction নয়। Banglish ambiguous: একই Latin input একাধিক বাংলা শব্দ বোঝাতে পারে। Curated alias table ও measured query vocabulary deterministic baseline দেয়। Suggestion count ও input length ছোট রাখুন।

পরিচিত একটি উপমা

ফোনবুকে প্রথম কয়েকটি অক্ষর দিয়ে নামের অংশে যাওয়া prefix lookup। পরিচিত ডাকনাম পাশে লেখা alias। ডাকনাম মানেই official নামের নিয়মতান্ত্রিক অনুবাদ নয়; ভুল মিল হলে suggestion দেখিয়ে user-কে বেছে নিতে দেওয়া ভালো।

নকশাটি দেখুন

flowchart TD
 U[Short query prefix] --> V[Length validation and NFC normalization]
 V --> A[Optional curated alias mapping]
 A --> T[Trie or indexed prefix lookup]
 T --> R[Rank public suggestions]
 R --> B[Return at most 8 items]

Input validation ও normalization ingestion এবং query দুই path-এ একই হওয়া দরকার। Alias mapping optional এবং curated। Candidate lookup-এর পরে popularity বা relevance ranking হতে পারে, তবে unbounded subtree fetch করবেন না। User history private হলে shared global suggestions-এ সেটি accidental leak হতে পারে; public topic vocabulary নিরাপদ baseline।

PHP ও Laravel-এ প্রয়োগ

Controller/service fragment PostgreSQL-specific prefix query। PHP intl ও mbstring extensions required; search_aliases.normalized_text পূর্বে একই NFC/lowercase pipeline-এ তৈরি। request $query max৬৪ characters validated। Banglish mapping এখানে precomputed alias rows, automatic transliteration নয়। SQL wildcard escape explicit।

use Illuminate\Support\Facades\DB;

$normalized = \Normalizer::normalize(trim($query), \Normalizer::FORM_C);
if ($normalized === false) {
    abort(422, 'Invalid Unicode text');
}
$prefix = mb_strtolower($normalized, 'UTF-8');
$escaped = str_replace(['!', '%', '_'], ['!!', '!%', '!_'], $prefix);

$suggestions = DB::table('search_aliases')
    ->where('is_public', true)
    ->whereRaw("normalized_text LIKE ? ESCAPE '!'", [$escaped.'%'])
    ->orderByDesc('popularity')
    ->orderBy('id')
    ->limit(8)
    ->get(['topic_slug', 'display_text']);

return response()->json(['suggestions' => $suggestions]);

সুবিধা, সীমাবদ্ধতা ও trade-off

Trie predictable prefix traversal দেয়, কিন্তু memory ও update/rebuild management লাগে। Database prefix search existing infrastructure-এ simple; collation/operator class অনুযায়ী index support যাচাই করতে হয়। Popularity sorting prefix index-এর সঙ্গে extra cost দিতে পারে। Aliases useful কিন্তু editorial maintenance লাগে। Overaggressive normalization distinct words এক করে meaning নষ্ট করতে পারে।

সাধারণ ভুল

• Banglish-এর একটি universal one-to-one mapping আছে বলা।
• Query normalize করলেও stored aliases আলাদা form-এ রাখা।
• Prefix-এর wildcard characters escape না করে broad query করা।

আরও একটু গভীরে

বাংলা conjunct, vowel signs ও grapheme cluster visual character count থেকে bytes/codepoints আলাদা করতে পারে। UI truncation grapheme-aware হওয়া দরকার। Debounce request volume কমায়, কিন্তু backend validation/limit-এর বিকল্প নয়। Stale response arrival নতুন prefix-এর suggestions overwrite করতে পারে; client latest request identity match করবে। Top suggestions cache করলে prefix cardinality bounded ও private query history বাদ রাখুন।

মনে রাখুন

Autocomplete language normalization, lookup ও ranking-এর pipeline। NFC transliteration নয়। Small public vocabulary-এ indexed aliases দিয়ে শুরু করে corpus evidence অনুযায়ী উন্নতি করুন।

নিজে চেষ্টা করুন

বাংলা, English ও Banglish মিলিয়ে ত্রিশ alias-এর ছোট dataset বানান। Canonically equivalent Unicode, %, _, empty input এবং ambiguous spelling পরীক্ষা করুন। Expected suggestion order ও no-private-data rule লিখুন।

নিজের বোঝা যাচাই করুন

1. Trie কী সাহায্য করে?

Shared prefix path ধরে candidate subtree-এ যেতে দেয়। Bounded top results ও update strategy তবু design করতে হয়।

2. NFC Banglish বদলায়?

না। Unicode canonical normalization করে; transliteration বা বাংলা spelling correction আলাদা কাজ।

3. SQL binding wildcard থামায়?

Injection syntax আটকায়, কিন্তু LIKE-এর %/_ অর্থ থাকে। Literal prefix চাইলে explicit escape করতে হবে।

4. Index use নিশ্চিত?

না। Collation, operator class, prefix ও sorting অনুযায়ী plan বদলায়। Target PostgreSQL configuration-এ EXPLAIN করুন।

5. Popularity data private হতে পারে?

হ্যাঁ। Individual history বা sensitive query global suggestion-এ leak হতে পারে। Public vocabulary ও aggregated approved signals ব্যবহার করুন।

আরও পড়ুন

• Unicode normalization standard
• PHP Normalizer
• PostgreSQL pattern matching