Nguyên cứu ứng dụng các kỹ thuật Big data trong hệ thống phát hiện sao chép
MỞ ĐẦU
Lý do chọn đề tài
Ngày nay, cùng với sự phát triển vượt bậc của ngành CNTT nói chung và hệ thống mạng Internet nói riêng, việc mọi người có thể tạo ra các tài liệu mới, chia sẻ và tìm kiếm thông tin trở nên dễ dàng và phổ biến. Chính vì điều này cũng tạo ra những mặt trái làm ảnh hưởng tiêu cực đến việc bảo đảm quyền tác giả, tác phẩm của một số công trình nghiên cứu như việc sao chép các bài báo, tài liệu nghiên cứu, báo cáo thực tập, khóa luận tốt nghiệp, luận văn,… được công khai phát tán, chỉnh sửa ngay cả khi không được sự đồng ý của tác giả. Nhận thấy đây là một vấn đề nghiêm trọng đối với việc chia sẻ thông tin nên nếu điều này không được giải quyết, nó sẽ làm cho tác giả không muốn chia sẻ tài liệu của mình và làm giảm cơ hội cho người muốn sử dụng truy cập những thông tin có giá trị.
Những nghiên cứu phát hiện sao chép và trùng khớp chuỗi văn bản đã cho ra đời nhiều công cụ hiệu quả và có thể sử dụng trực tuyến như Plagiarism Checker Software, Turnitin, …. Tuy nhiên, ngày nay có rất nhiều nguồn dữ liệu được lấy từ rất nhiều nguồn khác nhau như âm thanh, đoạn phim, hình ảnh, nguồn dữ liệu đầu vào rất là đa dạng hoặc một tập hợp dữ liệu rất lớn và rất phức tạp đến nỗi những công cụ, ứng dụng xử lý dữ liệu truyền thống không thể nào đảm đương được. Mặt khác, khi mà nguồn tài liệu ngày càng dồi dào, các kho tài liệu trở nên quá đồ sộ khiến cho việc lưu trữ trở nên khó khăn, một hệ thống máy tính không thể lưu trữ đủ mà việc lưu trữ phải được phân tán, chia nhỏ ra để lưu trữ trên nhiều hệ thống máy tính khác nhau. Điều này làm cho các công cụ xử lý dữ liệu truyền thống không còn hoạt động hiệu quả, do vấn đề quản lý dữ liệu, việc đọc ghi dữ liệu trở thành vấn đề mà các hướng tiếp cận xử lý dữ liệu đều phải tập trung giải quyết.
Dữ liệu nói chung và dữ liệu dưới dạng các văn bản điện tử đang tăng lên nhanh chóng. Theo thống kê thì cứ sau mỗi năm, dữ liệu tăng lên hơn gấp đôi so với dữ liệu của năm trước đó. Số lượng nội dung kỹ thuật số trên web hiện nay đạt xấp xỉ năm trăm tỷ gigabyte và con số này dự kiến sẽ tăng gấp đôi trong vòng một năm. Sự bùng nổ của các mạng di động, điện toán đám mây và các công nghệ mới đã làm tăng gần như không thể kiểm soát nguồn thông tin trên thế giới. Sự cần thiết của việc quản lý một cách hiệu quả nguồn dữ liệu ngày càng tăng theo cấp số nhân này đã được rất nhiều nhà khoa học quan tâm và thực hiện. Dữ liệu không chỉ cần phải được xử lý và phân tích nhanh, mà một yêu cầu khác cũng cần phải được quan tâm đầu tư là bảo đảm dữ liệu được sao lưu một cách đảm bảo để không bị mất dữ liệu. Đồng thời, chúng ta cũng cần có cơ chế để tránh sự trùng lặp hay sap chép lẫn nhau giữa các tài liệu. Điều này đặc biệt quan trọng khi vấn đề bản quyền, quyền tác giả ngày càng được thực thi một cách nghiệm túc.
Các kỹ thuật về big data đã được phát triển nhằm mục đích giải quyết vấn đề về cách tổ chức và xử lý dữ liệu khi kho dữ liệu ngày càng trở nên quá lớn. Tuy nhiên, chúng ta vẫn phải đối mặt với vấn đề về lưu trữ và phân tích dữ liệu nhằm đáp ứng yêu cầu của người sử dụng. Vấn đề mà chúng ta phải đối mặt là: trong khi khả năng lưu trữ của ổ đĩa cứng đã tăng mạnh trong những năm qua, tốc độ truy cập – tốc độ dữ liệu có thể được đọc từ ổ đĩa đã không bắt kịp. Phải mất một thời gian khá lâu để đọc tất cả các dữ liệu trên một ổ đĩa và thời gian để ghi dữ liệu thậm chí còn chậm hơn. Cách rõ ràng và đơn giản nhất để giảm thời gian xử lý dữ liệu là chúng ta cần phải đọc và ghi dữ liệu từ nhiều đĩa cùng một lúc. Bên cạnh việc thu giảm thời gian xử lý, làm việc song song còn giúp tiết kiệm các chi phí về đầu tư nguồn lực cho các máy tính có không gian lưu trữ và khả năng xử lý lớn, bằng cách tận dụng nhiều máy tính có khả năng lưu trữ và năng lực xử lý thấp hơn. Xử lý và phân tích dữ liệu trong thời gian tối thiểu có thể là vô cùng quan trọng trong khoa học xử lý dữ liệu nói riêng và trong khoa học máy tính ngày nay nói chung.
Các công cụ quản lý dữ liệu truyền thống như hệ quản trị CSDL quan hệ (RDBMS), không còn chứng minh được khả năng xử lý của chúng trong việc xử lý tình trạng bùng nổ dữ liệu như hiện nay. Để theo kịp với quy mô tăng trưởng một cách bùng nổ của dữ liệu, đặc biệt là các hệ dữ liệu lớn, các kho dữ liệu phân tán có quy mô lớn là phương tiện cần thiết để tổ chức, lưu trữ và đáp ứng khả năng mở rộng khi khối lượng dữ liệu tăng.
Những khó khăn trên là động lực để chúng tôi thực hiện luận văn này với đề tài là “Nguyên cứu ứng dụng các kỹ thuật Big data trong hệ thống phát hiện sao chép”, nhằm mục đích nghiên cứu và xây dựng công cụ phát hiện sao chép có thể thực hiện được với các kho tài liệu tiếng Việt.
Luận văn này cung cấp một cách nhìn tổng quan về các phương pháp mới trong việc xử lý các tập dữ liệu lớn, bằng cách sử dụng kỹ thuật MapReduce. Luận văn cũng tập trung vào nghiên cứu khung thức Hadoop và hệ thống tập tin phân bố Hadoop (Hadoop Distributed File System), trong đó sử dụng thuật toán MapReduce để quản lý số lượng dữ liệu lớn và khả năng mở rộng cao, bằng cách phân chia các tập dữ liệu lớn trên nhiều máy chủ và cơ chế xử lý song song từng phần và sau đó kết hợp các kết quả xử lý của từng phần lại với nhau để sản sinh ra câu trả lời cuối cùng. Trong đó, luận văn này áp dụng các kỹ thuật, khung thức và giải thuật đã nghiên cứu vào việc giải quyết bài toán xây dựng hệ thống phát hiện sao chép bằng kỹ thuật big data, mà cụ thể đó là thuật toán MapReduce trên nền khung thức Hadoop.
Mục đích nghiên cứu
Mục đích nghiên cứu của đề tài là xây dựng ứng dụng trong đó sử dụng phương pháp MapReduce để xử lý dữ liệu trên các kho dữ liệu lớn, để so khớp và phát hiện nội dung giống nhau giữa các tài liệu văn bản.
Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu của đề tài là cấu trúc tài liệu dạng văn bản, phương pháp và kỹ thuật tách câu Tiếng Việt, các thuật toán tìm kiếm và so khớp mẫu, và các kỹ thuật xử lý trong lĩnh vực big data để xử lý việc tìm kiếm, so trùng, phát hiện sao chép trên các kho dữ liệu lớn và phân bố.
Trong khuôn khổ của luận văn, tôi chỉ giới hạn việc nghiên cứu các phương pháp, các kỹ thuật có liên quan đến việc tách câu, tách từ trong tiếng Việt, nghiên cứu các giải thuật xử lý big data và triển khai thử nghiệm trên các kho dữ liệu mẫu. Luận văn chưa thực hiện trên các kho dữ liệu thực tế quy mô lớn.
Phương pháp nghiên cứu
Về phương pháp nghiên cứu, tôi đã sử dụng hai phương pháp chính là nghiên cứu lý thuyết và nghiên cứu thực nghiệm.
Phương pháp nghiên cứu tài liệu: Với phương pháp này, chúng tôi nghiên cứu các ứng dụng kỹ thuật và cách biễu diễn dữ liệu trong big data, các kỹ thuật tách câu, tách từ trong tiếng Việt, các thuật toán tìm kiếm, so khớp, và phát hiện sao chép, nghiên cứu các tài liệu liên quan đến big data và các giải thuật cũng như các kỹ thuật xử lý dữ liệu trong big data.
Phương pháp thực nghiệm: Với phương pháp này, chúng tôi ứng dụng kỹ thuật xử lý big data vào hệ thông phát hiện sao chép, nghiên cứu ngôn ngữ lập trình phù hợp (ngôn ngữ java) và hiện thực các kỹ thuật này trong ngôn ngữ lập trình. Chúng tôi cũng đã xây dựng chương trình và chạy thử nghiệm.
Ý nghĩa của đề tài
Về khoa học: Kết quả nghiên cứu của đề tài góp phần mở ra một hướng nghiên cứu cũng như ứng dụng mới, đó là việc ứng dụng các kỹ thuật xử lý big data vào bài toán so trùng và phát hiện sao chép.
Về thực tiễn: Đề tài sẽ góp phần nâng cao chất lượng trong quản lý, nâng cao chất lượng đào tạo cũng như góp phần hạn chế vấn đề vi phạm bản quyền, vấn đề sao chép lẫn nhau giữa các tài liệu.

Cấu trúc luận văn
Cấu trúc của luận văn bao gồm có 3 chương:
Chương 1: Nghiên cứu tổng quan
Chương 2: Phân tích ứng dụng và đề xuất giải pháp
Chương 3: Phát triển ứng dụng
NGHIÊN CỨU TỔNG QUAN
Chương này trình bày kết quả nghiên cứu các nội dung tổng quan về dữ liệu lớn (big data); đặc điểm của câu, từ trong văn bản tiếng Việt; phương pháp tách câu, tách từ trong văn bản tiếng Việt; các giải thuật so khớp mẫu; phần cuối của chương giới thiệu một số ứng dụng tương tự trong lĩnh vực so sánh trùng khớp cũng như tính toán độ tương tự giữa các văn bản nhằm mục đích hỗ trợ việc phát hiện sao chép giữa các tài liệu văn bản.
Dữ liệu lớn (Big Data) là một thuật ngữ được định nghĩa một cách lỏng lẻo dùng để mô tả các bộ dữ liệu rất lớn và phức tạp mà các ứng dụng xử lý dữ liệu truyền thống không xử lý được. Bao gồm các cách thức phân tích, thu thập, giám sát dữ liệu, tìm kiếm, chia sẻ, lưu trữ, truyền nhận, trực quan hóa, truy vấn và tính riêng tư. Thuật ngữ này thường đơn giản là sử dụng để phân tích dự đoán hoặc là một số phương pháp tiên tiến khác để trích xuất giá trị từ dữ liệu, mà ít khi đề cập đến kích thước của bộ dữ liệu. Dữ liệu lớn, như tên gọi của nó, có kích thước quá lớn, thay đổi quá nhanh và thường không thể lưu trữ tập trung, và thường không phù hợp với các cấu trúc của kiến trúc cơ sở dữ liệu.
Đến đây, chắc chắn chúng ta sẽ có câu hỏi là “Vậy dữ liệu lớn đến cỡ nào thì được coi là big data?”. Câu trả lời là tuỳ vào dữ liệu mà chúng ta đang xử lý. Có những dữ liệu kích thước nhỏ nhưng mà lại là “lớn”, và cũng có những dữ liệu kích thước lớn mà lại là “nhỏ”. Ví dụ, hệ thống của chúng ta hoạt động trong vòng 10 năm và tạo ra các tập tin nhật ký (tập tin log), các tập tin này đơn thuần là các tập tin văn bản ghi lại các thao tác của người dùng chẳng hạn. Tổng dung lượng của chúng có thể chỉ là vài trăm gigabyte (kích thước nhỏ) nhưng nó lại là “lớn” để tiến hành phân tích, do đó có thể coi đó là một ngưồn big data. Ngược lại, chúng ta có thể có hàng ngàn tập tin video, mỗi tập tin kích thước khoảng vài chục GB. Như vậy, tổng cộng nguồn dữ liệu của chúng ta có thể lên đến hàng chục hoặc hàng trăm tetrabyte (kích thước lớn), nhưng nó lại là nhỏ khi tiến hành phân tích và không phải là big data.
Sau đây là một vài ví dụ về các big data trên thế giới: Công ty Google đã tăng từ việc xử lý khoảng 100 TB dữ liệu mỗi ngày với MapReduce vào năm 2004 đến xử lý 20 PB một ngày với MapReduce vào năm 2008. Vào tháng tư năm 2009, công ty bán hàng trực tuyến eBay đã sở hữu hai kho dữ liệu khổng lồ: một kho với khoảng 2 PB dữ liệu người dùng, và kho khoảng 6,5 PB dữ liệu người dùng với hơn 170 ngàn tỷ hồ sơ và ngày càng tăng lên nhanh chóng với thêm 150 tỷ hồ sơ mới mỗi ngày.
Thực tế là các kho dữ liệu hiện tại đã là rất lớn và chúng còn đang tăng trưởng một cách nhanh chóng theo cấp số mũ. Các nguồn dữ liệu này không chỉ xuất phát từ con người (như nguồn thu thập từ các mạng xã hội) mà còn từ máy tính (các loại thông tin nhật ký được tạo bởi máy tính) và các vệ tinh (nguồn dữ liệu thu thập từ vệ tinh) được tạo ra liên tục dẫn đến vấn đề là làm thế nào chúng ta có thể giải quyết nguồn dữ liệu lớn và tăng trưởng liên tục như vậy. Hai yếu tố cần được quan tâm để giải quyết vấn đề này là:
- Xử lý dữ liệu nhanh
- Nguồn lưu trữ dữ liệu đáng tin cậy
Từ là đơn vị sẵn có trong ngôn ngữ. Từ là đơn vị nhỏ nhất, cấu tạo ổn định, mang nghĩa hoàn chỉnh, đựợc dùng để cấu thành Câu. Từ có thể làm tên gọi của sự vật (danh từ), chỉ các hoạt động (động từ), trạng thái, tính chất (tính từ), … Từ là công cụ biểu thị khái niệm của con người đối với hiện thực.
Câu là một tập hợp từ, ngữ kết hợp với nhau theo những quan hệ cú pháp xác định, được tạo ra trong quá trình tư duy, giao tiếp, có giá trị thông báo, gắn liền với mục đích giao tiếp nhất định. Nói đến cấu trúc câu là nói đến các thành phần tạo câu cùng với chức năng, mối quan hệ qua lại và sự phân bố chúng trong tổ chức nội bộ câu. Dựa vào vai trò tạo câu, các thành phần câu được chia thành ba loại lớn: thành phần nòng cốt, thành phần phụ và thành phần biệt lập.
Để tách một văn bản ra thành các đơn vị câu độc lập thường dựa vào các dấu hiệu kết thúc câu (dấu chấm “.”, dấu chấm than “!” và dấu chấm hỏi “?”, …). Nhưng vẫn có những câu mà dấu hiệu kết thúc câu vẫn chưa phải là kết thúc câu, đó là các ngoại lệ.
Văn bản tiếng Việt đặt dấu cách giữa các âm tiết chứ không phải giữa các từ. Một từ có thể có một, hai hoặc nhiều âm tiết nên có nhiều cách phân chia các âm tiết thành các từ, gây ra nhập nhằng. Hiện nay có nhiều phương pháp tiếp cận bài toán tách từ, nhưng luận văn này chỉ đề cập đến phương pháp sử dụng mô hình n-gram.
Với mô hình n-gram, chúng ta coi một văn bản, đoạn văn bản là chuỗi các từ liền kề nhau w1w2…wn và sau đó phân tích xác suất của chuỗi với công thức xác suất kết hợp:
p(w1w2…wn) = p(w1) * p(w2/w1) * p(w3/w1w2) *…* p(wn/w1w2…wn-1)
Một phép toán cơ bản trên chuỗi là “so khớp mẫu” (pattern matching). Bài toán này được định nghĩa như sau: Cho trước một chuỗi văn bản có độ dài là n và một mẫu có độ dài m, hãy tìm sự xuất hiện của mẫu trong văn bản. Để tìm tất cả các sự xuất hiện của mẫu trong văn bản, chúng ta thực hiện bằng cách quét qua toàn bộ văn bản một cách tuần tự. Bài toán “so khớp mẫu” có đặc trưng là một bài toán tìm kiếm, trong đó mẫu được xem như là khóa.
- GIỚI THIỆU MỘT SỐ THUẬT TOÁN
Chúng tôi tìm hiểu về 5 giải thuật cơ bản nhất trong so sánh chuỗi đó là: Knuth–Morris–Pratt, Boyer–Moore, Rabin–Karp, Brute–Force, Naïve.
- Thuật toán Knuth–Morris–Pratt
- Thuật toán Boyer-Moore
- Thuật toán Rabin-Karp
- Thuật toán Brute-Force
- Thuật toán Naïve
Đánh giá các thuật toán so khớp mẫu: Ta nhận thấy việc tìm kiếm bằng Brute–Force có thể là rất chậm đối với một số mẫu nào đó, ví dụ nếu chuỗi cần xét là một chuỗi nhị phân thì trong trường hợp xấu nhất là khi cả mẫu thử đểu là số 0 và kết thúc bởi một số 1. Khi đó, chúng ta cần phải thực hiện n–m+1 phép so sánh. Mặt khác thường thì m rất nhỏ so với n, như vậy số phép so sánh ký tự xấp xỉ bằng m * n.
Thuật toán Knuth–Morris–Pratt không bao giờ dùng nhiều hơn m+n phép so sánh ký tự, từ đó ta dễ nhận thấy thuật toán này dùng ít phép toán so sánh hơn Brute–Force. Tuy nhiên trong ứng dụng thực tế thì thuật toán Knuth–Morris–Pratt nhanh hơn không đáng kể so với thuật toán Brute–Force.
Thuật toán Boyer–Moore không dùng nhiều hơn m+n phép so sánh ký tự. Thuật toán là tuyến tính trong trường hợp cùng cách cài đặt với thuật toán Knuth–Morris–Pratt, thông thường thì Boyer–Moore không tuyến tính. Trong thực tế, khi các ký tự văn bản không xuất hiện trong mẫu thì mỗi phép so sánh dẫn đến mẫu sẽ dịch sang phải m ký tự, vì vậy đối với văn bản lớn và mẫu thử không dài thì thuật toán phải dùng n/m bước.
Còn thuật toán Rabin–Krap gần như là tuyến tính. Số phép so sánh theo thuật toán này là m+n, thuật toán chỉ đi tìm một vị trí trong văn bản có cùng giá trị mảng băm với mẫu.
Trong phần này, chúng tôi thực hiện việc khảo sát qua các công cụ, các hệ thống có chức năng tính độ tương tự giữa tài liệu cũng như phát hiện sao chép giữa các tài liệu. Các công cụ này có chức năng tương tự với hệ thống mà luận văn này sẽ xây dựng.
- Phần mềm Plagiarism Checker
- Công cụ Turnitin.com
- Công cụ Scanmyessay.com
- Công cụ Ithenticate.com
- Công cụ Copyscape.com
- Công cụ Plagspotter.com
PHÂN TÍCH ỨNG DỤNG VÀ ĐỀ XUẤT GIẢI PHÁP
Chương 2 này tập trung phân tích mô hình và ứng dụng phát hiện sao chép tài liệu trong các kho dữ liệu, bằng cách sử dụng kỹ thuật xử lý dữ liệu của big data. Để làm tăng hiệu quả cho hệ thống phát hiện sao chép trong các kho dữ liệu lớn, giải pháp được đề xuất như sau: Xây dựng mô hình đặc trưng cho các văn bản trong tập dữ liệu đầu vào, dựa trên các phương pháp tách từ và tách câu trong tiếng Việt; ứng dụng các thuật toán tìm kiếm và so khớp mẫu như đã tìm hiểu trong Chương 1; áp dụng chúng vào trong mô hình đặc trưng cũng như các công cụ xử lý big data.
- MÔ HÌNH ỨNG DỤNG PHÁT HIỆN SAO CHÉP
Hình 2.1 trình bày về mô hình ứng dụng phát hiện sao chép tài liệu bằng cách áp dụng các kỹ thuật big data. Trong đó, nhưng khối chức năng mà chúng ta cần phải giải quyết là:
Kho tài liệu có sẵn
N-Grams
Tài liệu cần kiểm tra
Bộ sưu tập tài liệu đã có
Hệ thống phát hiện sao chép bằng kỹ thuật
Big Data
– Những sao chép từ các tài liệu trong kho.
-Vị trí.
-Tên tài liệu
Hình 2.1. Mô hình ứng dụng phát hiện sao chép
- Hệ thống quản lý kho dữ liệu big data: Để thao tác với kho dữ liệu big data, chúng ta cần phải có hệ thống quản lý tương ứng. Trong lĩnh vực big data, dữ liệu thường không thể lưu trữ ở một máy (thậm chí là máy chủ) mà phải phân tán ở nhiều máy tính khác nhau. Trong luận văn này, chúng tôi tìm hiểu và vận dụng hệ thống quản lý tập tin phân tán của Hadoop để quản lý kho dữ liệu của hệ thống.
- Giải thuật song song thực hiện việc phát hiện và so trùng mẫu: Với hệ thống tập tin phân tán đã tổ chức, chúng ta cần sử dụng các giải thuật song song để thực thi trên hệ thống phân tán này. Với giải thuật xử lý song song, chúng ta có thể thu được kết quả trong khoản thời gian nhanh hơn. Giải thuật xứ lý song song được đề xuất trong luận văn này là giải thuật MapReduce. Chi tiết về giải thuật này cũng được chúng tôi trình bày trong phần sau.
- Ngoài hai khối chức năng chính nêu trên, luận văn còn phải áp dụng một số vấn đề đã được tìm hiểu trong Chương 1 vào ứng dụng phát hiện sao chép tài liệu như cách thức phân tích các từ, câu; mô hình cũng như phương pháp đánh giá trọng số về độ tương tự giữa các câu, các văn bản. Để tính trọng số về độ tương tự giữa các văn bản, luận văn sử dụng trong số Jaccard.
Trong các phần sau, chúng tôi lần lượt đi tìm hiểu và vận dụng các hệ thống, các giải thuật nêu trên vào ứng dụng của mình.
Khi kích thước của tập dữ liệu vượt quá khả năng lưu trữ của một máy tính, tất yếu sẽ dẫn đến nhu cầu hân chia dữ liệu lên trên nhiều máy tính. Các hệ thống tập tin quản lý việc lưu trữ dữ liệu trên một mạng nhiều máy tính gọi là hệ thống tập tin phân tán. Do hoạt động trên môi trường liên mạng, nên các hệ hống tập tin phân tán phức tạp hơn rất nhiều so với một hệ thống tập tin cục bộ. Ví dụ như một hệ hống tập tin phân tán phải quản lý được tình trạng hoạt động (live/dead) của các máy chủ tham gia vào hệ thống quản lý tập tin này. Hadoop mang đến cho chúng ta hệ thống tập tin phân tán HDFS (viết tắt từ Hadoop Distributed File System) với nỗ lực tạo ra một nền tảng lưu trữ dữ liệu đáp ứng cho một khối lượng dữ liệu lớn và chi phí rẻ. Trong phần này, chúng tôi sẽ giới thiệu kiến trúc của HDFS cũng như cách vận dụng nó.
F:\DỮ LIỆU COP CỦA CHỊ YẾN\DAI HOC DA NANG\KHOA HOC MAY TINH\LE NGOC QUYEN
Nguyên cứu ứng dụng các kỹ thuật Big data trong hệ thống phát hiện sao chép


