Posted on by mtoplistChuyên mục:Top List

Chuẩn hóa văn bản.

(Bản hoàn chỉnh, phiên bản ngày 25/9. Cần để ý theo dõi các chỉnh sửa bổ sung mới nếu có phát sinh)

Hạn nộp bài: 23:59′ ngày thứ Sáu 5/10/2012.

Ngôn ngữ viết dùng cho SMS, comment, blog, chat… có rất nhiều kiểu viết không theo như chính tả được quy định trong từ điển. Chẳng hạn đối với tiếng Việt có một số hình thức như:

1. Viết tắt (vd. ko thay cho không),

2. Ghi âm phương ngữ (vd. iu thay cho yêu),

3. Không bỏ dấu (vd Anh dang hoc thay cho Anh đang học).

…

Để có thể dùng loại văn bản này cho các tác vụ xử lý tự động thông thường đối với văn bản ngôn ngữ, chẳng hạn như tổng hợp tiếng nói, dịch máy, lọc ngữ nghĩa, cần có bước chuẩn hóa chính tả.

Chủ đề của bài tập này là xây dựng một thư viện nhỏ phục vụ công việc chuẩn hóa tiếng Việt và thử nghiệm thư viện đó.

Thư viện được đặt trong các lớp có tên SpellChecker và Rule.

SpellChecker có các phương thức sau:

  1. boolean loadRuleBase(String filename) nạp các quy tắc từ một file và hủy các quy tắc đã nạp trước đó nếu có. Nội dung của file là các quy tắc chuẩn hóa (ví dụ: ko thay bằng không, iu thay bằng yêu) theo định dạng như sau: Mỗi quy tắc nằm trên 1 dòng với cú pháp: 
    <in>:<space><out>

    trong đó, <in> là một chuỗi kí tự không chứa dấu hai chấm “:”; <space> chỉ bao gồm đúng 01 kí tự space; <out> là chuỗi kí tự kéo dài cho đến hết dòng. Trong mỗi file không có hai dòng nào có phần in giống nhau. Khi chạy chương trình, file này được đảm bảo chứa toàn dữ liệu đúng định dạng, bạn không cần phải kiểm tra. Trong hoặc sau khi nạp, cần sắp xếp danh sách các quy tắc theo thứ tự giảm dần. Xem mô tả về lớp Rule để biết về quan hệ lớn hơn/nhỏ hơn giữa các quy tắc.

  2. String fix(String input) chuẩn hóa xâu input theo các quy tắc đã nạp, trả về kết quả là xâu đã chuẩn hóa. Thuật toán rất đơn giản: duyệt từng quy tắc đã nạp, với mỗi quy tắc, áp dụng cho xâu input cho đến khi không thể áp dụng được quy tắc đó nữa. Với các bộ quy tắc phức tạp, thứ tự áp dụng quy tắc có thể dẫn đến các kết quả chuẩn hóa khác nhau. Ở đây, ta duyệt theo thứ tự đã được sắp xếp khi nạp file.

Rule: mỗi đối tượng Rule đại diện cho một quy tắc chuẩn hóa. Mỗi đối tượng SpellChecker có một danh sách quy tắc. Với các bộ quy tắc phức tạp, thứ tự thực hiện khác nhau có thể dẫn đến các kết quả khác nhau với chất lượng khác nhau. Do đó cần có một thứ tự ưu tiên thực hiện giữa các quy tắc và danh sách quy tắc nói trên cần được sắp thứ tự. Trong bài này, ta dùng một thứ tự ưu tiên đơn giản sau: Giữa mỗi cặp quy tắc (in, out), có một quan hệ sắp thứ tự, gọi tên là “lớn hơn”/”nhỏ hơn” được định nghĩa như sau:

  1. Quy tắc nào có phần in dài hơn là quy tắc “lớn hơn”.
  2. Nếu hai quy tắc có phần in có độ dài bằng nhau thì quy tắc có phần in đứng sau theo thứ tự từ điển (không phân biệt chữ hoa/thường) là quy tắc “lớn hơn”. Nếu quy tắc r1 “lớn hơn” quy tắc r2 thì r2 được coi là “nhỏ hơn” r1, và ngược lại.
  3. Nếu hai quy tắc có phần in giống hệt nhau thì quy tắc nào có phần out đứng sau theo thứ tự từ điển sẽ là quy tắc “lớn hơn”.

Ý nghĩa của (1) là để ưu tiên thực hiện các quy tắc phức tạp hơn trước các quy tắc đơn giản hơn. Mục đích của (2) và (3) là để chúng ta thống nhất một thứ tự áp dụng giữa các quy tắc không thể đánh giá ưu tiên theo (1).

Như vậy, ngoài các biến thực thể dành cho in và out, class Rule còn cần phương thức int compareTo(Rule r) để kiểm tra quan hệ “lớn hơn”/”nhỏ hơn”. Nếu đối tượng chủ “lớn hơn” đối tượng r thì phương thức trả về một giá trị dương, nếu nhỏ hơn thì trả về giá trị âm, nếu bằng nhau thì trả về 0.

SpellCheckerTest:
Thư viện SpellChecker trên không phải là một chương trình sẵn sàng để chạy.
Để thử nghiệm thư viện, sau khi thu bài, giáo viên sẽ dùng một chương trình test chức năng fix của thư viện SpellChecker của bạn theo các bộ test có dạng như sau: Mỗi bộ test (test set) gồm 1 file chứa quy tắc chính tả (như định dạng ở trên, kèm theo là các cặp input/output của các trường hợp test trong bộ đó.

Bạn cũng cần tự viết một chương trình SpellCheckerTest và thiết kế dữ liệu test cũng như cách test để tự kiểm thử SpellChecker trước khi nộp bài. Cần thiết kế và thực hiện tổng cộng ít nhất 10 test case trong các bộ test. Yêu cầu tối thiểu là test chức năng fix, nhưng cố gắng phủ tất cả các trường hợp, và lưu ý thông qua việc test SpellChecker.fix để test cả các lớp khác và các phương thức khác.

Ví dụ về một bộ test phương thức fix() của SpellChecker cùng với file quy tắc RULES.DAT

File RULES.DAT: 

e: em
a: anh
b h: bây giờ
b: nhưng
h: giờ
k: không
j`: gì
dc: được
uh: ừ

Các test case

STTInputOutputGhi chú
1

bao h e di dc ?
bao giờ em di được ?

Test này kiểm tra trường hợp đơn giản, không ảnh hưởng thứ tự sắp xếp. Chú ý có dấu cách giữa dc và ? thì mới đọc riêng được từ ‘dc’.

2

b h la may h?
bây giờ la may h?

quy tắc “b h” lớn hơn quy tắc “b” nên được xét áp dụng trước. Test này kiểm tra việc sắp xếp thứ tự các quy tắc.

Nộp bài

Bài đặt trong project có tên asg01 tại Bitbucket, cấp quyền đọc cho cả hai giáo viên chauttm và diepbp.
Nội dung cần nộp gồm có:

  1. Mã nguồn các lớp Rule, SpellChecker, SpellCheckerTest (và các lớp khác nếu có viết thêm và dùng đến) đặt trong thư mục có tên src
  2. Các bộ test bạn đã chạy với bản SpellCheckerTest của mình. Đặt trong thư mục có tên tests của project.
  3. Một file README.txt đặt tại thư mục gốc của project chứa các thông tin: họ và tên, mã sinh viên, lớp, hướng dẫn biên dịch, kết quả kiểm thử chương trình với các bộ test tự tạo hoặc thu thập.

Ví dụ, giả sử thư mục chứa các bài làm môn OOP là C:\OOP\, project cho assignment 01 của bạn đã được checkout thành thư mục C:\OOP\asg01. Khi đó, thư mục C:\OOP\asg01\src sẽ chứa các file Rule.java, SpellChecker.java, SpellCheckerTest.java, C:\OOP\asg01\tests\ chứa dữ liệu cho các bộ test, C:\OOP\asg01\README.txt là file giới thiệu về bài làm của bạn. Khi chạy test, bạn có thể chạy bằng lệnh java SpellCheckerTest khi đứng trong thư mục C:\OOP\asg01\src (tất nhiên là sau khi đã biên dịch thành công tại đó). Đừng dùng cấu trúc thư mục khác vì như vậy có thể nảy sinh rắc rối về đường dẫn khi giáo viên chấm bài tự động.

Khuyến cáo:

  • Bài được chấm tự động, output của mỗi test cần chính xác đến từng kí tự để được coi là đúng.
  • Bài mà giáo viên không thu được do nộp muộn hoặc thiếu quyền đọc sẽ không được thu bổ sung.
  • Những sinh viên có mã nguồn giống nhau đáng kể sẽ nhận điểm 0 cho bài tập lớp và điểm F cho môn học.
  • Sinh viên được khuyến khích trao đổi dữ liệu test.

mtoplist