Một số BTL cho kỳ hè 2013
Bài 1. Thống kê từ file log
Dữ liệu log về quảng cáo trong 1h được ghi ra các file log, mỗi trường được ngăn cách nhau bởi dấu tab (\t)
Nội dung các trường theo thứ tự
0 time create
1 browser code
2 browser version
3 os code
4 os version
5 device code
6 bannerId
7 ip
8 geoId
9 domain
10 path
11 ref url
12 click or view
13 cookie create time
14 guid
15 appid
16 sdk version
17 zoneId
18 campaign id
21 screen width
22 screen height
24 manufactory id
Cần thống kê:
- Số lượng thiết bị (Device) (Các thiết bị không xác định sẽ được gom lại thành 1 nhóm)
- Thống kê Pageview theo domain và theo từng page
Dữ liệu các bạn có thể tài về từ
https://drive.google.com/folderview?id=0B5nb3v94xY_WSFFxMmRiQ1hDN3M&usp=sharing
Bài 2. Cài đặt thuật toán Seamcarving dùng để resize lại ảnh
Mô tả thuật toán này các bạn có thể tìm tại
https://drive.google.com/folderview?id=0B5nb3v94xY_WSFFxMmRiQ1hDN3M&usp=sharing
Với ảnh màu RGB bạn có thể chọn một trong những cách sau đây
- Chuyển về ảnh mức xám
- Xử lý các thành phần màu RAG như 1 số nguyên 3 Byte
- xử lý từng thành phần màu R,G,B riêng rẽ
Bài 3. Xây dựng gợi ý khi gõ văn bản
Khi gõ một hoặc một số ký tự, chương trình sẽ tự động suggest nốt phần còn lại của từ
Ý tưởng: Dùng prefix Tree
Yêu cầu: Xây dựng prefix tree và áp dụng để suggest một số từ thông dụng cho từ điển tiếng Anh
(Từ điển có thể tải về từ
https://drive.google.com/folderview?id=0B5nb3v94xY_WSFFxMmRiQ1hDN3M&usp=sharing), file
mword10.zip, dùng file COMMON.TXT hoặc COMPOUND.TXT
Bài 4. Xây dựng thuật toán sinh màn chơi SODOKU theo các mức khó
Cài đặt thuật toán mô tả trong bài báo sau
http://zhangroup.aporc.org/images/files/Paper_3485.pdf
Tham khảo thêm tại
Bài 5. Xây dựng chương trình tự động suggest và sửa lỗi chính tả (tiếng Anh)
Với một văn bản tiếng Anh được nhập từ bàn phím, hoặc file, chương trình sẽ làm những việc sau:
- Phát hiện những từ sai chính tả (VD: Đầu dòng, đoạn phải viết hoa, những từ ko có trong từ điển), và đánh dấu bằng màu khác hoặc tô đậm
- Với những từ không có trong từ điển, chương trình có thể gợi ý những cách sửa (đưa ra 1 vài gợi ý dựa trên thuật toán tìm khoảng cách sửa đổi gần nhất của 2 xâu - Levenshtein Edit Distance)
(Từ điển có thể tải về từ
https://drive.google.com/folderview?id=0B5nb3v94xY_WSFFxMmRiQ1hDN3M&usp=sharing), file
mword10.zip, dùng file COMMON.TXT
Tham khảo
Bài 6: Thuật toán sinh mê cung
Yêu cầu: Sinh mê cung kích thước nxn bất kỳ
Đầu ra: Vẽ minh họa mê cũng sinh được (với trường hợp n nhỏ thì hiển thị trên màn hình, còn n lớn có thể ghi ra file), dùng các ký hiệu VD. _, | để minh họa
Tham khảo
Demo
Bài 7: Đưa ra từ gợi ý dựa trên n-gram (+2 điểm)
http://en.wikipedia.org/wiki/N-gram
n-gram là chuỗi n từ được đi liền với nhau (có thể có nghĩa hoặc không có nghĩa)
Ví dụ: với xâu "In the fields of computational linguistics and probability, an n-gram is a contiguous sequence of n items from a given sequence of text or speech. The items can be phonemes, syllables, letters, words or base pairs according to the application. The n-grams typically are collected from a text or speech corpus."
1-gram là các từ đứng rời In, the, fields, of, computational,....
2-gram là các cặp 2 từ liền nhau: In the, the fields, fields of, of computational,....
3-gram là các nhóm 3 từ liền nhau: In the fields, the fields of, fields of computational,....
tương từ với 4-gram, 5-gram
Đầu vào: là tập văn bản reuters21578
http://www.daviddlewis.com/resources/testcollections/reuters21578/
format của các văn bản này các bạn xem thêm tại:
http://www.daviddlewis.com/resources/testcollections/reuters21578/readme.txt
Yêu cầu:
- Lọc lấy tiêu đề và nội dung của các bài viết
- Tách và sinh ra các n-gram (1,2,3,4,5-gram)
- Thống kê tần số xuất hiện của các gram (không phân biệt hoa thường, và có phân biệt hoa thường)
- Gợi ý từ dựa trên các n-gram thống kê được
VD. Với dữ liệu mẫu là 3 gram ở trên thì khi người dùng gõ vào từ "In" ta có thể gợi ý các cặp là "In the", "In the fields".
Trong thực tế thì ta có thể chọn các cặp n-gram có tần số xuất hiện lớn nhất để đưa ra trước, nhưng vì tần số xuất hiện này còn tỉ lệ với độ dài gram. Do đó việc đưa ra các từ gợi ý dựa trên (tần số xuất hiện của gram)/(tổng số các n-gram).
Ví dụ. Có 2500 2-gram và 1000 3-gram
cụm 2-gram "In the" có tần số xuất hiện 15 lần thì tỉ lệ của nó sẽ là 15/2500
cụm 3-gram "In the fields" có tần số xuất hiện 7 lần thì tỉ lệ là 7/1000
Vậy khi đưa ra gợi ý ta sẽ đưa ra cụm "In the fields" trước cụm "In the"
Chú ý: Các cụm gram này dừng tại các dấu câu.
VD. câu "In the fields of computational linguistics and probability, an n-gram is a contiguous sequence of n items from a given sequence of text or speech."
được tách thành 2 phần
"In the fields of computational linguistics and probability"
"an n-gram is a contiguous sequence of n items from a given sequence of text or speech"
để đảm bảo các n-gram không chứa các dấu như , . : ? ! ;
Tham khảo thêm tại
- http://en.wikipedia.org/wiki/N-gram
- http://nlpwp.org/book/chap-ngrams.xhtml
- http://www.ngrams.info/
- https://drive.google.com/folderview?id=0B5nb3v94xY_WSFFxMmRiQ1hDN3M&usp=sharing
Bài 8: Xây dựng chương trình kiểm tra một biểu thức dạng trung tố có hợp lệ
Một
biểu thức dạng trung tố
- Toán tử có thể 1 ngôi hoặc 2 ngôi, chỉ gồm 1 ký tự
- Toán hạng: nếu là số thì có thể có 1 hoặc nhiều chữ số được viết liên nhau, nếu là chữ cái thì chỉ có 1 ký tự
- Các toán tử và toán hạng được viết liền nhau, giữa chúng không có khoảng cách trống
- Chỉ có một loại dấu ngoặc tròn
Ví dụ một số biểu thức hợp lệ
A=a+345-23*12+(a-34/2)
B=b+(45+a/3+(52-4*a))
C=|45+a*(2-7/b)|/23*a
Hãy viết chương trình kiểm tra biểu thwucs hợp lệ, với biểu thức có thể được nhập vào từ file hoặc từ bàn phím
