Điện toán đám mây, MapReduce và ứng dụng xây dựng hệ tìm kiếm theo yêu cầu người dùng

VIỆN CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG BỘ MÔN CÔNG NGHỆ PHẦN MỀM BÁO CÁO THỰC TẬP TỐT NGHIỆP Đề tài : Điện toán đám mây, MapReduce và ứng dụng xây dựng hệ tìm kiếm theo yêu cầu người dùng Giảng viên hướng dẫn: PGS.TS. Huỳnh Quyết Thắng ThS. Lê Quốc Bộ môn Công nghệ phần mềm Viện CNTT & TT Đại học Bách Khoa Hà Nội Sinh viên thực hiện: Nguyễn Văn Đông Anh 20060102  Hà Nội, 02/2011  Mục Lục 1. Bộ máy tìm kiếm ................................................................................................................ 3 a. Quy trình tìm kiếm ..................................................................................................................... 3 b. Tiêu chí cho một bộ máy tìm kiếm .......................................................................................... 3 2. Solr ........................................................................................................................................ 3 a. Solr là gì ......................................................................................................................................... 3 b. Tại sao chọn Solr ......................................................................................................................... 4 c. Quá trình thực hiện .................................................................................................................... 5 i. File chỉ mục .............................................................................................................................. 6 ii. Quá trình đánh chỉ mục ......................................................................................................... 8 iii. Quá trình tìm kiếm ............................................................................................................... 11 3. Solr trong dự án BKProfile ........................................................................................... 13 a. BKProfile là gì ........................................................................................................................... 13 b. Thiết kế cấu trúc bản ghi chỉ mục ........................................................................................ 14 c. Nâng cao chất lượng tìm kiếm .............................................................................................. 17 i. Đánh trọng số ........................................................................................................................ 17 ii. Gom nhóm các cụm từ hay xuất hiện ............................................................................... 17 4. Demo .................................................................................................................................. 19 Điện toán đám mây, MapReduce và ứng dụng xây dựng hệ tìm kiếm theo yêu cầu người dùng Nguyễn Văn Đông Anh - CNPM K51 - Hanoi University of Technology 3 1. Bộ máy tìm kiếm a. Quy trình tìm kiếm Quy trình tìm kiếm bao gồm có bốn bước: • Truy vấn tìm kiếm được thực hiện bởi người sử dụng bằng cách yêu cầu bộ máy tìm kiếm thực hiện tìm kiếm các từ khóa nào đó. • Bộ máy tìm kiếm sẽ thực hiện xử lý truy vấn • Máy tìm kiếm tìm các từ khóa trong bộ chỉ mục có sẵn của nó • Máy tìm kiếm thực hiện đánh điểm, sắp xếp theo độ phù hợp với yêu cầu tìm kiếm và trả kết quả về cho người dùng. b. Tiêu chí cho một bộ máy tìm kiếm Có rất nhiều tiêu chí cần đặt ra cho một bộ máy tìm kiếm. • Kết quả phải chính xác: • Sắp xếp theo thứ tự phù hợp: Càng phù hợp với yêu cầu tìm kiếm của người sử dụng thì càng được đưa lên đầu tiên • Tốc độ nhanh • Dễ dàng tùy chỉnh: Đối với người phát triển, một bộ máy tìm kiếm được coi là tốt nếu nó có thể dễ dàng thêm bớt, cấu hình các thuộc tính bên trong nhân của bộ tìm kiếm. Ngoài ra, máy tìm kiếm còn cho phép người phát triển dễ dàng theo dõi quá trình tìm kiếm, theo dõi quá trình thực hiện xử lý câu truy vấn của người dùng để từ đó có các bước tùy chỉnh phù hợp để nâng cao độ phù hợp của kết quả trả về • Phân tán: Với khối lượng thông tin khổng lồ và tăng nhanh từng ngày thì yêu cầu phân tán là một yêu cầu cần thiết đối với bộ máy tìm kiếm. • Một vài chức năng khác: o Có chức năng đánh dấu cho kết quả trả về o Tìm kiếm theo cụm: Người dùng có thể lọc dần các tiêu chí theo cụm từ lớn đến nhỏ dần để đưa ra kết quả phù hợp o Từ đồng nghĩa: Máy tìm kiếm cho phép tìm các từ có cùng nghĩa với các từ khóa người dùng nhập vào o Từ gốc: Máy tìm kiếm cho phép tìm các từ là từ gốc của các từ trong từ khóa của người dùng. o Kiểm tra chính tả: Máy tìm kiếm cho phép kiểm tra chính tả của người dùng và từ đó, gợi ý cho người dùng tìm kiếm theo các từ khóa đúng chính tả o Stopwords: Trong ngôn ngữ, có nhiều từ không mang nhiều ý nghĩa (ví dụ các từ cảm thán trong tiếng Việt hoặc trong tiếng Anh có các từ như a, the, not, but…) 2. Solr a. Solr là gì Solr là một máy chủ tìm kiếm văn bản có tốc độ thực thi rất nhanh. Solr sử dụng nhân tìm kiếm Lucene, là một thư viện tìm kiếm gồm có các chức năng sau: Điện toán đám mây, MapReduce và ứng dụng xây dựng hệ tìm kiếm theo yêu cầu người dùng 4 Nguyễn Văn Đông Anh - CNPM K51 - Hanoi University of Technology • Đánh chỉ mục ngược • Phân tích văn bản • Thuật toán đánh điểm tốt Solr được phát triển hoàn toàn bằng Java và được thực thi trong một container như Tomcat hoặc Jetty. Solr có các giao tiếp API dựa trên nền tảng XML hoặc Json khiến cho việc thực hiện tương tác với nhiều ngôn ngữ khác trở nên dễ dàng. Solr cho phép người dùng thực hiện việc cấu hình bên ngoài hệ thống thông qua việc chỉnh sửa trong file cấu hình (xml). Các thành phần khác mà Solr cung cấp: • Từ đồng nghĩa • Đánh dấu kết quả trả về • Phân tán • Kết hợp trực tiếp với các cơ sở dữ liệu (MySql, MSSQL) để lấy dữ liệu Trong Solr tồn tại hai quá trình: • Quá trình đánh chỉ mục: Để xây dựng bộ dữ liệu cho máy chủ tìm kiếm • Quá trình truy vấn: Để thực hiện tìm kiếm trong bộ dữ liệu của máy chủ tìm kiếm b. Tại sao chọn Solr Hiện nay có nhiều các loại máy chủ tìm kiếm khác nhau, tuy nhiên sau quá trình tìm hiểu và nghiên cứu, dựa trên các tiêu chí đánh giá về thời gian thực hiện quá trình đánh ch ỉ mục, thời gian thực hiện câu truy vấn, số lượng câu truy vấn được thực hiện trong một đơn vị thời gian, số lượng không gian đĩa c ứng mà bộ dữ liệu đánh chỉ mục chiếm dụng, Solr xứng đáng là ứng cử viên xuất sắc cho một bộ máy tìm kiếm Điện toán đám mây, MapReduce và ứng dụng xây dựng hệ tìm kiếm theo yêu cầu người dùng Nguyễn Văn Đông Anh - CNPM K51 - Hanoi University of Technology 5 c. Quá trình thực hiện Quá trình thực hiện của Solr cũng giống quá trình thực hiện trong một bộ máy tìm kiếm. • Xây dựng bộ dữ liệu chỉ mục thông qua quá trình đánh chỉ mục • Thực hiện yêu cầu truy vấn tìm kiếm của người dùng trong bộ dữ liệu chỉ mục và trả kết quả tìm kiếm tương ứng cho người dùng. Điện toán đám mây, MapReduce và ứng dụng xây dựng hệ tìm kiếm theo yêu cầu người dùng 6 Nguyễn Văn Đông Anh - CNPM K51 - Hanoi University of Technology i. File chỉ mục Mỗi một bản ghi trong Solr được gọi là một doc, trong doc này có nhiều trường, mỗi trường có một kiểu khác nhau (int, string…) File chỉ mục bao gồm các thông tin sau: • Tên trường: Tập tên trường chứa toàn bộ tất cả các trường có trong tất cả các bản ghi trong bộ chỉ mục của Solr. • Giá trị của trường: Đây là các giá trị trả về khi người dùng thực hiện truy vấn đối với bộ dữ liệu. • Từ điển terms: Chứa toàn bộ term trong bộ dữ liệu chỉ mục, đi kèm với nó là số lượng các bản ghi (doc) có chứa term đó và con trỏ chỉ tới tần suất xuất hiện của term và dữ liệu vị trí. o Dữ liệu tần suất xuất hiện: Với mỗi term trong từ điển, chứa thông tin số lượng bản ghi có chứa term đó và tần suất xuất hiện của term đó trong mỗi bản ghi o Dữ liệu vị trí: Đối với mỗi term trong từ điển, chứa thông tin vị trí của term xuất hiện trong mỗi bản ghi • Hệ số chuẩn hóa: Hệ số này có tác dụng trên mỗi trường của bản ghi, nhằm xác định hệ số nhân trong kết quả trả về của mỗi trường trong bản ghi. Hệ số này cho phép xác định được trường nào có trọng số cao hơn trường nào. • Term vector: Đối với mỗi trường, thông tin các term của một trường được chứa trong một vector. Điện toán đám mây, MapReduce và ứng dụng xây dựng hệ tìm kiếm theo yêu cầu người dùng Nguyễn Văn Đông Anh - CNPM K51 - Hanoi University of Technology 7 • Các bản ghi bị xóa: Chứa thông tin đánh dấu các bản ghi trong chỉ mục bị xóa. Sau này khi thực hiện tối ưu hóa, sẽ thực hiện xóa hẳn trong file chỉ mục. Đánh chỉ mục ngược: Bộ dữ liệu chỉ mục chứa các thông tin thống kê về term để việc tìm kiếm trên bộ dữ liệu về term này được thực hiện một các hiệu quả. Chỉ mục ngược có nghĩa là đ ối với mỗi term, file chỉ mục sẽ lưu các bản ghi có chứa term đó thay vì ngược lại. Bản ghi (document): Vì Solr sử dụng cơ sở dữ liệu bản ghi (document database), vì vậy, không hề tồn tại quan hệ giữa các bản ghi với nhau. Toàn bộ các thông tin tương ứng đối với một thực thể được lưu toàn bộ trong một bản ghi, và bản ghi này được lưu lại trong chỉ mục. Bản ghi bao gồm nhiều trường. Trường (field): Trong mỗi một bản ghi, có các trường tương ứng để chứa dữ liệu. Ví dụ thông tin về con người gồm có họ, tên, tuổi, quê quán… Mỗi một trường thuộc một kiểu dữ liệu xác định, có thể là nguyên thủy (int, string…) hoặc do người phát triển tự định nghĩa. Ngoài ra, còn có một số trường đặc biệt như: • CopyField: Là trường mà sẽ lấy thông tin từ một trường (source) và ghi vào một trường khác (destination) • DynamicField: Là trường cho phép người dùng không phải ghi rõ tên trư ờng mà chỉ cần sử dụng các ký tự đại diện (như *). • UniqueKey: Chỉ định rõ trư ờng nào đại diện cho một bản ghi • DefaultSearchField: Trường nào là trường mặc định để thực hiện việc tìm kiếm trên bộ dữ liệu • DefautlOperator: Toán hạng mặc định để thực hiện nối ghép các từ khóa trong yêu cầu tìm kiếm của người dùng. File định kiểu bản ghi (schema): Các bản ghi phải có một cấu trúc xác định trước, bao gồm các trường nào, kiểu dữ liệu như thế nào… Thông tin các trường, kiểu dữ liệu của các trường cũng như nhiều thông tin cấu thành nên bản ghi được lưu trong một file cấu hình (schema). File này có dạng xml, được đưa vào hệ thống lúc khởi động máy chủ. Điện toán đám mây, MapReduce và ứng dụng xây dựng hệ tìm kiếm theo yêu cầu người dùng 8 Nguyễn Văn Đông Anh - CNPM K51 - Hanoi University of Technology ii. Quá trình đánh chỉ mục Điện toán đám mây, MapReduce và ứng dụng xây dựng hệ tìm kiếm theo yêu cầu người dùng Nguyễn Văn Đông Anh - CNPM K51 - Hanoi University of Technology 9 Analizer: Là các thành phần xét các trường trong các bản ghi hoặc câu truy vấn của người dùng để tạo thành một loạt các token (các từ khóa) Tokenizer: Là các thành phần được sử dụng để tạo các term từ câu truy vấn của người dùng hoặc dữ liệu ở một trường nào đó dựa vào các tiêu chí định sẵn trong file cấu hình. Ví dụ: WhiteSpaceTokenizer sẽ tách câu truy vấn của người dùng thành các từ khóa dựa vào khoảng trắng. StandardTokenizer sẽ tách câu truy vấn của người dùng dựa vào khoảng trắng và các dấu chấm câu. LowerCaseTokenizer tách câu truy vấn của người dùng thành các từ khóa dựa vào các chữ cái không phải là ký tự và sau đó chuyển hết từ khóa về dạng chữ viết thường. Filter: Là các thành phần được sử dụng để phân tích các từ khóa và hoặc giữ chúng, chuyển chúng thành các phần khác, hoặc bỏ chúng, hoặc tạo thêm các từ khóa khác. Các tiêu chí trên được chỉ định bởi người phát triển trong file cấu hình. Một vài ví dụ cho filter như SynonymFilter sẽ thêm các từ khóa đồng nghĩa với các từ khóa trong câu truy vấn của người dùng hoặc trên trường được áp dụng Filter; StopwordFilter sẽ loại bỏ hết tất cả các từ khóa không mang giá trị (được định nghĩa trong một file văn bản). Quá trình đánh chỉ mục được thực hiện như sau: Sau khi lấy được các thông tin cần đánh chỉ mục và đưa vào các trường trong bản ghi, các thành phần Tokenizer và Filter người phát triển chỉ định trong file cấu hình sẽ thực hiện tách thông tin trong các trường thành các từ khóa cụ thể. Các Analyzer này sẽ bổ sung, xóa bớt hoặc giữ nguyên các từ khóa phụ thuộc vào cách cấu hình của người phát triển. Sau đó, các từ khóa được sinh ra sẽ được lưu lại trong bộ chỉ mục chuyên biệt để tìm kiếm. Các giá trị nguyên bản ứng với mỗi trường sẽ được lưu lại hoặc không lưu lại (tùy cách cấu hình trư ờng trong file cấu hình bản ghi (schema) của người phát triển); nếu được lưu lại, nếu máy tìm kiếm tìm được thông tin (hit), sẽ trả lại giá trị này, còn không sẽ không trả lại giá trị. Điện toán đám mây, MapReduce và ứng dụng xây dựng hệ tìm kiếm theo yêu cầu người dùng 10 Nguyễn Văn Đông Anh - CNPM K51 - Hanoi University of Technology Điện toán đám mây, MapReduce và ứng dụng xây dựng hệ tìm kiếm theo yêu cầu người dùng Nguyễn Văn Đông Anh - CNPM K51 - Hanoi University of Technology 11 iii. Quá trình tìm kiếm QueryParser: Là các bộ xử lý truy vấn của người dùng.Với mỗi bộ xử lý sẽ có cách xử lý truy vấn riêng như tìm ki ểm ở đâu, trên trường nào, có đánh trọng số lên trường nào lúc tìm kiếm hay không… Khi người dùng thực hiện một câu lệnh truy vấn, câu lệng truy vấn sẽ được xử lý bởi các request handler (bộ xử lý yêu cầu tìm kiếm, update, hoặc xóa…). Các request handler này sẽ xác định các logic Điện toán đám mây, MapReduce và ứng dụng xây dựng hệ tìm kiếm theo yêu cầu người dùng 12 Nguyễn Văn Đông Anh - CNPM K51 - Hanoi University of Technology cần thực hiện đối với các yêu cầu đó. Câu lệnh truy vấn sẽ được xử lý bởi QueryParser, bộ phận này sẽ chịu trách nhiệm sao cho câu truy vấn tìm kiếm của người dùng được tách khỏi các tham số trong câu lệnh truy vấn. Có nhiều loại QueryParser trong Solr, ví dụ Standard Query Parser cho phép người dùng xác định rõ câu truy vấn tìm kiếm; Dismax Query Parser cho phép người dùng thực hiện các câu lệnh tìm kiếm đơn giản nhưng trên nhiều trường khác nhau. Sau đó, truy vấn tìm kiếm được các Analyzer chỉ định bởi người phát triển tách thành các từ khóa khác nhau. Sau đó, bộ máy tìm kiếm sẽ tìm kiếm các từ khóa cùng với trọng số trên các từ khóa đó (nếu có) trong bộ dữ liệu chỉ mục của hệ thống. Giá trị trả về sẽ được xử lý tiếp dựa vào các tham số truyền vào trong câu lệnh truy vấn của người dùng như bắt đầu từ bản ghi nào, kết thúc đến bản ghi nào, trả về theo định dạng gì… Ngoài ra, các thành phần được chỉ định trong yêu cầu truy vấn sẽ được xử lý Điện toán đám mây, MapReduce và ứng dụng xây dựng hệ tìm kiếm theo yêu cầu người dùng Nguyễn Văn Đông Anh - CNPM K51 - Hanoi University of Technology 13 thêm trong phần này như thành phần HightLighting sẽ đánh dấu các từ khóa trong câu lệnh truy vấn của người dùng phù hợp với từ nào trong bản ghi trong bộ dữ liệu chỉ mục của bộ máy tìm kiếm. Các kiểu tìm kiếm được hỗ trợ trong Solr: • Normal Query: Chỉ có từ khóa trong câu lệnh truy vấn của người dùng • Wildcard Query: Có thêm các ký tự wildcard trong câu lệnh truy vấn. ? thay cho một ký tự; * thay cho không hoặc nhiều ký tự • Range Searches: Cho phép tìm kiếm trong một khoảng nhất định. Ví dụ tìm kiếm theo ngày từ ngày 01-01-2002 đến ngày 01-01-2003 có câu lệnh tìm kiếm như sau: date_search: [20020101 TO 20030101] • Boosting: Là trọng số đối với một số từ khóa nào đó trong câu truy vấn tìm kiếm của người dùng. Ví dụ: name: dong^2 anh thì dong có trọng số là 2 và kết quả trả về sẽ đưa lên đầu các tên có dong trước các tên có anh. • QueryField: Xác định xem trường nào sẽ được chỉ định thực hiện việc truy vấn ngay trên nó. Ví dụ: Tìm kiếm tên: name:dong anh sẽ tìm kiếm trên trường tên giá trị là dong anh • Boolean Operator: Là toán hạng sẽ được sử dụng để kết nối các giá trị của từ khóa người dùng.Ví dụ: name: dong AND anh thì sẽ tìm trong trường tên có giá trị là dong và anh. • Datetime Query: Thực hiện tìm kiếm trên các trường có kiểu datetime. Ví dụ: event_date: [* TO NOW-2YEAR] sẽ tìm kiếm các bản ghi có giá trị event_date từ năm bất kỳ đến cách đây 2 năm. Các tham số • Start: Bắt đầu từ bản ghi nào • Rows: Số lượng bản ghi cần trả về • DebugQuery: Trả về thêm các giá trị tính toán điểm cũng như các thành phần khác trong máy tìm kiếm để người phát triển có thể phân tích đánh giá kết quả trả về • Response Writer: Kiểu định dạng trả về cho người dùng, có thể thuộc dạng XML hoặc JSON. 3. Solr trong dự án BKProfile a. BKProfile là gì BKProfile là một bộ máy tìm kiếm, chuyên thực hiện tìm kiếm để trả về thông tin của con người. Bộ máy tìm kiếm này phục vụ mục đích tìm kiếm con người cho 3 đối tượng chính: Các sinh viên hoặc cựu sinh viên muốn tìm một sinh viên nào đó nhằm phục vụ một mục đích nào đó; Các nhà làm giáo dục có thể thực hiện tìm kiếm sinh viên sau khi ra trường để đánh giá thực trạng giáo dục…; Các nhà tuyển dụng tìm kiếm các ứng viên có tiềm năng. Điện toán đám mây, MapReduce và ứng dụng xây dựng hệ tìm kiếm theo yêu cầu người dùng 14 Nguyễn Văn Đông Anh - CNPM K51 - Hanoi University of Technology Vì BKProfile là một hệ thống tìm kiếm nên nó cũng có các yêu cầu cơ bản của một hệ thống tìm kiếm như • Độ phù hợp của kết quả cao • Tốc độ thực thi nhanh chóng • Thông tin trả về là duy nhất đối với một người • Có thêm các tính năng phong phú khác để tăng thêm tính hấp dẫn cho hệ thống b. Thiết kế cấu trúc bản ghi chỉ mục Bản ghi bao gồm có các trường • *_indexed: Để lưu các thông tin của các trường có kết thúc là _indexed. • Text: là một copy field, mọi giá trị của các trường khác sẽ được chuyển thẳng vào trong trường này. Trường này được thực hiện việc tìm kiếm mặc định. • Profile_id: Là đại diện cho một bản ghi. Thiết kế kiểu trường • BKText là một kiểu dữ liệu custom được tạo riêng cho dự án BKProfile. o Quá trình đánh chỉ mục  WhiteSpaceTokenizerFactory: Tách giá trị của các trường thành các từ khóa dựa vào khoảng trắng giữa các từ khóa  ASCIIFoldingFilterFactory: Chuyển tất cả từ khóa về dạng ASCII để có thể tìm kiếm theo dạng tiếng việt không dấu  WordDelimiterFilterFactory: Tách từ ghép trong đó có cả chữ cái và số thành chữ cái riêng và số riêng  LowerCaseFilterFactory: Chuyển tất cả từ khóa về dạng chữ cái thường  SynonymFilterFactory:Sử dụng từ đồng nghĩa đ ể cho phép quá trình tìm kiếm có kết quả tốt hơn  StopFilterFactory: Loại bỏ tất cả các từ không mang nhiều ý nghĩa. Các t ừ khóa này được định nghĩa trong một file riêng (stopword.txt). Hầu hết các từ này đều là từ cảm thán.  ShingleFilterFactory: Ghép nối các từ khóa thành các cụm từ (tối đa là 5) để tăng độ chính xác trong lúc tìm kiếm Điện toán đám mây, MapReduce và ứng dụng xây dựng hệ tìm kiếm theo yêu cầu người dùng Nguyễn Văn Đông Anh - CNPM K51 - Hanoi University of Technology 15  SnowballPorterFilterFactory: Để loại bỏ các từ bắt nguồn từ từ khác  RemoveDuplicatesTokenFilterFactory: Loại bỏ tất cả các từ khóa trùng nhau sau khi được tạo bởi tất cả các filter trên. Điện toán đám mây, MapReduce và ứng dụng xây dựng hệ tìm kiếm theo yêu cầu người dùng 16 Nguyễn Văn Đông Anh - CNPM K51 - Hanoi University of Technology o Quá trình tìm kiếm  WhiteSpaceFilterFactory:Tách truy vấn của người dùng thành các từ khóa dựa vào khoảng trắng  ASCIIFoldingFilterFactory: Chuyển các từ khóa thành dạng ASCII để có thể tìm kiếm tiếng việt không dấu  WordDelimiterFilterFactory:Tách từ ghép trong đó có cả chữ cái và số thành chữ cái riêng và số riêng  LowerCaseFilterFactory: Chuyển tất cả từ khóa về dạng chữ cái thường  SynonymFilterFactory: Sử dụng từ đồng nghĩa đ ể cho phép quá trình tìm kiếm có kết quả tốt hơn  StopFilter