Tự động sửa lỗi chính tả tiếng Việt

Tự động phát hiện và sửa lỗi chính tả (Auto Correction) là một trong những bài toán cơ bản nhất trong xử lý ngôn ngữ tự nhiên. Tính năng này có trong các ứng dụng soạn thảo văn bản, nhập liệu, nhận dạng… Với việc viết văn bản trên điện thoại di động rất dễ sinh ra lỗi, tính năng tự động sửa lỗi chính tả là thành phần không thể thiếu trong bất cứ bàn phím nào. Các kỹ thuật auto correction đã rất phát triển và hoạt động rất tốt với nhiều ngôn ngữ, nhất là tiếng Anh. Nhưng với tiếng Việt thì sao? Bạn hãy thử với bàn phím Samsung, Google, Swiftkey các cụm từ sau, và so sánh với Laban Key, bàn phím phát triển riêng cho người Việt:

trid yueej

Trong ví dụ trên, người dùng định gõ chữ trí tuệ, nhưng gõ sai dấu sắc trong chữ trí (s gõ thành d), sai chữ t trong chữ tuệ (t thành y). Bạn sẽ thấy chỉ có Laban Key tự động sửa được trường hợp trên.

Một trong những lý do các bộ gõ này sửa lỗi chính tả tiếng Việt không tốt là ở chỗ chúng đã không tính đến phương pháp gõ Telex khi xây dựng mô hình lỗi (error model). Bài viết này sẽ trình bày cách tiếp cận cơ bản khi sửa lỗi chính tả và vai trò của Telex trong mô hình lỗi. Chính nhờ có tính đến Telex Input trong mô hình lỗi mà Laban Key đã thể hiện khả năng sửa lỗi vượt trội so với các bàn phím đa ngôn ngữ khác. Chúng tôi cũng hy vọng kỹ thuật trình bày ở đây giúp ích được cho các nhu cầu khác trong các bài toán xử lý ngôn ngữ tự nhiên.

Phương pháp cơ bản

Các phương pháp truyền thống trong sửa lỗi chính tả dựa vào hai thành phần cơ bản là Language Model và Error Model. Language Model là mô hình xác xuất, cho biết xác suất xuất hiện của một từ trong một ngữ cảnh (context). Context thường là các từ đứng ngay trước từ đang được xem xét.

Gọi w là từ người dùng gõ. Gọi c là từ cần xem xét để tự động sửa w thành c. Yêu cầu của việc sửa lỗi chính tả là xác định c sao cho xác suất có điều kiện P(c|w) là lớn nhất.

Theo công thức Bayes:

P(c|w) = P(c). P(w|c) / P(w)

Trong đó:

- P(c): xác xuất của từ c

- P(w|c): xác xuất người dùng nhập nhầm w thay vì c (như mong muốn).

- P(w): xác xuất nhập từ w.

P(w) không đổi với các c khác nhau, để tìm P(c|w) lớn nhất, ta cần tìm c sao cho P(c).P(w|c) lớn nhất.

Một cách trực quan, từ sửa đúng nhất là từ có xác suất lớn (thể hiện qua P(c)), và gần giống với từ được gõ (thể hiện qua P(w|c)). P(c) được xác định từ mô hình Language Model, trong khi P(w|c) được xác định trong Error Model sẽ được được mô tả dưới đây.

Language Model

Language Model là mô hình xác suất cho biết xác suất xuất hiện của một từ. Mô hình xác suất của các từ đơn lẻ được gọi là unigram language model. Trên thực tế, language model không chỉ cân nhắc đến các từ đơn lẻ, mà còn tính đến ngữ cảnh, bao gồm các từ đứng trước hoặc sau từ đang được xem xét. Với bài toán nhập văn bản, chúng ta xét đến các từ đi liền trước. Xác suất một từ được cân nhắc là P(c|s), trong đó s là chuỗi các từ đi liền trước:

- Bigram language model: P(c|x) là mô hình xác xuất tính đến 1 từ ngay phía trước, cho biết xác xuất của c khi từ đi trước là x.

- Trigram language model: P(c | x1x2), xác xuất c đi sau 2 từ x1 x2.

- N-gram language model: P(c | x1…xn), xác xuất c đi sau n từ: x1…xn.

Để xây dựng language model, chúng ta dựa vào kho dữ liệu văn bản lớn (corpus) đếm tần suất xuất hiện của các từ, cụm từ. Mô hình thường được dùng nhất là bigram. Từ trigram trở lên, language model đòi hỏi kích thước rất lớn nên ít được dùng trên thực tế.

Error Model

Error Model là mô hình đánh giá khả năng một từ mong muốn c bị viết/gõ nhầm sang từ khác w: P(w|c). Để xây dựng error model, có hai cách tiếp cận:

- Dựa trên thống kê lỗi trên dữ liệu văn bản thu thập được, xây dựng mô hình xác xuất. Phương pháp này rất khó thực hiện, vì tần suất lỗi chính tả trong dữ liệu thu thập thường rất thấp. Để có mô hình tốt, cần phải có dữ liệu rất lớn.

- Định nghĩa các loại lỗi thường xảy ra và xây dựng mô hình đánh giá khả năng xảy ra lỗi (rules based). Đây là phương pháp đơn giản và cũng thường được dùng nhất, sẽ được mô tả chi tiết dưới đây.

Các lỗi nhập liệu sai có thể xếp thành các loại:

- Replace: something -> simething
- Transpose: something -> smoething
- Delete: something -> smething
- Insert: something -> sometthing

Để đo sự khác nhau giữa 2 chuỗi {c, w}, chúng ta dùng edit distance là số phép biến đổi được định nghĩa ở trên để biến c thành w, hoặc ngược lại.

Ví dụ: với w = somthing

- Tập các từ với edit distance = 1 là: {something, soothing}

- Tập các từ edit distance = 2 là : {loathing, nothing, scathing, seething, smoothing, something, soothing, sorting} (Tham khảo [1])

Dùng error model này, kết hợp với language model, thuật toán auto-correction đơn giản có thể thực hiện như sau theo thứ tự sau:

- Nếu w là từ đúng chính tả, chọn w.

- Tìm từ cP(c|x) cao nhất trong các từ sai 1 vị trí so với w (trong đó x là từ đứng trước .

- Tìm từ có P(c|x) cao nhất trong các từ sai 2 vị trí so với w.

Chỉ với language model và error model đơn giản như trên, các bộ auto correction cho tiếng Anh có thể đạt được độ chính xác trên 90% đối với các từ sai chính tả. Nhưng, tại sao với tiếng Việt, độ chính xác lại thấp như vậy? Nguyên nhân chính là do error model đã không xét đến cách gõ telex.

Ví dụ:

- Để gõ chữ “tuệ” bằng telex, sẽ cần gõ: t u e e j

- Người dùng gõ sai chữ t thành chữ y, là chữ nằm cạnh t trên bàn phím QWERTY. Lúc đó chuỗi input sẽ là: y u e e j. Bộ xử lý telex sẽ không hiểu chuỗi này và cho ra kết quả cuối cùng vẫn là yueej.

- Do số sai khác edit distance giữa “tuệ” và “yueej” là 5 nên không thực hiện auto-correct “yueej” thành “tuệ” được (để auto-correct hoạt động tin cậy và giới hạn không gian tìm kiếm, thường chỉ ta chỉ dùng với edit distance <= 3).

Phương pháp thực hiện trong Laban Key

Autocorrection trong Laban Key

Các thành phần kiểm tra, sửa lỗi chính tả trong Laban Key gồm có:

- Proximity Corrector: Lỗi hay xảy ra nhất khi gõ trên smartphone là gõ chệch phím. Chính vì thế Proximity Corrector dựa vào Keyboard Layout sẽ tìm các phím xung quanh các phím được gõ để sinh ra các dãy phím người dùng có thể định gõ. Các dãy phím này được đưa qua bộ kiểm tra Telex Processor.

- Telex Processor: sàng lọc các dãy phím, tìm ra các dãy có thể sinh ra từ tiếng Việt hợp lệ theo kiểu telex.

- Language Model: Tìm ra từ có điểm xác xuất cao nhất trong các từ nhận được từ Telex Processoor. Model này có xét đến ngữ cảnh bao gồm nhiều nhất 4 từ (âm tiết) đứng trước từ hiện tại.

Trong các khối trên, Proximity Corrector và Telex Processor đóng vai trò làm Error Model. Hình dưới đây mô tả chi tiết hơn cách hoạt động của Proximity Corrector và Telex Processor với chuỗi phím nhập vào là “yueej” đi sau từ “trí” (người dùng định gõ “tuệ” nhưng gõ chệch t thành y).

Bàn phím QWERTY
Một số chuỗi telex gần với chuỗi input {yueej}

Với mỗi phím được gõ, Proximity Corrector xác định các phím lân cận có thể là chủ ý của người dùng. Với chữ {y}, các chữ lân cận trên bàn phím QWERTY được xét đến là {t, u, h, g, j}. Tương tự, lân cận với chữ {u} là các chữ {y, i, j, u, k}… Telex Processor được dùng để kiểm tra một chuỗi phím có sinh ra từ tiếng Việt hợp lệ hay không. Kết quả quá trình này sẽ được các chuỗi {tueej, hueej, hieen, …}, tương ứng với các từ {tuệ, huệ, hiên,…}. Cuối cùng Language Model chọn ra từ tốt nhất có thể đi với từ trước đó là từ {trí}. Từ được chọn sẽ là {tuệ}.

Như vậy, thay vì tìm các từ gần giống với chuỗi kết quả cuối cùng (đã qua xử lý telex), Laban Key làm việc trên chuỗi phím gốc chưa qua xử lý telex. Từ chuỗi phím này, chúng ta tìm các chuỗi lân cận, với edit distance nhỏ hơn một giá trí nhất định (thường là 3). Cuối cùng, các chuỗi phím ứng viên được đưa qua bộ xử lý telex để tìm các chuỗi hợp lệ.

Cụ thể, theo cách tính edit distance cơ bản, không tính đến telex ta có:

edit_distance(“yueej”, “tuệ”) = 5
edit_distance(“yueej”, “huệ”) = 5
edit_distance(“yueej”, “hiên”) = 5

Nếu khống chế edit distance không quá 3, ta sẽ không thể đoán ra được các từ {tuệ, huệ, hiên}. Nhưng khi so sánh chuỗi gốc chưa qua xử lý telex, ta có:

edit_distance(“yueej”, “tueej”) = 1
edit_distance(“yueej”, “hueej”) = 1
edit_distance(“yueej”, “hieen”) = 3

Theo cách tính mới, thì cả 3 từ {tuệ, huệ, hiên} đều nằm trong phạm vi edit distance cho phép.

Kết luận

Trên đây chúng tôi đã trình bày phương pháp cơ bản xây dựng ứng dụng kiểm tra chính tả. Chúng tôi cũng đã phân tích lý do khiến phương pháp này không hiệu quả đối với nội dung gõ bằng telex. Việc không tính đến telex input đã làm cho error model không còn đúng, khi người dùng chỉ cần gõ sai 1, 2 phím cũng có thể dẫn đến kết quả edit distance lên đến 4, 5. Chúng tôi đã xây dựng trong Laban Key một error model dùng proximity corrector kết hợp với bộ xử lý telex để tìm ra các chuỗi phím telex hợp lệ gần với chuỗi được nhập vào. Điều này đã giúp cho Laban Key có khả năng sửa lỗi tiếng Việt tốt hơn hẳn các bộ gõ đa ngôn ngữ của các hãng như Google, Apple, Samsung.

Error Model trong Laban Key hiện mới chỉ tìm kiếm chuỗi sai khác theo dạng replace (thay phím này bằng phím khác). Hiện chưa xử được các dạng lỗi transpose (đảo chữ), delete (thiếu chữ), insert (thừa chữ). Để xử lý được các lỗi này, không gian tìm kiếm các chuỗi thay thế sẽ tăng lên rất nhiều, đòi hỏi thời gian tính toán nhiều hơn. Chúng tôi hiện đang phát triển các thuật toán tối ưu để xử lý được các lỗi này trong thời gian tới.

by Long Pham

Tham khảo:

[1] How to Write a Spelling Corrector

http://norvig.com/spell-correct.html