Một cách tiếp cận sử dụng mô hình N-Gram trong việc tự động phát hiện và sửa lỗi nhận dạng văn bản tiếng Việt - Nguyễn Chí Thành

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 33 MỘT CÁCH TIẾP CẬN SỬ DỤNG MÔ HÌNH N-GRAM TRONG VIỆC TỰ ĐỘNG PHÁT HIỆN VÀ SỬA LỖI NHẬN DẠNG VĂN BẢNTIẾNG VIỆT Nguyễn Chí Thành1*, Thái Trung Kiên1, Hoàng Đình Thắng1, Nguyễn Thị Lan Phượng2 Tóm tắt: Trong bài báo này, chúng tôi trình bày những kết quả nghiên cứu trong việc nâng cao độ chính xác của nhận dạng văn bản tiếng Việt. Kết quả của nhận dạng văn bản từ hình ảnh thường không đạt được độ chính xác tuyệt đối, nhất là đối với các tài liệu có chất lượng hình ảnh đầu vào thấp. Do đó, việc tự động phát hiện và sửa lỗi nhận dạng văn bản là cần thiết, giúp giảm công sức hiệu đính của người dùng. Trong nghiên cứu này, chúng tôi đề xuất một thuật toán phát hiện và sửa lỗi nhận dạng văn bản tiếng Việt dựa trên mô hình n-gram. Kết quả thử nghiệm cho thấy việc áp dụng thuật toán này giúp nâng cao độ chính xác của nhận dạng. Từ khóa: Nhận dạng văn bản, Mô hình ngôn ngữ. 1. ĐẶT VẤN ĐỀ 1.1. Giới thiệu Nhận dạng văn bản trong tiếng Anh thường được nhắc đến với cái tên nhận dạng ký tự quang học (optical character recognition) và được viết tắt là OCR. Đây là lĩnh vực được ứng dụng rộng rãi trong việc số hóa các văn bản, tài liệu cũng như việc hỗ trợ nhập liệu tự động các nguồn dữ liệu in trên giấy như hộ chiếu, giấy chứng minh thư, hóa đơn, báo cáo tài chính, danh thiếp Các nghiên cứu về nhận dạng văn bản tiếng Anh cũng như tiếng Việt đã đạt được nhiều kết quả tốt, có độ chính xác cao đối với những nguồn ảnh văn bản rõ ràng. Tuy nhiên, với các văn bản, tài liệu do đã cũ hoặc do quá trình bảo quản không tốt bị mờ chữ, mất chữ thì độ chính xác của quá trình nhận dạng văn bản bị giảm đi đáng kể. Một số phần mềm có tính năng tự sửa lỗi nhận dạng, tuy nhiên, chủ yếu sửa lỗi ở mức ký tự, sửa lỗi chính tả dựa vào từ điển, không có khả năng sửa lỗi ở mức từ, ở mức ngữ cảnh. Do đó, khi gặp những tài liệu có nguồn ảnh đầu vào không tốt thì công sức bỏ ra để hiệu chỉnh lại văn bản kết quả là khá lớn, nhiều khi còn tương đương với công đánh lại toàn bộ văn bản. Trong lĩnh vực nghiên cứu nhận dạng văn bản tiếng Anh, các kĩ thuật sửa lỗi cho nhận dạng sử dụng các kĩ thuật thống kê, các kĩ thuật xử lý ngôn ngữ tự nhiên được nghiên cứu từ lâu và đã đưa đến những kết quả sửa lỗi tốt, nâng cao đáng kể độ chính xác của nhận dạng văn bản, nhất là đối với các nguồn ảnh đầu vào có chất lượng không tốt. Tuy nhiên, với việc nhận dạng văn bản tiếng Việt thì các công trình nghiên cứu về phương pháp sửa lỗi sau khi nhận dạng còn khá mới mẻ, chưa có những nghiên cứu về việc sử dụng các kĩ thuật xử lý ngôn ngữ tự nhiên vào việc nâng cao tính chính xác của nhận dạng văn bản. Bài toán phát hiện và sửa lỗi văn bản không chỉ quan trọng trong quá trình nhận dạng văn bản từ hình ảnh mà nó còn đóng vai trò quan trọng trong nhiều ứng dụng khác như các giao diện nhập bằng viết tay cho phép người sử dụng viết chữ làm đầu vào cho máy tính, các thiết bị tổng hợp giọng nói (text-to-speech) và nhận Công nghệ thông tin N. C. Thành, , N. T. L. Phượng, “Một cách tiếp cận sử dụng văn bản tiếng Việt.” 34 dạng giọng nói (speech-to-text). Các ứng dụng khác cũng có thể sử dụng phát hiện và sửa lỗi văn bản để tăng chất lượng kết quả như các hệ thống soạn thảo văn bản, soạn thảo code, biên tập có trợ giúp của máy tính, dịch máy, học ngoại ngữ, tương tác cơ sở dữ liệu, cũng như các ứng dụng có đầu vào hoặc đầu ra là tiếng nói. 1.2. Các nghiên cứu liên quan Đã có một số phương pháp được đề xuất để giải quyết bài toán phát hiện và sửa lỗi chính tả tiếng Việt. Ở bài báo [1], các tác giả sử dụng luật cấu tạo âm tiết tiếng Việt hai thành phần để phát hiện lỗi chính tả. Một phương pháp phát hiện và sửa lỗi tiếng Việt sử dụng mô hình bi-gram đã được đề xuất trong [2]. Mô hình n-gram cũng được sử dụng để kiểm lỗi cách dùng từ và cụm từ tiếng Việt trong công bố [3], tuy nhiên, nghiên cứu này không đề xuất phương pháp sửa các lỗi chính tả phát hiện được. Bài báo [4] mô tả một phương pháp sử dụng một mô hình n-gram được xây dựng từ một kho ngữ liệu có kích thước lớn để phát hiện các lỗi chính tả khi đánh máy. Trong các nghiên cứu về phát hiện và sửa lỗi tiếng Việt, chỉ có một phương pháp có liên quan tới phát hiện và sửa lỗi nhận dạng văn bản (OCR – optical character recognition), trong nghiên cứu này, việc phát hiện lỗi tiếng Việt dựa vào xác suất unigram và bộ đếm sự xuất hiện đồng thời của các âm tiết [5]. Đối với nhận dạng văn bản tiếng Anh, đã có nhiều phương pháp được đề xuất để đưa ra danh sách các từ thay thế cho từ bị sai. Tương ứng với một từ lỗi thuật toán sẽ đưa ra một danh sách các ứng cử viên để thay thế cho từ đó. Một số thuật toán sửa lỗi dựa trên từ điển đã được đề xuất. Một trong số đó là thuật toán đối sánh chuỗi đánh trọng số các từ trong văn bản sử dụng độ đo khoảng cách. Ứng cử viên sửa lỗi với khoảng cách ngắn nhất với từ lỗi sẽ được chọn [6]. Thuật toán khác sử dụng thuộc tính cú pháp của ngôn ngữ và mô hình n-gram để tiến hành quá trình sinh ra các ứng cử viên sửa lỗi và chọn ra ứng cử viên tốt nhất. [7] đề xuất một phương pháp sửa lỗi sau OCR dựa trên học mẫu, trong đó đầu tiên một danh sách các ứng cử viên sửa lỗi được sinh ra từ một từ điển, sau đó ứng cử viên phù hợp nhất sẽ được lựa chọn dựa trên các đặc tính về từ vựng và ngữ pháp xung quanh từ lỗi. Các kĩ thuật sửa lỗi dựa trên từ điển là khá hợp lý và thành công. Tuy nhiên, chúng không thể sửa những lỗi dựa trên ngữ cảnh, ví dụ như sửa những lỗi dựa trên vị trí ngữ pháp của chúng trong câu. Các kĩ thuật sửa lỗi dựa trên ngữ cảnh thực hiện phát hiện lỗi và sửa lỗi dựa trên ngữ cảnh ngữ pháp và ngữ nghĩa. Nó có thể giải quyết vấn đề sửa lỗi từ thực như ở câu “Học sinh tơi trường” vì theo ngữ cảnh mà “tơi” xuất hiện, nó phải là một động từ chứ không phải là một danh từ. Để thực hiện sửa lỗi dựa trên ngữ cảnh, một số giải pháp đã được cân nhắc tới, phần lớn là dựa trên mô hình ngôn ngữ thống kê và mô hình dựa trên đặc trưng. [8] mô tả một hệ thống sửa lỗi từ theo ngữ cảnh dựa trên ánh xạ hỗn loạn, sử dụng xác xuất hỗn loạn để xác định các dãy tần suất sai và chuyển chúng thành chuỗi đúng nhất. Nói cách khác, nó mô hình hóa mức độ có thể xảy ra của một chữ cái có thể bị nhận nhầm thành chữ cái khác. [9] đề xuất một bộ phân lớp Bayesian trong đó coi các lỗi từ thực là nhập nhằng và sau đó tìm từ đúng bằng cách tính toán mối quan hệ xác xuất giữa từ lỗi và ứng cử viên sửa lỗi. Trong nghiên cứu [10], các tác giả sử dụng mô hình ngôn ngữ n-gram để phát hiện và sửa lỗi văn bản tiếng Anh. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 35 Trong bài báo này, chúng tôi nghiên cứu một phương pháp tự động và sửa lỗi nhận dạng văn bản tiếng Việt dựa trên mô hình ngôn ngữ n-gram. Nghiên cứu được trình bày theo thứ tự sau: Phần 2 trình bày nội dung nghiên cứu; Phần 3 trình bày các kết quả thử nghiệm, đánh giá; Cuối cùng, kết luận được trình bày trong Phần 4. 2. BÀI TOÁN PHÁT HIỆN VÀ SỬA LỖI NHẬN DẠNG VĂN BẢN Trên thực tế, tỉ lệ lỗi của các hệ thống nhận dạng văn bản (OCR) thường khá cao nếu tài liệu được quét có nhiều lỗi như trạng thái vật lý không tốt, chất lượng in kém, tài liệu phai màu, giấy cũ. Khi một hệ thống OCR không thể nhận dạng một ký tự sẽ tạo ra một lỗi OCR, thường là một lỗi chính tả trong văn bản đầu ra. Ví dụ, ký tự “B” có thể được nhận dạng sai thành số “8”, ký tự “S” nhận dạng thành số “5”, ký tự “O” nhận dạng thành số “0”, Để nâng cao độ chính xác của nhận dạng, cần phát hiện và sửa các lỗi ngôn ngữ trong văn bản OCR đầu ra sau khi ảnh đầu vào đã được quét và xử lý. Về cơ bản, có hai loại lỗi OCR: lỗi không từ và lỗi từ thực. Một lỗi không từ là một từ được nhận dạng bởi hệ thống OCR nhưng nó lại không tương ứng với một từ vựng nào. Ví dụ, khi “Chào bạn” được hệ thống OCR nhận dạng là “Chào bụn” thì “bụn” được xác định là lỗi không từ vì “bụn” không có nghĩa trong tiếng Việt. Trái lại, lỗi từ thực là một từ được nhận dạng và tương ứng với một từ trong từ điển mặc dù nó sai về ngữ pháp trong câu chứa nó. Ví dụ, khi “Học sinh tới trường” được hệ thống OCR nhận dạng thành “Học sinh tơi trường” thì “tơi” được coi là một lỗi từ thực vì “tơi” mặc dù đúng về mặt cú pháp (có xuất hiện trong tiếng Việt) nhưng việc sử dụng nó trong câu này là sai về ngữ pháp. Thông thường, các lỗi không từ và từ thực rơi vào một trong ba lớp lỗi sau: xóa, thêm và thay thế. Lỗi xóa xuất hiện khi một hoặc nhiều ký tự bị xóa khỏi từ gốc. Ví dụ nhận dạng nhầm từ “Trường” thành “Trưng”, “Trơng”, “Trươg”. Lỗi thêm xảy ra khi một hoặc nhiều ký tự được thêm vào từ gốc. Ví dụ, nhận dạng nhầm từ “Học” thành “Họcc” hay “Họoc”. Lỗi thay thế xảy ra khi một hoặc nhiều ký tự bị thay thế trong từ gốc, ví dụ như thay thế ký tự “m” trong “Thêm” thành ký tự “n” hoặc thay thế ký tự “g” trong “Thống” thành “q”. Để giải quyết được bài toán này, đầu tiên cần phân tích xem những lý do nào có thể gây nên việc nhận dạng lỗi một âm tiết. Qua quá trình khảo sát và thử nghiệm với bài toán nhận dạng văn bản, chúng tôi tổng hợp một số loại lỗi nhận dạng chủ yếu sau: a) Loại 1: Lỗi xóa Lỗi này xuất hiện khi âm tiết bị xóa mất 1 ký tự. Trường hợp này có thể xảy ra khi một ký tự bị mờ hoặc xóa mất trên ảnh đầu vào. Ví dụ: + "quan hệ đoàn kết giữa hai nước Việt Nam và Lào" có thể bị nhận dạng nhầm thành "quan hệ đoàn kết giữa ha nước Việt Nam và Lào" nếu như ký tự "i" của âm tiết "hai" bị mờ. Như vậy, âm tiết "hai" bị nhận dạng nhầm thành "ha", ký tự bị xóa mất là ký tự "i". Lỗi này có thể được mô hình hóa như sau. - Lỗi xóa: Âm tiết bị xóa bớt một ký tự. Công nghệ thông tin N. C. Thành, , N. T. L. Phượng, “Một cách tiếp cận sử dụng văn bản tiếng Việt.” 36 ( ) = Trong đó: là âm tiết ban đầu, là âm tiết sau khi bị nhận dạng sai, bị xóa mất ký tự (1 ≤ ≤ ). b) Loại 2: Lỗi thêm Lỗi này xảy ra khi âm tiết bị thêm 1 ký tự vào do có vết thêm vào trên ảnh nên vết này bị nhận dạng nhầm thành ký tự. Ví dụ: + "Thanh tra chính phủ" nếu có 1 vết gạch ở sau âm tiết "tra" thì có thể bị nhận dạng nhầm thành "Thanh trai chính phủ". Ở đây, âm tiết "tra" bị nhận dạng nhầm thành âm tiết "trai", ký tự bị thêm vào là ký tự "i". Lỗi này có thể được mô hình hóa như sau. - Lỗi thêm: Âm tiết bị thêm một ký tự vào sau khi nhận dạng. ∗, ( ) = ∗ ế ≤ ∗ ế = + 1 Trong đó: là âm tiết ban đầu, ∗ là âm tiết sau khi bị nhận dạng sai, bị thêm vào ký tự ∗ ở trước ký tự (nếu 1 ≤ ≤ ) hoặc sau ký tự nếu = + 1. c) Loại 3: Lỗi thay thế Lỗi này xuất hiện khi nhận dạng sai 1 ký tự của âm tiết thành 1 ký tự khác.Trường hợp này xảy ra khi thuật toán nhận dạng nhận nhầm ký tự này thành ký tự khác hoặc nhận dạng sai dấu trên ký tự. Ví dụ: + "ảnh hưởng của các yếu tố" có thể bị nhận dạng nhầm thành "ánh hưởng của các yếu tố". Ở đây, âm tiết "ảnh" bị nhận nhầm thành âm tiết "ánh" do dấu hỏi ở trên ký tự "a" bị nhận dạng nhầm thành dấu sắc. Ký tự "ả" bị thay thế bằng ký tự "a". + "các cơ sở giáo dục" có thể bị nhận dạng nhầm thành "các cơ sở giác dục" nếu ký tự "o" của âm tiết "giáo" bị mờ một phần bên phải. Trong trường hợp này, âm tiết "giáo" bị nhận dạng nhầm thành âm tiết "giác", ký tự "o" bị thay thế bằng ký tự "c". + "bài toán tự động phát hiện mục tiêu" có thể bị nhận dạng nhầm thành "bài toán tự đông phát hiện mục tiêu" nếu dấu nặng trong âm tiết "động" bị mờ hoặc dính sát vào chữ cái "ô". Trong trường hợp này, âm tiết "động" bị nhận dạng nhầm thành âm tiết "đông", ký tự "ộ" bị thay thế bằng ký tự "ô". Lỗi này có thể được mô hình hóa như sau: - Lỗi thay thế: nhận dạng sai một ký tự của âm tiết, thêm dấu vào âm tiết, bỏ mất dấu của âm tiết. ∗, ( ) = ∗ Trong đó: là âm tiết ban đầu, ∗ là âm tiết sau khi bị nhận dạng sai, ký tự (1 ≤ ≤ ) bị thay thế bằng ký tự ∗. d) Loại 4: Lỗi gộp ký tự Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 37 Lỗi này xuất hiện khi hai ký tự của âm tiết bị gộp làm một ký tự khác.Trường hợp này xảy ra khi 2 ký tự ở cạnh nhau có hình dạng giống với một ký tự thứ ba nên bị nhận dạng sai. Ví dụ: + "hội nghị thường niên" có thể bị nhận dạng nhầm thành "hội nghị thường mên". Trong trường hợp này, âm tiết "niên" bị nhận nhầm thành âm tiết "mên", do hai ký tự "ni" bị gộp lại thành một ký tự "m". + "các kỹ thuật tiên tiến" có thể bị nhận dạng nhầm thành "các kỹ thuật hên tiến". Trong trường hợp này, âm tiết "tiên" bị nhận nhầm thành âm tiết "hên", do hai ký tự "ti" bị gộp lại thành một ký tự "h". Lỗi này có thể được mô hình hóa như sau: - Lỗi gộp ký tự: 2 ký tự bị gộp làm 1. ( ) = ∗ Trong đó: là âm tiết ban đầu, ∗ là âm tiết sau khi bị nhận dạng sai, hai ký tự (1 ≤ ≤ − 1) bị gộp lại nhận dạng thành ký tự ∗. e) Loại 5: Lỗi chia tách ký tự Lỗi này xuất hiện khi một ký tự của âm tiết bị nhận dạng thành 2 ký tự. Trường hợp này xảy ra khi một ký tự khi tách đôi theo chiều dọc thì tạo thành hình ảnh tương tự 2 ký tự khác. Ví dụ: + "trong khoảng thời gian" có thể bị nhận dạng nhầm thành "trong khoảng thời giaii" nếu ký tự "n" của âm tiết "gian" bị mờ phần trên. Trong trường hợp này, âm tiết "gian" bị nhận nhầm thành "giaii", ký tự "n" bị nhận dạng tách thành 2 ký tự "ii". Lỗi này có thể được mô hình hóa như sau: - Lỗi chia tách ký tự: 1 ký tự bị tách ra làm 2. ( ) = Trong đó: là âm tiết ban đầu, là âm tiết sau khi bị nhận dạng sai, ký tự (1 ≤ ≤ ) bị nhận dạng nhầm thành hai ký tự . f) Loại 6: Lỗi gộp âm tiết Lỗi này xuất hiện khi 2 âm tiết bị gộp làm một âm tiết. Trường hợp này xảy ra khi 2 âm tiết xuất hiện sát gần nhau khiến cho phần mềm OCR nhận dạng chúng là 1 âm tiết. Ví dụ: + "mô phỏng huấn luyện" có thể bị nhận dạng nhầm thành "mô phỏng huấnluyện" nếu hai âm tiết "huấn" và "luyện" bị in sát nhau, hoặc có vết bẩn giữa hai âm tiết. Trong trường hợp này, hai âm tiết "huấn luyện" bị nhận nhầm thành "huấnluyện". Lỗi này có thể được mô hình hóa như sau. - Lỗi gộp âm tiết: 2 âm tiết bị gộp làm 1. _ (, ) = Công nghệ thông tin N. C. Thành, , N. T. L. Phượng, “Một cách tiếp cận sử dụng văn bản tiếng Việt.” 38 Trong đó: và là hai âm tiết ban đầu, là kết quả nhận dạng sai, hai âm tiết bị gộp làm một. g) Loại 7: Lỗi chia tách âm tiết Lỗi này xuất hiện khi 1 âm tiết bị tách làm 2 âm tiết sau khi nhận dạng.Trường hợp này xảy ra khi khoảng cách giữa 2 ký tự của âm tiết lớn hoặc một phần ký tự bị mờ làm cho âm tiết bị tách làm 2 phần. Ví dụ: + "Việc xác định" có thể bị nhận dạng nhầm thành "V iệc xác định" nếu chữ "V" bị mờ một phần bên phải.Trong trường hợp này âm tiết "Việc" bị nhận dạng nhầm thành hai âm tiết là "V" và "iệc". Lỗi này có thể được mô hình hóa như sau. - Lỗi chia tách âm tiết: 1 âm tiết bị tách ra làm 2. _ ( ) = + Trong đó: là âm tiết ban đầu, và là hai âm tiết sau khi bị nhận dạng sai (1 ≤ ≤ − 1). Lỗi nhận dạng có thể xảy ra theo một trong các trường hợp trên hoặc có thể là tổng hợp của các trường hợp trên. 3. PHƯƠNG PHÁP PHÁT HIỆN VÀ SỬA LỖI BẰNG MÔ HÌNH N-GRAM Chúng tôi đề xuất một phương pháp phát hiện và sửa lỗi nhận dạng văn bản tiếng Việt dựa trên mô hình n-gram. Trước hết, chúng ta cần xây dựng được mô hình n-gram dựa trên một tập hợp các văn bản huấn luyện, sau đó với mỗi văn bản cần tìm lỗi, dựa vào mô hình n-gram đã tính, xác định xác suất n-gram của các âm tiết liền nhau trong văn bản đang xét. Nếu xác suất này nhỏ hơn một ngưỡng lỗi thì dãy âm tiết đó được coi là có lỗi dùng từ. Để xây dựng mô hình n-gram, đầu tiên cần thu thập các văn bản tiếng Việt thành một kho ngữ liệu, và dùng kho này để làm dữ liệu huấn luyện. Sau đó, tiến hành tính toán các giá trị unigram (1-gram), bigram (2-gram) và trigram (3-gram) bằng cách thống kê tần suất xuất hiện và áp dụng các công thức để tính xác suất, làm trơn các xác suất thấp, hiệu chỉnh xác suất và tính các hệ số backoff. Tiếp theo cần xây dựng bộ từ điển các âm tiết có trong tiếng Việt để xác định các lỗi chính tả. Việc tính toán các giá trị n-gram và bộ từ điển âm tiết tiếng Việt được xây dựng tương tự với tài liệu [3]. Sau khi đã xây dựng được mô hình n-gram dựa trên tập dữ liệu huấn luyện, chúng ta có thể phát hiện lỗi cho kết quả nhận dạng văn bản theo các bước sau. Đầu tiên phát hiện các âm tiết sai sử dụng từ điển âm tiết. Sau đó, duyệt toàn bộ văn bản kết quả theo cụm 3 âm tiết liền nhau, tính xác suất trigram của từng cụm, nếu giá trị nhỏ hơn ngưỡng lỗi thì xác định cụm từ đó có lỗi dùng từ. Sau khi đã xác định cụm từ có lỗi thì chúng ta cần xác định vị trí của âm tiết bị lỗi. Một âm tiết nếu nó thuộc về hai hoặc ba cụm từ có lỗi thì có thể xác định đó chính là âm tiết gây ra lỗi. Do đó, chúng ta có thể xác định được chính xác vị trí của âm tiết gây lỗi. Sau khi đã xác định được âm tiết có lỗi, bước tiếp theo là xác định âm tiết đúng để sửa lỗi. Với mô hình n-gram, dựa vào xác suất của cụm âm tiết, chúng ta có thể đoán biết được khi cho trước một cụm âm tiết và vị trí âm tiết lỗi thì âm tiết nào có Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 39 khả năng thay thế âm tiết đó với xác suất cao nhất. Để xác định được âm tiết đúng để sửa lỗi, chúng ta có thể sử dụng phương pháp sinh ra tập các ứng cử viên để từ đó xác định ứng cử viên có khả năng đúng cao nhất. Từ những phân tích đó chúng tôi đề xuất một phương pháp xác định âm tiết đúng để sửa lỗi cho văn bản sau khi nhận dạng như sau. Sau khi đã xác định được âm tiết có lỗi, cần xác định âm tiết đúng là gì. Xuất phát từ chính âm tiết bị lỗi, chúng ta sử dụng các phép biến đổi từ âm tiết bị lỗi sinh ra 1 tập các âm tiết ứng cử viên là những âm tiết có thể là âm tiết đúng. () = { () ∪ () ∪ () ∪ () ∪ () ∪ _ () ∪ _ ()} Trong đó, tập ứng cử viên () là tập các ứng cử viên sinh ra từ âm tiết lỗi qua phép biến đổi ngược theo trường hợp ∗, , nghĩa là ∈ () khi ∗, () = . () = | ∗, () = , 1 ≤ ≤ + 1 Trong đó, n là số ký tự của u và ký tự ∗ là ký tự bất kì trong bảng chữ cái (có dấu hoặc không dấu). Ví dụ, với âm tiết "giác" thì "giá" một biến đổi ngược của phép thêm với = 4 ký tự thêm vào ∗ là "c". Nghĩa là "giá" ∈ ("giác") do "giác" = "", ("giá"). Tương tự, "gác" là một ngược của phép thêm với = 2 ký tự thêm vào ∗ là "i". Như vậy, "gác" ∈ ("giác"). Tương tự, () là tập các ứng cử viên sinh ra từ âm tiết lỗi qua phép biến đổi ngược theo trường hợp . () = | () = , 1 ≤ ≤ Trong đó, n là số ký tự của u. Ví dụ, với âm tiết "côn" thì "công" là một biến đổi ngược của phép xóa với = 4. Nghĩa là "công" ∈ ("côn") do "côn" = ("công"). () là tập các ứng cử viên sinh ra từ âm tiết lỗi qua phép biến đổi ngược theo trường hợp ∗, . () = | ∗, () = , 1 ≤ ≤ Trong đó, n là số ký tự của u. Ví dụ, với âm tiết "giác" thì "giáo" là một phép biến đổi ngược của phép thay thế với = 4, nghĩa là "giáo" ∈ ("giác") () là tập các ứng cử viên sinh ra từ âm tiết lỗi qua phép biến đổi ngược theo trường hợp . () = | () = , 1 ≤ ≤ − 1 () là tập các ứng cử viên sinh ra từ âm tiết lỗi qua phép biến đổi ngược theo trường hợp . () = | () = , 1 ≤ ≤ Công nghệ thông tin N. C. Thành, , N. T. L. Phượng, “Một cách tiếp cận sử dụng văn bản tiếng Việt.” 40 Tương tự, _ () là tập các ứng cử viên sinh ra từ âm tiết lỗi qua phép biến đổi ngược theo trường hợp _. _ () là tập các ứng cử viên sinh ra từ âm tiết lỗi qua phép biến đổi ngược theo trường hợp _ . Có thể áp dụng các phép biến đổi nhiều lần để tìm ra tập các ứng cử viên. () = (()) Sau khi có tập ứng cử viên, đầu tiên chúng ta loại bỏ các âm tiết không đúng chỉnh tả, là các âm tiết không có trong từ điển âm tiết. Sau đó, từ tập các ứng cử viên này chúng ta tính toán xác suất n-gram của các âm tiết trong tập âm tiết ứng cử viên để tìm ra âm tiết đúng. Để sửa lỗi tự động chúng ta có thể đặt ra ngưỡng để có thể tự động sửa lỗi, nếu tìm được đúng 1 âm tiết ứng cử viên có độ chính xác vượt ngưỡng hoặc âm tiết ứng cử viên có độ chính xác vượt trội hơn so với các ứng cử viên khác thì tự động sửa lỗi. Nếu có nhiều âm tiết chính xác thì chúng ta có 1 tập các âm tiết để người dùng có thể lựa chọn trong sửa lỗi bán tự động. Các bước trong thuật toán tìm tập ứng cử viên cho âm tiết bị lỗi dựa trên mô hình n-gram được minh họa ở hình 1. Dữ liệu đầu vào cho thuật toán là âm tiết bị lỗi và vị trí của nó trong văn bản. Đầu ra của thuật toán là tập các ứng cử viên có thể là âm tiết đúng ban đầu trong văn bản gốc. Bắt đầu Sinh tập ứng cử viên từ các phép biến đổi ngược Âm tiết bị lỗi Loại bỏ các ứng cử viên không có trong từ điển âm tiết Loại bỏ các ứng cử viên có xác suất n-gram thấp Kết thúc Hình 1. Các bước tìm ứng cử viên để sửa lỗi. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 41 4. THỬ NGHIỆM, ĐÁNH GIÁ Chương trình thử nghiệm đã được xây dựng dựa trên phương pháp tìm và sửa lỗi tự động trình bày ở trên. Phần mềm được viết bằng ngôn ngữ C# sử dụng bộ công cụ lập trình Microsoft Visual Studio. Sau khi lấy về kết quả nhận dạng của phần mềm mã nguồn mở VietOCR, chương trình thử nghiệm thực hiện phát hiện lỗi nhận dạng và tự động sửa lỗi, hỗ trợ người sử dụng sửa lỗi bán tự động bằng cách đưa ra một danh sách các âm tiết ứng cử viên để sửa lỗi. Hình 2 minh họa các bước hoạt động của chương trình thử nghiệm. Sau khi người dùng nhập đường dẫn đến file ảnh của văn bản cần nhận dạng, phần mềm tiến hành nhận dạng văn bản bằng cách gọi hàm của VietOCR. Sau đó, kết quả nhận dạng sẽ được xử lý để phát hiện lỗi nhận dạng dựa trên mô hình n-gram. Tiếp theo, các ứng cử viên để thay thế cho âm tiết lỗi sẽ được sinh ra bằng phương pháp sửa lỗi được đề xuất ở phần trước. Chương trình sẽ hiển thị kết quả sửa lỗi nhận dạng lên cửa sổ hỗ trợ sửa lỗi. Các âm tiết bị xác định là có lỗi nhận dạng sẽ được đánh dấu để người dùng dễ dàng nhận biết. Những âm tiết chỉ có 1 ứng cử viên thay thế sẽ được tự động sửa lỗi bằng ứng cử viên đó, với những âm tiết có nhiều ứng cử viên thay thế thì khi âm tiết đó được lựa chọn chương trình sẽ hiển thị danh sách ứng cử viên để người dùng lựa chọn. Đọc file ảnh đầu vào Nhận dạng văn bản (VietOCR) Phát hiện lỗi nhận dạng Sửa lỗi nhận dạng Hiển thị lỗi và hỗ trợ sửa lỗi Hình 2. Các bước hoạt động của chương trình. Để thực hiện phát hiện lỗi và sửa lỗi nhận dạng, cần có thông tin về các xác suất n-gram của các âm tiết. Các xác suất này được tính dựa trên một kho ngữ liệu huấn luyện. Trong chương trình thử nghiệm, mô hình n-gram được xây dựng từ trước và ghi vào file dữ liệu, kho ngữ liệu sử dụng để huấn luyện gồm hơn 300.000 câu tiếng Việt được thu thập từ nhiều lĩnh vực. Các xác suất unigram, bigram, trigram của các âm tiết được tính toán dựa trên thống kê tần suất xuất hiện các âm Công nghệ thông tin N. C. Thành, , N. T. L. Phượng, “Một cách tiếp cận sử dụng văn bản tiếng Việt.” 42 tiết trong kho ngữ liệu. Các xác suất n-gram thấp được làm trơn, sau đó tính toán các hệ số backoff. Chương trình đã được chạy thử nghiệm với một số văn bản quét và cho kết quả như trình bày ở Bảng 1. Văn bản đầu vào sử dụng phông Times New Roman, được quét thành ảnh trắng đen ở độ phân giải 300dpi. Sau khi sử dụng chương trình để phát hiện và sửa lỗi, độ chính xác của kết quả nhận dạng đã tăng lên. Ở đây, chúng tôi chỉ tính các âm tiết được sửa lỗi tự động, nghĩa là chương trình tự động thay thế âm tiết lỗi bằng âm tiết do chương trình tự động xác định là âm tiết đúng. Ngoài ra, đối với các âm tiết lỗi khác, chương trình cũng sinh ra một danh sách các ứng cử viên để hỗ trợ người dùng sửa lỗi một cách nhanh chóng và thuận tiện hơn. Trên bảng 1, số âm tiết nhận dạng lỗi ở cột (2) là số âm tiết lỗi sau khi nhận dạng bằng phương pháp nhận dạng của VietOCR, số lỗi này được xác định bằng cách so sánh với văn bản gốc bằng tay (sử dụng con người). Độ chính xác ở cột (3) là độ chính xác của văn bản là kết quả của module nhận dạng của VietOCR, tính bằng số âm tiết đúng chia cho tổng số âm tiết của trang văn bản. Cột (4) là số âm tiết lỗi còn lại sau khi một số âm tiết lỗi đã được sửa lỗi lại thành âm tiết đúng bằng thuật toán phát hiện và tự động sửa lỗi do chúng tôi đề xuất. Bảng 1. Kết quả thử nghiệm chương trình. Số âm tiết Âm tiết nhận dạng lỗi Độ chính xác Số âm tiết lỗi sau khi tự động sửa lỗi Độ chính xác sau sửa lỗi (1) (2) (3) (4) (5) Văn bản 1 446 15 96.64% 10 97.76% Văn bản 2 706 16 97.73% 13 98.16% Văn bản 3 509 10 98.04% 9 98.23% Văn bản 4 447 32 92.84% 25 94.41% Văn bản 5 367 28 92.37% 22 94.01% Tổng 2475 101 95.92% 79 96.81% Kết quả thử nghiệm cho thấy phương pháp được đề xuất có khả năng kiểm tra, phát hiễn lỗi tốt, giúp người dùng tự động sửa lỗi. Tốc độ phát hiện và sửa lỗi khá cao, có thể đưa vào sử dụng trong thực tế để xây dựng các hệ thống số hóa văn bản để xây dựng thư viện điện tử. 5. KẾT LUẬN Bài báo đã trình bày về kết quả nghiên cứu để tìm cách nâng cao độ chính xác của nhận dạng văn bản, sử dụng các tri thức khai thác được từ kho ngữ liệu thông qua mô hình thống kê n-gram. Chúng tôi đã đề xuất một phương pháp phát hiện và tự động sửa lỗi cho văn bản nhận dạng, đồng thời, xây dựng chương trình cài đặt thuật toán đó để thực hiện nâng cao độ chính xác cho nhận dạng văn bản. Chương trình thử nghiệm đã cho kết quả tốt, tự động sửa được lỗi nhận dạng và hỗ trợ người dùng sửa lỗi bán tự động. Kết quả nhận dạng đã được nâng lên so với phương pháp truyền thống. Kết quả này có thể được áp dụng để đưa vào thực hiện số hóa tài liệu cho các thư viện điện tử. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 43 Qua thực tế nghiên cứu và thử nghiệm việc nhận dạng các tài liệu, chúng tôi thấy rằng ngay cả khi đã áp dụng các phương pháp sửa lỗi, rất khó để đạt được tỉ lệ nhận dạng chính xác 100%. Do đó, để việc tìm kiếm, quản lý các kho tài liệu số hóa chính xác và thuận tiện hơn cần phát triển một hệ thống tìm kiếm thông minh có khả năng tìm được đúng các văn bản mà không cần các từ khóa phải chính xác 100% (do kết quả nhận dạng không đảm bảo được chính xác 100%). Việc áp dụng các kĩ thuật học máy, các lý thuyết tập mờ, tập thô vào bài toán tìm kiếm thông minh này là hết sức cần thiết. Lời cảm ơn: Tác giả cảm ơn sự tài trợ về kinh phí của đề tài: “Nghiên cứu phát triển giải pháp nâng cao độ chính xác của nhận dạng văn bản sử dụng tri thức khai thác từ kho ngữ liệu tiếng Việt ứng dụng vào hệ thống số hóa tài liệu để xây dựng các thư viện điện tử”. TÀI LIỆU THAM KHẢO [1]. Đinh Thị Phương Thu, Huỳnh Quyết Thắng, Nguyễn Văn Lợi. “Sử dụng luật cấu tạo âm tiết tiếng Việt hai thành phần trong bài toán kiểm tra chính tả tiếng Việt”. Tạp chí Bưu chính Viễn thông, Chuyên san Các nghiên cứu và triển khai ứng dụng trong viễn thông và Công nghệ thông tin, Số 18, tháng 10 năm 2007, trang 83-92. [2]. Nguyen Hong Phuong, Ngo Duc Thuan, Phan Anh Dung, Dinh Thi Phuong Thu, Huynh Quyet Thang. “Vietnamese spelling detection and correction by using a syllable Bi-gram and building a weight function combining Minimum Edit Distance and SoundEx algorithms with some heuristics”. International Conference on Research, Innovation and Vision for the Future in Computing and Communication Technologies, RIVF 2008, July 13-17, 2008, pp. 96 – 102. [3]. Trần Ngọc Anh, Đào Thanh Tĩnh. “Kỹ thuật mã hóa âm tiết tiếng Việt và các mô hình n-gram ứng dụng kiểm lỗi cách dùng từ và cụm từ tiếng Việt”. Tạp chí Công nghệ thông tin và Truyền thông, Tập V-1, Số 6 (26), tháng 9 năm 2011, tr.280-289. [4]. Huong, Nguyen Thi Xuan, Tran-Thai Dang, and Anh-Cuong Le. "Using large n-gram for Vietnamese spell checking." Knowledge and Systems Engineering. Springer, Cham, 2015. 617-627. [5]. Vu Hoang, Cong Duy, and Ai Ti Aw. "An unsupervised and data-driven approach for spell checking in Vietnamese OCR-scanned texts." Proceedings of the Workshop on Innovative Hybrid Approaches to the Processing of Textual Data. Association for Computational Linguistics, 2012. [6]. V.I. Levenshtein, "Binary codes capable of correcting deletions, insertions, and reversals", Cybernetics and Control Theory, 10(8), 707-710, 1966. [7]. H. Niwa, K. Kayashima, Y. Shimeki, "Postprocessing for Character Recognition Using Keyword Information", IAPR Workshop on Machine Vision Applications, Dec. 7-9, Tokyo, 1992. [8]. D. Evans, C. Zhai, X. Tong, N. Milic-Frayling, "OCR Correction and Query Expansion for Retrieval on OCR Data", Clarit trec-5 confusion track report, volume 52, 1996. Công nghệ thông tin N. C. Thành, , N. T. L. Phượng, “Một cách tiếp cận sử dụng văn bản tiếng Việt.” 44 [9]. R.A. Golding, "A Bayesian Hybrid Method for Context-Sensitive Spelling Correction", Proceedings of the Third Workshop on Very Large Corpora, Cambridge, MA. 39-53, 1995. [10]. Islam, Aminul, and Diana Inkpen. "Real-word spelling correction using Google Web IT 3-grams." Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 3-Volume 3. Association for Computational Linguistics, 2009. ABSTRACT AN APPROACH FOR VIETNAMESE OCR ERROR CHECK AND CORRECTION USING N-GRAM MODEL In the paper, the result of a studying on improving Vietnamese OCR accuracy is presented. OCR result rarely reach pefect accuracy, especially with documents with low quality image input. Therefore, automatic OCR check and correcion can reduce user efforts in OCR post-processing. In this study, a method for Vietnamese OCR error check and correction based on n- gram model is proposed. Experiment results show that the proposed method can improve the accuracy of OCR process. Từ khóa: Optical Character Recognition, Language model. Nhận bài ngày 16 tháng 8 năm 2017 Hoàn thiện ngày 26 tháng 11 năm 2017 Chấp nhận đăng ngày 28 tháng 11 năm 2017 Địa chỉ: 1Viện Công nghệ Thông tin, Viện KHCNQS; 2Trung tâm tin học, Trường Đại học Nội vụ Hà Nội. * Email: thanhnc80@gmail.com.