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

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