1.9K 68 23

Đã đăng vào thg 12 27, 2016 7:09 SA 20 phút đọc

468

Data structure and indexing for dictionary used for Autocomplete and Spell-checking

Bài đăng này đã không được cập nhật trong 7 năm

Introduction

Xử lý ngôn ngữ tự nhiên là một lĩnh vực quen thuộc trong trí tuệ nhân tạo. Autocompletion và Spell-checking (hay nói chung là Autocorrection) là những vấn đề đầu tiên và xưa nhất của lĩnh vực này. Trong bài này chúng ta sẽ thử tìm hiểu một vài cấu trúc dữ liệu được sử dụng cho Autocompletion và Autocorrection;

Khi nói đến xử lý ngôn ngữ tự nhiên, ta thường nghĩ đến việc thu thập và xử lý một lượng dữ liệu ngôn ngữ khổng lồ. Khi có trong tay lượng dữ liệu lớn như vậy rồi, vấn đề đầu tiên hẳn là sắp xếp và tìm kiếm trong đống dữ liệu ấy sao cho hiệu quả. Trong bài này chúng ta sẽ chỉ tập trung vào phương pháp tìm kiếm trong đống dữ liệu ấy. Vì thế Autocompletion và Autocorrection trong bài này cũng chỉ bàn đến trong trường hợp không có ngữ cảnh.

Trie

Khi nói về một cấu trúc dữ liệu được dùng cho tìm kiếm, cấu trúc kiểu cây hẳn là thứ ta nghĩ đến đầu tiên. Cấu trúc cây đơn giản nhất là một binary tree. Trong đó mỗi node sẽ có 2 node con. Có thể mở rộng cấu trúc này thành mỗi node có 3 node con hay còn gọi là ternary tree.

Trie cũng là một cấu trúc mở rộng của binary tree có thể dùng cho dictionary indexing. Thay vì mỗi node chỉ có 2 node con thì nó có thể có nhiều hơn thế. Bao nhiêu cũng được, tùy theo số chữ cái bạn có trong bảng chữ cái. Với cùng một số node, nếu mỗi node có thể có nhiều node con hơn thì cây sẽ càng rộng hơn, tuy nhiên cũng sẽ càng ngắn hơn. Việc tìm kiếm cũng vì thế mà nhanh hơn nhiều. Đối với trie, độ phức tạp của thuật toán tìm kiếm là O(n). Tuy nhiên nó phụ thuộc vào độ dài của từ chứ không phải kích thước của từ điển.

Với cấu trúc cây thông thường, ta lưu cả một từ trong một node, sắp xếp nó theo thứ tự để tìm kiếm. Ví dụ thế này.

Đối với trie, mỗi node sẽ lưu một chữ cái. Kiểu thế này.

Vì mỗi node chỉ lưu 1 chữ cái, ta cần một flag để biết được đến node nào thì ta có một từ hoàn chỉnh.

Tìm kiếm trong trie rất đơn giản, cứ lần theo từng chữ cái trong từ cần tìm thôi.

Cấu trúc Trie rất phù hợp cho Autocomplete vì ta có thể dễ dàng biết được những chữ cái có thể xuất hiện tiếp theo của từ đang gõ. Ví dụ khi bạn gõ că thì có thể biết được các gợi ý cho bạn gồm có [căn, căng].

Autocorrection, Levenshtein distance

Bạn chắc chắn không thể không biết đến tính năng "Do you mean" của các Search Engine. Thử gõ bừa một cái gì đấy không đúng chính tả vào Google, nó sẽ gợi ý cho bạn từ gần đúng nhất. Có thể bạn cũng quen với tính năng fuzzy search của các editor phổ biến như Sublime hay Atom. Cả tính năng Autocomplete của vài IDE cũng hoạt động tương tự như fuzzy search nữa. Các tính năng đó đều có thể gọi chung là Autocorrection.

Autocorrection gồm 2 bước là

Error detection
Error correction

Trong bài này ta chỉ nói về bước thứ hai thôi. Đó là phần sửa lỗi. Cũng như phần Autocomplete, ta chỉ xét trường hợp không có ngữ cảnh thôi.

Để có thể sửa được chữ viết sai, ta cần tìm cách để so sánh sự khác biệt giữa 2 string để từ đó tìm được gợi ý gần đúng nhất. Để xác định mức độ khác biệt giữa 2 string ta dùng đến số đo gọi là edit distance. Đó là khoảng cách hay số thao tác cần thực hiện để edit một string thành string kia.

Cách tính edit distance phổ biến nhất là khoảng cách Levenshtein (Đặt theo tên tác giả - Levenshtein).

Khoảng cách Levenshtein giữa 2 string A và B là số bước ít nhất cần thực hiện để biến đổi từ A thành B. Các phép biến đổi gồm có:

Thêm một ký tự
Bớt một ký tự
Thay đổi một ký tự

Ví dụ ta có thể biến đổi "mèo" thành "éo" qua hai bước:

Xóa chữ m
Đổi chữ è thành é

Vậy khoảng cách Levenshtein giữa "mèo" và "éo" là 2

Ngoài ra còn một phép biến đổi nữa đó là

Đổi chỗ 2 ký tự

Nếu tính cả phép biến đổi trên thì khoảng cách giữa 2 string sẽ được gọi là khoảng cách Damerau-Levenshtein (Cũng đặt tên theo tác giả luôn - Damerau và Levenshtein), có thể coi là một phiên bản mở rộng của cái kia.

Bây giờ có khoảng cách giữa 2 string rồi thì ta có thể bắt đầu với một phương pháp Autocorrection đơn giản. Đơn giản hết mức có thể luôn. Đó là so sánh từ cần sửa với từng từ một trong từ điển. Từ có edit distance đến từ cần sửa gần nhất sẽ là gợi ý gần đúng nhất.

Cách này có độ phức tạp là O(n) và phụ thuộc vào độ lớn của từ điển. Đối với từ điển nhỏ thì độ phức tạp O(n) cũng không phải là quá tệ. Tuy nhiên, với ngôn ngữ tự nhiên, kích thước từ điển có thể không dưới vài chục nghìn đến vài trăm nghìn từ. Với kích thước như thế thì cách tiếp cận này chắc chắn là không ổn rồi. Để tăng tốc độ tìm kiếm, ta cần phải tìm cách index cho từ điển.

Simple index

Đầu tiên chắc chắn chúng ta không muốn phải xét từng từ một trong từ điển như trước nữa. Vì thế phải có một điều kiện nào đó để thu hẹp phạm vi tìm kiếm.

Gọi N là khoảng cách tối đa của một từ đến từ cần sửa để từ đó có thể là một gợi ý đúng. Ví dụ với N = 1 và ta có từ fèo. Từ mèo là một gợi ý cho fèo vì khoảng cách giữa chúng bằng 1 và từ eo thì không phải vì khoảng cách giữa chúng bằng 2.

Ở phần trước ta thấy thuật toán kém hiệu quả vì ta phải chạy qua một lượt toàn bộ từ điển để tính khoảng cách. Vậy nên dù cấu trúc của từ điển là gì hay được index thế nào thì hiệu năng cũng không hề khá nên được. Như kiểu table có index nhưng câu SQL query lại có một điều kiện non-sargable dẫn đến phải full scan cả table ấy.

SELECT word FROM dictionary WHERE distance(word, 'mèo') < 2

Vậy thì bây giờ phải tìm cách để query cái từ điển mà không cần xét đến điều kiện về edit distance. Mình có thể làm thế này. Với mỗi từ cần sửa, bằng các phép biến đổi, tạo ra tất cả các từ có thể trong khoảng cách cho phép. Ví dụ với từ mèo và N = 1 ta tạo ra các từ èo, xèo, o .etc Sau đó tìm các từ này trong từ điển, nếu tìm thấy thì đó được xem là một gợi ý đúng. Như ở trên thì từ xèo là một gợi ý đúng chẳng hạn. Với cách này ta có thể dùng HashSet để lưu từ điển với tốc độ tìm kiếm gần như luôn là O(1). Nghĩa là độ phức tạp của cách này không phụ thuộc vào từ điển vì tốc độ tìm kiếm luôn luôn như nhau. Tuy nhiên, nó phụ thuộc vào độ dài của từ, khoảng cách cho phép, và cả kích thước của bảng chữ cái nữa. Với một từ có độ dài kha khá thì số từ cần tạo ra cũng phải vào khoảng vài trăm. Trong vài trăm từ cần phải thử ấy thì chỉ có tầm hơn chục từ là đúng.

Cách này tuy có vẻ hơi lãng phí thời gian và công sức nhưng thực ra khá hiệu quả và đủ dùng trong nhiều trường hợp. Và phần lớn lỗi sai cũng đều nằm trong khoảng cách 1-2 thôi nên cũng không đáng ngại lắm.

BK-tree

Ở phần Trie, ta thấy thuật toán tìm kiếm của nó không phụ thuộc vào kích thước từ điển mà phụ thuộc vào độ dài của từ và nó rất hiệu quả khi dùng cho Autocompletion. Tuy nhiên nó không phù hợp cho Autocorrection vì ta thấy để tim một từ, nó phải bò dần dần trên cây, qua từng ký tự để tìm kiếm. Thế nên nó không phù hợp lắm để tìm kiếm khi lỗi sai có thể xuất hiện bất cứ chỗ nào trong từ. Nó cũng không có thông tin nào về edit distance nữa nên sẽ lại phải tính edit distance cho từng từ một. Hơn nữa nó không thể tìm được lỗi sai ở ký tự đầu tiên vì khi đó từ gợi ý đúng nằm ở một root hoàn toàn khác.

Có một kiểu cấu trúc cây khác có thể được được dùng cho Autocorrection gọi là BK-Tree (Đặt theo tên tác giả - Burkhard và Keller).

Đối với Autocompletion, ta index theo thứ tự của các kí tự vì các ký tự được nhập vào liên tiếp. Vậy thì đối với Autocompletion ta sẽ index theo edit distance vì đó là chỉ số cho biết khả năng một từ có thể là từ gợi ý đúng.

Edit distance cũng có mấy tính chất cơ bản giống như các đại lượng khoảng cách khác như

d(x, y) = d(y, x)
d(x, y) + d(y, z) = d(x, z)

Tính chất thứ hai tạm gọi là tính chất kết hợp cho dễ hiểu. Ta có hình vẽ thế này.

Ta thấy nếu có 3 string và khoảng cách tối đa N, tức là max(d1 + d2) = N thì c có thể là từ gợi ý cho a nếu d2 nằm trong khoảng d1 - N đến d1 + N.

Từ đó, ta có thể xây dựng cấu trúc BK-Tree tương tự như trên. Đầu tiên chọn một từ bất kì làm gốc cho cây. Thêm các từ khác vào các nhánh với khoảng cách tương ứng. Nếu đã có một nhánh có cùng khoảng cách rồi thì thêm nó thành nhánh con của nhánh đó.

Ví dụ ta có các từ cat, cats, chó, trắng, cát

Bắt đầu với từ cat ở root, ta thêm từ cats vào với khoảng cách là 1.

Tiếp đến là chó với khoảng cách là 2

Khoảng cách đến trắng là 5

Tiếp theo là từ cát. Khoảng cách đến cat là 1, đã có từ cats trước đó. Nên ta thêm vào node con của cats. Khoảng cách sẽ là 1 + 1 = 2 vì phải edit thông qua từ cats chứ không phải trực tiếp từ root. Ta thấy hình ở bước này giống cái hình đã miêu tả ở phần trước.

Bây giờ đã có cấu trúc dữ liệu rồi, bắt tay vào tìm kiếm thôi. Gọi N là khoảng cách tối đa. Đầu tiên ta tính khoảng cách từ từ cần sửa đến root, gọi là d. Sau đó tiếp tục leo từ root sang các cành khác. Với tính chất kết hợp, ta có thể biết được cành nào có chứa từ gợi ý cần tìm hay không. Cụ thể là chỉ cần leo sang các cành có khoảng cách nằm trong khoảng d - N và d + N thôi.

Ví dụ ta cần tìm gợi ý cho từ tát với khoảng cách tối đa là N = 1.

Khoảng cách từ tát đến cat (root) là 2

=> Leo sang các cành có khoảng cách trong khoảng từ 1 đến 3 (2 - 1 và 2 + 1)
Leo sang cats, khoảng cách là 3 => không phải
Từ cats leo tiếp sang cát, khoảng cách là 1 => đúng rồi
Hết rồi, lại về root
Leo sang chó, khoảng cách là 3 => không phải
Cành của trắng có khoảng cách là 5 nên không leo sang đấy
Hết rồi

=> Từ gợi ý đúng cho tát có thể là cát

Bạn có thể thấy là, ta luôn phải leo cho đến hết. Vậy là thuật toán tìm kiếm của nó phụ thuộc vào kích thước của từ điển. Độ phức tạp của thuật toán tìm kiếm trong BK-Tree là O(log n). Tuy nó chậm hơn cách trước nhưng mà nó chỉ cần tìm kiếm một lần thôi chứ không phải vài chục hay vài trăm lần như trước.

Utilizing symetric property

Ở phần Simple index chúng ta đã dùng đến cách biến đổi từ để tìm kiếm trong từ điển mà không phụ thuộc vào kích thước của từ điển. Tuy nhiên nó lại phải tìm kiếm nhiều lần cho một từ.

Phần trước ta có nhắc đến 1 tính chất của khoảng cách đó là

d(x, y) = d(y, x)

Tạm gọi nó là tính chất giao hoán. Nghĩa là bạn so sánh từ cần sửa với từ trong từ điển hay ngược lại thì kết quả cũng như nhau. Lần trước chúng ta đã so sánh từ cần sửa với từ trong từ điển rồi nên bây giờ hãy thử làm ngược lại. Với mỗi từ trong từ điển, tạo tất cả các biến đổi có thể trong khoảng cách cho phép. Ta sẽ có một index cho từ điển.

Ví dụ với từ mèo trong từ điển thì ta tạo các biến đổi của nó như èo, qèo .etc. Bây giờ nếu bạn viết sai từ qèo thì bạn chỉ cần tìm qèo trong index và sẽ biết được từ gợi ý cho nó là mèo.

Nghe có vẻ index này sẽ rất to vì chỉ một từ thôi mà đã có thể có vài chục đến vài trăm biến đổi rồi, bây giờ lại cả cái từ điển mấy trăm nghìn từ thì... Nhưng có rất nhiều biến đổi trùng nhau nên kích thước của nó cũng không đến nỗi khổng lồ như thế. Ví dụ èo có thể là biến đổi của cả mèo, xèo, tèo .etc. Vậy nên chỉ cần tìm một lần thôi là sẽ lấy được tất cả các từ gợi ý có thể. Tốc độ tìm kiếm vẫn không đổi và không phụ thuộc vào kích thước từ điển hay độ dài của từ.

Kích thước của index sẽ phụ thuộc vào kích thước từ điển và kích thước của bảng chữ cái. Và dù sao đi nữa thì nó cũng vẫn rất rất to và thời gian cần để tạo index chắc cũng rất lâu.

Các tính chất của khoảng cách cũng gợi ý một vài cách để làm giảm bớt kích thước của index. Vì khoảng cách giữa 2 string có thể đổi chỗ cho nhau nên từ đó có thể loại bỏ bớt các trường hợp trùng lặp.

Đầu tiên ta có thể thấy rằng hai phép biến đổi thêm và bớt ký tự thực ra có thể được xem là một. Ví dụ bạn có thể thêm chữ "t" vào cá để có cát hay bỏ chữ "t" ở cát để có cá. Vì d(cá, cát) = d(cát, cá) nên việc dùng đến cả 2 phép biến đổi là không cần thiết.

Tương tự phép thay thế 1 ký tự cũng có thể xem là một phép xóa ký tự. Ví dụ mèo và méo khi xóa ký tự ở giữa thì đều được mo. Và d(mèo, mo) = d(méo, mo) = 1.

Phép đổi chỗ 2 kí tự cũng có thể xem là 2 phép xóa. Ví dụ mèo và mòe đều có khoảng cách đến m bằng 2.

Vậy là cả 4 phép biến đổi đều có thể được rút gọn về 1 đó là phép xóa ký tự. Thế là đã giảm được một lượng lớn từ trong index rồi. Thêm nữa, vì chỉ dùng đến phép xóa nên cũng không cần lo về kích thước của bảng chữ cái nữa. Với khoảng cách tối đa là 2 thì mỗi từ có n chữ cái sẽ có 2n - 1 biến đổi. Đây có thể xem là một con số rất chấp nhận được rồi. Nhất là đối với những hệ thống lớn như search engine chẳng hạn thì kích thước không được coi trọng bằng tốc độ. Nó cũng phù hợp với cả các hệ thống có từ điển nhỏ thì vì kích thước của index nằm trong mức cho phép và thời gian tìm kiếm thì được giảm đáng kể.

Bye!

Trên đây là một vài phương pháp đơn giản để tìm kiếm hiệu quả trong từ điển để dùng cho Autocompletion và Autocorrection. Mỗi cái lại có ưu nhược điểm riêng. Chúng ta cũng mới chỉ xét trong trường hợp không có ngữ cảnh. Trong trường hợp có ngữ cảnh cụ thể thì việc phát hiện lỗi, sửa lỗi cũng phức tạp hơn nhiều.

Natural Language Processing