Practical story about Trie and Prefix Search
golang
49
algorithm
33
White

huydx viết ngày 07/01/2018

Là một người thường xuyên đọc Quora, có một điểm cá nhân tôi thấy rất ấn tượng ở quora chính là khả năng autocomplete với tốc độ ánh sáng.

Nhìn ảnh gif ở trên, chắc mọi người hiểu cái tôi định nói. Làm một chút tìm kiếm đơn giản, chúng ta có một câu trả lời ngắn gọn từ Adam, Quora CEO:

Adam nói là hệ thống của quora được tối ưu cho "Prefix matching".
Chắc ai đã từng học qua về Algorithm đều biết đến một cấu trúc dữ liệu tên là "Trie" (đọc là "trai" để phân biệt với tree đọc là "tri"). Mục đích của Trie là cây tìm kiếm, và đặc điểm của nó là:

  • Chủ yếu dành cho tìm kiếm "text"
  • Tìm kiếm prefix (tìm kiếm tiền tố?): đưa cho Trie một string, nó sẽ tìm cho bạn tất cả các kết quả mà chứa string đó như là tiền tố (Ví dụ: searchPrefix("foo") --> return ("foooo", "fooaaa"))

Ý tưởng của Trie khá đơn giản, bạn có 2 chuỗi ABCD và ABCE cần lưu trữ trên Trie, thay vì nếu sử dụng Binary Search Tree (BST) bạn cần 2 node lưu toàn bộ chuỗi, thì bạn sẽ sử dụng 5 node, tương ứng với 5 character A,B,C,D,E như bạn có thể hình dung dễ dàng qua hình dưới đây

Điểm khác biệt lớn nhất của Trie là tối ưu cho bài toán tìm kiếm Prefix, với độ phức tạp là O(m) với m là độ dài của từ cần tìm kiếm, hay nói cách khác, độ phức tạp của thao tác Search gần như là cố định, và không phụ thuộc vào số lượng từ.

Để mô tả rõ hơn, tốt hơn chúng ta nên dùng ví dụ cụ thể và thực tế. Trong phần dưới đây, tôi sẽ thử dùng Trie để làm chức năng tìm kiếm title cùng với autocomplete cho Kipalog.

Để làm thử ví dụ đó thì việc đầu tiên chúng ta cần là dữ liệu từ kipalog. Tôi là admin, nên tôi có thể vào server, select, và ghi vào json file =)). Còn nếu bạn không phải là admin, PLEASE DON'T CRAWL DATA, it hurt our server :(.

Vậy giả sử là chúng ta đã có trong tay một file dạng

[
 { "title": "fooo1" },
 { "title": "fooo2" }
]

Việc tiếp theo là mô tả Trie. Trie Node có thể được mô tả khá đơn giản như dưới đây

type TrieNode struct {
       isWord   bool
       value    string
       children map[string]*TrieNode
}

Điểm đáng chú ý ở đây là TrieNode, không giống như BST chỉ có left node và right node, có thể có nhiều Node con. Chúng ta có nhiều lựa chọn để mô tả các Node con của Trie, Array List, Linked List. Tuy nhiên các lựa chọn về List sẽ dẫn đến việc có nhiều data trống (sparse data). Do đó chúng ta còn một lựa chọn nữa là sử dụng HashMap, như trong đoạn code trên có thể thấy.
Mỗi một cặp trong children là string prefix của node tiếp theo, nối đến pointer của node đó.

Thao tác Insert một từ khoá mới vào Trie rất đơn giản

func (r *TrieNode) Insert(word string) {
       var currentNode *TrieNode
       currentNode = r
       for _, c := range word {
              var ch = string(c)
              if cn := currentNode.children[ch]; cn != nil {
                     currentNode = cn
              } else {
                     n := new(TrieNode)
                     n.value = currentNode.value + ch
                     n.children = make(map[string]*TrieNode)
                     currentNode.children[ch] = n
                     currentNode = n
              }
       }
       currentNode.isWord = true // end node
}

Thao tác tìm Prefix thì phức tạp hơn tí tẹo. Bạn cần 2 bước:

  • Step 1: Tìm ra node nào là node X chứa prefix cần tìm kiếm
  • Step 2: Từ node X duyệt trâu bò trả về tất cả các node con của node X
func (r *TrieNode) FindPrefix(prefix string, max int) []*TrieNode {
       // step 1
       currentNode := r
       ret := make([]*TrieNode, 0)
       for _, _w := range prefix {
              w := string(_w)
              if c := currentNode.children[w]; c != nil {
                     currentNode = c
              } else {
                     return ret
              }
       }

       // step 2
       queue := NewQueue(1000)
       queue.Push(currentNode)
       var found int
       for {
              if queue.count == 0 {
                     break
              }
              cn := queue.Pop()
              if cn.isWord {
                     found++
                     ret = append(ret, cn)
              }
              if found >= max {
                     return ret
              }
              for _, v := range cn.children {
                     queue.Push(v)
              }
       }
       return ret
}

Vậy là chúng ta đã có cái khung, việc tiếp theo là áp vào để làm một ứng dụng autocomplete, với dữ liệu có được từ kipalog.

Để áp dụng vào dữ liệu kipalog, là tiếng Việt, chúng ta cần thêm một chút công sức để làm tính năng đó có tính "thực tế", đó là 2 việc:

  • Chúng ta cần chức năng search hoạt động với cả không dấu và có dấu
  • Tính năng search cần hoạt động không chỉ với prefix, ví dụ bạn có title "Tìm kiếm trên ElasticSearch", vậy thì khi đánh vào từ "ElasticSearch", cũng phải tìm kiếm được.

Đi vào điểm đầu tiên, vấn đề search không dấu có thể giải quyết dễ dàng bằng việc "normalize" một chuỗi có dấu, thành một chuỗi không dấu, trước khi Insert vào Trie. Việc normalize này khá thú vị để viết một cách sáng sủa, nên mặc dù ngoài scope của bài viết, mình vẫn sẽ đưa vào đây.

Để biến một chuỗi có dấu thành không dấu, idea đơn giản nhất là giữ một cái map với key là chữ có dấu, và value là chữ không giấu. Nói cách khác

vietnameseMap = {
 "â": "a",
 "ă": "a",
....
}

Sau đó với mỗi một character ch đầu vào bạn chỉ cần biến nó về vietnameseMap[ch] tương ứng.

Tuy nhiên việc viết một cái map như trên trong code rất là mất thời gian và ... xấu. Mặc dù viết theo chiều map "có dấu" -> "không dấu" rất xấu, nhưng chiều ngược lại thì lại dễ viết hơn rất nhiều. "không dấu" -> List of "có dấu".

Vậy để giải quyết bài toán "xấu", chúng ta chỉ cần làm 2 việc:

  • Chịu khó viết một invert map cho tiếng Việt.
  • Convert invert map thành Vietnamese Map rồi thực hiện convert trên đó.

2 việc đó thể hiện ở đoạn code dưới đây:

var (
       invertVietnameseMap = map[string][]string{
              "a": {"à", "á", "ạ", "ả", "ã", "â", "ầ", "ấ", "ậ", "ẩ", "ẫ", "ă", "ằ", "ắ", "ặ", "ẳ", "ẵ"},
              "e": {"è", "é", "ẹ", "ẻ", "ẽ", "ê", "ề", "ế", "ệ", "ể", "ễ"},
   ...........
)

// normalize a string with Vietnamese and space
// into non-space non-accent mark
func normalize(in string) string {
       var out string
       var vietnameseMap = map[string]string{}
       for k, v := range invertVietnameseMap {
              for _, v2 := range v {
                     vietnameseMap[v2] = k
              }
       }

       for _, i := range in {
              if _, ok := vietnameseMap[string(i)]; ok  {
                     out += vietnameseMap[string(i)]
                     continue
              }              
              if string(i) == " " {
                     continue
              }
              out += string(i)
       }

       return out
}

Tiếp đến bài toán thứ 2: Tìm kiếm các từ mà ... không phải prefix. Điểm này có vẻ hơi đi ngược lại với mục đích của Trie là Prefix Matching. Tuy nhiên bài toán này lại có thể giải quyết một cách cực kì dễ dàng bằng cách thay vì Insert một chuỗi, thì chúng ta Insert chuỗi đó, cộng với các chuỗi con của nó.

Ví dụ bạn thay vì Insert "Tìm kiếm trên Elasticsearch", thì bạn Insert thêm "kiếm trên ElasticSearch", "trên ElasticSearch", "ElasticSearch".

Thao tác đó có thể được mô tả qua đoạn code dưới đây:

for _, post := range k {
       if post.Title != "" {
              t := post.Title
              trie.Insert(normalize(post.Title))
              for i, c := range t {
                     if string(c) == " " { // tokenize by space
                            trie.Insert(normalize(post.Title[i+1:]))
                     }
              }
       }
}

Kết hợp tất cả những building block lại chúng ta có một thứ na ná như dưới đây

Một điểm cần quan tâm ở đây là, Trie thường được lưu trên memory, không như B-Tree là một cấu trúc dữ liệu có thể dùng rất tốt trên disk. Memory thì không như disk, là tài nguyên mặc dù rẻ đi nhiều rồi nhưng vẫn rất giới hạn.

Vậy thử xem với trường hợp kipalog, gần 2500 bài viết published, thì sau khi insert theo kiểu aggresive như trên, sẽ tạo ra

Ξ prefix/main git:(master) ▶ go run main.go
indexed 16327 documents
indexed 265132 nodes

Thử xem lượng memory sử dụng dùng go pprof tool

go tool pprof http://127.0.0.1:8080/debug/pprof/heap

Chúng ta có kết quả như dưới đây:

Chúng ta có thể thấy gần 71MB được sử dụng cho trie. Tức là khoảng 400KB trung bình cho 1 node.

Thử tưởng tượng trong trường hợp quora, nếu quora có 1tr title, thì sẽ tốn tầm 30GB cho trie của toàn bộ title. Nếu trie dành cho user name mà không cần aggresive insert như title (không chỉ search prefix), thì sẽ tốn ít hơn rất nhiều.

Vậy trong trường hợp dữ liệu của bạn không đủ để fit vào memory một máy thì sao? Tôi có thử tìm kiếm với từ khoá "disk based trie" nhưng không tìm thấy nhiều tài liệu khả quan. Tôi đoán là các công ty như quora hay google sẽ thay vì dùng diskbase trie sẽ dùng sharding để scale các service autocomplete của họ. Việc sharding có thể thực hiện theo prefix (ví dụ: server1: A-E, server2: F-Z) hay qua các cách khác. Nếu bạn nào biết cách quora hay google làm thì để lại comment cho tôi nhé. Thanks :D.

Code trong bài viết tôi đặt tại https://github.com/huydx/bigg/tree/master/prefix

Các bạn có thể thoải mái sử dụng hay comment nếu có đoạn nào không hợp lý. Cám ơn trước :D .

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

huydx

116 bài viết.
940 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
148 14
Introduction (Link) là một cuộc thi ở Nhật, và cũng chỉ có riêng ở Nhật. Đây là một cuộc thi khá đặc trưng bởi sự thú vị của cách thi của nó, những...
huydx viết gần 2 năm trước
148 14
White
118 15
Happy programmer là gì nhỉ, chắc ai đọc xong title của bài post này cũng không hiểu ý mình định nói đến là gì :D. Đầu tiên với cá nhân mình thì hap...
huydx viết hơn 3 năm trước
118 15
White
95 10
(Ảnh) Mở đầu Chắc nhiều bạn đã nghe đến khái niệm oauth. Về cơ bản thì oauth là một phương thức chứng thực, mà nhờ đó một web service hay một ap...
huydx viết gần 3 năm trước
95 10
Bài viết liên quan
White
16 0
Crawl dữ liệu Crawl là một vấn đề hay gặp trong quá trình làm software. Ví dụ lấy tin tức, tin giảm giá, vé xem phim... là những dạng của crawl. Mộ...
Thach Le viết hơn 2 năm trước
16 0
White
9 2
Makefile thực hiện một số thao tác thường dùng trong Go Khi làm project Go mình thường tạo một file Makefile dạng này: Lưu ý nhớ thay thành tên m...
Huy Trần viết 2 năm trước
9 2
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
116 bài viết.
940 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!