Membuat Search Auto Complete dengan Struktur Data Trie
Saat kita lagi searching di Google atau berbelanja di online shop katakanlah di tokopedia, blibli, shopee, dll. ketika kita mulai mengetik di kotak pencarian, muncul satu atau lebih hasil pencarian yang relevan dengan kata yang sedang kita ketik. Nah, fitur ini dikenal dengan autocomplete, typeahead, search-as-you-type, atau incremental search. wuu banyak padanan nye ye.
Gambar diatas menunjukkan bagaimana pencarian di Google menampilkan daftar hasil autocomplete ketika kita mengetikkan kata “belajar” di box pencarian.
Autocomplete dalam pencarian adalah fitur yang sangat penting dan digunakan dalam banyak produk. Nah pada artikel ini kita akan belajar bagaimana membuat autocomplete sederhana dengan memanfaatkan struktur data Trie.
Untuk membuat sistem autocomplete yang lebih kompleks, seperti punya nya google atau online shop kayak blibli, mereka pasti mempunyai resep lain dan teknik khusus untuk membangunnya mengingat jumlah data yang mereka miliki sangat besar dan memiliki requirements spesifik yang membuat kompleksitasnya meningkat.
Untuk sekarang, kita hanya akan membuat autocomplete yang sederhana saja. seenggaknya bisa bilang woww it’s works using trie 😎
Apa itu Trie?
Trie adalah struktur data mirip Tree (pohon) yang dapat menyimpan rangkaian karakter secara efisien. Nama Trie berasal dari kata “retrieval”, yang menunjukkan bahwa ia dirancang untuk operasi pengambilan string. Ide utama dari Trie meliputi hal-hal berikut:
- Trie adalah struktur data mirip pohon.
- Akar Trie mewakili sebuah string kosong.
- Setiap node menyimpan sebuah karakter dan memiliki 26 anak, masing-masing mewakili satu karakter yang mungkin.
- Setiap node pohon mewakili satu kata atau rangkaian karakter awalan.
Gambar dibawah menunjukkan contoh Trie dengan query pencarian “Cinta”, “Cendol”, dan “Die”. query pencarian ditandai dengan soft yellow background color.
Basic Struktur data Trie menyimpan karakter-karakter dalam node-node. Untuk mendukung pengurutan berdasarkan frekuensi, informasi frekuensi perlu dimasukkan ke dalam node-node tersebut. Misalkan kita memiliki tabel frekuensi berikut.
Kata — Frekuensi
Cinta — 100
Cendol — 50
Die — 10
Jadinya, Trie akan terlihat seperti ini:
How it works using Trie?
Sebelum membahas algoritmanya, mari kita definisikan beberapa istilah terlebih dahulu.
p: panjang dari sebuah awalan (prefix)
n: total jumlah node dalam trie
c: jumlah anak dari suatu node tertentu
Langkah-langkah untuk mendapatkan k query yang paling sering dicari adalah sebagai berikut:
- Temukan node awalan (prefix). Kompleksitas waktu: O(p).
- Traverse di bawah pohon dari node awalan untuk mendapatkan semua anak yang valid. Sebuah anak dianggap valid jika bisa membentuk string query yang valid. Kompleksitas waktu: O(c).
- Urutkan anak-anak yang valid dan ambil k teratas. Kompleksitas waktu: O(c log c).
Misalnya kita mengetikkan “c” pada kotak pencarian. Algoritma tersebut bekerja sebagai berikut:
Langkah 1: Temukan node awalan “c”.
Langkah 2: traverse di bawah pohon untuk mendapatkan semua anak yang valid. Dalam kasus ini, node [cinta: 100], [cendol: 50] adalah valid.
Langkah 3: Urutkan anak-anak yang valid dan ambil 2 teratas. [cinta: 100] dan [cendol: 50] adalah 2 pertanyaan teratas dengan awalan “c”.
Kompleksitas waktu dari algoritma ini adalah hasil penjumlahan waktu yang dihabiskan pada setiap langkah yang disebutkan di atas:
O(p) + O(c) + O(c log c)
Meskipun algoritma di atas cukup sederhana, tetapi ia bisa menjadi terlalu lambat karena kita harus menelusuri seluruh trie untuk mendapatkan k hasil teratas dalam skenario terburuk. Berikut adalah dua optimasi yang dapat dilakukan:
- Batasi panjang maksimum sebuah awalan (prefix).
- Simpan hasil pencarian teratas di setiap node dalam cache.
Tapi kita tidak akan membahas optimasi ini lebih lanjut karena kita hanya akan membuat autocomplete yang sederhana saja. hehe 😁
Implementasi Search Autocomplete dengan Trie
Nah nah, part yang paling ditunggu-tunggu nih. Kita akan bikin search auto complete sederhana dengan memanfaatkan struktur data trie. Kita akan gunakan bahasa Go 😎
type TrieNode struct {
children map[rune]*TrieNode
isEndOfWord bool
frequency int
prefix string
}
type AutocompleteSystem struct {
root *TrieNode
}
func NewTrieNode() *TrieNode {
return &TrieNode{
children: make(map[rune]*TrieNode),
isEndOfWord: false,
frequency: 0,
prefix: "",
}
}
func NewAutocompleteSystem() *AutocompleteSystem {
return &AutocompleteSystem{
root: NewTrieNode(),
}
}Intinya code snippet diatas digunakan untuk membuat dan menginisialisasi node Trie baru. Node Trie memiliki atribut children untuk menyimpan anak-anaknya (children), isEndOfWord untuk menandai akhir kata, frequency untuk menyimpan frekuensi kata, dan prefix untuk menyimpan prefix dari data sebelumnya.
func (a *AutocompleteSystem) Insert(word string, frequency int) {
current := a.root
prefix := ""
for _, ch := range word {
prefix += string(ch)
node, found := current.children[ch]
if !found {
node = NewTrieNode()
node.prefix = prefix
current.children[ch] = node
}
current = node
}
current.isEndOfWord = true
current.frequency += frequency
}Fungsi Insert digunakan untuk memasukkan kata ke dalam Trie. Kata yang dimasukkan akan dipecah menjadi karakter-karakter individual, dan setiap karakter akan menjadi anak dari node sebelumnya. Akhir kata ditandai dengan mengatur atribut isEndOfWord pada node terakhir menjadi true. Frekuensi kata juga disimpan dalam atribut frequency pada node terakhir. dan prefix akan diisi dengan akumulasi/append dari kata-kata sebelumnya.
func (a *AutocompleteSystem) Search(prefix string) []*TrieNode {
result := make([]*TrieNode, 0)
current := a.root
for _, ch := range prefix {
node, found := current.children[ch]
if !found {
return result
}
current = node
}
a.dfs(current, &result)
return result
}Fungsi Search digunakan untuk mencari kata-kata yang cocok dengan sebuah prefix dalam Trie. Fungsi ini menerima prefix sebagai argumen dan mencari node yang sesuai dengan prefix tersebut dalam Trie. Kemudian, fungsi dfs (depth-first search) dipanggil untuk mengumpulkan semua node akhir (node yang menandai akhir kata) yang memiliki prefix yang sesuai.
func (a *AutocompleteSystem) dfs(node *TrieNode, result *[]*TrieNode) {
if node.isEndOfWord {
*result = append(*result, node)
}
for _, child := range node.children {
a.dfs(child, result)
}
}Fungsi diatas adalah implementasi rekursif dari depth-first search (DFS) untuk mencari semua node akhir yang berasal dari suatu node Trie. Setiap node akhir yang ditemukan akan ditambahkan ke dalam slice result.
func sortResults(results []*TrieNode) {
sort.Slice(results, func(i, j int) bool {
return results[i].frequency > results[j].frequency
})
}Fungsi ini digunakan untuk mengurutkan hasil pencarian berdasarkan frekuensi secara menurun. Fungsi ini menggunakan algoritma pengurutan seperti quicksort atau mergesort, di mana dalam contoh ini, pengurutan dilakukan dengan menggunakan algoritma quicksort.
func AutocompleteHandler(w http.ResponseWriter, r *http.Request) {
prefix := r.URL.Query().Get("prefix")
if prefix == "" {
w.WriteHeader(http.StatusBadRequest)
return
}
// Menerapkan logika autocomplete
results := autocomplete.Search(strings.ToLower(prefix))
// Mengurutkan hasil berdasarkan frekuensi secara descending
sortResults(results)
// Mengambil hanya prefix dari kata-kata yang cocok
suggestions := make([]string, len(results))
for i, node := range results {
suggestions[i] = node.prefix
}
// Mengembalikan hasil dalam format JSON
response := map[string]interface{}{
"suggestions": suggestions,
}
jsonResponse, err := json.Marshal(response)
if err != nil {
w.WriteHeader(http.StatusInternalServerError)
return
}
w.Header().Set("Content-Type", "application/json")
w.WriteHeader(http.StatusOK)
w.Write(jsonResponse)
}Fungsi diatas adalah handler untuk endpoint /autocomplete. Fungsi ini menerima permintaan autocomplete dengan mengambil prefix dari query string. Kemudian, fungsi Search digunakan untuk mencari kata-kata yang cocok dengan prefix tersebut dalam Trie. Hasil pencarian diurutkan berdasarkan frekuensi dan dikirim sebagai respons dalam format JSON.
func SearchHandler(w http.ResponseWriter, r *http.Request) {
tmpl := template.Must(template.ParseFiles("index.html"))
err := tmpl.Execute(w, nil)
if err != nil {
log.Println(err)
w.WriteHeader(http.StatusInternalServerError)
return
}
}Fungsi diatas adalah handler untuk endpoint /search. Fungsi ini menampilkan halaman pencarian dengan menggunakan template HTML.
func main() {
autocomplete = NewAutocompleteSystem()
//Buka file CSV keywords sebagai data awal untuk mengisi Trie
file, err := os.Open("keywords.csv")
if err != nil {
log.Fatal(err)
}
defer file.Close()
reader := csv.NewReader(file)
lines, err := reader.ReadAll()
if err != nil {
log.Fatal(err)
}
for i := 1; i < len(lines); i++ {
row := lines[i]
if len(row) >= 2 {
kataKunci := row[0]
frekuensi, err := strconv.Atoi(row[1])
if err != nil {
log.Printf("Error parsing frekuensi: %v", err)
continue
}
// Masukkan keywords ke Trie dengan frekuensi
autocomplete.Insert(kataKunci, frekuensi)
}
}
http.HandleFunc("/autocomplete", AutocompleteHandler)
http.HandleFunc("/search", SearchHandler)
log.Println("Server is running on port 8080")
log.Fatal(http.ListenAndServe(":8080", nil))
}Nah ini merupakan main function yang melakukan inisialisasi sistem Autocomplete, mengisi data contoh ke dalam Trie, mengatur endpoint HTTP untuk permintaan autocomplete dan halaman pencarian, dan menjalankan server HTTP.
Oh ya, ketika user memilih salah satu saran ataupun memasukkan keyword baru, kita harus menjalankan trigger function insert supaya data di trie di update (menambah frequency ataupun membuat node yang baru). Tapi kita tidak implementasikan itu sekarang. but, harusnya itu cukup mudah di implement. PR buat temen2 ya hehe
Yep lanjut, dibawah dalah file keywords.csv sbg data awal kita untuk mengisi trie
kata_kunci,frekuensi
cara melihat hantu,200
apple,10
application,5
apply,8
banana,10
tutorial,12
tutor,7
cara mengganti password,1000
resep masakan sederhana,850
belajar bahasa Inggris,750
tips memasak sehat,700
tutorial makeup natural,650
sepeda lipat,600
film action terbaik,550
.... Dan yg terakhir kodingan untuk tampilan halaman searching kita
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Search Autocomplete</title>
<script src="https://cdn.tailwindcss.com"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/axios/1.4.0/axios.min.js"
integrity="sha512-uMtXmF28A2Ab/JJO2t/vYhlaa/3ahUOgj1Zf27M5rOo8/+fcTUVH0/E0ll68njmjrLqOBjXM3V9NiPFL5ywWPQ=="
crossorigin="anonymous"
referrerpolicy="no-referrer"></script>
<style>
.autocomplete {
position: relative;
display: inline-block;
}
.autocomplete input {
width: 400px;
padding: 10px;
border-radius: 8px;
border: 1px solid #e4e7eb;
box-shadow: 0 2px 4px rgba(0, 0, 0, 0.1);
}
.autocomplete ul {
position: absolute;
width: 100%;
margin-top: 8px;
padding: 0;
list-style: none;
background-color: #fff;
border-radius: 8px;
border: 1px solid #e4e7eb;
box-shadow: 0 2px 4px rgba(0, 0, 0, 0.1);
z-index: 1;
}
.autocomplete li {
padding: 10px;
cursor: pointer;
}
.autocomplete li strong {
font-weight: bold;
}
.autocomplete li:hover {
background-color: #f5f7fa;
}
</style>
</head>
<body class="bg-gray-100">
<div class="flex mt-12 justify-center h-screen">
<div class="autocomplete">
<input id="searchInput" type="text" placeholder="Search" autocomplete="off" class="bg-white">
<ul id="suggestionList"></ul>
</div>
</div>
<script>
const searchInput = document.getElementById('searchInput');
const suggestionList = document.getElementById('suggestionList');
searchInput.addEventListener('input', function() {
const prefix = searchInput.value;
if (prefix.length > 0) {
axios.get('/autocomplete', { params: { prefix } })
.then(function(response) {
const suggestions = response.data.suggestions;
let html = '';
for (const suggestion of suggestions) {
const suggestionHtml = suggestion.replace(
new RegExp(`(${prefix})`, 'gi'),
'<strong>$1</strong>'
);
html += `<li>${suggestionHtml}</li>`;
}
suggestionList.innerHTML = html;
suggestionList.style.display = 'block';
})
.catch(function(error) {
console.error(error);
});
} else {
suggestionList.innerHTML = '';
suggestionList.style.display = 'none';
}
});
suggestionList.addEventListener('click', function(event) {
const selectedSuggestion = event.target.innerText;
searchInput.value = selectedSuggestion;
suggestionList.innerHTML = '';
suggestionList.style.display = 'none';
});
</script>
</body>
</html>Mari kita lihat hasilnya
Okeyy… tadi kita telah kenalan dikit tentang struktur data Trie, termasuk prinsip dasar dan representasi grafis nya. Selanjutnya, kemudian implementasi Trie untuk membuat search auto complete dengan menggunakna Bahasa Go.
Selamat mencoba dan semoga bermanfaat. Terima kasih 😊