Phương pháp phát hiện sao chép dữ liệu văn bản

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (4.62 MB, 24 trang )

Trang 1<div class="page_container" data-page="1">

MỞ ĐẦU 1. Tính cấp thiết của đề tài

Với sự phát triển nhanh chóng của Cơng nghệ thông tin trong những năm gan đây đã tạo nên sự thay đổi to lớn trong tat cả các lĩnh vực

khác nhau. Nhiều quốc gia trong đó có Việt Nam xem Công nghệ thông

tin như công cụ đột phá trong phát triển kinh tế xã hội. Bên cạnh những

thành tựu đạt được, nhiều thách thức mới cũng đã xuất hiện như vấn đề

an tồn thơng tin, vấn đề q tải thông tin, vấn đề ngăn ngừa thông tin độc hại. Đặc biệt, van dé sao chép dit liệu văn bản bang các hình thức khác nhau trên Internet được xem là một vẫn nạn phổ biến được cộng đồng quan tâm nghiên cứu.

Sao chép dữ liệu văn bản xuất hiện bằng nhiều hình thức khác

nhau cịn gọi là đạo văn. Có nhiều hình thức ăn cắp dir liệu văn bản khác

nhau: cắt, dán, sao chép nguyên bản, sao chép từng đoạn, sao chép ý tưởng, dịch không xin phép. Những hình thức sao chép như trên tạo nên một thói quen nguy hiểm trong các hoạt động giáo dục đào tạo, nghiên

cứu khoa học và nhiều lĩnh vực liên quan khác. Một nghiên cứu về hiện trạng sao chép kết quả học tập của sinh viên ở Anh cho thấy 70% sinh

viên thú nhận có sao chép một phan trong các bài tập, 40% thú nhận sử dụng biện pháp cắt dán khi hoàn thành bài tập, 10% sinh viên Mỹ, Uc,

Anh bảo vệ kết quả học tập bằng các kết quả sao chép. Chính vì vậy, việc xây dựng các phương pháp và công cụ tự động nhận biết một tài liệu là “sao chép” hay “không sao chép” thu hút được cộng đồng nghiên cứu trong 10 năm gần đây.

Có nhiều phương pháp và cơng nghệ khác nhau đã được đề xuất dé phát hiện sao chép dữ liệu văn bản tiếng Anh. Tuy nhiên, việc áp dụng

các phương pháp và công nghệ phát hiện sao chép dữ liệu văn bản cho

các ngôn ngữ khác nhau van là chủ đề mở cần được cộng đồng quan tâm

</div>Trang 2<div class="page_container" data-page="2">

nghiên cứu. Dé tài: “Phương pháp phát hiện sao chép dữ liệu văn

bản” thực hiện trong khuôn khổ luận văn tốt nghiệp thạc sỹ ngành hệ thống thông tin nhằm nghiên cứu các kỹ thuật phát hiện sao chép dữ liệu

văn bản. Đề tài được thực hiện với mục tiêu và phương pháp cụ thể như

dưới đây.

Cấu trúc của luận văn như sau: LỜI CAM ĐOAN

Chương 1 - TONG QUAN VE SAO CHEP VĂN BAN

1.1 Giới thiệu về sao chép văn bản

1.2 Các giai đoạn của quá trình sao chép văn bản1.3 Các kỹ thuật phát hiện sao chép văn bản

1.3.1 Phương pháp dựa trên ký tự

1.3.2 Phương pháp dựa trên cau trúc (Structural-based)

1.3.3 Phương pháp phân cụm (Cluster-Based) va phân loại (classification)1.3.4 Phương pháp dựa trên cú pháp(syntax-based)

1.3.5 Phương pháp xuyên ngôn ngữ(Cross Language-based)

</div>Trang 3<div class="page_container" data-page="3">

2.2 Phương pháp dựa vào cụm tù(Pharse-Based)

2.2.1 Phương pháp phát hiện sao chép toàn cục

2.2.2 Phương pháp phát hiện sao chép cục bộ

2.3 Phương pháp phát hiện sao chép văn bản dựa vào cấu trúc 2.4 Phát hiện sao chép dựa vào phương pháp ngữ nghĩa an

2.4.1 Cau trúc từ trong tiếng Việt

2.4.2 Tách từ trong văn bản tiếng Việt

2.4.3 Câu trúc từ trong tiếng Việt

2.4.4 Xác định độ tương tự văn bản — văn bản 2.5 Kết luận chương

Chương 3 - XÂY DỰNG HE THONG PHÁT HIỆN VÀ PHỊNG CHĨNG

SAO CHÉP DỮ LIỆU VĂN BẢN

3.1 Phát biêu bài toán 3.2 Thiết kế hệ thống

3.2.1 Biểu đồ phân rã chức năng

3.2.2 Mơ tả hệ thống

3.2.3 Tính tốn độ tương tự văn bản

3.3 Xây dựng phần mềm phát hiện sao chép trên ngôn ngữ VB.Net

</div>Trang 4<div class="page_container" data-page="4">

Chương 1 - TONG QUAN VE SAO CHEP DU LIEU

VAN BAN

1.1. Giới thiệu về sao chép dữ liệu văn bản

1.2. Các giai đoạn của quá trình phát hiện sao chép văn bản1.3. Các kỹ thuật phát hiện sao chép dữ liệu văn bản

Nội dung chính của mục này thảo luận về một số kỹ thuật phát hiện sao chép dữ liệu văn bản được đưa ra gần đây. Các kỹ thuật này có thê được phân loại thành: các phương pháp dựa trên ký tự

(Character-based), Phương pháp dựa trên cấu trúc (Structual-(Character-based), Phương pháp

phân cụm (Cluster-Based), Phương pháp phân loại (classification),

Phương pháp dựa trên cú pháp (syntax-based), Phương pháp xuyên ngôn ngữ (Cross language-based), Phương pháp Ngữ nghĩa ân

(Semantic-Based) và phương pháp trích dẫn (Citation-(Semantic-Based) [1].

1.3.1. Phương pháp dựa trên ký tự

1.3.2. Phương pháp dựa trên cấu trúc (Structural-based)

1.3.3.Phuong pháp phân cụm (Cluster-Based) và phân loại

1.3.4. Phương pháp dựa trên cú pháp (syntax-based)

1.3.5. Phương pháp xuyên ngôn ngữ (Cross Language-based)

1.3.6. Phương pháp ngữ nghĩa (semantic-based) 1.3.7. Phương pháp trích dẫn

1.4. Cac công nghệ phát hiện sao chép dữ liệu văn bản

1.5. Kết luận chương

Nội dung của Chương đã trình bày tổng quan về vấn đề sao chép

dữ liệu văn bản. Sao chép dữ liệu văn bản được thực hiện theo nhiều hình thức khác nhau địi hỏi các hệ thống phát hiện sao chép văn bản

</div>Trang 5<div class="page_container" data-page="5">

phải xây dựng phương pháp phát hiện phù hợp với từng kiểu sao chép. Các phương pháp phát hiện sao chép dữ liệu được thực hiện phổ biến là phương pháp dựa vào ký tự. Một số phương pháp khác được thực hiện

dựa vào cấu trúc văn bản và ngữ nghĩa văn bản. Dựa trên các phương

pháp này, nhiều hệ thống phát hiện sao chép dữ liệu văn bản đã được

xây dựng có tính thương mại cao.

Ở Việt Nam, mặc dù chưa có kết quả nghiên cứu chính thức về số

lượng người dùng dữ liệu văn bản có hành vi sao chép bất hợp pháp,

nhưng chắc chan đây cũng là van nạn phổ biến đang diễn ra trong nhiều

lĩnh vực khác nhau. Việc nghiên cứu và triển khai các phương pháp phát hiện sao chép dữ liệu văn bản tiếng Việt thành công sẽ là công cụ hữu

hiệu áp dụng cho nhiều tổ chức nghiên cứu và đào tạo. Trong những chương tiếp theo, em xin trình bày kết quả nghiên cứu của mình trong

lĩnh vực phát hiện sao chép tài liệu tiếng Việt,

</div>Trang 6<div class="page_container" data-page="6">

Chương 2 - PHƯƠNG PHÁP PHÁT HIỆN SAO CHÉP

DỮ LIỆU VĂN BẢN

2.1. Phương pháp Character-Based

Phương pháp phát hiện sao chép dựa vào ký tự biểu diễn văn bản như một dãy tuần tự các ký tự cho toàn bộ tài liệu. Do vậy, phương

pháp này có thê sử dụng phát hiện sao chép tài liệu tiếng Việt mà khơng

cần có sự thay đổi nào. Phương pháp phát hiện sao chép tài liệu dựa vào

ký tự được chia thành hai phương pháp chính: phương pháp toàn bộ

(Full) và phương pháp cục bộ (Selective) []. Phương pháp toàn cục áp

dụng cho toàn bộ văn bản, phương pháp cục bộ áp dụng cho từng đoạn văn bản. Nội dung cụ thé của hai phương pháp như dưới đây.

2.1.1. Phương pháp Character-Based toàn cục

Đối với phương pháp toàn phần, văn bản nghi ngờ được phân tích

thành tập hợp tat cả các xâu ký tự con độ dài k. Vi dụ, với văn bản D có

độ dài IDI=5 chứa duy nhất một từ “touch”. Khi đó, “touc’, “ouch” là

tập các từ độ dài 4. Tổng quát, cho văn bản D độ dai IDI, số các xâu ký tự độ dài & có thể có là IDI-k+/ và được gọi là k-grams. Khi đó, việc so

sánh sự giống nhau giữa hai văn bản được đưa về việc ước lượng mức

độ sự giống nhau giữa các xâu con độ dài k.

Có nhiều phương pháp khác nhau để ước lượng mức độ giống

nhau giữa hai văn bản. Phương pháp đơn giản nhất dé so sánh mức độ giống nhau giữa hai văn ban A và văn bản B được tính tốn theo cơng thức (1).

R= Tr (1)

Trong đó,

</div>Trang 7<div class="page_container" data-page="7">

e |Al số lượng K-grams phân tích từ văn A.

® R là mức độ tương tư giữa văn ban A va văn bản D.

se Nlà số lượng k-grams xuất hiện trong cả văn bản A và văn bản B.

Dé dàng nhận thấy 0< R <7 vì nếu N=0 thì R = 0, nếu =lAl thì R

= 1. Với N=0 tương ứng với trường hợp khơng có bat kỳ một xâu con

độ dài k nào của văn bản B xuất hiện trong văn bản A. Khi đó, ta có thể

kết luận văn bản B không được sao chép từ văn ban A. Với N=/ tương

ứng với trường hợp toàn bộ các xâu con độ dài k của văn bản B đều xuất

hiện trong văn ban A. Khi đó, ta có thể kết luận B sao chép nguyên ban

từ A. Với 0< R </( ví dụ R = 0.35) ta sẽ xác định được tỉ lệ phần trăm

sao chép giữa hai văn bản. Tóm lại, phương pháp tồn cục phát hiện saochép dữ liệu văn bản dựa vào ký tự được thực hiện thơng qua ba bước chính

như sau:

Bước 1. Sử dụng k-grams, phân tích văn bản thành tập các chuỗi

ký tự kgrams.

Bước 2. Xác định mức độ giống nhau giữa các văn bản dựa vào

k-grams đã được phân tích.

Bước 3. Trả lại văn bản có độ giống nhau lớn nhất giữa các văn bản.

Thực nghiệm và đánh giá kết quả kết quả:

Phương pháp Character-Based được tiến hành thực nghiệm trên cả

hai loại văn bản tiếng Việt và tiếng Anh. Đối với tiếng Anh, lấy một bài báo khoa học nguyên bản bằng tiếng Anh và dịch thành tiếng Việt làm

dữ liệu kiểm tra. Thay đổi nội dung bài báo dịch sang tiếng Việt trong

các trường hợp dưới đây dé phát hiện mức độ sao chép dữ liệu văn bản.

</div>Trang 8<div class="page_container" data-page="8">

Trường hợp 1: Phát hiện sao chép 20%. Thay đôi nội dung bài dịch tiếng Việt khoảng 80% và thực hiện phát hiện sao chép.

Trường hợp 2: Phát hiện sao chép 50%. Thay đôi nội dung bài

dịch tiếng Việt khoảng 50% và thực hiện phát hiện sao chép.

Trường hợp 3: Phat hiện sao chép 80%. Thay đôi nội dung bài

dịch tiếng Việt khoảng 20% và thực hiện phát hiện sao chép.

Trường hợp 4: Phát hiện sao chép nguyên bản . Giữ nguyên nội dung bài dịch tiếng Việt làm dữ liệu kiểm tra sao chép.

Trường hợp 5: Không phát hiện sao chép văn bản tiếng Việt . Lay một tài liệu Việt khác khơng liên quan gì đến tài liệu ké trên làm dit liệu kiểm tra sao chép.

Trường hợp 6: Phát hiện sao chép xuyên ngôn ngữ 20%. Sử dụng Google Translate API dịch 20% phần tiếng Việt thành

tiếng Anh và thực hiện tiễn hành phát hiện phan dữ liệu đã dịch sang tiếng Anh.

Trường hợp 7: Phát hiện sao chép xuyên ngôn ngữ 40%. Sử

dụng Google Translate API dịch 40% phần tiếng Việt thành

tiếng Anh và thực hiện tiễn hành phát hiện phan dữ liệu đã dịch

sang tiếng Anh.

Trường hợp 8: Phái hiện sao chép xuyên ngôn ngữ 60%. Sử dụng Google Translate API dịch 60% phần tiếng Việt thành

tiếng Anh và thực hiện tiến hành phát hiện sao chép phần dữ liệu đã dịch sang tiếng Anh.

Trường hợp 9: Phát hiện sao chép xuyên ngôn ngữ 80%. Sử

dụng Google Translate API dịch 80% phần tiếng Việt thành

</div>Trang 9<div class="page_container" data-page="9">

tiếng Anh và thực hiện tiến hành phát hiện sao chép phần dữ liệu đã dịch sang tiếng Anh.

e Trường hợp 10: Phái hiện sao chép nguyên bản xuyên ngôn ngữ. Su dụng Google Translate API dịch ban tiéng Viét thanh

tiếng Anh sau đó thực hiện tién hành phát hiện sao chép.

Vì phương pháp dựa vào ký tự phụ thuộc vào k-grams biéu diễn

văn ban. Do vậy em tiến hành phân tích văn bản sử dụng 4-grams, 10-grams, 16-grams và 32-grams. Kết quả kiểm nghiệm phát hiện sao chép được thể hiện trong Bang 2.1.

Bảng 2.1. Giá trị R phát hiện mức độ sao chép văn bản

Phát hiện | Giá trị của R ứng với các trường hợp phát hiện sao chépsao chép 4-grams 10-grams 16-grams 32-grams

</div>Trang 10<div class="page_container" data-page="10">

Đánh giá kết qua thử nghiệm:

Phát hiện sao chép nguyên bản (Trường hợp 4). Giá trị của R

luôn là 1 trong tất cả các phép thử 4-grams, 10-grams,

16-grams và 32-16-grams. Tuy nhiên, về thực tế trường hợp có xảy ra

nhưng là trường hợp dễ phát hiện nhất. Kết quả này cũng hoàn

toàn phù hợp với các loại văn bản tiếng Anh.

Không phát hiện sao chép (Trường hợp 5). Cho lại kết quả

khá tốt mặc dù kết quả giao nhau giữa các 4-grams lên đến

6.1%. Tuy nhiên, giá trị này vẫn đủ tốt dé ta có kết luận khơng

sao chép dữ liệu văn bản.

Trường hợp sao chép 20%, 50%, 80% (Trường hợp, 1, 2, 3):

Kết quả phát hiện sao chép dữ liệu văn bản tiếng Việt sử dụng

4-grams, 10-grams, 16-grams trong các trường hợp này thường

cao hơn kết quả thực tế. Kết quả này hoàn toàn phù hợp với văn bản tiếng Việt hoặc tiếng Anh vì với k đủ nhỏ sẽ tồn tại nhiều &-grams trùng lặp giữa các van bản khác nhau mặc dù họ tác giả

khơng có ý định sao chép. Riêng với trường hợp sử dụng

32-grams, kết quả cho lại thường thấp hơn thực tế vì khi & đủ lớn

</div>Trang 11<div class="page_container" data-page="11">

-

l]-các chuỗi ký tự trùng lặp sẽ bị hạn chế ít đi. Trong kiểm nghiệm

này, em nhận thấy sử dụng /6-grams cho văn bản tiếng Việt cho kết quả hợp lý hơn các trường hợp cịn lại.

e Trường hợp phát hiện sao chép xun ngơn ngữ (Truong

hợp 6, 7, 8, 9, 10). Luận văn đã mạnh dạn đề xuất việc thử nghiệm phát hiện sao chép văn bản tiếng Việt bằng cách sử dụng Google Translate API. Mặc dù sử dụng kết quả của Google Translate API chưa thé dùng được cho văn phong tiếng Việt và các tài liệu chuyên ngành. Tuy vậy, kết quả dịch bằng

Google Translate sang tiếng Việt vẫn phản ánh đúng hầu hết những từ dùng trong bản dịch ở mức độ nhất định. Kết quả

kiêm nghiệm cũng cho thấy, mặc dù giá trị của R thấp hơn giá

trị thực đối với các văn bản thuần Việt nhưng cũng vẫn chấp

nhận được trong kết luận sao chép văn bản trong một số trường hợp. Ví dụ với trường hợp dịch nguyên bản tiếng Việt thành tiếng Anh, kết quả phát hiện sao chép đều đạt trên 80%. Nếu sử

dụng Google Translate cùng với 16-grams và 32-grams thì kết quả đạt đến trên 90%. Kết quả này đủ tốt để cho phép chúng ta

khẳng định văn bản tiếng Việt được dịch nguyên bản từ bản tiếng Anh.

2.1.2. Phương pháp Character-Based cục bộ

Phương pháp dựa toàn phần dựa vào ký tự phát hiện khá tốt trong các trường hợp dữ liệu văn bản sao chép nguyên bản hoặc một phần của

tài liệu gốc. Tuy nhiên, nếu văn bản bị nghi ngờ sao chép chỉ thực hiện sao chép một đoạn hoặc một trang từ văn bản gốc thì phương pháp cho lại kết quả không mong muốn. Để hạn chế nhược điểm này, phương

</div>Trang 12<div class="page_container" data-page="12">

-

12-pháp ký tự cục bộ thực hiện tách và so sánh mỗi đoạn của văn bản A với

mỗi đoạn của văn bản B dé tìm ra độ tương tự giữa các đoạn văn bản. Bài toán được đặt ra như sau.

2. 2. Phương pháp dựa vào cụm từ (Pharse-Based)

Phương pháp phát hiện sao chép dữ liệu văn bản dựa vào ký tự cho lại kết quả khá tốt trong các trường hợp khác nhau. Tuy vậy, điểm hạn chế lớn nhất của phương pháp là việc sử dụng k-grams cho ký tự đòi hỏi

tài nguyên lưu trữ khá lớn và mat nhiều thời gian so sánh các k-grams.

Dé hạn chế nhược điểm này ta có thể xem mỗi văn bản như là tập hợp

các từ sử dụng trong văn bản. Khi đó, bài tốn phát hiện sao chép dữ liệu văn bản được được đưa về bài toán so sánh giữa tập các từ hoặc cụm từ trong các văn bản khác nhau. Phương pháp phát hiện sao chép dữ liệu

văn bản dựa vào cụm từ cũng được chia thành hai hướng tiếp cận: phương pháp phát hiện sao chép toàn cục và phương pháp phát hiện sao chép cục bộ. Điểm khác biệt duy nhất giữa hai hướng tiếp cận là đơn vị

tính tốn mức độ sao chép của phương pháp tồn cục là cả tập văn bản,

trái lại phương pháp phát hiện sao chép cục bộ thực hiện trên mỗi đoạn

văn bản. Nội dung cụ thể mỗi phương pháp được thực hiện như dưới đây.

2.2.1. Phương pháp phát hiện sao chép toàn cục

2.2.2. Phương pháp phát hiện sao chép cục bộ

2.3. Phương pháp phát hiện sao chép văn bản dựa vào cấu trúc

Phương pháp phát hiện sao chép dữ liệu văn ban dựa vào cau trúc cũng được phân thành hai loại: phương pháp phát hiện sao chép cấu trúc toàn bộ và phương pháp phát hiện cấu trúc từng phần. Nhiệm vụ của

phương pháp phát hiện sao chép cấu trúc toàn bộ là xác định mức độ

giông nhau về câu trúc giữa hai văn bản. Nhiệm vụ của của phương pháp

</div>Trang 13<div class="page_container" data-page="13">

-

13-phát hiện sao chép cấu trúc cục bộ là định mức độ giống nhau từng phân

về cấu trúc giữa hai văn bản [].

Có nhiều đề xuất khác nhau giải quyết bài toán phát hiện sao chép

cấu trúc văn ban. Phương pháp hiệu quả nhất phải kế đến là các phương

pháp tô chức cây cấu trúc văn bản dựa vào cây nhiều nhánh, cây tìm

kiếm và dựa vào hàm băm []. Một số phương pháp khác sử dụng lại kết

quả của phương pháp Character-Based hoặc Pharse-Based. Ưu điểm của phương pháp này là đơn giản, dễ cài đặt và tận dụng triệt để ngữ nghĩa

các từ khóa và có thé triển khai phương pháp dựa vào câu