Bài tập lớn CTDL & GT cho lớp chiều thứ 2 (tiết 1-4)
Yêu cầu chung:
- Sinh viên tự đề xuất thuật toán dựa trên yêu cầu của đề bài
- Tự chọn CTDL phù hợp và giải thích vì sao mình chọn CTDL đó
- Đánh giá hiệu quả về thời gian và bộ nhớ của thuật toán
Đây là các đề bài xuất phát từ yêu cầu thực tế, rất khó có thuật toán cho kết quả chính xác 100% (Điểm đánh giá sẽ ưu tiên các thuật toán nào cho kết quả tốt hơn)
Dữ liệu đầu vào:
Dữ liệu cho tất cả cacsc bài tập ở dưới được Download theo link sau:
https://www.dropbox.com/s/k7y57sqsy5qzrkl/TechCrunch_Files.rar?dl=0
- Các tập dữ liệu đầu vào được lấy từ các bài viết mới gần đây trên trang công nghệ TechCrunch, và ở dạng ngôn ngữ tiếng Anh.
- Các bài viết được tổ chức thành từng file riêng theo dạng 0001.txt, 0002.txt,... (có khoảng gần 5K bài viết)
- Format của mỗi bài viết gồm
- Dòng đầu tiên là tiêu đề : title
- Dòng tiếp là tác giả: author
- Dòng tiếp là ngày được xuất bản : publish date
- Các dòng tiếp theo là nội dung bài viết
- Trong bài viết có nhiều ngoại lệ (exception), sinh viên nên tự phát hiện và loại bỏ để tăng độ chính xác (VD. các thông tin phụ ở cuối bài viết)
Dữ liệu đầu ra:
- Sinh viên nên tổ chức dữ liệu đầu ra dưới dạng file văn bản để dễ theo dõi
Sinh viên có thể dùng các hệ quản trị CSDL đễ hỗ trợ tổ chức và lưu trữ dữ liệu (tuy nhiên điều này không được khuyến khích)
Bài 1. Phát hiện các danh từ riêng, tên riêng trong các văn bản
Sắp xếp các danh từ này theo tần số xuất hiện trên toàn bộ tập văn bản, và trên số lượng văn bản mà nó xuất hiện
Hai cặp danh từ được coi là cùng xuất hiện nếu chúng xuất hiện gần nhau (trong khoảng cách 2-3 câu)
Những danh từ nào có tần số xuất hiện nhiều nhất?
- Trên toàn bộ tập văn bản (mỗi từ được tính nhiều lần nếu xuất hiện nhiều lần ở cùng 1 văn bản)
- Trên nhiều văn bản nhất (mỗi từ chỉ được tính 1 lần xuất hiện trong 1 văn bản)
Cặp danh từ nào được xuất hiện nhiều nhất?
VD với văn bản
A recent article in
TechCrunch characterized nascent upstarts in the restaurant industry as wide-eyed idealists with little reality of the harsh, high-touch operating environment in which they operate. Having worked in the tech, food and health worlds for most of my career, I believe the article misrepresented the significant progress being made across the industry. On almost every front within hospitality — be it point of sale, loyalty, delivery or sourcing — change is in the air.
For all the talk of the
Aloha and
MICROS point of sale (
POS) systems dominanting in restaurants, a bevy of newcomers have been making inroads. Square, with its slick reader and now retail
POS terminal, carries the most gravitas among the mobile
POS companies for good reason: it inks deals with large retailers:
Starbucks in 2012, then
Whole Foods,
Uniqlo and
Godiva in 2014. Granted, none of these establishments switched over an entire store to
Square, but these relationships suggest large retailers will embrace new technology.
Danh từ riêng được in đậm
- là các từ có ít nhất 1 chữ in hoa
- Không chấp nhận các từ ở đầu câu hoặc đầu đoạn
- Các từ hoa liền nhau (ngăn cách bởi 1 dấu cách trống) nên nối thành 1 từ dài
- Các từ hoa liền nhau ngăn cách từ >= 2 dấu cách trống thì nên tách riêng ra.
- Nếu mà phân biệt được các từ viết tắt thì càng tốt (các từ mà tất cả các ký tự đều viết hoa)
Cặp danh từ trong phạm vi 2 câu là
- {Aloha - MICROS} - POS
- POS - {Starbucks - Whole Foods - Uniqlo - Godiva}
- {Starbucks - Whole Foods - Uniqlo - Godiva} - Square
Bài 2. Thống kê tên thương hiệu (sản phẩm)/ công ty được đề cập trong bài báo
Với các danh từ riêng trong bài báo ta cần phân ra được thành
- Tên địa điểm, vị trí
- Tên người
- Tên sản phẩm/ tên công ty
Làm sao phân biệt được tên địa điểm, tên người với các tên riêng khác ?
- Tên địa điểm, vị trí, thời gian: gần đó thường có các giới từ như at, in, on
- Tên người: gần đó thường có sở hữu cách:'s hoặc of
- Tên sản phẩm/ tên công ty:
Nếu không làm được ==> tự xây dựng từ điển tên công ty/ sản phẩm bằng tay (không khải thi cho lắm nếu chạy trên dữ liệu thực tế - khoảng vài tỷ bài viết)
Công ty / sản phẩm nào được đề cập đến nhiều nhất ?
Bài 3. sản phẩm nào là của công ty nào được đề cập trong các bài báo?
VD. Apple : iphone, ipad,....
Làm thế nào biết được sản phẩm nào của công ty nào?
- Phát hiện tên công ty
- Tên sản phẩm
- Thường có các từ đặc trưng để kết nối như: a product of, a service of,....
Bài 4. Tìm các bài viết đánh giá tốt hoặc xấu về một sản phẩm/ thương hiệu của công ty
- Phát hiện ra các tên công ty, tên sản phẩm
- Các tính từ đánh giá như : good, bad, worse,, (sinh viên tự xây dựng từ điển)
Các tính từ này phải nằm gần các câu chứa các danh từ thương hiệu (trong phạm vi khoảng 2-3 câu)
Bài 5. Hai văn bản được coi là có liên quan đến nhau nếu có tập danh từ riêng trùng nhau nhiều
- Tìm các tập danh từ riêng của 2 văn bản
- Xác định tập danh từ riêng trùng nhau của 2 văn bản
- Quyết định xem 2 văn bản có liên quan đến nhau hay không dựa trên ngưỡng (số lượng từ trùng nhau trên tổng số danh từ riêng của cả 2 văn bản). Ngưỡng này do sinh viên tự đề xuất!
Với 1 bài đang đọc, hãy đưa ra danh sách các bài viết có liên quan (được sắp xếp theo thứ tự độ liên quan giảm dần)
Để đảm bảo yêu cầu về thời gian xử lý, sinh viên có thể cần tính trước độ liên quan của các bài viết và đưa vào file tạm.
Bài 6. n-gram là các cụm từ liên tiếp nhau (ở đây ta quan tâm tới 2-gram và 3-gram)
Ta chỉ xét các n-gram trong phạm vi một bộ phận câu (bị ngăn cách bởi các dấu câu như dấu ! dấu . dấu : dấu - )
Dấu , được bỏ qua
VD. Với văn bản
I believe the article misrepresented the significant progress being made across the industry. On almost every front within hospitality — be it point of sale, loyalty, delivery or sourcing — change is in the air.
Ta có các bộ phận câu như
- I believe the article misrepresented the significant progress being made across the industry
- On almost every front within hospitality
- be it point of sale, loyalty, delivery or sourcing
- change is in the air
Với câu
Ta có các 3-gram là:
- change is in
- is in the
- in the air
Hai văn bản liên quan đến nhau (thường là trùng nhau hoặc cùng một chủ đề) nếu có số lượng n-gram trùng nhau nhiều.
Hãy tìm các văn bản trùng/ có liên quan đến văn bản hiện tại dựa trên 3-gram (hoặc 2-gram)
Ngưỡng trùng do sinh viên tự đề xuất.
