Luận văn Thuật toán đánh chỉ mục ngược với Mapreduce và ứng dụng trong việc đánh giá ý kiến của học sinh Hòa bình trên mạng xã hội

vi phạm bất cứ điều gì trong luật sở hữu trí tuệ và pháp luật Việt Nam. Nếu sai, tôi hoàn toàn chịu trách nhiệm trước pháp luật. TÁC GIẢ LUẬN VĂN Lê Đinh Hợp ii Lời cám ơn Tôi xin chân thành cảm ơn Trường Đại học Công nghệ thông tin và Truyền thông - Đại học Thái Nguyên đã tạo điều kiện thuận lợi cho tôi hoàn thành khóa học này. Tôi xin chân thành cảm ơn các Thầy Cô giáo – Các nhà khoa học đã trực tiếp giảng dạy truyền đạt những kiến thức chuyên ngành Khoa học máy tính cho tôi trong những tháng năm học tập tại trường. Đặc biệt tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc tới PGS TS Đỗ Trung Tuấn đã tận tình hướng dẫn, dìu dắt và chỉ bảo cho tôi những kiến thức về chuyên môn thiết thực và những chỉ dẫn khoa học quý báu để tôi hoàn thành bản luận văn này. Luận văn này còn nhiều thiếu sót, rất mong được các thầy cô giáo trong hội đồng chấm luận văn xem xét, góp ý kiến để luận văn được hoàn thiện hơn. Tôi xin chân thành cảm ơn! Thái Nguyên, tháng 12 năm 2016 iii Mục lục Lời cam đoan .........................................................................................................i Lời cám ơn .......................................................................................................... iii Mục lục ................................................................................................................iv Danh sách các từ viết tắt ......................................................................................vi Danh mục các hình vẽ, bảng biểu ...................................................................... vii Chương mở đầu .................................................................................................... 9 Đặt vấn đề ..................................................................................................... 9 Đối tượng và phạm vi nghiên cứu .............................................................. 11 Hướng thực hiện đề tài ............................................................................... 11 Những nội dung nghiên cứu chính ............................................................. 11 CHƯƠNG 1 MÔ HÌNH MapReduce ................................................................. 12 1.1. Tổng quan về MapReduce ........................................................................... 12 1.1.1. Sự quan trọng của MapReduce ......................................................... 12 1.1.2. Các ý tưởng của MapReduce ........................................................... 13 1.1.3. Cấu trúc dữ liệu trong MapReduce .................................................. 15 1.1.4. Mapper và Reducer .......................................................................... 15 1.1.5. Partitioner và Combiner ................................................................... 17 1.2. Bộ khung thực thi ........................................................................................ 19 1.2.1. Lập lịch ............................................................................................. 19 1.2.2. Di chuyển dữ liệu và mã lệnh ........................................................... 19 1.2.3. Đồng bộ hóa ..................................................................................... 20 1.2.4. Xử lý lỗi ............................................................................................ 20 1.3. Hệ thống file phân tán .................................................................................. 20 1.3.1. Kiến trúc của HDFS ......................................................................... 21 1.3.2. Nhiệm vụ của NameNode ................................................................ 21 1.3.3. Nhiệm vụ của DataNode .................................................................. 22 1.3.4. Nhiệm vụ của Secondary NameNode .............................................. 23 CHƯƠNG 2THUẬT TOÁN XỬ LÝ DỮ LIỆU VĂN BẢN VỚI MapReduce 25 2.1. Thiết kế thuật toán MapReduce cơ bản ....................................................... 25 iv 2.1.1. Gộp lớn cục bộ ................................................................................. 26 2.1.2. Bộ hai và bộ ba ................................................................................. 30 2.1.3. Tính toán tần số tương đối .................................................................. 33 2.1.4. Sắp xếp thứ cấp ................................................................................ 36 2.2 Thuật toán tính chỉ mục ngược để tìm kiếm dữ liệu văn bản ....................... 36 2.2.1. Dò tìm Web ...................................................................................... 37 2.2.2 Thuật toán chỉ mục ngược ................................................................. 39 2.2.3. Cài đặt theo cơ bản ........................................................................... 41 2.2.4. Cài đặt thuật toán cải tiến ................................................................. 43 2.2.5. Nén chỉ mục ...................................................................................... 45 2.3. Về tìm kiếm ................................................................................................. 52 CHƯƠNG 3 THỬ NGHIỆM THUẬT TOÁN ĐÁNH GIÁ Ý KIẾN TRÊN MẠNG XÃ HỘI ............................................................................................................ 56 3.1 Mã nguồn mở Solr ........................................................................................ 56 3.1.1. Giới thiệu .......................................................................................... 56 3.1.2. Các tính năng chính của Solr: .......................................................... 56 3.2 Mã nguồn mở Nutch ..................................................................................... 56 3.2.1. Các lý do để tự xây dựng một Search Engine .................................. 56 3.2.2. Các tính năng chính của Nutch ........................................................ 57 3.3. API biểu đồ Facebook ................................................................................. 58 3.4. Solr trên Hadoop và tìm kiếm thử nghiệm .................................................. 60 3.4.1. Sơ đồ ................................................................................................. 60 3.4.1. Cài đặt cụm máy Hadoop ................................................................. 62 3.4.2. Cài đặt Nutch tích hợp với Solr ........................................................ 67 3.4.3. Thu thập dữ liệu ............................................................................... 69 3.5. Thực hiện tìm kiếm thử nghiệm trên tập chỉ mục đã thu thập được. .......... 72 Kết luận .............................................................................................................. 75 v Danh sách các từ viết tắt CNTT Công nghệ Thông tin HDFS Hadoop Distributed File System URL Uniform Resource Locator HTML HyperText Markup Language LISP LISt Processing ML Markup Language HPC High-Performance Computing NAS Network-Attach Storage SAN Storage Area Network GFS Google File System SPOF Single Point Of Failure SNN Secondary NameNode APW Associated Press Wordstream REST Representational State Transfer PRAM Parallel Random Access Machine BSP Bulk Synchronous Parallel vi Danh mục các hình vẽ, bảng biểu Hình 1.1. Mô hình chia để trị ............................................................................. 14 Hình 1.2. Hàm Map và Fold trong Functional Programming ............................ 15 Hình 1.3. Hai pha Map và Reduce của một MapReduce job ............................. 16 Hình 1.4. Mô hình MapReduce đầy đủ các thành phần ..................................... 19 Hình 1.5. Kiến trúc của HDFS ........................................................................... 21 Hình 1.6. Vai trò của NameNode và DataNode trong HDFS ............................ 23 Hình 1.7. Kiến trúc HDFS đầy đủ ...................................................................... 23 Hình 2.1. Bảo toàn trạng thái trong Hadoop ...................................................... 26 Hình 2.2. Tiến trình hoạt động của chương trình WordCount ........................... 27 Hình 2.3. Thời gian chạy của thuật toán "pairs" và "stripes" ............................. 32 Hình 2.4. Ví dụ minh họa cặp giá trị .................................................................. 35 Hình 2.5. Minh họa đơn giản của một chỉ mục ngược. ...................................... 40 Hình 2.6: Minh họa đơn giản cơ sở thuật toán lập chỉ mục ngược trong MapReduce với ba mapper và hai reducer .................................................................... 43 Hình 2.7. Mười số nguyên dương đầu tiên trong nguyên phân, γ, và mã Golomb (b = 5, 10) ...................................................................................................................... 49 Hình 2.8. Ma trận Term-document ..................................................................... 53 Hình 3.1. Sơ đồ hoạt động của Nutch khi sử dụng như một Crawler ................ 57 Hình 3.2. Sơ đồ đầy đủ của Nutch khi sử dụng như một Search Engine ........... 58 Hình 3.3. Facebook ............................................................................................ 58 Hình 3.4. Trao đổi qua API ................................................................................ 59 Hình 3.5: Mô hình tổng quan của hệ thống khảo sát .......................................... 60 Hình 3.6: Sơ đồ giai đoạn đánh chỉ mục ............................................................ 61 Hình 3.7: đánh chỉ mục với MapRedece trên Solr ............................................. 61 Hình 3.8: Giao diện làm việc của Solr ............................................................... 68 Hình 3.9: Giao diện làm việc của Facebook Graph API .................................... 69 Hình 3.10: Access Token của một trình Facebook Graph API .......................... 70 vii Hình 3.11: Thu thập dữ liệu từ trang mạng của trường THPT Hoàng Văn Thụ 70 Hình 3.12:Giao diên theo dõi quá trình làm việc của MapReduce .................... 71 Bảng 3.2: Kết quả thu thập dữ liệu ở 2 chế độ ................................................... 72 Hình 3.13: Giao diện trang web tìm kiếm trên Solr ........................................... 73 Bảng 3.3: Một số kết quả truy vấn theo chủ đề .................................................. 73 viii Chương mở đầu Đặt vấn đề Trong thời đại hiện nay, công nghệ thông tin được ứng dụng tại mọi lĩnh vực trong cuộc sống, với một hệ thống máy tính người ta có thể làm được rất nhiều công việc, tiết kiệm được thời gian, công sức và tiền bạc. Với sự phát triển vượt bậc của Internet hiện nay, lượng thông tin ngày càng nhiều, sự tăng trưởng có thể nói là được tính bằng cấp số nhân, theo một nghiên cứu thì cứ khoảng 5 năm thì lượng tri thức của nhân loại sẽ tăng gấp đôi, với lượng thông tin đồ sộ trên mạng hiện nay thì việc tìm kiếm và khai thác thông tin là một công việc hết sức quan trọng, mang lại nhiều lợi ích về khoa học và kinh tế. Cùng với sự ra đời của Internet, sự xuất hiện và phát triển không ngừng của lĩnh vực thương mại điện tử, các lĩnh vực nghiên cứu xã hội khiến cho việc xúc tiến các hoạt động kinh doanh hoặc nghiên cứu, quảng bá sản phẩm dịch vụ diễn ra trên khắp các kênh thông tin xã hội, đặc biêt là trên Internet. Như chúng ta đã biết ngày nay mọi thông tin đều được đưa lên các trang mạng xã hội dưới dạng các Posts và rất nhiều người dùng để lại các nhận xét (comments) về các thông tin được đưa lên, ta thấy đó chính là một kho thông tin vô cùng hưu ích, nếu ta có thể tìm kiếm và phân loại dữ liệu ấy, chúng ta có thể thu được các kết quả khảo sát cần thiết phục vụ cho các hoạt động nghiên cứu hoặc các hoạt động sản xuất kinh doanh. Kết quả khảo sát ấy có thể là những tỉ lệ như "thích" (like) hay là không có ý kiến gì đối với một vấn đề được đưa ra. Việc tìm kiếm và xử lý và tổng hợp các thông tin hưu ích đó cần phải có một mô hình đáp ứng được nhu cầu về việc có thể làm việc trên một lượng dữ liệu lớn và tốc độ cao. Mô hình MapReduce là một mô hình lập trình giúp các ứng dụng có thể xử lý nhanh hơn một lượng dữ liệu lớn dữ liệu trện các máy phần tán song song, độc lập với nhau từ đó giúp rút ngắn thời gian xử lý toàn bộ dữ liệu. MapReduce có thể chạy trên các phần cứng thông thường (commodity hardware), không đòi hỏi các server chạy MapReduce phải là các máy tính có cấu hình đặc biết mạnh mẽ. Do vậy chi phí triển khai Mapreduce sẽ rẻ hơn. MapReduce làm đơn giản hóa các giải thuật tính toán phân tán. Với MapReduce, bạn chỉ cần cung cấp hai hàm Map và Reduce cùng với một số thành phần xử lý dữ liệu đầu vào. Do vậy, các nhà phát triển ứng dụng phần tán có thể tập trung nhiều hơn cho phần logic của úng dụng, bỏ qua các chi tiết phức 9 tạp của việc phân tán xử lý. Sự ra đời của MapReduce đã mở ra cho các doanh nghiện và các trung tâm nhiên cứu cơ hội xử lý các nguồn dữ liệu đồ sộ với chi phí thấp và thời gian nhanh hơn. Hiện nay, đã có nhiều công ty lớn triển khai sử dụng mô hình MapReduce trong việc kinh doanh và khảo sát. Công ty Amazon sử dụng MapReduce để xử lý các file log trong quá trình mua hàng của khách hàng để dự đoán được xu hướng mua hàng... Facebook có thể xử lý được khối lượng hơn 10 tỷ hình ảnh mà hộ đang lưu trữ để thu thập các thông tin về hình ảnh, và thu thập 15 terabyte dữ liệu mỗi ngày vào một kho dữ liệu quy mô Petabyte để thực hiện việc khảo sát và đánh giá xu hướng người dùng. Việc nghiên cứu về xu hướng, đánh giá khảo sát một vấn đề trên quy mô lớn luôn là 1 vấn đề gặp nhiều khó khăn. Trước đây các nhà khảo sát, đánh giá ý kiến trên các đối tượng nghiên cứu thường sử dụng phương pháp thủ công rất tốn kém và mất rất nhiều thời gian để tổng hợp tin tức, chẳng hạn như muốn khảo sát ý kiến của học sinh đối với một số thay đổi trong chương trình học, người ta không thể lựa chọn hỏi ý kiến của tất cả các học sinh mà chỉ có thể lựa chọn một số địa điểm đặc trưng để thực hiện khảo sát, và đôi khi, kết quả của những khảo sát này không mang được tính khách quan vì tâm lý e ngại của các em học sinh. Và những cuộc khảo sát này, đôi khi phải thực hiện trong vòng một vài năm mới có thể có kết quả tổng hợp. Như vậy là mất rất nhiều công sức, của cải và thời gian. Với việc thực trạng hiện nay hầu hết rất cả các em trong lứa tuổi học sinh, sinh viên đều biết sử dụng và thích tham gia các mạng xã hội trên Internet ( đặc biết là Facebook) thì việc tìm kiếm một từ khóa có tần suất xuất hiện cao sẽ phản ánh được những xu hướng, những ý kiến của người dùng hơn là việc khảo sát thủ công rất nhiều và việc nhận về những kết quả khảo sát ý kiến. Tổng hợp các thông tin trên máy tính với sự hỗ trợ của mô hình MapReduce sẽ giúp chúng ta có thể thực hiện quá trình đánh giá, khảo sát ý kiến hết sức nhanh chóng và mang lại hiệu quả, cũng như tiết kiệm được rất nhiều thời gian và tiền bạc. Với những nhu cầu cấp thiết trên, học viên thực hiện nghiên cứu kỹ thuật chỉ mục ngược (Inverted Indexing) đó là phương pháp thực hiện quét một lần trên văn bản sau đó lập danh sách các thuật ngữ (từ, cụm từ) trong file đó và bao gồm cả những thông tin đi kèm với mỗi thuật ngữ (term) ( vị trí, tần suất, độ quan trọng...). Các thông tin này sẽ được tổ chức theo một cấu trúc dữ liệu riêng và được gọi là chỉ mục. Với phương pháp đánh chỉ mục ngược kết hợp với mô hình MapReduce sẽ giải quyết được những hạn chế trước đây trong phương pháp thông kê, đánh giá ý kiến trên một quy mô lớn, và đó là lý do học viên lựa chọn 10 đề tài "Thuâṭ toá n đánh chỉ mục ngược với MapReduce và ứ ng dung̣ trong việc đánh giá ý kiến của học sinh Hòa Bình trên mạng xã hội". Đối tượng và phạm vi nghiên cứu Luận văn tập trung nghiên cứu vào mô hình MapReduce, cấu trúc và cách thức hoạt động. Từ đó kết hợp với thuật toán đánh chỉ mục và chỉ mục ngược để thực hiện việc tìm kiếm và thống kê kết quả. Hướng thực hiện đề tài  Nghiên cứu về mô hình MapReduce  Nghiên cứu về thuật toán đánh chỉ mục và chỉ mục ngược  Thực hiện thử nghiệm và cài đặt Những nội dung nghiên cứu chính Luận văn được trình bày trong 3 chương. Các nội dung cơ bản của luận văn được trình bày theo cấu trúc như sau: 1. Chương 1: Tổng quan về MapReduce; Giới thiệu khái niệm về MapReduce, một số các thành phần, mô hình lập trình của MapReduce và hệ thống phân phối tập tin của nó; Trình bày nhu cầu về đánh giá ý kiến trên mạng xã hội và khả năng áp dụng. 2. Chương 2: Thuật toán xử lý dữ liệu văn bản với MapReduce; Trình bày về thiết kế thuật toán MapReduce cơ bản và thuật toán chỉ mục ngược để tìm kiếm văn bản; 3. Chương 3: Thử nghiệm ứng dụng MapReduce và thuật toán đánh chỉ mục ngược để đánh giá ý kiến trên mạng xã hội; Trình bày mô hình hoạt động của ứng dụng đánh giá ý kiến trên mạng xã hội. Các kết quả thử nghiệm của hệ thống tìm kiếm và đánh giá ý kiến trên dữ liệu văn bản có sử dụng MapReduce và thuật toán tính chỉ mục ngược. 11 CHƯƠNG 1 MÔ HÌNH MapReduce 1.1. Tổng quan về MapReduce 1.1.1. Sự quan trọng của MapReduce Về tính thiết thực, MapReduce cung cấp một công cụ rất hiệu quả để giải quyết các bài toán dữ liệu lớn. Ngoài ra, MapReduce còn quan trọng trong cách nó đã thay đổi việc sắp xếp tính toán trên quy mô lớn. Nói một cách công bằng thì MapReduce không phải là mô hình tính toán song song đầu tiên được đưa ra. Mô hình phổ biến nhất trong lý thuyết khoa học máy tính có từ mấy thập kỷ trước là PRAM1 (Parallel Random Access Machine). Trong mô hình này, một lượng lớn các vi xử lý chia sẻ một bộ nhớ lớn không giới hạn, hoạt động đồng thời trên một lượng dữ liệu chia sẻ để tạo ra kết quả. Các mô hình khác như LogP2 và BSP3 (Bulk Synchronous Parallel), tuy nhiên không có mô hình nào có được sự thành công như MapReduce. MapReduce là mức trừu tượng thành công nhất trên các tài nguyên tính toán mở rộng cho đến nay. Tuy nhiên, mức trừu tượng giải quyết sự phức tạp bằng cách che dấu sự chi tiết và đưa ra các hành vi được thiết kế tốt cho ngƣời sử dụng ứng với mức trừu tượng đó. Chính vì thế, mức trừu tượng không thể hoàn hảo, nó làm cho một số công việc dễ hơn, nhưng cũng làm một số công việc khác khó hơn hoặc có khi là không thể thực hiện được. Vấn đề này làm cho việc ứng dụng MapReduce trong một số bài toán cũng có mặt hạn chế. Điều đó có nghĩa MapReduce không phải là mô hình cuối cùng trong lớp mô hình lập trình mới cho phép xử lý tính toán trên quy mô lớn một cách hiệu quả. 1 2 3 12 1.1.2. Các ý tưởng của MapReduce Giải quyết các bài toán dữ liệu lớn đòi hỏi cách tiếp cận riêng biệt mà nhiều khi đối lập với mô hình tính toán truyền thống. Dưới đây là các ý tƣởng chính của MapReduce: Scale “out” not “up” (mở rộng chứ không nâng cấp): Để tăng sức mạnh xử lý thay vì nâng cấp bộ vi xử lý cũng như khả năng lưu trữ của máy tính (mua các server có khả năng xử lý cao – high-end server) giải pháp đưa ra là tăng số lượng các server thông dụng (low-end server). Giải pháp này kinh tế hơn nhiều so vì nó chỉ bổ sung một số máy tính và tận dụng được các server sẵn có trong khi giải pháp nâng cấp có thể dẫn đến việc mua sắm mới lại toàn bộ các server. Hơn nữa giá thành của một server chuyên dụng đắt hơn nhiều so với một cụm máy tính thông thường với khả năng xử lý tương đương. Assume failures are common (chấp nhận việc xảy ra lỗi là thường xuyên): Với sự gia tăng về số lượng của các server trong một cluster, lỗi xảy ra là điều bình thường. Do đó các dịch vụ phân tán trên nhiều server phải tính toán đến các lỗi về phần cứng cũng như phần mềm thường xuyên xảy ra. Mô hình lập trình MapReduce có khả năng xử lý các lỗi thông qua một số cơ chế như tự động khởi động lại các task trên cluster node khác nhau. Move processing to the data (đưa xử lý đến dữ liệu): Trong các ứng dụng tính toán hiệu năng cao truyền thống (High – Prefomance Computing - HPC). Thông thường, một siêu máy tính có các nút xử lý (processing node) và các nút lưu trữ (storage node) được kết nối với nhau qua một kết nối tốc độ cao. Nhiều công việc nặng nề về dữ liệu không phải là những đòi hỏi xử lý cao. Do đó việc tách rời việc lưu trữ dữ liệu và tính toán tạo ra sự thắt cổ chai trong mạng. Do đó sẽ hiệu quả hơn nếu chuyển sự thực thi xử lý đến dữ liệu thay vì chuyển dữ liệu đến nơi xử lý chúng. MapReduce sử dụng một kiến trúc trong đó các bộ xử lý và đĩa lưu trữ được đặt cùng với nhau. Trong sự thiết lập như vậy, chúng ta có thể tận dụng lợi thế của dữ liệu cục bộ bằng cách chạy đoạn mã trên bộ xử lý một cách trực tiếp trên khối dữ liệu cần xử lý. Hệ thống tập tin phân tán có nhiệm vụ quản lý dữ liệu mà MapReduce xử lý. Process data sequentially and avoid random access (xử lý dữ liệu tuần tự và tránh truy cập ngẫu nhiên): Trong trường hợp xử lý một lượng lớn dữ liệu, dung lượng bộ nhớ thường không đủ cho toàn bộ dữ liệu xử lý. Do đó dữ liệu phải được lưu trữ trên đĩa. Thời gian cho việc truy cập ngẫu nhiên thường hạn chế bởi sự di chuyển của đầu đọc cũng như tốc độ đĩa do đó làm chậm công việc xử lý. Để tránh hạn chế này, MapReduce được thiết kế để xử lý các 13 khối dữ liệu của một tập dữ liệu lớn. Hide system-level details from the application developer (che giấu mức chi tiết hệ thống đối với nhà phát triển): Để dễ dàng cho các lập trình viên khi viết ứng dụng xử lý phân tán, MapReduce che giấu sự thực thi phức tạp bên dưới. Thay vào đó, MapReduce cung cấp một mô hình lập trình trừu tượng với các interface đơn giản được định nghĩa sẵn. Phương pháp thường được sử dụng để giải quyết các bài toán dữ liệu lớn hiện nay là chia để trị. Ý tưởng là phân mảnh một bài toán lớn thành các bài toán con nhỏ. Các bài toán nhỏ độc lập với nhau để có thể được giải quyết song song bởi các workers khác nhau – workers có thể là các tiến trình trong bộ vi xử lý hoặc các bộ vi xử lý trong trong bộ vi xử lý đa nhân, các bộ xử lý trên một máy, các máy trên một cụm máy tính. Các kết quả trung gian từ các worker cụ thể sẽ được gộp lại để tạo thành kết quả cuối cùng. Hình 1.1. Mô hình chia để trị MapReduce có nguồn gốc từ lập trình hàm (Functional Programming). Ví dụ điển hình như các ngôn ngữ lập trình Lisp và ML. Tính năng chính của lập trình hàm là khái niệm về các hàm bậc cao (higher-order functions), hoặc các hàm chấp nhận tham số của nó là một hàm. Hai hàm bậc cao thường được xây dựng sẵn là Map và Fold. Như hình dưới, cho một danh sách, Map lấy tham số là một hàm f (có 1 tham số) và áp dụng cho toàn bộ phần tử trong danh sách. Cho một danh sách, Fold lấy tham số là một hàm g (có 2 tham số) và một giá trị khởi tạo: g đầu tiên được áp dụng cho giá trị khởi tạo và phần tử đầu tiên trong danh sách, kết quả 14 được lưu trong biến trung gian, tiếp tục dùng biến trung gian này để phần tử thứ 2 trong danh sách để làm tham số cho hàm g, công việc tiếp lặp đi lặp lại đến khi hết toàn bộ danh sách. Fold trả về kết quả cuối cùng là giá trị cuối cùng của biến trung gian. Hình 1.2. Hàm Map và Fold trong Functional Programming Hàm Map trong MapReduce tương ứng với hàm Map, hàm Reduce tương ứng với hàm Fold trong lập trình hàm. 1.1.3. Cấu trúc dữ liệu trong MapReduce Các cặp key-value là cấu trúc dữ liệu cơ bản trong MapReduce. Key và value có thể nhận các giá trị có kiểu cơ bản như số nguyên, số thực, chuỗi hay có thể nhận các kiểu giá trị có cấu trúc do người dùng định nghĩa. Một phần quan trọng của giải thuật MapReduce là việc xác định cấu trúc key-value trên các tập dữ liệu cần xử lý. Ví dụ, đối với một tập các trang web, các key có thể là các URL và các value có thể là nội dung của các trang HTML, đối với một đồ thị, key có thể là node id và value có thể là danh sách kề của node đó. Trong một số thuật toán key được sử dụng để phân biệt các bộ dữ liệu (giống như khái niệm khóa trong cơ sở dữ liệu), trong khi ở một số thuật toán, các input key không quan trọng và thường được bỏ qua. 1.1.4. Mapper và Reducer Trong MapReduce, lập trình viên định nghĩa một lớp Mapper và một lớp Reducer với hai hàm cơ bản sau:  map (k1, v1) → [ (k2, v2)]  reduce (k2, [v2]) → [ (k3, v3)] Ký hiệu [] để chỉ một danh sách các giá trị. Đầu vào của một công việc MapReduce (MapReduce job) là dữ liệu được lưu trữ trên hệ thống file phân tán (Distributed File System). Hàm map và reduce lần lượt được cài đặt trong hai lớp 15 Mapper và Reducer. Mapper được áp dụng cho mọi cặp key-value để tạo ra các cặp key-value trung gian. Reducer được áp dụng cho tất cả các giá trị (value) ứng với cùng một key trung gian để tạo các cặp key-value ở đầu ra. Giữa 2 pha map và reduce là một phép xử lý nhóm phân tán các cặp key-value trung gian dựa trên các key. Dữ liệu trung gian được gởi đến mỗi reducer theo thứ tự được sắp xếp bởi các key. Tuy nhiên không có một quan hệ thứ thự nào được thiết lập cho các key giữa các reducer với nhau. Các cặp key-value ở đầu ra của các reducer được ghi vào hệ thống file phân tán (các cặp key-value trung gian được bỏ qua). Đầu ra cuối cùng là r file trên hệ thống file phân tán, trong đó r là số các reducer. Trong phần lớn các trường hợp, việc tổng hợp các đầu ra của các reducer là không cần thiết bởi vì r files thường lại là đầu vào cho một MapReduce job khác. Hình 5 mô tả 2 giai đoạn của một MapReduce job. Hình 1.3. Hai pha Map và Reduce của một MapReduce job Ví dụ minh họa MapReduce: Ứng dụng đếm từ (Word count) trong một tập văn bản.  Input: Tập văn bản  Outut: Danh sách các từ cùng số lần xuất hiện của chúng trong tập văn bản. class Mapper method Map (docId a, doc d) 16 for all term t ϵ doc d do Emit (term t, count 1) class Reducer method Reduce (term t, counts[c1, c2,]) sum ← 0 for all count c ϵ counts[c1, c2,] do sum ← sum + c Emit (term t, count sum) Hàm Map duyệt qua từng từ trong tập văn bản ứng với mỗi từ sẽ tạo ra một cặp key-value với key chính là từ vừa gặp và value = 1. Hàm Reduce nhận đầu vào là một từ (term) và và danh sách tần số ci bắt gặp của term đó (các giá trị thực là các số 1), Reduce chỉ đơn giản cộng tất cả các giá trị ci trong danh sách counts. 1.1.5. Partitioner và Combiner Phần trên chúng ta đã làm đơn giản cái nhìn về MapReduce, ngoài hai thành phần Mapper và Reducer, thường thì lập trình viên phải chỉ thêm 2 thành phần phụ nữa: 1.1.5.1. Thành phần Partitioner Nó có nhiệm vụ chia không gian khóa (key) trung gian sau bƣớc Map và gán các cặp key-value trung gian tới các Reduce. Hay nói một cách khác, partitioner chỉ định tác vụ (task) mà cặp key-value trung gian phải được chuyển đến đó. Trong mỗi Reducer, các khóa được xử lý theo thứ tự đã được sắp xếp. Partitioner đơn giản nhất bao gồm việc tính toán giá trị băm của key và sau đó thực hiện phép chia lấy phần dƣ của giá trị này với số lượng reducer. Do đó các partitioner có thể gán một key và danh sách value của nó tới một reducer có số hiệu là giá trị băm vừa tính được. Thông thường hàm băm phải được tính toán sao cho số lượng key gửi đến mỗi reducer xấp xỉ bằng nhau. Tuy nhiên partitioner không chú ý đến giá trị value trong cặp key-value, do đó có thể xảy ra tình trạng phân bố dữ liệu không đồng đều trên các reducer. 1.1.5.2. Thành phần Combiner Thành phần này trong MapReduce đóng vai trò như một thành phần tối ưu giúp giảm tải việc chuyển dữ liệu giữa từ các Mapper đến các Reducer. Có thể 17 xem combiner như là một reducer nhỏ (mini-reducer) đặt tại đầu ra của mapper, trước pha trộn và sắp xếp (shuffle and sort phase) gởi các cặp key-value tới các reducer. Mỗi combiner hoạt động cô lập và do đó nó không truy xuất đến các cặp key-value của các mapper khác. Đầu vào của combiner là các cặp key-value từ đầu ra của mapper và nó xử lý tất cả các cặp key-value có key giống nhau để chuyển thành cặp key-value (cùng định dạng như ở đầu vào của combiner có key không thay đổi nhưng value đã bị biến đổi) ở đầu ra. Tuy nhiên, Reducer và Combiner không thể hoán đổi vai trò cho nhau. 18 Hình 1.4. Mô hình MapReduce đầy đủ các thành phần 1.2. Bộ khung thực thi Một trong những ý tưởng quan trọng nhất trong MapReduce là tách biệt việc xử lý phân tán cái gì (what) ra khỏi việc xử lý phân tán như thế nào (how). Một chương trình MapReduce (Mapreduce Job), bao gồm đoạn mã cho Mapper, Reducer và có thể thêm Partioner và Combiner được đóng gói lại với nhau với các tham số cấu hình (ví dụ vị trí các tập tin đầu vào và nơi lưu trữ đầu ra). Nhà phát triển đưa chương trình lên cho node quản lý tác vụ trong cluster (trong Hadoop gọi là JobTracker) và execution framework xử lý tất cả những thứ khác: xử lý trong suốt các vấn đề của việc thực thi mã lệnh phân tán. Các chức năng chính của Execution framework bao gồm: 1.2.1. Lập lịch Mỗi chương trình MapReduce được chia nhỏ thành các đơn vị nhỏ gọi là tasks. Ví dụ, một map task có thể chịu trách nhiệm xử lý một khối các cặp key-value nào đó (trong Hadoop gọi là input split), tương tự, một reduce task có thể xử lý một phần của không gian khóa. 1.2.2. Di chuyển dữ liệu và mã lệnh Ý tưởng của MapReduce là di chuyển mã lệnh, không phải di chuyển dữ liệu. 19 Tuy nhiên, trong một số trường hợp – để cho việc tính toán có thể thực hiện chúng ta phải đưa dữ liệu đến mã lệnh. Trong MapReduce, việc này phụ thuộc phần lớn vào hệ thống file phân tán. Để có được việc cục bộ d...ể các biên. Với việc sử dụng các tổ hợp, các tính biên một phần sẽ được tổng hợp trước khi được gửi đến gia giảm. Ngoài ra, mô hình kết hợp trong mapper có thể được sử dụng để tổng hợp nhiều hơn hiệu quả đếm biên. Trong giảm tốc, chúng ta phải đảm bảo rằng các cặp khóa-giá trị đặc biệt của đại diện resenting những đóng góp biên một phần được xử lý trước khi các cặp khóa- giá trị bình thường đại diện cho số lượng doanh. Điều này được thực hiện bằng cách 34 xác định thứ tự sắp xếp của các phím để cặp với các biểu tượng đặc biệt trong mẫu (wi, *) được đặt hàng trước bất kỳ cặp khóa-giá trị khác mà từ trái là wi. Ngoài ra, như với trước khi chúng ta cũng phải xác định đúng các phân vùng phải chú ý đến chỉ từ trái trong mỗi cặp. Với các dữ liệu trình tự đúng cách, giảm tốc có thể trực tiếp tính toán tần số tương đối. Một ví dụ cụ thể được thể hiện trong hình, trong đó liệt kê trình tự các cặp giá trị Key-mà giảm có thể gặp. Thứ nhất, giảm được trình bày với các phím đặc biệt (dog, *) và một số các giá trị, mỗi trong số đó đại diện cho một biệt tiềm đóng góp biên từ giai đoạn bản đồ (giả sử ở đây, hoặc tổ hợp hoặc trong-mapper kết hợp, vì vậy các giá trị đại diện cho số lượng một phần tổng hợp). Việc giảm tích tụ các tính đến nơi ở biên,.wt N (dog, wr). Việc giảm nắm giữ trên để giá trị này là nó xử lý các khóa tiếp theo. Sau (dog, *), là sản phẩm giảm sẽ gặp phải một loạt các phím đại diện cho số lượng doanh; hãy nói rằng người đầu tiên trong số này là khóa (dog, aarvark). Kết hợp với khóa này Hình 2.4. Ví dụ minh họa cặp giá trị Ví dụ về trình tự các cặp khóa-giá trị trình bày với Reducer trong thuật toán cặp để tính tần số tương đối. Điều này cho thấy việc áp dụng các mẫu thiết kế để đảo ngược. Sẽ có một danh sách các giá trị đại diện cho số lượng doanh một phần từ giai đoạn bản đồ (hai giá trị riêng biệt trong trường hợp này). Tổng hợp các tính sẽ mang tính liên kết, tức là, số lần con chó và lợn đất đồng xảy ra trong toàn bộ bộ sưu tập. Tại thời điểm này, kể từ khi giảm tốc đã biết biên, giản ple số học đủ để tính toán tần số tương đối. Tất cả các tính chung sau đó được xử lý một cách chính xác theo cách tương tự. Khi giảm tốc gặp sự đặc biệt tiếp theo cặp khóa-giá trị (doge, *), là sản phẩm giảm reset trạng thái nội bộ của mình và bắt đầu tích lũy biên trên một lần nữa. Nhận thấy rằng các yêu cầu bộ nhớ cho thuật toán này là rất ít, vì chỉ có biên (một số nguyên) cần phải được lưu trữ. Không đệm đếm từ xảy ra đồng cá nhân là cần thiết, và do đó chúng tôi đã loại bỏ các nút cổ chai khả năng mở rộng của thuật toán trước đó. Mẫu thiết kế này, mà chúng ta gọi là "trật tự đảo ngược", xuất hiện đáng ngạc nhiên thường xuyên và trên các ứng dụng trong nhiều lĩnh vực. Nó như vậy được đặt tên vì thông qua sự phối hợp thích hợp, chúng ta có thể truy cập vào kết quả của một 35 phép tính trong giảm tốc (ví dụ, một số liệu thống kê tổng hợp) trước khi xử lý các dữ liệu cần thiết để tính toán đó. Sự thấu hiểu chính là chuyển đổi các trình tự tính toán vào một vấn đề phân loại. Trong hầu hết các trường hợp, một thuật toán đòi hỏi dữ liệu theo một trật tự nhất định: bằng cách kiểm soát cách các phím được sắp xếp và làm thế nào các không gian chính là phân vùng, chúng tôi có thể trình bày dữ liệu đến giảm theo thứ tự cần thiết để thực hiện các tính toán thích hợp. Điều này giúp giảm số lượng kết quả một phần là giảm tốc cần nắm giữ trong bộ nhớ. Để tóm tắt, các ứng dụng cụ thể của các mẫu thiết kế để đảo ngược để tính toán tần số tương đối yêu cầu sau đây: 1. Phát ra một cặp khóa-giá trị đặc biệt cho mỗi cặp từ đồng xảy ra trong mapper để nắm bắt việc đóng góp cho biên. 2. Kiểm soát thứ tự sắp xếp của các chính trung gian để các cặp khóa-giá trị thể hiện sự đóng góp cận biên được xử lý bởi giảm tốc trước khi bất kỳ của các cặp đại diện từ doanh đếm đồng xảy ra. 3. Xác định một phân vùng tùy chỉnh để đảm bảo rằng tất cả các cặp cùng bên trái từ được xáo trộn đến giảm tương tự. 4. Bảo tồn nhà nước trên nhiều phím trong bộ giảm đầu tiên tính toán biên dựa trên các cặp khóa-giá trị đặc biệt và sau đó chia cho số đếm chung của dữ liệu lề để đi đến các tần số tương đối. Như chúng ta sẽ thấy, mẫu thiết kế này cũng được sử dụng trong xây dựng chỉ số ngược để thiết lập đúng thông số nén cho các danh sách thông tin đăng. 2.1.4. Sắp xếp thứ cấp MapReduce sắp xếp các cặp key-value theo keys trong pha Shuffle and Sort, sẽ rất thuận tiện nếu việc tính toán ở reducer dựa vào thứ tự sắp xếp. Tuy nhiên, làm cách nào để ngoài sắp xếp theo key, ta sắp theo theo value nữa? MapReduce của Google có tính năng secondary được xây dựng sẵn để đảm bảo các values được sắp xếp khi đến Reducer. Tuy nhiên, Hadoop chưa có tính năng này. Có 2 cách để dùng secondary sort trong Hadoop: một là lưu tạm trong bộ nhớ sau đó sắp xếp, tuy nhiên cách này sẽ bị giới hạn khi dữ liệu trong bộ nhớ quá lớn. Cách thứ hai là sử dụng mẫu thiết kế Value- to-key tạo nên các composite key (khóa kết hợp) (k,v1). 2.2 Thuật toán tính chỉ mục ngược để tìm kiếm dữ liệu văn bản Tìm kiếm web là một vấn đề lớn về dữ liệu tinh túy. Việc đưa ra một thông tin cần thể hiện như một truy vấn ngắn bao gồm một vài điều khoản, nhiệm vụ của hệ thống là để lấy đối tượng web có liên quan và trình bày chúng cho người dùng. Trang web lớn như thế nào? Rất khó để tính toán chính xác, nhưng kể cả dự tính khái quát / ước lượng cũng sẽ ra kích thước ở vài chục tỷ trang, với tổng trị giá hàng trăm 36 terabytes (chỉ xét văn bản). Trong các ứng dụng thực tế, người sử dụng yêu cầu kết quả nhanh chóng từ một công cụ tìm kiếm truy vấn - thời gian trễ dài hơn một vài trăm mili giây sẽ thử thách sự kiên nhẫn của người dùng. Thực hiện các yêu cầu này là khá một kỳ công, lưu tâm đến các khoản dữ liệu liên quan! Gần như tất cả các động cơ truy hồi/thu hồi cho tìm kiếm văn bản đầy đủ ngày hôm nay dựa trên một cấu trúc dữ liệu được gọi là chỉ số đảo ngược, mà cho một thuật ngữ, cung cấp truy cập vào danh sách các tài liệu có chứa thuật ngữ. Trong thông tin theo cách nói retrieval, đối tượng được lấy lại được gọi khái quát là "tài liệu", mặc dù trong thực tế chúng có thể là các trang web, các file PDF, hoặc thậm chí mảnh mã. Cho một truy vấn của người dùng, retrieval engines sử dụng inverted index để ghi tài liệu có chứa các thuật ngữ truy vấn liên quan tới một số mô hình xếp hạng, có tính đến tính năng tài khoản như thuật ngữ thích hợp, trạng thái thuật ngữ (term proximity), các thuộc tính của các điều khoản/thuật ngữ trong tài liệu. Các vấn đề tìm kiếm web bị phân hủy thành ba thành phần: thu thập nội dung web, xây dựng các chỉ số và các văn bản xếp hạng cho một truy vấn. Crawling và indexing chia sẻ những đặc điểm và yêu cầu tương tự nhau, nhưng chúng rất khác với thu hồi. Thu thập nội dung trang web và xây dựng các chỉ số đảo ngược được cho hầu hết các vấn đề offline. Cả hai cần phải được mở rộng và hiệu quả, nhưng chúng không cần hoạt động trong thời gian thực. Indexing thường là một quá trình batch để chạy theo định kỳ: tần suất làm mới và cập nhật thường phụ thuộc vào thiết kế của bộ tìm kiếm. Một số trang web (ví dụ, các tổ chức tin tức) cập nhật nội dung của họ khá thường xuyên và cần phải được truy cập thường xuyên; các trang web khác (ví dụ, chính phủ quy định) là tương đối tĩnh. Tuy nhiên, ngay cả đối với các trang web hay cập nhật, thường thì có thể chấp nhận được việc chậm trễ một vài phút cho đến khi nội dung tìm được. Hơn nữa, vì số lượng nội dung thay đổi nhanh chóng là tương đối nhỏ, chạy cập nhật chỉ số quy mô nhỏ hơn ở tần số lớn hơn thường là một là giải pháp thỏa đáng. Tìm kiếm là một vấn đề trực tuyến đòi hỏi thời gian phản ứng phụ thứ hai (sub- second response time). Người dùng cá nhân mong đợi độ trễ truy vấn thấp, nhưng thông lượng truy vấn cũng không kém phần quan trọng vì retrieval engine thường phục vụ cho nhiều người sử dụng đồng thời. Hơn nữa, tải truy vấn được đánh giá cao biến, tùy thuộc vào thời gian trong ngày, và có thể triển lãm "Spikey" hành vi do trường hợp đặc biệt (ví dụ, một tin tức sự kiện mới gây ra một số lượng lớn tìm kiếm trên cùng một chủ đề). Mặt khác, tiêu thụ tài nguyên cho vấn đề indexing có thể dự đoán được hơn. 2.2.1. Dò tìm Web Trước khi xây dựng chỉ số đảo ngược, đầu tiên chúng ta phải có được bộ sưu tập tài liệu qua đó xây dựng các chỉ số. Trong học viện và cho các mục đích nghiên cứu, điều này có thể tương đối đơn giản. Bộ sưu tập tiêu chuẩn cho thông tin nghiên cứu thu hồi được phổ biến rộng rãi cho nhiều thể loại khác nhau, từ các blog đến 37 newswire text. Đối với các nhà nghiên cứu, những người muốn khám phá web-scale retrieval, sẽ là bộ sưu tập ClueWeb09 có chứa một tỷ trang web trong mười ngôn ngữ (Tổng cộng 25 terabyte) được thu thập thông tin bởi Đại học Carnegie Mellon vào đầu năm 2009. Việc tiếp cận với những bộ sưu tập tiêu chuẩn thường là đơn giản như ký một giấy phép dữ liệu thích hợp từ các nhà phân phối của các bộ sưu tập, trả chi phí hợp lý, và sắp xếp cho nhận dữ liệu. Đối với tìm kiếm web trong thực thế, tuy nhiên, có thể không chỉ đơn giản cho rằng dữ liệu là có sẵn. Tiếp thu nội dung trang web đòi hỏi phải crawling, là quá trình đi qua trang web theo các siêu liên kết liên tục và lưu trữ các trang được tải về cho lần xử lý tiếp theo. Về mặt khái niệm, quá trình này khá đơn giản để hiểu: chúng ta bắt đầu bằng cách gia tăng một hàng đợi với một "hạt giống" danh sách các trang. Crawler tải các trang trong hàng, trích xuất đường dẫn từ những trang đó để thêm vào hàng đợi, lưu trữ các trang để xử lý tiếp, và lặp đi lặp lại. Trong thực tế, trình thu thập web thô sơ có thể được viết bằng hàng trăm dòng mã. Tuy nhiên, hiệu quả việc dò tìm web hiệu quả phức tạp hơn rất nhiều. Dưới đây liệt kê một số vấn đề mà trình thu thập thực tế (real-world crawlers) phải đấu tranh với:  Một trình thu thập (crawler) web phải thực hành tốt "nghi thức" và không quá tải web server. Ví dụ, việc chờ đợi một số lượng thời gian cố định trước khi lặp lại yêu cầu đến cùng một server là một thực tế phổ biến. Để tôn trọng những hạn chế trong khi duy trì thông lượng tốt, một crawler thường giữ nhiều thread chạy song song và duy trì nhiều kết nối TCP (có lẽ hàng trăm) mở cùng một lúc.  Khi một trình thu thập có băng thông hữu hạn và nguồn lực, nó phải ưu tiên thứ tự mà trong đó các trang chưa xem được tải xuống. Quyết định này phải được thực hiện trực tuyến và trong một môi trường thù địch (adversarial environment), có nghĩa là spammer chủ động tạo ra các trang đầy spam "trang trại liên kết" và "bẫy nhện" (“link farms” and “spider traps”) để lừa một trình thu thập vào nội dung overrepresenting từ một trang web cụ thể.  Hầu hết các trình thu thập web thực tế được phân phối hệ thống chạy trên các cụm máy , thường phân bố cục bộ. Để tránh tải một trang nhiều lần và để đảm bảo tính nhất quán dữ liệu, các trình thu thập như một toàn thể cần cơ chế phối hợp và cân bằng tải. Nó cũng cần phải có sức mạnh (robust) đối với thất bại của máy, mất mạng, và các loại lỗi.  Nội dung web thay đổi, nhưng với tần số khác nhau tùy thuộc vào cả hai trang web và bản chất của nội dung. Một trình thu thập web cần phải học những các mẫu cập nhật đó để đảm bảo nội dung đó là hợp lý trong hiện 38 tại. Lấy tần số thu thập lại thông đúng là khó khăn: quá thường xuyên có nghĩa là lãng phí nguồn lực, nhưng không đủ thường xuyên lại dẫn đến nội dung cũ.  Các trang web có đầy các nội dung trùng lặp. Các ví dụ bao gồm nhiều bản sao của một bài viết hội nghị phổ biến, mẫu của các trang web thường xuyên được truy cập như Wikipedia, và nội dung newswire thường được nhân đôi. Vấn đề phức tạp bởi thực tế rằng các trang lặp đi lặp lại hầu hết đều không trùng lặp hoàn toàn mà gần như trùng lặp (có nghĩa là, về cơ bản các trang tương tự nhưng với quảng cáo khác nhau, các thanh menu, vv). Việc xác định gần bản sao và chọn mẫu mực tốt nhất để chỉ mục trong quá trình thu thập thông tin là một việc đáng kỳ vọng.  Các trang web đa ngôn ngữ. Không có đảm bảo rằng các trang trong một ngôn ngữ chỉ liên kết đến các trang trong cùng một ngôn ngữ. Ví dụ, một giáo sư tại Châu Á có thể duy trì trang web của mình bằng ngôn ngữ địa phương, nhưng chứa các liên kết đến các ấn phẩm bằng tiếng Anh. Hơn nữa, có nhiều trang chứa một hỗn hợp văn bản trong các ngôn ngữ khác nhau. Kể từ khi các kỹ thuật xử lý tài liệu (ví dụ, tokenization, stemming) khác biệt bởi ngôn ngữ, Việc xác định ngôn ngữ (chi phối) trên một trang là rất quan trọng. 2.2.2 Thuật toán chỉ mục ngược Trong hình thức cơ bản của nó, một chỉ mục ngược bao gồm danh sách tin đăng, một liên kết với từng kỳ hạn xuất hiện trong bộ sưu tập. Cấu trúc của một chỉ mục ngược được minh họa trong hình. Một danh sách đăng bao gồm những bài viết cá nhân, mỗi trong số đó bao gồm một id tài liệu và trọng số - thông tin về lần xuất hiện của thuật ngữ trong tài liệu. Trọng số đơn giản nhất là... không có gì! Với simple boolean retrieval, việc không có thêm thông tin là cần thiết trong việc đăng khác với id tài liệu; sự tồn tại của bản thân việc gửi bài cho thấy sự hiện diện của các thuật ngữ trong tài liệu. Trọng số phổ biến nhất, tuy nhiên, là tần số hạn (tf), hoặc số lần thuật ngữ xảy ra trong tài liệu. Trọng tải phức tạp hơn bao gồm các vị trí của mỗi sự xuất hiện của thuật ngữ trong tài liệu (để hỗ trợ cụm từ truy vấn và ghi tài liệu dựa trên term gần), tính chất của thuật ngữ (chẳng hạn như nếu nó xảy ra trong tiêu đề trang hay không, để hỗ trợ bảng xếp hạng tài liệu dựa trên khái niệm quan trọng), hoặc thậm chí kết quả xử lý ngôn ngữ bổ sung (ví dụ, chỉ ra rằng term là một phần của tên địa điểm, để hỗ trợ tìm kiếm địa chỉ). Trong bối cảnh web, thông tin văn bản (anchor text information) (văn bản liên quan đến các siêu liên kết từ các trang khác trang trong câu hỏi) là hữu ích trong việc làm phong phú thêm các đại diện của tài liệu nội dung (ví dụ, thông tin này thường cũng được lưu trữ trong các chỉ số. Trong ví dụ thể hiện trong hình 4.1, chúng ta thấy rằng: 39 term 1 occurs in {d1, d5, d6, d11,...}, term 2 occurs in {d11, d23, d59, d84,...}, and term 3 occurs in {d1, d4, d11, d19,...}. Trong thực tế thực hiện, chúng tôi giả định rằng các tài liệu có thể được xác định bởi một số nguyên duy nhất từ 1 đến n, trong đó n là tổng số tài liệu. Nói chung, thông tin đăng được sắp xếp theo id tài liệu, mặc dù cũng có các cách sắp xếp khác. Id tài liệu không có ý nghĩa ngữ nghĩa vốn có, mặc dù việc chuyển nhượng id số đến các văn bản không cần phải được tùy ý. Ví dụ, các trang từ cùng một tên miền có thể được đánh số liên tục. Hoặc là, theo một cách khác, những trang có chất lượng cao hơn (có cơ sở, ví dụ, trên các giá trị PageRank) có thể được gán giá trị số nhỏ hơn để chúng xuất hiện trước danh sách tin đăng. Dù bằng cách nào, một cấu trúc dữ liệu phụ trợ là cần thiết để duy trì mapping từ id tài liệu số nguyên cho một số xử lý khác có ý nghĩa hơn, chẳng hạn như một URL. Hình 2.5. Minh họa đơn giản của một chỉ mục ngược. Mỗi term có liên quan với một danh sách các thông tin đăng. Mỗi niêm yết bao gồm một id tài liệu và một trọng số, ký hiệu là p trong trường hợp này. Một chỉ số đảo ngược cung cấp truy cập nhanh đến tài liệu id có chứa một từ. Cho một truy vấn, thu hồi liên quan đến danh sách đăng đem lại kết hợp với truy vấn điều khoản và vượt qua các tin đăng để tính toán kết quả. Trong trường hợp đơn giản nhất, boolean retrieval liên quan đến việc thiết lập hoạt động (hợp nhất cho boolean OR và giao cắt cho boolean AND) vào danh sách tin đăng, mà có thể được thực hiện rất hiệu quả từ các bài đăng được sắp xếp theo id tài liệu. Trong trường hợp tổng quát, tuy nhiên, điểm số truy vấn tài liệu phải được tính toán. Điểm số tài liệu một phần được lưu trữ trong các cấu trúc được gọi là tích lũy. Cuối cùng (tức là, một khi tất cả tin đăng đã được xử lý), các tài liệu đầu k được giải nén (extract) sau đó để mang lại một danh sách xếp hạng các kết quả cho người sử dụng. Tất nhiên, có rất nhiều 40 chiến lược tối ưu hóa để đánh giá truy vấn (cả hai gần đúng và chính xác) để giúp giảm số lượng đăng mà một động cơ thu hồi phải kiểm tra. Kích thước của một chỉ số đảo ngược khác nhau, tùy thuộc vào trọng số lưu trữ trong mỗi bài gửi. Nếu tần số chỉ có hạn được lưu giữ, một chỉ số đảo ngược cũng được tối ưu hóa có thể là một phần mười kích thước của bộ sưu tập tài liệu gốc. Một chỉ số đảo ngược chứa đựng thông tin về vị trí sẽ dễ dàng lớn hơn nhiều lần chỉ số không chứa. Nói chung, có thể giữ toàn bộ từ vựng (tức là, Từ điển của tất cả các term) trong bộ nhớ, đặc biệt là với các kỹ thuật như rontcoding. Tuy nhiên, ngoại trừ có nguồn lực tốt, web thương mại công cụ tìm kiếm, danh sách đăng thường quá lớn để lưu trữ trong bộ nhớ và phải được tổ chức vào đĩa, thường ở dạng nén. Đánh giá truy vấn, do đó, nhất thiết phải liên quan đến việc truy cập đĩa ngẫu nhiên và "giải mã" các thông tin đăng. Một khía cạnh quan trọng của vấn đề thu hồi là tổ chức hoạt động của đĩa như giảm thiểu tìm kiếm ngẫu nhiên. Một lần nữa, cuộc thảo luận ngắn gọn này bao quát nhiều phức tạp và tạo nên một sự bất bình đẳng to lớn đến một lượng lớn các nghiên cứu trong tìm kiếm thông tin. Tuy nhiên, mục tiêu của chúng tôi là cung cấp cho người đọc một cái nhìn tổng quan của các vấn đề quan trọng; Thuật toán lập chi mục ngược cơ bản (4) 1: class Mapper 2: procedure Map (docid n, doc d) 3: H ← new AssociativeArray 4: for all term t ∈ doc d do 5: H{t} ← H{t} + 1 6: for all term t ∈ H do 7: Emit (term t, posting (n, H{t})) 1: class Reducer 2: procedure Reduce (term t, postings [ (n1, f1), (n2, f2)...]) 3: P ← new List 4: for all posting (a, f) ∈ postings [ (n1, f1), (n2, f2)...] do 5: Append (P, (a, f)) 6: Sort (P ) 7: Emit (term t, postings P ) 2.2.3. Cài đặt theo cơ bản MapReduce được thiết kế ngay từ đầu để sản xuất các cấu trúc dữ liệu khác nhau liên quan đến tìm kiếm web, bao gồm các chỉ số ngược và web đồ thị. Chúng ta bắt đầu với các thuật toán lập chỉ mục ngược cơ bản thể hiện trong thuật toán. 4 Data-Intensive Text Processing with MapReduce - Jimmy Lin The iSchool University of Maryland 41 Đầu vào cho các mapper gồm id tài liệu (key) kết hợp với thực tế nội dung (value). Tài liệu cá nhân được xử lý song song bởi mappers. Đầu tiên, mỗi tài liệu được phân tích và chia nhỏ thành các thành phần term của nó. Các đường ống xử lý khác nhau tùy theo ứng dụng và loại tài liệu, nhưng đối với các trang web thường liên quan đến việc stripping out các thẻ HTML và các yếu tố khác như mã JavaScript, tokenizing, case folding, removing stopwords (các từ phổ biến như 'the', 'a', 'của', vv), và stemming (loại bỏ sẽ gắn từ từ để 'những con chó' trở thành 'chó'). Một khi các tài liệu đã được phân tích, tần số hạn được tính bằng cách duyệt qua tất cả các điều khoản và theo dõi đếm. Dòng 4 và 5 trong mã giả phản ánh quá trình tính toán tần số hạn, nhưng ẩn chứa các chi tiết của tài liệu xử lý. Sau khi biểu đồ này đã được xây dựng, các mapper sau đó lặp lại trên tất cả các kỳ hạn. Đối với mỗi học kỳ, một cặp bao gồm id tài liệu và tần số hạn được tạo ra. Mỗi cặp, ký hiệu là hn, H {t} i trong mã giả, đại diện một đăng tải cá nhân. Mapper sau đó phát ra một cặp key-value trung gian với term như là key và posting là value, trong dòng 7 của mapper pseudo-code. Mặc dù như đã trình bày ở đây chỉ có tần số hạn được lưu trữ trong việc posting, thuật toán này có thể dễ dàng tăng cường để lưu trữ thông tin bổ sung (ví dụ, vị trí term) trong payload. Trong giai đoạn shuffle và sắp xếp, thời gian chạy MapReduce về cơ bản thực hiện một nhóm lớn, phân phối bởi các tin đăng bởi term. Không có bất kỳ nỗ lực thêm vào nào của các lập trình viên, các framework thực hiện tập hợp tất cả các bài đăng thuộc trong cùng một danh sách tin đăng. Việc này đơn giản hóa rất nhiều nhiệm vụ của reducer, chỉ cần đơn giản tập hợp lại với nhau tất cả các bài đăng và ghi chúng vào đĩa. Reducer bắt đầu bằng việc khởi tạo một danh sách rỗng và sau đó gắn thêm tất cả các tin đăng liên quan cùng một key (term) vào danh sách. Các tin đăng này sau đó được sắp xếp theo id tài liệu, và toàn bộ danh sách thông tin đăng phát ra như là một value, với term như là key. Thông thường, danh sách đăng được nén đầu tiên, nhưng chúng ta sẽ tạm bỏ lại điều này bây giờ. Các cặp key-value cuối cùng được ghi vào đĩa và bao gồm các chỉ số ngược. Vì mỗi reducer viết ra nó trong một file riêng biệt trong hệ thống tập tin phân phối, chỉ số cuối cùng của chúng tôi sẽ được chia trên các tập tin r, trong đó r là số reducers. Không cần thiết củng cố thêm những tập tin này. Xét một cách riêng biệt, chúng tôi cũng phải xây dựng một chỉ số cho bản thân các danh sách bài đăng cho công cụ phục hồi: việc này là điển hình trong hình thức của việc mapping từ term đến pairs (tập tin, byte offset), để đưa ra một thuật ngữ, các công cụ phục hồi có thể lấy danh sách tin đăng của mình bằng cách mở các tập tin thích hợp và tìm đến đúng vị trí byte offset trong tập tin đó. Thực hiện các thuật toán hoàn chỉnh được minh họa trong hình với một ví dụ đồ chơi gồm ba tài liệu, ba mapper, và hai reducer. Cặp key-value trung gian (từ mapper) và các cặp key-value cuối cùng bao gồm các chỉ số đảo ngược (từ reducer) được hiển thị trong các hộp với các đường chấm. Các bài đăng được hiển thị như các cặp hộp (pairs of boxes), với id tài liệu ở bên trái và tần số term ở bên phải. 42 Hình 2.6: Minh họa đơn giản cơ sở thuật toán lập chỉ mục ngược trong MapReduce với ba mapper và hai reducer Mô hình lập trình MapReduce cung cấp một biểu hiện rất ngắn gọn về các thuật toán lập chỉ mục ngược. Thực hiện của nó ngắn gọn tương tự: các thuật toán cơ bản có thể được thực hiện với chỉ một vài chục dòng mã trong Hadoop (với xử lý tài liệu tối thiểu). Một thực hiện như vậy có thể hoàn thành một nhiệm vụ lập trình kéo dài một tuần trong một khóa học cho học viên cao học hoặc sinh viên năm thứ nhất tốt nghiệp đại học. Trong một phi MapReduce indexer (non- MapReduce indexer), một phần đáng kể của các mã được dành cho nhóm đăng bởi term, hạn chế được áp đặt bởi bộ nhớ và đĩa (ví dụ, dung lượng bộ nhớ bị hạn chế, đĩa tìm là chậm, vv). Trong MapReduce, các lập trình viên không cần phải lo lắng về bất cứ vấn đề này, hầu hết các nâng nặng được thực hiện bởi framework thực hiện. 2.2.4. Cài đặt thuật toán cải tiến Các thuật toán lập chỉ mục ngược được trình bày trong phần trước phục vụ như là một cơ sở hợp lý. Tuy nhiên, có một khả năng mở rộng ý nghĩa bottleneck (nghẽn cổ chai): thuật toán giả định rằng có đủ bộ nhớ để giữ tất cả các tin đăng liên quan cùng một term. Vì framework MapReduce cơ bản không đảm bảo về trật tự của các value liên quan đến cùng một key, reducer đầu tiên buffers tất cả các tin đăng và sau đó thực hiện một sắp xếp trong bộ nhớ trước khi ghi vào đĩa. Đối với phục hồi hiệu quả, thông tin đăng cần phải được sắp xếp theo id tài liệu. Tuy nhiên, khi bộ sưu tập trở nên lớn hơn, danh sách tin đăng trở nên dài hơn, và tại một số điểm trong thời gian, reducer sẽ hết bộ nhớ. Có một giải pháp đơn giản cho vấn đề này. Kể từ khi framework thực hiện đảm bảo rằng các key đến được với từng reducer trong thứ tự sắp xếp, một cách để vượt qua những khả năng mở rộng bottleneck là để cho thời gian chạy MapReduce làm các phân loại cho chúng ta. Thay vì phát ra cặp key-value của các loại sau đây: (term t, posting ) 43 Người ta phát ra cặp key-value trung bình của các loại thay vào đó: (tuple , tf f) Nói cách khác, key là một tuple chứa các thuật ngữ và các id tài liệu, trong khi value là tần số term. Đây chính là mẫu thiết kế chuyển đổi value-to-key chính xác được giới thiệu. Với thay đổi này, Mô hình lập trình đảm bảo rằng các thông tin đăng đến được theo thứ tự đúng. Điều này, kết hợp với thực tế mà reducer có thể giữ trạng thái trên nhiều key, cho phép danh sách tin đăng phải được tạo ra với việc sử dụng bộ nhớ tối thiểu. Một chi tiết là, hãy nhớ rằng chúng ta phải xác định một partitioner tùy chỉnh để đảm bảo rằng tất cả các tuples với cùng một term được xáo trộn đến cùng một reducer. Các thuật toán MapReduce ngược lập chỉ mục sửa đổi (revised MapReduce inverted indexing algorithm) được thể hiện trong thuật toán Mapper vẫn không thay đổi đối với hầu hết các phần, khác hơn sự khác biệt trong các cặp key-value trung gian. Phương pháp Reduce được gọi cho mỗi key (tức là, ht, ni), và do thiết kế, sẽ chỉ có một value liên quan tới mỗi key. Đối với mỗi cặp key-value, một bài viết có thể được bổ sung trực tiếp vào danh sách tin đăng. Khi thông tin đăng được đảm bảo đến đúng thứ tự sắp xếp bởi id tài liệu, chúng có thể từng bước mã hóa trong hình thức nén - do đảm bảo một bộ nhớ nhỏ. Cuối cùng, khi tất cả các tin đăng liên quan đến cùng một term đã được xử lý (tức là, t 6 = tprev), toàn bộ danh sách thông tin đăng được phát ra. Danh sách đăng cuối cùng phải được viết ra trong phương thức Close. Với các thuật toán cơ bản, trọng tải có thể dễ dàng thay đổi: bằng việc đơn giản thay thế các giá trị trung gian f (tần số term) với bất cứ điều gì khác đang mong muốn (Ví dụ, thời hạn thông tin định vị). Có một chi tiết mà ta phải nắm rõ khi xây dựng chỉ số đảo ngược. Vì gần như tất cả các mô hình retrieval đi vào chiều dài tài liệu tài khoản khi tính toán điểm số truy vấn tài liệu, thông tin này cũng phải được giải nén. Mặc dù việc thể hiện tính toán này là minh bạch như các job MapReduce khác, nhiệm vụ này thực sự có thể được xếp vào quá trình lập chỉ mục ngược. Khi xử lý các term trong mỗi tài liệu, chiều dài tài liệu được biết đến, và có thể được viết ra như "phụ liệu" trực tiếp để HDFS. Chúng ta có thể tận dụng lợi thế của các khả năng cho một mapper để giữ trạng thái qua xử lý nhiều tài liệu theo cách sau đây: một mảng kết hợp trong bộ nhớ (in-memory associative) được tạo ra để lưu trữ độ dài tài liệu, được phổ biến như mỗi tài liệu được xử lý. Khi mapper kết thúc xử lý hồ sơ đầu vào (input records), độ dài tài liệu được viết ra để HDFS (tức là, trong các phương thức Close). Cách tiếp cận này thực chất là một biến thể của trong-mapper kết hợp mô hình (in-mapper combining pattern). Dữ liệu chiều dài tài liệu (Document length data) kết thúc trong m file khác nhau, trong đó m là số mapper; những tập tin này sau đó được hợp nhất thành một đại diện nhỏ gọn hơn. Ngoài ra, thông tin chiều dài tài liệu có thể được phát ra trong cặp key-value đặc 44 biệt bởi các mapper. Một người sau đó phải viết partitioner tùy chỉnh để các cặp key- value đặc biệt được xáo trộn đến một reducer đơn, trong đó sẽ chịu trách nhiệm viết ra chiều dài dữ liệu tách biệt với danh mục tin đăng. Thuật toán Tập chỉ mục ngược mở rộng (5) 1: class Mapper 2: method Map (docid n, doc d) 3: H ← new AssociativeArray 4: for all term t ∈ doc d do 5: H{t} ← H{t} + 1 6: for all term t ∈ H do 7: Emit (tuple (t, n), tf H{t}) 1: class Reducer 2: method Initialize 3: tprev ← ∅ 4: P ← new PostingsList 5: method Reduce (tuple (t, n), tf [f ]) 6: if t ƒ= tprev ∧ tprev ƒ= ∅ then 7: Emit (term tprev, postings P ) 8: P.Reset () 9: P.Add ( (n, f)) 10: tprev ← t 11: method Close 12: Emit (term t, postings P ) 2.2.5. Nén chỉ mục Chúng ta trở lại câu hỏi về việc làm thế nào để posting được thực sự nén và lưu trữ trên đĩa. Chương này dành một số lượng đáng kể không gian cho chủ đề này vì nén chỉ số là một trong những khác biệt chính giữa một "đồ chơi" indexer và một indexer hoạt động trên bộ sưu tập thực tế. Trái lại, thuật toán MapReduce inverted indexing khá đơn giản. Chúng ta hãy xem xét các trường hợp kinh điển mà mỗi lần post bao gồm một tài liệu id và tần số term. Một thực hiện đơn giản (na¨ıve implementation) có thể biểu diễn đầu tiên như một số nguyên 32-bit và thứ hai là một số nguyên 16-bit. Do đó, một danh sách tin đăng có thể được mã hóa như sau: [ (5, 2), (7, 3), (12, 1), (49, 1), (51, 2),...] 5Data-Intensive Text Processing with MapReduce - Jimmy Lin The iSchool University of Maryland 45 nơi từng posting được đại diện bởi một cặp trong ngoặc đơn. Lưu ý rằng tất cả các dấu ngoặc, dấu ngoặc đơn, dấu phẩy chỉ được bao gồm để tăng cường khả năng đọc; trong thực tế các thông tin đăng sẽ được biểu diễn như một dòng suối dài các số nguyên. Thực hiện đơn giản này sẽ yêu cầu sáu byte cho mỗi đăng tải. Sử dụng chương trình này, toàn bộ chỉ số đảo ngược sẽ lớn như chính bản thân bộ sưu tập. May mắn thay, chúng tôi có thể làm tốt hơn thế một cách đáng kể. Bí quyết đầu tiên là để mã hóa sự khác nhau giữa id tài liệu, trái ngược với bản thân các tài liệu id. Khi thông tin đăng được sắp xếp theo id tài liệu, sự khác biệt (gọi là d -gaps) phải là số nguyên dương lớn hơn không. Danh sách tin đăng bên trên, đại diện với d -gaps, sẽ là: [ (5, 2), (2, 3), (5, 1), (37, 1), (2, 2),...] Tất nhiên, chúng tôi thực sự phải mã hóa các id tài liệu đầu tiên. Chúng tôi đã không bị mất bất kỳ thông tin nào, vì các id tài liệu gốc có thể dễ dàng xây dựng lại từ d -gaps. Tuy nhiên, không rõ ràng rằng chúng tôi cũng đã giảm yêu cầu không gian vì d -gap lớn nhất có thể nhỏ hơn số lượng tài liệu trong bộ sưu tập. Đây là nơi mà bí quyết thứ hai xuất hiện, là đại diện cho các d –gaps theo cách mà mất ít không gian cho số nhỏ hơn. Tương tự như vậy, chúng tôi muốn áp dụng các kỹ thuật tương tự để nén các tần số hạn, vì đối với hầu hết các phần, chúng cũng là những giá trị nhỏ. Nhưng để hiểu làm thế nào đi...i bắt đầu với một thực hiện cơ bản của một thuật toán lập chỉ mục ngược, nhưng nhanh chóng nhận thấy một bottleneck có khả năng mở rộng xuất phát từ việc buffer postings trong bộ nhớ. Áp dụng mô hình thiết kế chuyển đổi value-to-key giải quyết vấn đề này bằng cách giảm tải nhiệm vụ đăng sắp xếp bởi id tài liệu đến framework thực hiện MapReduce. Chúng tôi cũng đã khảo sát các kỹ thuật khác nhau cho việc nén số nguyên, việc trình bày danh sách posting nhỏ gọn hơn và nhanh hơn để xử lý. Một ví dụ cụ thể: ta có thể sử dụng mã Golomb cho nén d -gaps và mã số γ cho các tần số term. Chúng tôi đã cho thấy mẫu thiết kế để đảo ngược được giới thiệu như thế nào trong phần trên để tính toán tần số tương đối có thể được sử dụng để thiết lập đúng thông số nén. 55 CHƯƠNG 3 THỬ NGHIỆM THUẬT TOÁN ĐÁNH GIÁ Ý KIẾN TRÊN MẠNG XÃ HỘI 3.1 Mã nguồn mở Solr 3.1.1. Giới thiệu Solr là một máy chủ tìm kiếm độc lập với các hàm API giống REST (Representational State Transfer). Bạn đưa các documents cho nó (để đánh chỉ mục) thông qua XML, JSON hoặc nhị phân bằng HTTP. Và truy vấn thông qua HTTP GET và nhận được các kết quả XML, JSON hoặc nhị phân. Solr sử dụng thư viện tìm kiếm Lucene và mở rộng nó. 3.1.2. Các tính năng chính của Solr:  Khả năng tìm kiếm văn bản toàn diện (Full-Text Search)  Được chỉnh sửa để tối ưu khi lưu lượng tìm kiếm trên server lớn.  Sử dụng các chuẩn mở để giao tiếp với các hệ thống khác. Thông qua XML, JSON và HTTP.  Có giao diện quản lý server trên web toàn diện và dễ sử dụng.  Khả năng mở rộng cao – dễ dàng nhân bản hiệu quả tới các Solr Search Servers khác để cùng xử lý.  Sự mềm dẻo và khả năng chỉnh sửa dễ dàng thông qua cấu hình bằng XML. Sử dụng kiến trúc Plugin mở rộng, giúp cho việc thêm các chức năng mới dễ dàng hơn. 3.2 Mã nguồn mở Nutch Nutch là một cài đặt mã nguồn mở của một search engine được Doug Cutting – Người sáng lập của cả Lucene và Hadoop, và Mike Cafarella khởi đầu. Nó cung cấp tất cả công cụ cần thiết để xây dựng một search engine. 3.2.1. Các lý do để tự xây dựng một Search Engine 1. Sự trong suốt. Nutch là mã nguồn mở, vì thế mọi người có thể thấy được cách các thuật toán xếp hạng hoạt động. Với những search engines thương mại, sự chi tiết về thuật toán là bí mật vì thế không thể biết một kết quả tìm kiếm được xếp hạng như thế nào. Hơn thế nữa, một vài search engines cho phép việc xếp hàng dựa trên việc trả tiền. Nutch phù hợp cho việc giảng dạy và các 56 tổ chức chính phủ, khi mà sự rõ ràng của việc xếp hạng là quan trọng hơn. 2. Sự hiểu biết. Chúng ta không có mã nguồn của Google, vì thế Nutch có lẽ là thứ tốt nhất chúng ta có. Rất thú vị để thấy cách hoạt động của một search engine lớn. Nutch còn thu hút các nhà nghiên cứu muốn thử các thuật toán tìm kiếm mới vì nó rất dễ mở rộng. 3. Sự mở rộng. Không thích cách các search engine khác hiển thị kết quả? Tự viết search engine sử dụng Nutch! Nutch rất mềm dẻo, nó có thể được tùy chỉnh và tích hợp vào trong ứng dụng. 3.2.2. Các tính năng chính của Nutch Nó cho phép: 1. Thu thập dữ liệu, phân tích và đánh chỉ mục song song và phân tán thông qua việc sử dụng MapReduce và hệ thống file phân tán (Hadoop). 2. Hỗ trợ đánh chỉ mục nhiều loại định dạng: plain text, HTML, XML, ZIP, OpenDocument (OpenOffice.org), Microsoft Office (Word, Excel, Powerpoint), PDF, JavaScript, RSS, RTF 3. Sử dụng cơ sở dữ liệu đồ thị liên kết (Link-graph database) để sử dụng trong thuật toán PageRank. Hình 3.1. Sơ đồ hoạt động của Nutch khi sử dụng như một Crawler Đầu tiên, có tập URLs khởi tạo, thông qua Injector chuyển nó vào CrawlDB. CrawlDB thông qua Generator sẽ tạo ra một Segment (lúc này trong Segment sẽ có một thư mục crawl_generate chứa các URLs cần thu thập dữ liệu). Fetcher sẽ dùng các URLs trong Segment để thu thập dữ liệu từ các trang web và cập nhật lại Segment (lúc này, Segment sẽ có thêm các dữ liệu thu thập được). Parser sử dụng dữ liệu trong Segment để phân tích ra text, URLs, metadata Sau đó CrawlDBTool sẽ cập nhật 57 thêm các URLs mới từ các trang web thu thập được vào trong CrawlDB. Quá trình này sẽ được lặp đi lặp bao nhiêu lần tùy theo việc cấu hình độ sâu cần thu thập trên mỗi trang web. Hình 3.2. Sơ đồ đầy đủ của Nutch khi sử dụng như một Search Engine Trong hình trên, dữ liệu thu thập từng phần (Segments) được sử dụng để tạo ra LinkDB (cơ sở dữ liệu chứa các liên kết). Sau đó Indexer sử dụng Segments, LinkDB và CrawlDB để đánh chỉ mục (sử dụng Lucene) tạo ra Index. Segments chứa các dữ liệu đã thu thập được, LinkDB được sử dụng trong thuật toán PageRank lúc đánh chỉ mục và CrawlDB chứa các URLs đã thu thập được. Searcher tìm kiếm các kết quả trong Index để trả về cho giao diện người dùng (Web). 3.3. API biểu đồ Facebook Trong khuôn khổ luận văn, chương trình được thử nghiệm trên mạng xã hội Facebook. Để có thể truy xuất và thu thập dữ liệu trên Facebook, chúng ta đã được các nhà phát triển cung cấp 1 công cụ tuyệt vời đó là Facebook Graph API. Trước hết Facebook coi các mối quan giữa các thực thể như là một "Đồ thị xã hội" (Social Graph) Hình 3.3. Facebook Facebook Graph API là cách chủ yếu để lấy dữ liệu vào và ra khỏi đồ thị xã hội 58 của Facebook. Đó là một HTTP API dựa trên mức độ thấp mà bạn có thể sử dụng để truy vấn dữ liệu, gửi những câu chuyện mới, tải lên hình ảnh và một loạt các nhiệm vụ khác mà một ứng dụng có thể cần phải làm. Hình 3.4. Trao đổi qua API Graph API được đặt tên theo ý tưởng của một "đồ thị xã hội" - một đại diện của các thông tin trên Facebook bao gồm:  node (nút): Một cách cơ bản là những "thứ" người ta sử dụng, một hình ảnh, một trang, một nhận xét trong facebook  edge (cạnh): Là các kết nối giữa những "thứ", chẳng hạn như kết nối giữa hình ảnh và trang chứa ảnh đó, hoặc một ghi chú và bức ảnh được ghi chú đó  field (trường/lĩnh vực): Thông tin về những "thứ", chẳng hạn như ngày sinh nhật của người sử dụng, hoặc tên của một trang. Graph API là dựa trên HTTP, do đó, làm việc với bất kỳ ngôn ngữ nào có một thư viện HTTP, như cURL, urllib. Chúng tôi sẽ giải thích thêm một chút về những gì bạn có thể làm với điều này trong phần dưới đây, nhưng nó có nghĩa là bạn cũng có thể sử dụng Graph API trực tiếp trong trình duyệt của bạn, ví dụ như gửi một đòi hỏi này tương đương với: Và nhận được kết quả, nó chứa thông tin về icon của facebook graph. Copy giá trị url có trong kết quả và dán lên trình duyệt bạn sẽ có được icon đó. { "data": { "url": "https://fbcdn-profile-a.akamaihd.net/hprofile-ak-xpf1/t1.0- 1/p50x50/1377580_10152203108461729_809245696_n.png", "is_silhouette": false } } Facebook Graph API hỗ trợ định dạng dữ liệu JSON. 59 Với Facebook Graph API, ta có thể truy xuất tìm kiếm tất cả các dữ liệu thống kê có trong các trang mạng xã hội Facebook. 3.4. Solr trên Hadoop và tìm kiếm thử nghiệm 3.4.1. Sơ đồ 3.4.1.1. Sơ đồ hoạt động của hệ thống khảo sát Chuẩn metadata JSON APACHE HADOOP Tài liệu 1 Crawler HDFS HDFS Tài liệu n MẠNG HỘI XÃ Facebook HTTP FS Graph API APACHE SOLR Đánh chỉ mục ngược Kết quả truy vấn Bộ tìm kiếm Hình 0.5: Mô hình tổng quan của hệ thống khảo sát Đầu tiên là Crawler sẽ thực hiện việc dò tìm dữ liệu, cụ thể là các Post và comments nằm rải rác trên các trang mạng xã hội Facebook, tạo thành các Documents dữ liệu đầu vào cho dạng JSON và được đưa tới phân tán tại server của Apache Hadoop, Apache Solr sử dụng các tài liệu trên hệ thống HDFS để thực hiện việc đánh chỉ mục và tìm kiếm. Dữ liệu đầu ra là kết quả tìm kiếm theo từ khóa người dùng, thống kê và trực quan hóa kết quả. Hệ thống chỉ mục, tìm kiếm từ khóa sẽ trả kết quả về văn bản gốc phù hợp đã được lưu trữ tại hệ thống lưu trữ. Thư viện lập chỉ mục đã được tích hợp sẵn trong Apache Solr. 60 3.4.1.2. Sơ đồ giai đoạn đánh chỉ mục Data Data Data Inverted Index Documents INDEX Hình 0.6: Sơ đồ giai đoạn đánh chỉ mục Các tài liệu được lưu trữ phân tán trên Hadoop được đánh chỉ mục với MapReduce theo mô hình sau: Hình 0.7: đánh chỉ mục với MapRedece trên Solr Solr sử dụng chuyển đổi tất cả các bản ghi đầu vào trở thành các cặp <Key- Value> và từ đó tạo thành class SolrInputDocument và sau đó thực hiện đánh chỉ mục hàng loạt. Solr sử dụng một số class được viết sẵn có hỗ trợ MapReduce để thực hiện đánh chỉ mục: MapReduceIndexTool 61 Để gọi class MapReduceIndexerTool trong Solr ta làm như sau: $ hadoop jar /opt/cloudera/parcels/CDH/lib/solr/contrib/mr/search-mr-*- job.jar \ org.apache.solr.hadoop.MapReduceIndexerTool \ -D 'mapred.child.java.opts=-Xmx500m' \ --log4j /opt/cloudera/parcels/CDH/share/doc/search*/examples/solr- nrt/log4j.properties \ --morphline-file morphline.conf \ --output-dir hdfs://nameservice1:8020/tmp/outdir \ --verbose --go-live --zk-host localhost:2181/solr Ngoài ra còn có 1 số class hỗ trợ đánh chỉ mục trong Solr như: SolrIndexUpdateMapper SolrXMLDocRecordReader SolrIndexUpdater 3.4.1. Cài đặt cụm máy Hadoop Phần này trình bày cách xây dựng một cụm máy Hadoop hoàn chỉnh với 2 máy trong môi trường ảo hóa. Máy ảo sẽ đóng vai trò là máy khách và máy chính sẽ đóng vai trò máy chủ. Quá trình cài đặt trải qua các bước sau: Bước 1: Chuẩn bị Cài đặt java Hadoop được viết bằng Java, vì vậy để chạy được Hadoop, tại mỗi máy trên cụm đều phải được cài đặt môi trường Java (báo cáo này sử dụng Java phiên bản 1.8) Kiểm tra cài đặt môi trường java bằng câu lệnh như sau: $ java -version java version "1.8.0_91" Java (TM) SE Runtime Environment (build 1.8.0_91-b14) Java HotSpot (TM) 64bit server VM (build 25.91-b14, mixed mode) Nếu kết quả hiện thị có dạng tương tự như trên thì điều này có nghĩa máy tính đã được cài đặt môi trường Java. Cài đặt mạng Hadoop sử dụng IP4 vì vậy sau khi hoàn tất bước 2 (cài đặt Hadoop) ta sẽ thực hiện vô hiệu hóa IP6 khi máy chạy Hadoop. Việc này được thực hiện bằng cách thêm dòng sau vào tệp tin có đường dẫn là /usr/local/hadoop/conf/hadoop-env.sh: export HADOOP_OPTS=-Djava.net.preferIPv4Stack=true Tiếp theo, để đơn giản ta sẽ gán địa chỉ IP cho máy chủ là 192.168.18.1 và máy 62 khách là 192.168.18.128. Tên của 2 máy này cũng được xác định ở bước này, 2 máy sẽ có tên gọi là MAY_CHU và MAY_KHACH. Mở tệp hosts ở đường dẫn /etc/hosts trên cả 2 máy và thêm 2 dòng sau vào cuối nội dung của tệp: 192.168.18.1 MAY_CHU 192.168.18.128 MAY_KHACH Người dùng trên các máy Trên cả 2 máy ta đều sử dụng người dùng có tên là hduser để đơn giản và để tránh việc Hadoop xung đột với các chương trình khác đang chạy trên máy. Việc tạo người dùng hduser trên hệ thống của cả 2 máy được thực hiện như sau: $ sudo addgroup hadoop $ sudo adduser --ingroup hadoop hduser Cấu hình SSH Hadoop sử dụng SSH để điều khiển việc chạy các tiến trình trên các máy khách từ máy chủ. Theo cơ chế trên, máy chủ sẽ thực hiện kết nối với các máy khách một cách tự động thông qua qua dịch vụ SSH trên máy khách này. Do vậy, trên mỗi máy khách cần được cài đặt SSH và SSH trên mỗi máy khách này cần được cấu hình để cho phép các tiến trình chạy với quyền của người dùng Hadoop (hduser) có thể đăng nhập vào mà không cần điền mật khẩu. Nếu máy chưa được cài đặt SSH ta phải cài đặt gói OpenSsh cho máy bằng câu lệnh sau: $ sudo apt-get install openssh-server Sau khi cài đặt SSH thành công, ta thực hiện cấu hình cho cả 2 máy để cho phép các tiến trình hoạt động dưới quyền hdsuer mà không cần điền mật khẩu: $ su - hduser $ ssh-keygen -t rsa -P "" $ cat $HOME/.ssh/id_rsa.pub >> $HOME/.ssh/authorized_keys Trên máy chủ ta thực hiện câu lệnh như sau để ghi đè mật khẩu lên cả máy chủ và máy khách: $ ssh-copy-id -i $HOME/.ssh/id_rsa.pub hduser@MAY_KHACH $ ssh-copy-id -i $HOME/.ssh/id_rsa.pub hduser@MAY_CHU Sau khi đã cấu hình thành công mật khẩu ta thực hiện kết nối với máy chủ với máy chủ và máy chủ với máy khách như sau: $ ssh hduser@MAY_CHU $ ssh hduser@MAY_KHACH Bước 2: Cài đặt hadoop Bước này sẽ hướng dẫn cấu hình cụm máy Hadoop với cấu trúc khách – chủ. Máy chủ sẽ đóng 2 vai trò: vai trò điều khiển đông thời với vai trò lưu trữ và thực hiện tác vụ con như một máy khách. Máy khách sẽ đóng vai trò lưu trữ và xử lý tác vụ con. 63 Ta thực hiện các bước sau trên tất cả các máy:  Tải Hadoop 1.2.0 từ trang chủ của Hadoop về máy, đặt tệp tin cài đặt hadoop vào thư mục ở địa chỉ /usr/local. Ta thực hiện các câu lệnh sau: $ cd /usr/local $ sudo tar xzf hadoop-1.2.0.tar.gz $ sudo mv hadoop-1.2.0 hadoop  Mở tệp tin $HOME/.bashrc và thêm các dòng sau vào cuối nội dung của tệp tin ở địa chỉ $HOME/.bashrc: # Set Hadoop-related environment variables export HADOOP_HOME=/usr/local/hadoop # Set JAVA_HOME (we will also configure JAVA_HOME directly for Hadoop later on) export JAVA_HOME=/usr/lib/jvm/java-8-oracle # Some convenient aliases and functions for running Hadoop-related commands unalias fs &> /dev/null alias fs="hadoop fs" unalias hls &> /dev/null alias hls="fs -ls" # If you have LZO compression enabled in your Hadoop cluster and # compress job outputs with LZOP (not covered in this tutorial): # Conveniently inspect an LZOP compressed file from the command # line; run via: # # $ lzohead /hdfs/path/to/lzop/compressed/file.lzo # # Requires installed 'lzop' command. # lzohead () { hadoop fs -cat $1 | lzop -dc | head -1000 | less } # Add Hadoop bin/ directory to PATH export PATH=$PATH:$HADOOP_HOME/bin  Thay đổi biến môi trường Java cho Hadoop bằng cách sửa tệp tin ở đường dẫn /usr/local/hadoop/conf/hadoop-env.sh như sau: Sửa 2 dòng sau: # The java implementation to use. Required. # export JAVA_HOME=/usr/lib/j2sdk1.5-sun Thành 64 # The java implementation to use. Required. export JAVA_HOME=/usr/lib/jvm/java-8-oracle  Cấu hình thư mục trên máy tính mà Hadoop Hadoop sẽ lưu dữ liệu như sau: $ sudo mkdir -p /app/hadoop/tmp #...and if you want to tighten up security, chmod from 755 to 750... $ sudo chmod 750 /app/hadoop/tmp  Thêm các dòng sau đây vào giữa thẻ ... của tệp tin ở đường dẫn /usr/local/hadoop/conf/core-site.xml: hadoop.tmp.dir /app/hadoop/tmp A base for other temporary directories. fs.default.name hdfs://MAY_CHU:54310 The name of the default file system. A URI whose scheme and authority determine the FileSystem implementation. The uri's scheme determines the config property (fs.SCHEME.impl) naming the FileSystem implementation class. The uri's authority is used to determine the host, port, etc. for a filesystem.  Cấu hình địa chỉ của máy cũng như cổng mà công việc sẽ được thực hiện. Thêm các dòng sau đây vào giữa thẻ ... của tệp tin ở đường dẫn /usr/local/ hadoop/ conf/mapred-site.xml: mapred.job.tracker MAY_CHU:54311 The host and port that the MapReduce job tracker runs at. If "local", then jobs are run in-process as a single map and reduce task.  Cấu hình số lượng nhân bản mà Hadoop sẽ thực hiện để nhân bản dữ liệu bằng cách thêm các dòng sau vào giữa thẻ ... của tệp tin ở đường dẫn sau /usr/local/hadoop/conf/hdfs-site.xml: 65 dfs.replication 2 Default block replication. The actual number of replications can be specified when the file is created. The default is used if replication is not specified in create time.  Riêng trên máy chủ ta phải cấu hình thêm như sau: Cấu hình máy sẽ làm nhiệm vụ điều khiển ở đây là máy Chu. Trên máy chủ, ta thêm dòng sau vào tệp tin ở đường dẫn /usr/local/hadoop/conf/masters: MAY_CHU Ta cấu hình các máy sẽ làm nhiệm vụ làm việc ở đây cả 2 máy sẽ đóng vai trò làm việc nên ta thêm 2 dòng sau vào cuối tệp tin ở đường dẫn /usr/local/hadoop/conf/slaves. MAY_CHU MAY_KHACH  Trước khi bắt đầu sử dụng cụm máy Hadop này, ta phải định dạng lại HDFS thông qua máy điều khiển bằng câu lệnh như sau: $ cd /usr/local/hadoop $ bin/hadoop namenode -format Chú ý rằng khi ta thực hiện câu lệnh này, tất cả dữ liệu hiện đang có trên hệ thống dữ liệu HDFS đều bị xóa bỏ. Bước 3: Khởi động cụm máy Hadoop và kết thúc khi hoàn thành công việc Quá trình khởi động thực hiện qua 2 bước: Khởi động HDFS và khởi động MapReduce Thành phần điều khiển được khởi động trên máy Chu và máy lưu trữ sẽ được khởi động trên cả máy Chu và may LamViec. Chạy tệp tin $HADOOP_HOME/bin/start-dfs.sh trên máy Chu: $ cd $HADOOP_HOME $ bin/start-dfs.sh Khởi động MapReduce: Thành phần quản lý công việc con sẽ được khởi động trên máy Chu và thành phần quản lý các tác vụ con được khởi động trên cả máy Chu và máy LamViec. Chạy câu lệnh bin/start-mapred.sh trên máy chủ. $ cd $HADOOP_HOME $ bin/start-dfs.sh Kiểm tra đã hoàn tất cài đặt Hadoop bằng câu lênh jps: 66 Trên máy chủ: $ jps 16017 Jps 14799 NameNode 15686 TaskTracker 14880 DataNode 15596 JobTracker 14977 SecondaryNameNode Trên máy khách: $ jps 15183 DataNode 15897 TaskTracker 16284 Jps Nếu kết quả như trên thì có nghĩa việc cài đặt Hadoop đã hoàn tất. Để tắt Hadoop ta thực hiện câu lệnh sau: $ cd $HADOOP_HOME $ bin/stop-all.sh 3.4.2. Cài đặt Nutch tích hợp với Solr Hướng dẫn cài đặt Nutch tích hợp với Solr. Trong báo cáo này ta sử dụng Nutch 1.6 và Solr 4.8.0. Cài đặt Nutch  Tải tệp tin apache-nutch-1.6-src.tar.gz từ địa chỉ https://archive.apache.org/dist/nutch/1.6/.  Giải nén tệp tin và chuyển thư mục tới đường dẫn /usr/local/nutch. $ tar –xvzf apache-nutch-1.6-src.tar.gz $ sudo mv apache-nutch-1.6-src /usr/local/nutch  Đi đến thư mục cài đặt Nutch bằng câu lệnh cd /usr/local/nutch.  Chỉnh sửa tệp tin nutch-default.xml bằng câu lệnh sudo gedit conf/nutch-default.xml, thêm những dòng sau vào cuối nội dung tệp tin: http.agent.name My Nutch Spider  Chạy câu lệnh: $ cd /usr/local/nutch $ ant runtime  Kết quả của câu lệnh trên là thư mục /usr/local/nutch/runtime được tạo ra. 67  Kiểm tra cài đặt Nutch thành công bằng câu lệnh sau $ cd /usr/local/nutch/runtime/deploy $ bin/nutch Nếu kết quả có dạng như sau thì có nghĩa việc cài đặt Nutch đã hoàn tất: Usage: nutch [-core] COMMAND ... Cài đặt Solr  Tải về tệp tin solr-4.8.0.tgz từ địa chỉ https://archive.apache.org/dist/lucene/solr/4.8.0/.  Giải nén tệp tin và di chuyển tới địa chỉ /usr/local/solr bằng câu lệnh: $ tar –xvzf solr-4.8.0.tgz $ sudo mv solr-4.8.0.tgz /usr/local/solr Hình 0.8: Giao diện làm việc của Solr  Đi đến thư mục example của Solr và khởi động Solr bằng câu lệnh: $cd /usr/local/solr/example $java –jar start.jar  Sau khi khởi động Solr ta có thể kiểm tra hoàn tất cài đặt Solr bằng cách truy cập trình duyệt web theo đường dẫn sau: Tích hợp Solr với Nutch  Sao chép tệp tin /usr/local/nutch/conf/schema-solr4.xml vào thư mục conf ở đường dẫn /usr/local/solr/example/solr/conf và đổi tên tệp tin thành schema.xml  Thêm dòng sau vào tệp tin schema.xml sau dòng <field name=“id” ./>: 68 <field name="_version_" type="long" indexed="true" stored ="true"/>  Khởi động Solr bằng câu lệnh $cd /usr/local/solr/example $java –jar start.jar  Ta có thể truy cập vào địa chỉ web 3.4.3. Thu thập dữ liệu Quá trình thu thập dữ liệu được thực hiện trên nền tảng MapReduce của Hadoop, tất cả các bước trong quá trình thu thập dữ liệu đều được thực hiện song song trên tất cả các máy của cụm máy Hadoop. Từng máy sẽ làm các nhiệm vụ thu thập dữ liệu với các URL được phân công sau đó kết quả của quá trình thu thập dữ liệu được trộn lại với nhau bằng hàm rút gọn kết quả (reducer). Các thư mục cuối cùng của quá trình thu thập được lưu lại trên hệ thống lưu trữ phân tán HDFS. Trước hết, việc thu thập dữ liệu trên Facebook được thực hiện qua Facebook Graph API. Ta có thể truy cập vào Facebook Graph API qua đường link sau: https://developers.facebook.com/tools/explorer Giao diện hiện lên như hình dưới: Hình 0.9: Giao diện làm việc của Facebook Graph API Đăng ký một App trên bộ công cụ phát triển Facebook, ta được cấp 1 Access Token (Là mã cho phép gửi đòi hỏi tới Server. Nếu bạn đang login vào một tài khoản facebook nào đó, giá trị này sẽ được mặc định hiển thị cho tài khoản đó.), sử dụng nó để có thể truy cập vào các trang Fanpage hoặc các trang cá nhân. 69 Hình 0.10: Access Token của một trình Facebook Graph API Sau đó ta thực hiện việc lấy thông tin từ các trang Facebook cần dò tìm khảo sát. Với công cụ Facebook Graph API, các lựa chọn tìm kiếm được thể hiện rõ ràng trong hình dưới: Hình 0.11: Thu thập dữ liệu từ trang mạng của trường THPT Hoàng Văn Thụ Tất cả các dữ liệu sau khi được Crawler lấy từ Fabook Graph API sẽ được đưa về Hadoop dưới định dạng JSON. Khởi động Hadoop và Solr: $ cd $HADOOP_HOME $ bin/start-all.sh $ cd $SOLR_HOME/example $ java –jar start.jar Sauk hi hoàn tất việc đưa thư mục chứa URL cần thu thập dữ liệu lên HDFS ta 70 bắt đầu thực hiện công việc thu thập dữ liệu bằng các câu lệnh sau: $ cd /usr/local/nutch/runtime/deploy $ hadoop –jar apache-nutch-1.6.job org.apache.nutch.crawl.Crawl thuthap1 –dir data –solr -depth 1 Câu lệnh này sẽ thực hiện thu thập dữ liệu từ trang web và đưa kết quả đên Solr để tạo chỉ mục ngược cho dữ liệu. Sau câu lệnh này cụm máy hadoop bắt đầu thu thập dữ liệu từ địa chỉ có trong nội dung tệp tin seed.txt. Ta có thể theo dõi quá trình thu thập dữ liệu các, công việc đang được tiến hành bằng mapReduce bằng cách truy cập địa chỉ Hình 0.12:Giao diên theo dõi quá trình làm việc của MapReduce Để đọc thông tin trong Crawldb của Nutch ta thực hiện câu lệnh sau: $ cd $NUTCH_HOME $ bin/nutch readdb data/crawldb –stats Quá trình thu thập dữ liệu của trang nhóm học sinh THPT 19-5 Hòa Bình ta có kết quả như sau: 71 Bảng 0.1: Kết quả thu thập dữ liệu ở 2 chế độ Chiều Chế độ một máy đơn Chế độ phân tán ảo Số URL đã được sâu (Standalone) (pseudo distributed) thu thập 1 137 giây 576 giây 1 2 748 giây 2016 giây 226 3 10264 giây Hơn 10 giờ 4513 Dựa vào bảng ta có thể thấy, với chiều sâu lớn hơn thì thời gian thu thập dữ liệu cũng tăng lên. Điều này là hoàn toàn dễ hiểu khi qua mỗi vòng lặp số URL mà Nutch phải thu thập cũng tăng lên ( từ 1 đến 4513). So sánh giữa 2 chế độ một máy đơn và chế độ phân tán ảo ta thấy có sự khác biệt rất rõ ràng. Chế độ phân tán ảo cho kết quả thời gian thu thập dữ liệu lớn hơn rất nhiều so với chế độ một máy đơn. Có thể giải thích điều này như sau: với một môi trường phân tán ảo thực tế tài nguyên của máy bị chi phối vào việc duy trì một môi trường ảo hóa do vậy tài nguyên RAM, tài nguyên chip xử lý không những không được tận dụng mà còn bị chi phối đi. Tuy nhiên việc thử nghiệm môi trường phân tán ảo cho ta kết quả về sự nhân bản của các khối dữ liệu là đúng, điều này chứng minh khả năng chịu lỗi và khôi phục dữ liệu khi có trục trặc của Hadoop. 3.5. Thực hiện tìm kiếm thử nghiệm trên tập chỉ mục đã thu thập được. Sau khi thực hiện thu thập dữ liệu ta có thể truy cập trang để thực hiện câu lệnh truy vấn ngay. Kết quả của các câu lệnh truy vấn này có thể ở nhiều dạng khác nhau rất dễ dàng tích hợp với các ứng dụng web. Có nhiều định dạng khác nhau được Solr sử dụng như định dạng PHP, XML, Json 72 Hình 0.13: Giao diện trang web tìm kiếm trên Solr Ta có thể dễ dàng xây dựng một giao diện web để thực hiện giao tiêp với Solr. Việc giao tiếp này bao gồm các công việc gửi từ truy vấn đến Solr, sau khi nhận được yêu cầu truy vấn Solr thực hiện tìm kiếm và trả lại kết quả. Kết quả này sẽ được trang web phân tích và hiển thị cho người dùng. Có nhiều bộ thư viện cho phép ta làm các công việc trên. Báo cáo này sử dụng một bộ thư viện giao tiếp với Solr có tên gọi là AJAX SOLR. AJAX SOLR cung cấp các thư viện cho phép giao tiếp với Solr và rất dễ sử dụng. Để thực hiện tìm kiếm thử trên Nutch cho kết quả rõ ràng hơn, báo cáo này đã thực hiện thu thập dữ liệu của các nhóm học sinh của một số trường trong tỉnh Hòa Bình: 1. https://www.facebook.com/groups/1573580766273010 2. https://www.facebook.com/Trường-THPT-Công-Nghiệp-Hòa-Bình 3. https://www.facebook.com/pages/THPT-chuyên-Hoàng-Văn-Thụ Tổng số tài liệu mà việc thu thập đã thực hiện là khoảng 2000 trang(bao gồm các trang mạng cá nhân và các trang fanpage tập thể của học sinh). Với dung lượng dữ liệu lên đến khoảng 2GB. Kết quả tìm kiếm thử nghiệm theo một số chủ đề phổ biến được ghi lại ở bảng sau: Bảng 0.2: Một số kết quả truy vấn theo chủ đề Từ khóa Thời gian tìm kiếm (1/1000 giây) Số kết quả Giáo dục 103 2910 Tuyển sinh 94 4361 Bóng đá 10 3689 Tình yêu 3 5743 Luật pháp 31 3713 Lớp 54 4078 Gia đình 3 4333 Đồng phục 2 3477 Toán 30 4118 Văn 2 4103 Tiếng Anh 6 3570 Một yêu cầu bắt buộc của các chương trình tìm kiếm dữ liệu là yêu cầu về thời gian. Một chương trình tìm kiếm phải đảm bảo đáp ứng thời gian tìm kiếm nhanh hơn rất nhiều so với đại đa số các nhiệm vụ trên dữ liệu lớn khác. Theo đánh giá ban đầu kết quả tìm kiếm trên tập dữ liệu là tương đối khả quan với điều kiện phần cứng trung bình. Các kết quả truy vấn không có thời gian vượt quá hàng phút đáp ứng được yêu cầu về thời gian tìm kiếm trên môi trường web. 73 Chương 3 trình bày cách xây dựng một cụm máy Hadoop hoàn chỉnh với thử nghiệm trên môi trường phân tán ảo so sánh khả năng hoạt động của Hadoop trên môi trường phân tán ảo và với duy nhất một máy tính. Thực nghiệm cho thấy khả năng hoạt động của Hadoop phụ thuộc rất nhiều vào dung lượng của RAM và khả năng tính toán của chip xử lý, tốc độ của Hadoop chỉ thực sự tăng lên khi cụm máy Hadoop được mở rộng quy mô về RAM cũng như chip xử lý. Việc thực hiện thử nghiệm Hadoop trên mội trường phân tán ảo, tuy vậy, cung đem lại nhiều kết quả rất tích cực ta có thể thấy thực tế quá trình nhân bản dữ liệu qua các máy trong cùng một mạng của Hadoop, ta có thể thấy được khả năng phục hồi dữ liệu khi xảy ra sự cố của Hadoop. Cách mà Hadoop phân chia các quá trình con của công việc thu thập dữ liệu bằng Nutch trên cụm máy phân tán. Theo dõi các công việc con hoạt động trong MapReduce, quá trình tạo cấu trúc dữ liệu của Nutch. Chương 3 cũng thực hiện việc cấu hình Nutch với một chương trình đánh chỉ mục và tìm kiếm nguồn mở được sử dụng rộng rãi là Solr. Solr cho kết quả truy vấn trên chỉ mục tương đối khả quan với điều kiện phần cứng và dữ liệu ở mức trung bình. Hoàn thành được việc xây dựng một trang web tìm kiêm đơn giản giao tiếp với Solr thay thế cho giao diện tìm kiếm mặc định của Solr. 74 Kết luận 1. Đánh giá kết quả của đề tài Đề tài đã tìm hiểu được kiến thức tổng quan về MapReduce, thuật toán đánh chỉ mục và chỉ mục ngược. Đồng thời xây dựng được hệ thống tìm kiếm và khảo sát đánh giá ý kiến học sinh trên mạng xã hội. Đề Tài đã thực hiện được các nội dung sau: - Tìm hiểu tổng quan về MapReduce và xây dựng thuật toán MapReduce cơ bản. - Tìm hiểu về thuật toán đánh chỉ mục và chỉ mục ngược kết hợp với MapReduce. - Xây dựng được chương trình khảo sát ý kiến trên mạng xã hội, tổng hợp,cài đặt và thử nghiệm hệ thống. 2. Hạn chế - Chưa nghiên cứu được các giải pháp tách từ tiếng Việt đầy đủ, do đó ảnh hưởng tới kết quả và độ chính xác của hệ thống khảo sát ý kiến - Hệ thống dò tìm Web còn đơn giản, chưa hỗ trợ được các mạng xã hội hoặc các Url của các website trên internet ở mức độ khác nhau. 3. Hướng phát triển của đề tài Mặc dù đã thực hiện được các nội dung cơ bản và xây dựng hệ thống vẫn hành thành công. Tuy nhiên, đề có thể hoàn thiện tốt hơn, đề tài cần nghiên cứu và bổ sung thêm các nội dung về tìm kiếm web trên các mạng xã hội khác ngoài Facebook, có thể mở rộng thêm tìm kiếm trên các website, Forum học tập của học sinh. Tăng cường hiệu năng tìm kiếm các từ chính xác hơn. 75 TÀI LIỆU THAM KHẢO [1] . Data-Intensive Text Processing with MapReduce - Jimmy Lin The iSchool University of Maryland. [2] . MapReduce: Simplified Data Processing on Large Clusters - Jeffrey Dean and Sanjay Ghemawat Google Inc. [3] . Azza Abouzeid, Kamil Bajda-Pawlikowski, Daniel Abadi, Avi Silberschatz, and Alexander Rasin. HadoopDB: An architectural hybrid of MapReduce and DBMS technologies for analytical workloads. In Proceedingsof the 35th International Conference on Very Large Data Base (VLDB 2009), pages 922{933, Lyon, France, 2009. [4] . Vo Ngoc Anh and Alistair Mo_at. Inverted index compression using word-aligned binary codes. Information Retrieval, 8 (1):151{166, 2005. [5] . Stefan Buttcher, Charles L. A. Clarke, and Gordon V. Cormack. Information Retrieval: Implementing and Evaluating Search Engines. MIT Press, Cambridge, Massachusetts, 2010. [6] . Jonathan Cohen. Graph twiddling in a MapReduce world. Computing in Science and Engineering, 11 (4):29{41, 2009. [7] . Jeffrey Dean and Sanjay Ghemawat. MapReduce: A exible data processing tool. Communications of the ACM, 53 (1):72{77, 2010. [8] . F. N. Afrati, A. D. Sarma, D. Menestrina, A. G. Parameswaran, and J. D. Ullman. Fuzzy joins using mapreduce. In ICDE, pages 498–509, 2012. [3] F. N. Afrati and J. D. Ullman. Optimizing multiway joins in a map-reduce environment. TKDE, 23 (9):1282–1298, 2011. [9] . S. Blanas, J. M. Patel, V. Ercegovac, J. Rao, E. J. Shekita, and Y. Tian. A comparison of join algorithms for log processing in mapreduce. In SIGMOD, pages 975–986, 2010. 76