Chương I: GIỚI THIỆU 1.1 Tính cấp thiết của đề tài Trong thời đại ngày nay, internet phát triển với quy mô rất rộng trên toàn thế giới và với tốc độ ngày càng nhanh. Đi cùng với sự phát triển của internet là sự phát triển của các trang mạng xã hội chẳng hạn như là Facebook, Google plus, twitter. và còn nhiều trang chia sẽ thông tin, hình ảnh khác. Để thấy được sự bùng nổ của các mạng xã hội như thế nào thông qua một vài thông tin và những con số đã nghiên cứu, tìm hiểu được ở 2 mạng xã hội nổi tiếng: Facebook [11]: · Trung bình 618 triệu người dùng hoạt động trên Facebook mỗi ngày.
· Trung bình hàng tháng có 680 triệu người dùng hoạt động trên Facebook thông qua thiết bị di động. · Có hơn 250 triệu hình ảnh được đăng tải và chia sẻ trên Facebook mỗi ngày. · Trung bình mỗi người dùng Facebook sử dụng mạng xã hội này 700 phút mỗi tháng, có 130 người bạn và chia sẻ 90 nội dung khác nhau hàng tháng. · 23% người dùng Facebook thường xuyên check tài khoản của mình tối thiểu 5 lần/ngày.
· 167 triệu người dùng ở Mỹ, chiếm đến hơn 50% dân số của quốc gia này. 70% số lượng người dùng còn lại của Facebook trải đều trên khắp toàn cầu. · Với 10,6 triệu người dùng tại Việt Nam là quốc gia đứng thứ 22 trong tổng số các quốc gia có lượng người dùng Facebook lớn nhất thế giới hiện nay. Google + [12]: · 540 triệu thành viên sử dụng.
· 1,5 tỷ bức ảnh được đăng tải trên mạng xã hội này mỗi tuần. 13 NGHIÊN CỨU PHÁT TRIỂN GIẢI PHÁP PHÁT HIỆN ẢNH TRÙNG NHAU Với sự bùng nổ dữ liệu như trên, thách thức đặt ra là làm sao quản lý những khối dữ liệu khổng lồ này. Với bài toán này hiện nay cũng đã có những nhiều phương pháp quản lý Một kỹ thuật loại trừ dữ liệu trùng nhau (data deduplication) là một kỹ thuật nén dữ liệu đặc biệt dùng để loại bỏ những bản sao của dữ liệu được lặp đi lặp lại. Kỹ thuật này được sử dụng để cải thiện việc lưu trữ và cũng có thể được áp dụng cho việc làm giảm các byte cần phải di chuyển qua lại trên mạng.
Quá trình phân tích diễn ra tiếp tục trong khi những phần khác được so sánh với các bản sao lưu và bất cứ khi nào có một sự tìm thấy sự trùng lấp, các phần dư thừa này sẽ được thay thế bằng một tham khảo đến phần lưu trữ. Với cùng một mẫu, thì việc trùng lại xảy ra hàng chục, hàng trăm, thậm chí hàng nghìn lần ( tần số trùng dữ liệu phụ thuộc vào kích thước vùng lưu trữ). Vài lợi ích của việc loại trừ dữ liệu trùng nhau: - Làm giảm số lượng lưu trữ cần thiết cho một tập các files. - Network data deduplication được dùng để giảm số lượng byte cần phải chuyển giữa các thiết bị đầu cuối, suy ra giảm được lượng băng thông cần thiết.
Chúng ta có thể bắt gặp rất nhiều trong tối ưu hóa mạng WAN. - Máy chủ ảo( Virtua Server) : giúp cho các tập tin hệ thống trên danh nghĩa là riêng biệt cho mỗi máy chủ ảo, nhưng nó được kết hợp lại thành một không gian lưu trữ duy nhất. Đồng thời cũng nhờ đó mà giúp cho việc sao lưu hoặc tạo nhân bản môi trường dễ dàng hơn. Bài toán loại trừ dữ liệu trùng nhau nêu trên là là rất cần thiết, ngoài data, byte ra thì ta còn có hình ảnh, nhạc, ứng dụng mà hiện nay facebook, picasa (google), itune (apple) cũng đang đi tìm lời giải tốt nhất cho mình.
Đề tài luận văn tập trung vào bài toán tìm kiếm dữ liệu trong tập dữ liệu lớn, từ đó cho ra kết quả ta mong muốn là đã tồn tại hay chưa. Đây là một phần quan trọng đóng vai trò quyết định trong tốc độ và điểm mấu chốt chính của toàn bộ hệ thống. 14 NGHIÊN CỨU PHÁT TRIỂN GIẢI PHÁP PHÁT HIỆN ẢNH TRÙNG NHAU 1.2 Phát biểu vấn đề Hình 1: Cấu trúc chính của hệ thống Hình 1 mô tả các thành phần chủ yếu của hệ thống quản lý ảnh và tìm ảnh trùng nhau. Gói Full Scan image nhận hình ảnh từ mạng bên ngoài và chuyển cho module Hash Join.
Module này thực hiện chuyển định dạng ảnh sang định dạng text và giải mã dữ liệu thành key tương ứng cho hình ảnh đó. Phần key này có đặc tính là hình ảnh khác nhau thì key được tạo ra cũng khác nhau và ngược lại. Tất cả các key được tạo ra sau module này được chuyển giao qua module quản lý (Manage Key). Module này sẽ tổng hợp và quản lý tất cả các key, dựa vào các câu truy vấn tìm hình ảnh mà module này cho ra kết quả phù hợp.
Vấn đề quan tâm của luận văn này là xây dựng module quản lý key (Manage Key) cho toàn bộ hệ thống. Nguyên tắc cơ bản của module này là thực hiện các thuật toán so trùng và tìm kiếm key. Do không gian và độ lớn của tập dữ liệu thực tế của chúng ta rất 15 NGHIÊN CỨU PHÁT TRIỂN GIẢI PHÁP PHÁT HIỆN ẢNH TRÙNG NHAU lớn, cho nên lúc thiết kế và hiện thực ta phải quan tâm đến vấn đề tốc độ xử lý, độ chính xác, tính mềm dẻo và khả năng mở rộng.3 Tóm tắt các giải pháp và các kết quả đạt được của đề tài: Kết quả đạt của đề tài là đưa ra được một mô hình hệ thống quản lý tập dữ liệu ảnh cho phép gắn kết với bất cứ kho dữ liệu hình ảnh nào. Mô hình hệ thống này giúp cho người dùng hay các doanh nghiệp sở đang sở hữu khối lương lớn hình ảnh như các trang mạng xã hội, các cty game, các công ty hình ảnh.
dễ dàng truy vấn và loại trừ được các cảnh trùng nhau một cách nhanh chóng. Bên cạch việc dễ dàng truy vấn, kết quả đạt được còn giúp cho các tổ chức, các doanh nghiệp giảm thiểu được việc phải lưu trữ quá nhiều ảnh dư thừa làm hao tổn tài nguyên và tiền bạc một cách hoan phí. Ngoài ra, vì quy mô của đề tài khá rộng lớn và phức tạp nên mô hình này cũng đã được chạy thử nghiệm một phần để đảm bảo tính khả thi và khả năng tìm kiếm nhanh mà đề tài đặt ra. Để có thể có được kết quả trên, đề tài đề xuất ra hai giải pháp tương ứng với hai bài toán con mà đề tài đã đưa ra: Giải pháp lưu trữ khối dữ liệu khá lớn.
Thay vì hệ thống phải lưu trữ và tìm kiếm trên hàng petabytes hình ảnh thì hệ thống chỉ cần chuyển các hình ảnh này sang các key tương ứng với hình ảnh đó, và chỉ việc tìm kiếm và quản lý trên tập dữ liệu key này. Tuy nhiên với tập dữ liệu key này nó vẫn còn khá lớn để có thể thực hiện một lần trên bộ nhớ chính của máy tính được, và các key được tao ra một cách ngẫu nhiên không liên tục nhau do đó sắp xếp các key sao cho việc tìm kiếm được thực hiện một cách tối ưu nhất có thể, bên cạnh đó vì khối lượng key chúng ta có được rất lớn, cho nên với hệ thống máy tính hiện nay chúng ta có được không thể đáp ứng được việc đưa toàn bộ khối dữ liệu này nạp vào bộ nhớ chính, do đó giải pháp phân hoạch tập dữ liệu này ra từng tập con nhỏ hơn để cho các hệ thống máy tính hiện nay có thể đáp ứng được. Giải pháp cho việc phân hoạch các key: Và dựa trên ý tưởng của hệ thống Haystack của facebook các dữ liệu của hình ảnh sẽ được gom nhóm thành những file có kích thước trung bình từ 100-200 megabytes. Những key có giá trị liên tiếp nhau sẽ được gom lại thành từng file và khi file này có độ lớn vượt quá mức giới hạn cho phép độ lớn 16 NGHIÊN CỨU PHÁT TRIỂN GIẢI PHÁP PHÁT HIỆN ẢNH TRÙNG NHAU của từng file thì các key tiếp theo sẽ được lưu vào các file khác và cứ tiếp tục như thế cho đến khi nào toàn bộ khối dữ liệu ban đầu được phân hoạch ra từng tập dữ liệu con thì việc phân hoạch xem như hoàn thành.
Việc tổ chức và thiết kế mô hình gom các thông tin theo dạng file sẽ giúp cho việc tìm kiếm và lưu trữ trở nên hiệu quả hơn. Với giải pháp phân hoạch tập key ra từng phân hoạch nhỏ hơn giúp cho việc tìm kiếm tốt hơn, tuy nhiên để tìm một key trong một tập dữ liệu có độ lớn từ 100-200 megabytes cũng tốn khá nhiều thời gian và trong khi kết quả ta cần chỉ là vài kilobytes dữ liệu trong số đó. Chính vì vậy đề tài này đưa ra nhầm mục đích: · Làm sao xác định được key này thuộc phân hoạch nào một cách nhanh nhất. · Làm sao tìm được key này khi đã xác định được phân hoạch đang có khả năng chứa nó.4 Cấu trúc luận văn Phần tiếp theo của luận văn có cấu trúc như sau: Chương 2: Trình bày các kiến thức nền tảng liên quan đến đề tài, bao gồm hệ giải thuật hash, giải thuật tìm kiếm và các kết quả nghiên cứu trước đây.
Chương 3: Tổng quan về vấn đề xử lý nội dung, cách thức quản lý dữ liệu. Chương 4: Trình bày thiết kế kiến trúc của hệ thống. Chương 5: Đánh giá và kiểm nghiệm hệ thống, bao gồm luôn cả việc kiểm nghiệm độ chính xác của việc tạo key của hàm hash. Chương 6: Tổng kết các kết quả của luận văn và đề xuất hướng phát triển tiếp theo.
17 NGHIÊN CỨU PHÁT TRIỂN GIẢI PHÁP PHÁT HIỆN ẢNH TRÙNG NHAU Chương II: KIẾN THỨC NỀN TẢNG 2.1 Giải thuật hash Hàm băm (hash function) là giải thuật nhằm sinh ra các giá trị băm tương ứng với mỗi khối dữ liệu (có thể là một chuỗi kí tự, một đối tượng trong lập trình hướng đối tượng, v. Giá trị băm đóng vai gần như một khóa để phân biệt các khối dữ liệu, tuy nhiên, người ta chấp hiện tượng trùng khóa hay còn gọi là đụng độ và cố gắng cải thiện giải thuật để giảm thiểu sự đụng độ đó. Hàm băm thường được dùng trong bảng băm nhằm giảm chi phí tính toán khi tìm một khối dữ liệu trong một tập hợp (nhờ việc so sánh các giá trị băm nhanh hơn việc so sánh những khối dữ liệu có kích thước lớn). Hình 2: Hash funtion 2.1 Ứng dụng: Các hàm băm được ứng dụng trong nhiều lĩnh vực, chúng thường được thiết kế phù hợp với từng ứng dụng.
Ví dụ, các hàm băm mật mã học giả thiết sự tồn tại của một đối phương - người có thể cố tình tìm các dữ liệu vào với cùng một giá trị băm.