Phương pháp mã hóa văn bản thành chuỗi số DNA để đánh giá mức độ giống nhau của văn bản

Bài báo này trình bày phương pháp mã hóa văn bản thành các chuỗi số duy nhất, được gọi tên là chuỗi DNA nhằm giải quyết bài toán đánh giá mức độ giống nhau của một văn bản với tập văn bản khác có trong kho dữ liệu để ứng dụng trong phát hiện sao chép văn bản.
Nội dung trích xuất từ tài liệu:
Phương pháp mã hóa văn bản thành chuỗi số DNA để đánh giá mức độ giống nhau của văn bản Hồ Phan Hiếu, Nguyễn Thị Ngọc Anh và Võ Trung Hùng 223 Phương pháp mã hóa văn bản thành chuỗi số DNA để đánh giá mức độ giống nhau của văn bản Hồ Phan Hiếu, Nguyễn Thị Ngọc Anh và Võ Trung Hùng The University of Danang, 41 Leduan St., Danang City, Vietnam hophanhieu@ac.udn.vn, ngocanhnt@ued.udn.vn, vthung@dut.udn.vn Tóm tắt. Trong bài báo này, chúng tôi trình bày phương pháp mã hóa văn bản thành các chuỗi số duy nhất, được gọi tên là chuỗi DNA nhằm giải quyết bài toán đánh giá mức độ giống nhau của một văn bản với tập văn bản khác có trong kho dữ liệu để ứng dụng trong phát hiện sao chép văn bản. Chúng tôi thực nghiệm trên bộ dữ liệu của PAN với các mức ngưỡng từ ε = 10-5 đến ε = 10-10 và cho thấy khi lựa chọn ngưỡng ε = 10-10 cho kết quả có độ chính xác prec trên 98% và rec gần 97% trong việc phát hiện sự giống nhau của văn bản. Kết quả thực nghiệm cho thấy phương pháp đề xuất có độ chính xác rất cao và có thể triển khai vào thực tế tại Đại học Đà Nẵng. Từ khóa: Mã hóa văn bản, chuỗi DNA, độ tương đồng, phát hiện sao chép. 1 Giới thiệu Trên thế giới, các kết quả nghiên cứu về đánh giá độ tương đồng (mức độ giống nhau) trong văn bản tiếng Anh đã có nhiều công trình nghiên cứu và nhiều ứng dụng hữu ích, trong đó có bài toán phát hiện “sao chép” hay “đạo văn” [1-3]. Tuy nhiên, vấn đề này vẫn còn nhiều thách thức cần được nghiên cứu. Tuy đã có nhiều nghiên cứu và hệ thống phát hiện sao chép văn bản, nhưng đến này vẫn chưa có cơ sở chung nào để đánh giá hiệu quả của chúng. Trong khi đó, ở Việt Nam cũng mới bắt đầu có các nhóm nghiên cứu về lĩnh vực này [4, 5] và cũng có rất ít nhóm xây dựng hệ thống ứng dụng vào thực tiễn hoặc thương mại hóa. Bên cạnh đó, các vấn đề trong xử lý ngôn ngữ tự nhiên, tìm kiếm và so khớp nội dung tài liệu văn bản là lĩnh vực đang được cộng đồng khoa học trong và ngoài nước quan tâm. Đối với các bài toán xử lý văn bản, việc biểu diễn văn bản là một bước tiền xử lý rất quan trọng. Mô hình biểu diễn văn bản truyền thống như mô hình túi từ và không gian vectơ là các mô hình được sử dụng phổ biến nhất [6, 7]. Qua nghiên cứu, chúng tôi đã thực nghiệm phương pháp đánh trọng số và biểu diễn văn bản dựa trên mô hình vector ứng dụng trong bài toán phát hiện sao chép văn bản [8, 9]. Mặc dù, các phương pháp dựa trên mô hình vector đã được ứng dụng để phát hiện sao chép văn bản. Tuy nhiên, phương pháp biểu diễn theo vector vẫn còn hạn chế về số chiều biểu diễn cho tập văn bản sẽ rất lớn nên tốn không gian lưu trữ, độ phức tạp của thuật toán khi so sánh tăng và làm giảm tốc độ tính toán. Chính vì vậy, chúng tôi đã nghiên cứu và đề ra giải pháp mới để giải quyết bài toán này tối ưu hơn, đó là chuyển từ văn bản sang chuỗi số để tận dụng những ưu điểm về số trong xử lý dữ liệu lớn, tìm kiếm nhanh và độ chính xác cao. Chúng tôi đề xuất hướng giải quyết bài toán dựa trên phép biến đổi Wavelet rời rạc (DWT) và sử dụng bộ lọc Haar [10, 11]. Trong bài báo này, chúng tôi tập trung trình bày cách mã hóa văn bản thành các chuỗi số riêng biệt, được gọi tên là chuỗi DNA và thực nghiệm trên bộ dữ liệu thực tế của PAN với các mức ngưỡng lựa chọn ε = 10-5 đến ε = 10-10 đánh giá kết quả đạt được và ứng dụng để phát triển hệ thống thử nghiệm. 224 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA 2018 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC 2 Cơ sở lý thuyết liên quan 2.1 Biến đổi Wavelet rời rạc (DWT) Phương pháp biến đổi Wavelet rời rạc (Discrete Wavelet Transform - DWT) mã hóa đơn giản và nhanh nên được sử dụng rất hiệu quả trong xử lý tín hiệu số. DWT cho tín hiệu một chiều được mô tả sơ lược như sau: Tín hiệu được chia thành hai phần, đó là phần tần số cao và phần tần số thấp; thành phần tần số thấp lại được chia tiếp thành hai phần có tần số cao và thấp; các bước như vậy gọi là lấy mẫu giảm xuống. Bên cạnh đó, độ phức tạp của mã hóa là tuyến tính và hỗ trợ nhiều mức phân giải. Phân tích đa phân giải sử dụng các kỹ thuật lọc tín hiệu số trong quá trình phân tích để lọc nhiễu và xác định tín hiệu bất thường [12, 13]. Phân tích đa phân giải có khả năng như hai bộ lọc tín hiệu, trong đó mỗi một tín hiệu được phân tích thành hai thành phần gồm: Thành phần xấp xỉ A tương ứng với thành phần tần số thấp và thành phần chi tiết D tương ứng với thành phần tần số cao, thông qua hai bộ lọc thông thấp sử dụng hàm tỉ lệ Φ(x) và bộ lọc thông cao sử dụng hàm Wavelet ψ(x). Mối quan hệ giữa hàm tỉ lệ và hàm Wavelet được cho bởi: N 1  ( x)   Ck . (2x  k ) (1) k 0 N 1  ( x)   (1)k Ck . (2x + k  N  1) (2) k 0 trong đó, Ck là chỉ số vô hướng nhằm xác định các hệ số tỷ lệ. Các phép lọc được tiến hành với nhiều tầng khác nhau và để giảm khối lượng tính toán, khi qua mỗi bộ lọc, tín hiệu được lấy mẫu giảm xuống hai lần. Ứng với mỗi tầng, tín hiệu có độ phân giải khác nhau nên DWT được gọi là phân tích đa phân giải. Tại mỗi tầng, biểu thức của phép lọc được cho bởi công thức sau: high  y (n)  S (n).g (2k  n) (3) n y (n)   S (n).h(2k  n) (4) low n trong đó, S(n) là tín hiệu; h(n) là đáp ứng xung của các bộ lọc thông thấp tương ứng với hàm tỉ lệ Φ(n); g(n) là đáp ứng xung của các b ...