Bài tập lớn CTDLGT học kỳ hè 20133

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

• http://stackoverflow.com/questions/9295537/sudoku-generator-algorithm
• http://www.codeproject.com/Articles/23206/Sudoku-Algorithm-Generates-a-Valid-Sudoku-in
• http://dryicons.com/blog/2009/08/14/a-simple-algorithm-for-generating-sudoku-puzzles/

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:

1. 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
2. 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

• http://web.stanford.edu/class/cs124/lec/med.pdf
• http://en.wikipedia.org/wiki/Levenshtein_distance
• http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance

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

• http://en.wikipedia.org/wiki/Maze_generation_algorithm
• http://www.mazeworks.com/mazegen/mazetut/
• http://stackoverflow.com/questions/38502/whats-a-good-algorithm-to-generate-a-maze

Demo

• http://www.mazegenerator.net/

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:

1. Lọc lấy tiêu đề và nội dung của các bài viết
2. Tách và sinh ra các n-gram (1,2,3,4,5-gram)
3. 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)
4. 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