Luận văn Nghiên cứu máy tìm kiếm qua hệ thống Greenstone

art lẫn kết quả Inktomi ngoại trừ khoảng thời gian ngắn trong năm 1999 khi kết quả từ Alta Vista được sử dụng để thay thế. Hiện nay, Google đang là máy tìm kiếm phổ biến nhất. Ở mỗi quốc gia, đối với thị trường trong nước, đều có các công ty cạnh tranh máy tìm kiếm 11 với Google. Trong đó, một thành công vang dội phải kể đến Baidu, một máy tìm kiếm phổ biến nhất ở Trung Quốc. 1.3. Tình hình nghiên cứu, ứng dụng máy tìm kiếm tại Việt Nam 1.3.1 Tình hình nghiên cứu Nghiên cứu máy tìm kiếm bắt đầu ở Việt Nam từ năm 1997. Bắt đầu với sự xuất hiện Vinaseek(2000) của công ty Tinh Vân và Netnam(2001) của Viện công nghệ thông tin. Cả hai đều đã gây ra tiếng vang lớn thời bấy giờ. Đến nay, có rất nhiều các công trình nghiên cứu về máy tìm kiếm. Sau đây, chúng tôi đưa ra ba hướng nghiên cứu đáng chú ý hiện nay của các trường đại học trên cả nước. Tìm kiếm tài liệu, dữ liệu dựa trên Ontology của trường ĐH Công Nghệ và ĐH Bách Khoa Hà Nội . Trong đó, một Ontology là một mô hình dữ liệu biểu diễn một lĩnh vực và được sử dụng để suy luận về các đối tượng trong lĩnh vực đó và mối quan hệ giữa chúng. Trong hệ hống tìm kiếm này, có hai module: module sinh cá thể từ tập dữ liệu huấn luyện, module suy diễn. Cả hai module này nhằm đưa về kết quả chứa các tri thức tốt hơn các phương pháp tìm kiếm thông thường. Nghiên cứu xây dựng máy tìm kiếm của trường ĐH Bách Khoa TPHCM, có hai hướng. Đầu tiên, máy tìm kiếm liên hợp (meta search engine), không giống như máy tìm kiếm thông thường, nó gửi câu truy vấn tới các máy tìm kiếm khác (tạm gọi là máy tìm kiếm nguồn) như Google, Yahoo và sau đó xử lý kết quả trả về từ các máy tìm kiếm này trước khi trả ra kết quả cho người dùng. Máy tìm kiếm liên hợp chủ yếu tập trung vào phát triển các thuật toán xử lý kết quả từ các máy tìm kiếm khác. Các thuật toán xử lí thông thường gồm có gom cụm (clustering) để loại bỏ trùng lắp (duplicate elimination), và phân tích ngữ nghĩa (semantic analysis) để có thể cho kết quả gần với yêu cầu của người dùng nhất. Bạn có thê tham khảo phần mềm tại trang web này www.ahhere.com . Thứ hai, máy tìm kiếm video . Đặc điểm thứ nhất, đó là hướng tới mức high-level features (còn được gọi là concept). Mức này cho kết quả tốt hơn mức low-level features (color, shape, texture) - một mức mà rất nhiều các 12 máy tìm kiếm video, ảnh sử dụng. Concept ở đây dùng để chỉ tìm kiếm ở mức ngữ nghĩa, ví dụ bạn gõ vào airplane thì sẽ tìm được các shot có liên quan đến airplane. Đặc điểm thứ hai, đó là sự hỗ trợ person search. Nghĩa là người dùng đưa vào tên, và hệ thống sẽ trả về các video shots có nhân vật đó xuất hiện. Đặc điểm ba, đó là hỗ trợ exploratory search. Nghĩa là cho phép những người dùng chưa có ý định tìm kiếm gì cụ thể trong đầu, "thám hiểm" xem trong video archives có cái gì. Hướng nghiên cứu cuối cùng, đó là chỉ mục ngữ nghĩa tiềm ẩn (Latent Semantic Indexing-LSI), được thiết kế để giải quyết vấn đề đồng nghĩa và các vấn đề đa nghĩa của từ ngữ. LSI dùng kỹ thuật phân tích giá trị riêng (SVD-singular value decomposition) để giảm bớt kích thước ma trận thuật ngữ-tài liệu, không gian N-chiều sẽ được giảm bớt xuống một không gian K chiều, K<<N, không gian mới này được gọi là không gian khái niệm. LSI được sử dụng ở rất nhiều các ứng dụng tìm kiếm để tăng hiệu năng của hệ thống. 1.3.2 Tình hình ứng dụng Máy tìm kiếm ở Việt Nam bắt đầu vào năm 2000, khi mà Vinaseek ra đời, phục vụ miễn phí trên internet. Đây là công cụ tìm kiếm tiếng Việt mạnh nhất thời bấy giờ (sau đó có thêm panvietnam.com và hoatieu.com). Bởi sự hỗ trợ tất cả các bảng mã (TCVN3, VNI, TVCN-6909, VIQR…). Nhưng sau đó, theo xu hướng chung, hầu hết các web tiếng việt đều tuân thủ mã Unicode và Google đã hỗ trợ tốt bảng mã quốc tế này. Do đó Vinaseek không thể hiện được sức mạnh và phải nhường chỗ cho Google Việt Nam. Ở Việt Nam những năm gần đây, chúng ta cũng thấy xuất hiện rất nhiều cỗ máy tìm kiếm. Như cỗ máy chuyên tìm kiếm nhạc, video là www.baamboo.com, mp3.zing.vn hay các website tìm kiếm thông tin tổng hợp, âm nhạc, hình ảnh như www.monava.vn, www.7sac.com, www.socbay.com, www.xalo.vn. Sự đối đầu trực tiếp với Google như Monava, 7sac,.. là không nên. Sự thành công của baamboo, mp3.zing khi tiếp cận theo hướng “vertical search” (tìm kiếm trong các lĩnh vực chuyên biệt như tìm nhạc, tìm blog, tìm dịch vụ…), đã chứng tỏ một cách tiếp cận khôn ngoan khi đối diện với Google. Đó là các loại dịch vụ tìm kiếm theo 13 chiều dọc với khả năng đưa ra thị trường nhanh nhất và phù hợp nhất với người dùng Việt Nam. 1.4. Động cơ và mục tiêu của luận văn Với mong muốn nghiên cứu tìm hiểu cỗ máy tìm kiếm và xây dựng máy tìm kiếm dựa trên những đặc trưng của tiếng Việt, chúng tôi nhận thấy luận văn đặt trọng tâm vào những mục tiêu chính sau đây:  Tìm hiểu kiến trúc công nghệ cơ bản của máy tìm kiếm. Đó là tiến trình lập chỉ mục, tiến tình tìm kiếm, xếp hạng tài liệu.  Tìm hiểu kiến trúc hệ thống Greenstone, để biết được công nghệ và kiến trúc của máy tìm kiếm là như thế nào.  Ứng dụng công nghệ Lucene để xây dựng máy tìm kiếm tiếng Việt.  Đưa tách từ (word segmentation) vào máy tìm kiếm tiếng Việt. 14 Chương 2. Các vấn đề cơ bản trong một hệ thống máy tìm kiếm 2.1. Tiến trình lập chỉ mục (Indexing) 2.1.1. Lập chỉ mục Lập chỉ mục là quá trình phân tích và xác định các từ, cụm từ (được gọi là các term) thích hợp cốt lõi có khả năng đại diện cho nội dung của tài liệu. Như vậy, vấn đề đặt ra là phải rút trích ra những thông tin chính, có khả năng đại diện cho nội dung của tài liệu. Thông tin này phải “vừa đủ”, nghĩa là không thiếu để trả ra kết quả đầy đủ so với nhu cầu tìm kiếm, nhưng cũng phải không dư để giảm chi phí lưu trữ và chi phí tìm kiếm và để loại bỏ kết quả dư thừa không phù hợp. Việc rút trích này chính là việc lập chỉ mục trên tài liệu. Một thủ tục lập chỉ mục tự động cơ bản cho các tài liệu tiếng Anh có thể được xử l ý như sau: Step of tokenization: Tách văn bản ra thành các chuỗi nhờ vào khoảng trắng, mỗi chuỗi xem như là một từ. Step of removal of stop words: bỏ những từ thường xuyên xuất hiện trong hầu hết các tài liệu nhưng lại không quan trọng trong các tài liệu như tính từ, đại từ. Step of stemming: loại bỏ các hậu tố (suffixes) để đưa về các từ gốc Lấy gốc từ (stemming): {destroy, destroyed, destruction}: destr mistakes! : {centennial,century,center}: cent 15 2.1.2. Các loại chỉ mục Trong phần này, chúng tôi giới thiệu hai loại chỉ mục cho tài liệu là chỉ mục tệp đảo IFID và chỉ mục tệp ký số SFID và sau đó tiến hành đánh giá hai cấu trúc này. 2.1.2.1. Chỉ mục tệp đảo Sau khi thực hiện tiến trình lập chỉ mục, chúng ta sẽ có được tệp đảo (IF) chứa một bộ từ vựng (lexicon) -một danh sách tất cả thuật ngữ xuất hiện trong CSDL. Bộ từ vựng trợ giúp một ánh xạ từ các thuật ngữ tới các danh sách đảo (IL) tương ứng của chúng và ở dạng đơn giản nhất của nó là một danh sách các xâu và địa chỉ đĩa từ. Danh sách đảo (IL) lưu trữ một danh sách con trỏ tới tất cả xuất hiện của thuật ngữ đó trong văn bản chính. Đây là phương pháp chỉ mục tự nhiên nhất, gần tương ứng với chỉ mục của một cuốn sách và với cách dùng mục lục truyền thống. Hình 2-1 Văn bản mẫu; mỗi dòng là một tài liệu Ví dụ về một IFID, xét văn bản mẫu ở hình 2-1, với mỗi dòng được coi là một tài liệu để chỉ mục. IF sinh ra cho văn bản này được chỉ ra ở hình 2-2, trong đó các thuật ngữ được gộp dạng nhưng không được truy gốc và không một từ nào bị bỏ qua. Nói chung, các IL cho một CSDL có độ dài rất khác nhau. 16 Một truy vấn bao gồm một thuật ngữ đơn được trả lời bằng cách quét IL của nó và truy tìm mọi tài liệu mà nó trích dẫn. Đối với truy vấn Boole hội có dạng t1 AND t2 AND ... AND tn , giao của các IL của thuật ngữ được tạo ra. Đối với truy vấn tuyển, trong đó toán tử là OR, phép hợp được thực hiện; đối với truy vấn phủ định dùng NOT, phép bù được thực hiện. Hình 2-2 IF mức từ đối với văn bản của hình 2-1 Trong hình 2-2, chúng ta có thể thấy cấu trúc của bảng như sau, đối với từ some, xuất hiện ở 2 tài liệu 4 và 5, ở tài liệu 4 xuất hiện 2 lần ở vị trí 1 và 5, ở tài liệu 5 xuất hiện một lần ở vị trí 1 (tài liệu được tính bắt đầu từ vị trí 0). 2.1.2.2. Chỉ mục tệp ký số SFID là cấu trúc chỉ mục khác. Sự tổ hợp nhất định của các trường hợp có thể xử lý truy vấn nhanh hơn IF, nhưng ở các tình huống giống nhau có khả năng đòi hỏi một lượng không gian lớn hơn. Tệp ký số (SF) đặc biệt thông dụng trong quá khứ bởi vì chúng hoàn toàn bị nén theo một nghĩa nào đó và như vậy, tốn ít không gian lưu trữ hơn IF không nén. Ở đây, chúng tôi xét biểu diễn SF và so sánh với IF nén trong phạm vi của cả hai yêu cầu xử lý và giá lưu trữ. 17 Hình 2-3 – Bảng mã hash các term Mỗi một thuật ngữ trong tài liệu được sử dụng để sinh ra một số giá trị băm. Các ký số này được xây dựng bằng câu lệnh phía dưới với b =3 và w =16. for i = 1 to b sig[hash i (term)%W] = 1; Mỗi một từ được băm 3 lần dùng các hàm khác nhau và các bit chỉ thị như vậy là bit “1” ở ký số của từ đó. Những xung đột có thể dẫn đến ít hơn ba bit được cài đặt ở một số ký số thuật ngữ, nhưng không cần tính đến nó. Chẳng hạn, ở hình 2-3 thuật ngữ hot có 2 bit cài đặt . Mô tả các xâu bit như ký số là sự sử dụng rất thích hợp của từ - như với chữ ký con người. Bây giờ, xét ký số tổng hợp khi các ký số của các từ ở mỗi một tài liệu được đặt chồng lên - tức là, hoặc đồng thời để làm ký số tài liệu. 18 Hình 2-4 Ký số tổng hợp Để thử nghiệm liệu một thuật ngữ truy vấn có xuất hiện ở một tài liệu đã cho, các giá trị của hàm băm cho thuật ngữ được tính toán. Nếu tất cả bit tương ứng trong bộ mô tả của tài liệu nào đó được cài đặt, thuật ngữ hầu như chắc chắn xuất hiện trong tài liệu đó. Hơn nữa, cho đến nay không thể nói thuật ngữ không xuất hiện trong tài liệu, dù tổ hợp các từ khác nào đó có thể ngẫu nhiên cài đặt tất cả bit kiểm tra đối với thuật ngữ truy vấn. Để giải quyết sự không chắc chắn này, tài liệu phải được bắt và quét để kiểm tra rằng thuật ngữ thực sự xuất hiện. Xác suất của so khớp sai như thế có thể bị bắt ngẫu nhiên nhỏ bằng cách cài đặt một số bit cho mỗi một thuật ngữ và thực hiện ký số hiệu quả lớn, nhưng kiểm tra so khớp sai thường được đòi hỏi với các SFID và có thể thêm thực sự vào giá xử lý truy vấn vì mỗi một tài liệu kiểm tra phải được giải mã hoàn toàn, phân tích cú pháp thành các từ và các từ hoàn toàn được truy gốc. Ví dụ: Tìm kiếm với từ cold thì kết quả trả về là dòng 1 và dòng 4. Tìm kiếm với từ old thì kết quả trả về sẽ là 2, 3, 5, 6 nhưng chỉ có 2 dòng chứa từ này. Vì thế nên mới có toán tử Maybe và not Với một câu truy vấn chứa từ khoá T, nếu như tất cả các bit 1 của T đều đã được cài đặt trong tài liệu nào đó, thì tài liệu đó có thể chứ từ khoá T nên ta dùng toán tử Maybe. Nếu như một bit 1 của T không được cài đặt trong tài liệu, thì tài liệu đó không chứ từ khoá T. 19 Hình 2-5 Giá trị của câu truy vấn của SFID Do tính chưa chắc chắn được, nên ta phải dùng 3 giá trị logic: N, M, Y Hình 2-6 Giá trị của các phép toán trong SFID Sau đây là các kết nối logic chứa trong câu truy vấn giữa các từ khoá s, h và p: Hình 2-7 Giá trị câu truy vấn đối với các tài liệu SFID 2.1.2.3. Đánh giá và kết luận SF có thể tạo ra các truy cập không cần thiết tới văn bản chính bởi vì các so khớp sai, nhưng chúng có thể được giảm không đáng kể nếu ký số là đủ lớn (W là 1000 -> 10000) và một số bit thích hợp được cài đặt đối với từng thuật ngữ . Tương phản, nếu IL được truy cập theo độ dài tăng lên và từ vựng của CSDL được điều khiển trong bộ nhớ chính thì một IF yêu cầu truy cập đĩa tổng cộng không nhiều hơn so với một SF, ngoại trừ một ít trường hợp không hợp lý. Hơn nữa, các thao tác SF trở nên phức tạp nếu phép tuyển và phép phủ định được cho phép, SF không thể được sử dụng để 20 trợ giúp các truy vấn xếp hạng. SF có thể đặc biệt tai hại khi độ dài bản ghi có thể thay đổi nhiều. Những hạn chế trên đa tạo ra một luận cứ đầy đủ ủng hộ IF nén đối với các ứng dụng bao gồm CSDL văn bản. 2.2 Tiến trình tìm kiếm thông tin (Searching) Tìm kiếm thông tin là tìm kiếm các tài liệu mà thoả mãn câu truy vấn (query). Câu truy vấn có thể gồm rất nhiều từ khoá và các từ khoá được kết hợp với nhau nhờ các toán tử logic. Các từ khoá chỉ chứa các kí tự alphabet hoặc các chữ số. Các từ phải được cách ra bằng khoảng trắng. Dấu chấm câu, chấm phẩy, gạch ngang..v.v.. được coi như khoảng trắng và do dó bị xem như không có. Ví dụ ta có câu truy vấn sau: Argo-forestry in the Pacific Islands: Systems for Sustainability 1993 Tuỳ vào từng hệ thống, có thể đầu tiên query sẽ được lowercase, sau đó sẽ được loại bỏ các từ stopword và hệ thống sẽ tìm những tài liệu nào chứa một trong số những từ dưới đây. Câu truy vấn sau khi biến đổi: argo forestry pacific islands systems sustainability 1993 Bạn cũng có thể dùng dấu ngoặc kép để tìm những tài liệu chứa cả cụm từ trên. Vừa rồi các bạn nhìn thấy phép “or” còn đối với phép “and” các bạn dùng “AND” giữa các từ khoá. Và phép “not” bạn dùng “AND NOT” trước các từ khoá. Đối với mỗi máy tìm kiếm khác nhau, sự quy định các dấu thay thế cho các toán tử này cũng khác nhau. Ngoài chiến lược tìm chính xác theo từ khoá, các search engine còn cố gắng ‘hiểu‘ ý nghĩa thực sự của câu hỏi thông qua những câu chữ do người dùng cung cấp. Điều này được thể hiện qua chức năng sửa lỗi chính tả, tìm cả những hình thức biến đổi khác nhau của một từ. Ví dụ : search engine sẽ tìm những từ như speaker, speaking, spoke khi người dùng nhập vào từ speak. 21 2.3. Xếp hạng tài liệu liên quan (Ranking) 2.3.1. Các khái niệm cơ bản Tf(t in d) là tần số của từ đó, được định nghĩa là căn bậc 2 của số lần từ đó xuất hiện trong tài liệu d: tf(t in d) = frequency½ Idf(t) là tần số tài liệu, liên quan tới số tài liệu chứa từ này: NumDocs là số lượng tài liệu đã được đánh chỉ mục. DocFreq là số lượng các tài liệu chứa từ khoá này. Coord(q,d) được tính dựa trên có bao nhiêu phần trăm từ khoá của câu truy vấn q xuất hiện trong tài liệu d. QueryNorm(q) dùng để so sánh các câu truy vấn với nhau Ví dụ, đối với truy vấn dạng booleanquery q.getBoost() giá trị mặc định là 1. T.getBoost() là tích của các giá trị boost của các document chứa từ t. Giá trị mặc định là 1. 22 Norm(t,d): + Document boost: được thiết lập khi tạo tài liệu d bằng câu lệnh doc.setBoost() + Field boost: được thiết lập trước khi tạo trường này trong document d bằng câu lệnh field.setBoost() + lengthNorm(field): được thiết lập khi tài liệu này được indexing, giá trị của nó tỷ lệ với số lượng token trong trường này của tài liệu d. Doc.getBoost mặc định là 1. lengthNorm = 1/ căn bậc hai của số lượng token trong trường đó. 2.3.2. Xếp hạng tài liệu Khi một câu truy vấn được đưa vào hệ thống, các tài liệu chứa các từ theo yêu cầu sẽ được trả về. Câu truy vấn ‘greenstone pdf’, được hiểu là tìm những tài liệu nào chứa greenstone hoặc pdf. Như vậy, câu truy vấn này sẽ được tách thành hai câu truy vấn con, tìm tài liệu nào chứa từ greenstone và tài liệu nào chứ từ pdf. Mỗi một câu truy vấn con có điểm là tổng của hai trọng số queryWeight và fieldWeight: + queryWeight = idf * queryNorm. + QueryNorm là giá trị của câu truy vấn gốc, sẽ thay đổi giá trị khi khác câu truy vấn hoặc trường truy vấn hoặc bộ analysis. Ngược lại, cùng câu truy vấn và trường truy vấn và bộ analysis, thì giá trị sẽ giống nhau. Được tính bằng 1/ căn bậc 2 của tổng các bình phương idf của các từ trong query gốc . + fieldWeight = tf * idf * fieldNorm . + FieldNorm = t.getBoost * norm 23 Sau khi cộng tổng các điểm của các câu truy vấn con, nó sẽ được nhân với giá trị coord() . Như vậy, đối với mỗi tài liệu trả về sẽ có một chỉ số. Chỉ số này được tính bằng cách so sánh tài liệu đó với các câu truy vấn con và cộng tổng lại và nhân với giá trị coord() của tài liệu đó so với câu truy vấn gốc. Tài liệu nào có chỉ số cao hơn sẽ được trả về trước. Minh hoạ cho câu truy vấn trên, tài liệu có chỉ số lớn nhất: 4.7319136 = (MATCH) sum of:  3.2000232 = (MATCH) weight(name:greenston in 9643), product of: o 0.82235277 = queryWeight(name:greenston), product of:  7.782604 = idf(docFreq=10, numDocs=9706)  0.1056655 = queryNorm o 3.891302 = (MATCH) fieldWeight(name:greenston in 9643), product of:  1.0 = tf(termFreq(name:greenston)=1)  7.782604 = idf(docFreq=10, numDocs=9706)  0.5 = fieldNorm(field=name, doc=9643)  1.5318903 = (MATCH) weight(name:pdf in 9643), product of: o 0.56897795 = queryWeight(name:pdf), product of:  5.384709 = idf(docFreq=120, numDocs=9706)  0.1056655 = queryNorm o 2.6923544 = (MATCH) fieldWeight(name:pdf in 9643), product of:  1.0 = tf(termFreq(name:pdf)=1)  5.384709 = idf(docFreq=120, numDocs=9706)  0.5 = fieldNorm(field=name, doc=9643) Câu truy vấn ‘" cung cấp một phương thức " + "greenstone"‘: được chia làm hai câu truy vấn, tính toán tương tự như trên. 24 0.5364156 = (MATCH) sum of:  0.14055021 = weight(keyword:"cung_cấp một phương_thức" in 9665), product of: o 0.86087066 = queryWeight(keyword:"cung_cấp một phương_thức"), product of:  13.931962 = idf(keyword: cung_cấp=245 một=1328 phương_thức=49)  0.061791055 = queryNorm o 0.16326518 = fieldWeight(keyword:"cung_cấp một phương_thức" in 9665), product of:  1.0 = tf(phraseFreq=1.0)  13.931962 = idf(keyword: cung_cấp=245 một=1328 phương_thức=49)  0.01171875 = fieldNorm(field=keyword, doc=9665)  0.39586538 = (MATCH) weight(keyword:greenstone in 9665), product of: o 0.508824 = queryWeight(keyword:greenstone), product of:  8.23459 = idf(docFreq=6, numDocs=9706)  0.061791055 = queryNorm o 0.7780006 = (MATCH) fieldWeight(keyword:greenstone in 9665), product of:  8.062258 = tf(termFreq(keyword:greenstone)=65)  8.23459 = idf(docFreq=6, numDocs=9706)  0.01171875 = fieldNorm(field=keyword, doc=9665) 25 Chương 3. Hệ thống Greenstone 3.1. Giới thiệu chung về Greenstone Greenstone là một hệ thống hoàn chỉnh dùng đê xây dựng và trình bày các bộ sưu tập gồm có hàng ngàn, hàng triệu tài liệu bằng chữ, hình ảnh, băng tiếng hay băng hình. 3.1.1. Các bộ tài liệu Một thư viện số thông thường được xây dựng bằng phần mềm Greenstone sẽ chứa được nhiều bộ sưu tập, được sắp xếp riêng lẻ thông qua sự giống nhau nổi bật, được duy trì dễ dàng. Ngoài ra bộ tài liệu còn có thể được bổ sung và tự động tái tạo lại. Có nhiều cách để tìm kiếm thông tin trong bộ sưu tập Greenstone. Ví dụ, bạn có thể tìm bằng từ khoá (là từ xuất hiện trong một đoạn văn bản hay một phần trong tài liệu cần tìm). Bạn có thể trình duyệt tài liệu theo tiêu đề bằng cách nhấp chuột vào quyển sách. Bạn cũng có thể trình duyệt tài liệu theo chủ đề. Các chủ đề được sắp xếp theo dạng kệ sách, bạn chỉ cần nhấp chuột vào kệ sách để tìm các quyển sách ở trong đó. Nhiều khi các tài liệu còn có cả bảng mục lục: Bạn có thể nhấp chuột vào một chương hoặc một thư mục nhỏ để mở ra xem, để mở rộng cả bảng mục lục, hay mở toàn bộ tài liệu trong cửa sổ trình duyệt của bạn (Giúp ích cho việc in ấn). Trang web Thư viện số New Zealand (nzdl.org) cung cấp rất nhiều bộ sưu tập mẫu. Trên mỗi trang đầu của bộ sưu tập đều trình bày mục đích sử dụng và hình trang bìa của từng quyển sách, và những chỉ dẫn cách sắp xếp bộ tài liệu. Hầu hết các bộ sưu tập đều có thể được truy cập bằng cả hai cách: tìm kiếm và trình duyệt. Khi tìm kiếm, phần mềm Greenstone sẽ tìm toàn bộ nội dung của tất cả các văn bản trong bộ sưu tập. Trong hầu hết các bộ sưu tập, người sử dụng có thể chọn sử dụng các chỉ mục được xây dựng từ những phần khác nhau của tài liệu. Một số bộ sưu tập có chỉ mục tất cả tài liệu, chỉ mục từng đoạn, và chỉ mục các tựa sách. Có thể tìm các chỉ mục này theo từ hay cụm từ khóa. Bằng cách này, bạn có thể tìm được tất cả các văn bản có chứa các từ khóa nào đó (các từ khoá này có thể được phân bố rải rác 26 trong văn bản), hoặc tất cả những đoạn văn có chứa các từ này (các từ này phải cùng xuất hiện trên cùng một đoạn văn), hoặc tất cả các sưu tập có các tiêu đề chứa các từ này (các từ này phải cùng xuất hiện trên tựa của văn bản). Còn có cả các chỉ mục khác, ví dụ chỉ mục theo từng phần hay theo những đề mục nhỏ. Trong quá trình trình duyệt, người sử dụng có thể ngiên cứu danh mục các tác giả, danh mục các tiêu đề, danh mục các ngày, cấu trúc phân loại theo từng lớp, v.v… Các bộ sưu tập khác nhau có thể có các cách trình duyệt khác nhau. 3.1.2. Tìm kiếm thông tin Phần mềm Greenstone xây dựng những chỉ mục toàn phần theo nội dung văn bản - nghĩa là những chỉ mục giúp bạn tìm kiếm theo bất cứ từ nào trong toàn bộ nội dung tài liệu. Chỉ mục có thể được dùng để tìm kiếm theo các từ khoá, hay các cụm từ, và kết quả sẽ được sắp xếp theo thứ tự dựa trên sự phù hợp đối với câu truy vấn. Trong hầu hết các bộ tài liệu, các dữ liệu mô tả như Tác giả, Tiêu đề, ngày tháng, từ khoá, v.v.. đều đi kèm với từng tài liệu. Dữ liệu này được gọi là dữ liệu khóa (metadata). Nhiều bộ sưu tập chứa cả chỉ mục nội dung của một số loại dữ liệu khoá. Ví dụ, một số bộ sưu tập, người dùng có thể tìm kiếm dựa trên chỉ mục về Tên tài liệu. Người dùng có thể trình duyệt một cách trực tiếp dựa trên danh mục và cấu trúc phân lớp được thiết lập từ dữ liệu khoá có liên quan đến các tài liệu trong bộ sưu tập. Dữ liệu khoá là dữ liệu thô cuả việc tìm kiếm. Nó phải được trực tiếp cung cấp hoặc được tự động rút ra từ chính các tài liệu. Các bộ sưu tập khác nhau có thể có những tính năng tìm kiếm và trình duyệt khác nhau. Chỉ mục tìm kiếm và trình duyệt được thiết lập trong quá trình xây dựng bộ sưu tập dựa trên các thông tin trong tập tin cấu hình. Greenstone tự động tạo ra các chỉ mục từ các tài liệu và tập tin hỗ trở: Không một quá trình nào phải làm bằng tay. Nếu các tài liệu mới có cùng một định dạng, chúng sẽ tự động được xếp vào chung một bộ sưu tập. Trên thực tế, trên nhiều bộ sưu tập, việc này được tiến hành bởi các quá trình 27 được kích hoạt thường xuyên để theo dõi tài liệu mới, và cập nhập lại các chỉ mục - Tất cả đều được thực hiện một cách tự động. 3.1.3. Định dạng dữ liệu Tài liệu nguồn có nhiều dạng khác nhau, và được chuyển sang định dạng chuẩn XML để sử dụng plugins. Các plugins được phân phát với Greenstone để hỗ trợ các văn bản thô, HTML, WORD, PDF, Usenet và E- mail. Còn plugins khác có thể được viết cho những kiểu dữ liệu khác (để sử dụng chúng, bạn cần phải đọc phần Hướng dẫn phát triển Phần mềm Greenstone). Để xây dựng cấu trúc trình duyệt từ dữ liệu khóa, ta sẽ tương tự sử dụng một cách phân loại theo lớp. Các phân loại này sẽ tạo ra các chỉ mục trình duyệt khác nhau: liệt kê dạng thanh cuộn, dạng mẫu tự Alphabet, dạng ngày tháng, hay một dạng cấu trúc lớp tùy ý. Một lần nữa, các lập trình viên trên Greenstone có thể tạo ra cấu trúc trình duyệt mới. 3.1.4. Các tài liệu đa phương tiện và đa ngôn ngữ Bộ sưu tập có thể chứa chữ, hình ảnh tĩnh, hình ảnh động, âm thanh. Những tài liệu không thuộc dạng chữ được liên kết với những tài liệu dạng chữ hay những tài liệu mô tả dạng chữ (ví dụ như chú thích hình ảnh) để hỗ trợ việc tìm kiếm và trình duyệt nội dung Unicode, phông chữ chuẩn trên Thế giới dùng để trình bày nội dung tài liệu, cũng được sử dụng trong Greenstone. Điều này cho phép bất cứ ngôn ngữ nào cũng đều được xử lý và trình bày theo một kiểu thống nhất. Các bộ sưu tập được đã được xây dựng có chứa các kiểu chữ Ả rập, Trung Quốc, Anh, Pháp, Mäori và Tây Ban Nha. Chương trình tự động nhận ra ngôn ngữ mẫu trong bộ sưu tập và giao diện được trình bày theo những ngôn ngữ sẵn có trên. 3.1.5. Chức năng phân phối của phầm mềm Các bộ sưu tập được truy cập thông qua Internet, dưới dạng các ấn phẩm, hoặc bằng đĩa CD-ROM tự cài đặt. Chương trình nén được sử dụng để nén nội dung tài liệu và chỉ mục. Một giao thức Corba sẽ hổ trợ cho các bộ sưu tập được phân phối và giao diện truy vấn. 28 Thư viện số New Zealand(nzdl.org) cung cấp các bộ sưu tập mẫu bao gồm: Tập tài liệu về lịch sử, thông tin về con người và sự phát triển, báo cáo kỹ thuật và tiểu sử, các tác phẩm văn học và tạp chí. Là phần mềm mã nguồn mở, Greenstone dễ mở rộng và hưởng lợi từ các modules truy cập nội dung, quản lý cơ sở dữ liệu, và lấy nội dung từ các loại định dạng khác nhau của sự cho phép của GNU. Chỉ với sự hợp tác quốc tế thì phần mềm này mới có thể trở thành một phần mềm hoàn thiện, dáp ứng được những yêu cầu ngày càng đa dạng và phong phú của người sử dụng. 3.2. Kiến trúc của hệ thống Greenstone Hệ thống Greenstone bao gồm nhiều thành phần quan trọng sau: Library Servlet, Receptionist, các Action, MessageRouter , ServiceCluster và các collection. Library Servlet: + Thực hiện viện nhận các query của người dùng, đóng gói dưới dạng XML và gửi xuống tầng Receptionist. + Hiển thị kết quả trả về. Receptionist: + Đọc file interfaceConfig.xml và tải những lớp Action khác nhau cùng với các thẻ ngôn ngữ + Chỉnh sửa yêu cầu trước khi giử tới Action thích hợp + Thêm một số dữ liệu vào trang trả về + Chuyển thông điệp trả về thành HTML nhờ XSLT 29 Hình 3-1 Kiến trúc hệ thống Greenstone Action: Receptionist sẽ giử yêu cầu người dùng vào đúng Action thích hợp + PageAction điều khiển những trang tĩnh được sinh tự động (homepage, aboutpage, prefpage). + QueryAction điều khiển trang truy vấn. + DocumentAction hiển thị tài liệu + BrowseAction trình duyệt bộ sưu tập chỉ định. 30 + ProcessAction xử lý các yêu cầu nhập tài liệu (import), xây dựng bộ sưu tập (build), tạo mới (active), thêm tài liêu (add). MessageRouter: + Là chức năng ở trung tâm, tất cả các thông điệp phải đi qua nó. + Nếu yêu cầu là tạo mới, thêm tài liệu, nhập tài liệu, xây dựng bộ sưu tập thì sẽ được chuyển đến ServiceCluster. + Nếu như yêu cầu liên quan đến việc truy vấn một bộ sưu tập (colletion) nào đó có sẵn nào đó. MessageRouter tải đối tượng collection cho collection cần chọn. Đối tượng collection đọc file buildconfig.xml và CollectionConfig.xml để xác định các siêu dữ liệu do người dùng định nghĩa khi xây dựng Collection và tải các ServiceRack . ServiceCluster: + ImportCollection Service: nhập tài liệu vào bộ sưu tập + BuildCollection Service: xử lý tài liệu của bộ sưu tập + ActivateCollection Service: tạo mới một bộ sưu tập hoặc kích hoạt bộ sưu tập cũ nhưng các chức năng của nó sẽ bị xoá. + AddDocument Service: thêm tài liệu vào bộ sưu tập. Collection: + Các Service truy vấn (query). + Các Service về tài liệu (document). 3.3. Xây dựng bộ sưu tập 3.3.1 Khái niệm Greenstone là một phần mềm thư viện số, cho phép tạo ra và quản lý các bộ sưu tập (collection). Bộ sưu tập bao gồm nhiều dạng tài liệu như HTML, XHTML và XML, TXT, Word, RTF, PDF, PostScript, dạng multi-media như âm thanh (ví dụ .mp3), hình ảnh, phim. 31 Mỗi dạng tài liệu đều có các plugin tương ứng để chuyển về một dạng thống nhất là XML của Greenstone. Plugin sẽ đọc tài liệu và trích xuất những thông tin metadata và nội dung của tài liệu đó vào trong file XML. Các plugin được viết bằng ngôn ngữ lập trình Perl. Mọi plugin đều kế thừa từ plugin cơ sở BasPlug. Plugin cơ sở BasPlug thực hiện những thao tác cơ bản như tạo tài liệu mới XML theo định dạng của Greenstone, gán định danh cho tài liệu. Các plugin được đặt trong thư mục “greenstone\perllib\plugins”. Tên plugin Công dụng Kiểu tập tin xử lý Các tập tin không xử lý BasPlug Là lớp cơ sở cho tất cả các plugin - - ConvertToPlug Gọi các chương trình bên ngoài để chuyển các tài liệu độc quyền (word hay pdf) sang html hay plain text - - ArcPlug Đọc tập tin archives.inf, tập tin archive.inf là cầu nối giữa tiến trình import và tiến trình build. Những tệp tin khai báo trong archives.inf sẽ được xử lý. Plugin này bắt buộc phải khai báo trong tập tin cấu hình RecPlug Duyệt qua thư mục để xử lý các tập tin mà plugin này tìm thấy GAPlug Xử lý những tập tin xml được khai báo trong archive.inf phát sinh từ chương trình import.pl .xml TEXTPlug Xử lý tập tin text thuần túy .txt, .text HTMLPlug Xử lý tập tin HTML .htm, .html, .cgi, .php, .asp, .shm, .gif, .jpg, .jpeg, .png, .css, .rtf 32 .shtml WordPlug Xử lý tài liệu Word .doc .gif, .jpg, .jpeg, .png, .css, .rtf PDFPlug Xử lý tập tin pdf .pdf .gif, .jpg, .jpeg, .png, .css, .rtf PSPlug Xử lý tài liệu postscript, trích thông tin metadata ngày, tựa đề, số trang .ps .eps EMAILPlug Xử lý những thông điệp email, trích thông tin như tác giả, chủ đề, ngày… Tên tập tin kết thúc bằng số, hoặc số theo sau là .Email BibTexPlug Xử lý các tập tin bibliography theo chuẩn BibTex .bib ReferPlug Xử lý các tập tin bibliography theo chuẩn Refer .bib SRCPlug Xử lý các tập tin mã nguồn Makefile, Readme, .c, .cc,.cpp, .h, .hpp, pl, .pm, .sh .o, .obj, .a, .so, .dll ImagePlug Xử lý các tập tin ảnh. Plugin này chỉ dùng trên UNIX .gif, .jpg, .jpeg, .png, .bmp, .xbm, .tif, .tiff SplitPlug Giống BasPlug và ConvertToPlug. Không dùng trực tiếp plugin này, 33 plugin này phải được kế thừa lại để xử lý tài liệu FOXPlug Xử lý các tập tin FoxBase .dbt, .dbf ZIPPlug Xử lý các tập tin nén .gzip, .bzip, .zip, .tar, .gz, .bz, .tgz, .taz Đối với tài liệu độc quyền như word, pdf, ta dùng các plugin tương ứng là WordPlug và PDFPlug. Các plugin này thực hiện 2 thao tác: 1. Chuyển tài liệu nguồn sang dạng html 2. Sử dụng plugin HTMLPlug chuyển kết quả ở bước 1 sang dạng XML của Greenstone. Sau khi đã chuyển các tài liệu về dạng chuẩn XML, hệ thống Greenstone sẽ tiến hành nén và lập chỉ mục (indexing) cho các tài liệu đó. Greenstone hỗ trợ Unicode, nên lập được chỉ mục cho Tiếng Việt ở mức tiếng. Để nâng cao hiệu quả của hệ thống, chúng tôi đã chèn thêm khả năng tách từ Tiếng Việt cho Greenstone theo thuật toán longest matching. 3.3.2. Thực nghiệm xây dựng bộ sưu tập Như đã giới thiệu ở trên, quá trình xây dựng một bộ sưu tập trải qua 3 pha chính:  Pha 1: Tạo cấu trúc chung cho bộ sưu tập  Pha 2: Chuyển định dạng tài liệu nguồn sang định dạng XML  Pha 3: Nén và tạo chỉ mục trên các tài liệu của bộ sưu tập Ở mỗi pha ta dùng chương trình do Greenstone hỗ trợ để xây dựng bộ sưu tập  Pha 1: dùng chương trình mkcol.pl  Pha 2: dùng chương trình import.pl 34  Pha 3: dùng chương trình buildcol.pl Các chương trình trên được đặt trong thư mục “greenstone\bin\script”. Để thực thi các chương trình này trong môi trường DOS, ta dùng cú pháp lệnh như sau: perl –S 3.3.2.1. Chương trình mkcol.pl Công dụng: Chương trình mkcol.pl dùng để tạo cấu trúc chung cho một bộ sưu tập, tạo tập tin cấu hình mặc định cho bộ sưu tập collect.cfg đặt trong thư mục con “etc” của bộ sưu tập. Cú pháp: mkcol.pl [Các tùy chọn] Ví dụ : perl -S mkcol.pl -creator hei@gmail.com demo Các tùy chọn: -creator : địa chỉ email của người tạo bộ sưu tập -optionfile : lấy những tùy chọn từ một tập tin nào đó. -maintainer : địa chỉ email của người quản lý bộ sưu tập. -collectdir : thư mục chứa bộ sưu tập. Giá trị mặc định là “greenstone\collect” -public : cho phép bộ sưu tập được truy cập rộng rãi hay không. Giá trị mặc định là “true” -title : tựa đề của bộ sưu tập -about : thông tin mô tả bộ sưu tập -plugin : tên plugin được dùng -quiet : không hiển thị các thông báo của chương trình 35 -win31compat : cho biết tên thư mục của bộ sưu tập có tuân theo quy ước của Windows 3.1 hay không (tên thư mục có độ dài tối đa 8 kí tự). Giá trị mặc định là “true”. 3.3.2.2. Chương trình import.pl Công dụng: Chuyển định dạng tài liệu nguồn sang định dạng XML của Greenstone, tạo tập tin tóm tắt thông tin archive.inf. Cú pháp: import.pl [Các tùy chọn] Ví dụ : perl -S import.pl –removeold -importdir E:\data demo Các tùy chọn: -archivedir : đường dẫn đến các tập tin sau khi import, mặc định là “greenstone\collect\\archives” -collectdir : thư mục chứa các bộ sưu tập, mặc định là “greenstone\collect” -debug: chạy chương trình ở chế độ debug, chỉ xuất kết quả ra màn hình, không tạo các tập tin kết quả sau khi import -faillog : đường dẫn đến tập tin log lưu tên của những tập tin không import được. Mặc định là “greenstone\collect\<tên thư mục chứa bộ sưu tập>\etc\fail.log” -groupsize : số tài liệu được nhóm thành một tập tin XML, mặc định là 1 -gzip: dùng gzip để nén những tài liệu XML kết quả. Chú ý phải thêm plugin ZIPPlug vào danh sách các plugin trong tập tin cấu hình. -importdir : đường dẫn đến các tập tin ngưồn -keepold: không xóa nội dung của thư mục archive (mặc định) -maxdocs : số tài liệu tối đa được import 36 -OIDtype : phương thức dùng để phát sinh ra ID duy nhất cho mỗi tài liệu. Giá trị mặc định là hash.Các giá trị có thể là hash, incremental, assigned, dirname. -out : tên tập tin hoặc handle để in ra các dòng thông báo. Giá trị mặc định là STDERR 3.3.2.3. Chương trình buildcol.pl Công dụng Nén văn bản, tạo chỉ mục trên tài liệu XML, lưu thông tin thể hiện bộ sưu tập vào cơ sở dữ liệu (icon, tiêu đề, thông tin classifier tạo ra…) Để lập chỉ mục bằng lucene, ta chỉnh tham số trong file collect.cfg trong thư mục etc từ buildtype mgpp => buildtype lucene Cú pháp buildcol.pl [Các tùy chọn] Ví dụ : perl -S buildcol.pl demo Các tùy chọn -remove_empty_classifications : giấu đi những classifier và những nút phân cấp rỗng (chúng không chứa những tài liệu nào) -archivedir : đường dẫn đến thư mục archives -builddir : đường dẫn đến thư mục building chứa các chỉ mục đã được tạo -collectdir : đường dẫn thư mục chứa các bộ sưu tập, mặc định là “greenstone\collect” 37 -debug: chạy chương trình ở chế độ debug, chỉ xuất các kết quả ra màn hình, không tạo ra các tập tin kết quả. -faillog : đường dẫn đến tập tin log, mặc định là “greenstone\collect\\etc\fail.log” -index : xác định loại chỉ mục sẽ được xử lý. Nếu tùy chọn này không được chọn thì các chỉ mục trong tập tin cấu hình collect.cfg sẽ được xử lý. -keepold: không xóa nội dung hiện tại ở thư mục building -maxdocs : số tài liệu tối đa được xử lý -mode : chỉ ra các công việc được thực hiện trong quá trình building, giá trị mặc định là all 3.3.2.4. Cấu trúc của một bộ sưu tập: Hình 3-2 Cấu trúc của một bộ sưu tập Tên thư mục Mục đích archives Chứa các tập tin sau khi thực hiện câu lệnh import , chứa các tài liệu ở dạng chuẩn XML building Chứa các tập tin trong quá trình nén, tạo chỉ mục, tạo cơ sở dữ liệu cho bộ sưu tập etc Chứa tập tin cấu hình collect.cfg Collection name archives building etc import index macros macros 38 images Chứa các ảnh dành riêng cho bộ sưu tập import Chứa các tài liệu nguồn cần xây dựng bộ sưu tập index Chứa các tập tin sau khi nén, tạo chỉ mục, cơ sở dữ liệu lấy từ thư mục building tmp Chứa các file pdf hay word đã được chuyển sang dạng html Trong các thư mục trên, thư mục index là quan trọng nhất, vì nó là kết quả tổng hợp cuối cùng và hệ thống trình duyệt web sẽ chỉ đọc hai thư mục etc và index. Thư mục index: Hình 3-3 Cấu trúc thư mục index của mỗi bộ sưu tập Tên thư mục Mục đích Assoc Các file nguồn thuộc dạng độc quyền như word , pdf sẽ được lưu ở đây , cung cấp thêm chức năng tải file cho người dùng . didx Lưu trữ chỉ mục ở mức document text Lưu trữ các tài liệu ở dạng chuẩn XML Index assoc didx text 39 3.3.3. Hiển thị collection lên website 3.3.3.1. Thư mục etc: Thêm file collectionConfig.xml: + //giới thiệu về collection //tên ảnh .gif cho collection //tên ảnh .gif cho collection //là title của collection + // kiểu dạng search mgpp và lucene // có 2 thuộc tính search để lựa chọn section và document. Mỗi loại sẽ có thư mục index riêng. Tìm kiếm theo Document thì index được chứa trong didx. Tìm kiếm theo section thì chứa trong sidx. section document // thiết lập giá trị mặc định của search 40 //các bộ phân loại và tên của nó sẽ được hiển thị all fields text titles subjects organisations //là các thuộc tính được chọn khi index + 41 // các plugin mà hệ thống sẽ sử dụng + //các bộ phân loại chính thức được hiển thị 42 + dc.Title,dls.Title dc.Subject,dls.Subject dc.Language,dls.Language dc.Organization,dls.Organization 3.3.3.2. Thư mục index: Thư mục index được tạo bằng cách sao chép toàn bộ thư mục building khi đã xây dựng xong. Bởi thư mục building là thư mục lưu trữ kết quả đang xây dựng collection, tránh ảnh hưởng đến thư mục index – thư mục chứ kết quả của collection trước đó. Thêm file buildConfig.xml: + //số lượng các document được index 11 mgpp + 1 : //tên của collection là gs2mgppdemo giúp cho việc truyền query đến đúng collection 43 2 : // thực hiện việc mapping đến các thuộc tính của document được lưu trong thư mục index . 44 3 : 4 : 45 Chương 4. Thực nghiệm xây dựng máy tìm kiếm tiếng Việt 4.1. Vấn đề tìm kiếm tiếng Việt và tiếp cận Do Tiếng Việt là ngôn ngữ đơn lập. Đặc điểm này bao quát tiếng Việt cả về mặt ngữ âm, ngữ nghĩa, ngữ pháp. Khác với các ngôn ngữ Ấn-Âu, mỗi từ là một nhóm các ký tự có nghĩa được cách nhau bởi một khoảng trắng. Còn tiếng Việt, và các ngôn ngữ đơn lập khác, thì khoảng trắng chỉ là căn cứ để nhận diện tiếng. Các tiếng kết hợp với nhau tạo nên từ. Từ là sự hoàn chỉnh về mặt nội dung, là đơn vị nhỏ nhất để đặt câu.Vì vậy tách từ là một khâu quan trọng trong quá trình lập chỉ mục. Chúng tôi nhận thấy việc tách từ trong tiếng Việt là một bài toán khó vì những nguyên nhân sau đây: - Từ ở dạng nguyên thể, hình thức và ý nghĩa của từ độc lập với cú pháp. - Từ bao gồm nhiều tiếng. - Từ bao gồm từ đơn (từ một tiếng) và từ phức (n tiếng , với n<5), bao gồm từ láy và từ ghép. - Các tiếng cuối của từ này có thể là tiếng đầu của từ khác. - Gianh giới giữa các từ có thể là dấu trắng cũng chính là gianh giới giữa các tiếng Trong luận văn này, chúng tôi xây dựng tách từ trong văn bản tiếng Việt dựa trên thuật toán tách từ dài nhất (Longest matching), việc tách từ chủ yếu dựa trên các thông tin có trên từ điển. Do chỉ dựa vào từ điển mà không dựa trên văn cảnh nên phương pháp này có nhiều hạn chế trong việc xử lý các trường hợp nhập nhằng có trong văn bản. Thuật toán tách từ dài nhất là thuật toán dựa trên tư tưởng tham lam, nó xét các tiếng từ trái qua phải, các tiếng đầu tiên dài nhất có thể mà xuất hiện trong từ điển sẽ được tách ra làm một từ. Thuật toán luôn dừng khi xét hết 46 các tiếng. Thuật toán này chỉ đúng khi không có sự nhập nhằng những tiếng đầu của từ sau có thể ghép với từ trước tạo thành một từ có trong từ điển. Nếu xét từng câu một, độ phức tạp của thuật toán này là O (L * L * O (của thao tác tìm kiếm một từ trong từ điển)), L là số tiếng trong câu . Do số tiếng của một từ nhỏ hơn 5 nên có thể cải thiện thành O ( L*(độ phức tạp của thao tác tìm kiếm một từ trong từ điển)). Do vậy, để thuật toán nhanh cần xây dựng cách tìm một từ trong từ điển sao cho nhanh nhất có thể. Có thể dùng cách tìm kiếm bằng bảng băm, tìm kiếm nhị phân,…. Ví dụ minh hoạ: tôi yêu thích học môn toán 4.2. Hệ thống Lucene Lucene là một thư viên IR hoàn hảo, cung cấp hai khả năng lập chỉ mục (indexing) và tìm kiếm (searching) cho các ứng dụng. Một số ứng dụng sử dụng Lucene như SearchBlow, Nutch, Larm, jSearc… Indexing là sự xử lý dữ liệu nguồn thành một bảng tra cứu với hiệu suất cao để việc tìm kiếm trở nên nhanh chóng. Lucene sử dụng chỉ mục tệp đảo (IFID) để xây dựng tệp đảo. Để indexing được dữ liệu, Lucene sử dụng các bộ phân tích để tách các tài liệu thành các từ để lập chỉ mục. Có năm bộ phân tích: WhitespaceAnalyzer: + Tách các từ tại các khoảng trắng. SimpleAnalyzer: Bước Từ dài nhất có thể Danh sách các tiếng còn lại 1 tôi yêu thích môn toán 2 yêu thích học môn toán 3 học môn toán 4 môn toán 47 + Tách các từ tại các ký tự không phải là chữ và lowercase StopAnalyzer: + Giống SimpleAnalyzer và thêm loại bỏ stopword StandardAnalyzer: + Tách từ dựa trên ngữ pháp nên có thể nhận ra địa chỉ email, ký tự Trung- Nhật – Hàn + LowerCase và loại bở stopword. PositionalPorterStopFilter: + Tách từ tại các khoảng trắng, loại bỏ stopword và truy gốc từ theo thuật toán truy gốc Porter. Đối tượng của các bộ phân tích này là các tài liệu (document). Trong đó, mỗi tài liệu có nhiều trường, mỗi trường bao gồm nội dung và kiểu trường. Các kiểu trường có thể là: Field.Text: Analyzed , Indexed , Stored Field.Keyword: Indexed , Stored Field.UnIndex: Stored Field. UnStored: Analyzed , Indexed Trường Field.Text, nội dung của trường này sẽ được phân tích ra thành các từ và lưu vào tệp đảo, Stored nghĩa là nội dung này sẽ được lưu giữ và có thể được trích xuất ra. Trường Field.Keyword, nội dung được giữ nguyên và đưa vào trong tệp đảo và nội dung này cũng được lưu trữ. Trường Field.UnIndex, nội dung chỉ được lưu mà không được phân tích và lưu vào bảng chỉ mục. Trường Field.UnStored, nội dung sẽ không được lưu nhưng được phân tích và lưu vào bảng chỉ mục. 48 Bảng chỉ mục sẽ giúp cho các tài liệu được tìm thấy bởi các từ khoá (keyword). 4.3. Phần mềm VietSearch 4.3.1. Hệ thống lập chỉ mục Hình 4-1 Indexing System Hệ thống lập chỉ mục làm nhiệm vụ lập chỉ mục cho các tài liệu nguồn. Tài liệu nguồn này có rất nhiều dạng như file pdf, doc, rtf, txt, html, xml, jpeg, mp3…. . Hệ thống sẽ phải trích rút ra nội dung của những file này cũng như các siêu dữ liệu (metadata) của chúng để thiết lập các tài liệu (document) của hệ thống. Việc thiết lập nội dung cho các tài liệu phải trải 49 qua các tiến trình như Filter , Language , LongestMatching (LM), FilterStopword (FS). Chức năng Miêu tả Gather Data Nhận dạng loại file, và khởi tạo bộ đọc file tương ứng để lấy ra nội dung của file đó. Filter Dữ liệu có nhiểu ký tự dư thừa, không có ý nghĩa, sẽ được loại bỏ và Lowercase. Language Xác định ngôn ngữ cho tài liệu, tiếng Anh hay là tiếng Việt. Giúp cho việc chọn bộ tách từ phù hợp. Longest Matching (LM) Nếu là tiếng Việt, nội dung của văn bản sẽ được tách từ theo thuật toán tách từ dài nhất và loại bỏ các từ stopword trong tiếng Việt Ví dụ: tôi yêu thích học môn toán => tôi yêu_thích học môn_toán Whitespace Analysis Các Document tiếng Việt sau khi đã qua LM, thì việc tách từ trở nên đơn giản hơn, lúc này khoảng trắng chính là dấu phân cách giữa các từ FilterStopword Nếu là tài liệu tiếng Anh sẽ được loại bỏ các từ Stopword trong tiếng Anh EnglishAnalysis Sử dụng PositionalPorterStopFilter 50 4.3.2. Hệ thống tìm kiếm Hình 4-2 Searching System Hệ thống nhận câu truy vấn của người sử dụng, lowercase câu truy vấn. Nếu người sử dụng chọn tách từ theo tiếng Việt, thì chức năng VNFilter sẽ được gọi. VNFilter sẽ tách từ và lọc stopword tiếng Việt. Sau đó câu truy vấn sẽ được chuyển về dạng câu truy vấn chuẩn của hệ thống Lucene. Chức năng Search Index sẽ thiết lập đối tượng tìm kiếm, người sử dụng chọn tiếng Việt thì WhiteSpace Analysis được chọn, nếu chọn tiếng Anh thì PositionalPorterStopFilter sẽ đựơc chọn. 4.3.3. Mô hình tương tự Trong phần này, chúng ta xem xét ba phương pháp khác nhau, dùng để xác định mức độ tương đồng giữa hai vector đặc trưng va và vb . Trong đó  wwwv in2i1ii ,......,, và  bai , , 10  wij ,  nj ,.....,2,1 , và n là tổng số đặc trưng của vector. 51 Có ba phương pháp xác định mức độ tương đồng giữa hai vector này, đó là dùng: Hệ số Cosine, Khoảng cách Euclidean và Manhattan. 4.3.3.1. Hệ số Cosine Hệ số cosine là một hệ số được dùng phổ biến để xác định mức độ tương đồng giữa các vector đặc trưng của hai văn bản. Nếu hệ số cosine giữa hai văn bản càng lớn thì mức độ tương đồng giữa chúng càng lớn. Cho hai vector va và vb, mức độ tương đồng giữa hai vector này được xác định bằng công thức:            n 1i 2 bi n 1i 2 ai n 1i biai ba ww ww vv ,cos_sim 4.3.3.2. Khoảng cách Euclidean Khoảng cách Euclidean là một phương pháp phổ biến nhất để xác định mức độ tương đồng giữa các vector đặc trưng của hai văn bản. Cho hai vector va và vb, khoảng cách Euclidean được định nghĩa như sau:        n 1i 2 ba wwvv biai,euc_dist Vì   n ,euc_dist vv ba nằm trong khoảng 0 và 1, do đó mức độ tương đồng giữa hai vector này được xác định bằng công thức như sau:   1,_ vv basimeuc   n ,euc_dist vv ba =      n 1i 2 ww biai 11 n 4.3.3.3. Khoảng cách Manhattan: Khoảng cách Manhattan là một phương pháp thứ ba dùng để xác định mức độ tương đồng giữa các vector đặc trưng của hai văn bản. Cho hai vector va và vb, khoảng cách Manhattan được định nghĩa như sau: 52      n i biai wwman 1 ba vv ,_dist Vì   n ,_dist vv baman nằm trong khoảng 0 và 1, do đó mức độ tương đồng giữa hai vector này được xác định bằng công thức như sau:   1,_ vv basimman   n ,_dist vv baman =    n i biai wwn 1 11 4.3.4. Bộ phân loại tự động Dữ liệu chuẩn cho bộ phân loại tự động là các thư mục theo từng category. Các thư mục này chứa các dữ liệu chỉ liên quan đến lĩnh vực của nó. Các tài liệu của mỗi category phải bao trùm hết các khía cạnh của category đó. Lập chỉ mục cho bộ dữ liệu này, là để thiết lập cơ sở dữ liệu cho bộ phân loại tự động. Bộ phân loại tự động được khởi tạo bằng các tải các tài liệu đã được lập chỉ mục, và trích chọn lấy những từ khoá quan trọng, đặc trưng cho tài liệu đó vào category của nó. Kết quả là mỗi category có các từ khoá thể hiện đặc trưng của category đó. Kèm với mỗi từ khoá là số lần xuất hiện của nó trong tất cả văn bản thuộc category này. Khi chúng ta cần phân loại cho một văn bản, thì hệ thống sẽ trích chọn các từ khoá thể hiện đặc trưng của văn bản này. Văn bản đó sẽ được thể hiện bằng một chuỗi các từ khoá và số lần xuất hiện của chúng trong văn bản. Quyết định văn bản này thuộc category nào, là việc so sánh giữa hai vector category với văn bản. Ở đây chúng tôi dùng hệ số cosine để tính toán và tìm ra category phù hợp nhất. Trong phần mềm VietSearch, có hai category là kinh-doanh và vi-tinh. Việc thực hiện phân loại tự động cho kết quả rất tốt. Khả năng phân loại vào khoảng 92%. 53 4.3.5. Tìm kiếm các tài liệu liên quan Khi người sử dụng nhập vào một câu truy vấn, hệ thống tìm kiếm trả về kết quả là một chuỗi các tài liệu thoả mãn. Người sử dụng lại muốn đưa lên một yêu cầu, tìm các tài liệu liên quan đối với một tài liệu trong số các tài liệu thoả mãn. Nhận được yêu cầu này từ người sử dụng. Hệ thống sẽ tải tài liệu này lên và trích chọn những từ khoá đặc trưng cho văn bản này và tiến hành xây dựng câu truy vấn vào hệ thống. Câu truy vấn mang nghĩa, tìm tất cả các tài liệu liên quan đến những từ khoá đặc trưng cho văn bản đó. 4.4. Kết quả và đánh giá Dữ liệu dùng để xây dựng bộ chỉ mục là 1Gigabyte. Đây là dữ liệu được biên tập thủ công, được phân ra hai category là kinh-doanh và vi-tinh. Thời gian lập chỉ mục là 5h (trên máy Dou 2 Core 1.8, ram 1G) và kết quả là dữ liệu chỉ mục 100 Megabyte. Do hệ thống phải tách từ cho các tài liệu tiếng Việt nên thời gian có tăng. Nhìn vào những dữ liệu trên , ta có thể thấy tốc độ chạy của hệ thống là tốt. Khi người dùng nhập câu truy vấn vào hệ thống, thời gian chạy câu truy vấn thường là 20 milliseconds. Ví dụ ở đây chúng ta có câu truy vấn: Tìm hiểu hệ thống Greenstone Tách từ được chọn và Tiếng Việt. Vì thế câu truy vấn sẽ là: tìm_hiểu hệ_thống greenstone Hệ thống sẽ tìm trong tệp đảo với cách từ khoá: tìm_hiểu, hệ_thống, greentone. Kết quả của câu truy vấn được trả về là 491 tài liệu trong 16 miliseconds. Đối với mỗi tài liệu đều có 2 chức năng. Đó là xem nội dung của tài liệu và tìm các tài liệu liên quan tới tài liệu này. 54 Hình 4-3 Giao diện tìm kiếm của hệ thống Khi sử dụng hệ thống, bạn có thể chọn tách từ theo tiếng Việt hoặc tách từ theo tiếng Anh. Bạn cũng có thể giới hạn tìm kiếm của mình trong một lĩnh vực. Ở đây, có hai lĩnh vực là kinh-doanh và vi-tinh. Phần mềm cũng hỗ trợ phân trang. Mỗi lần chỉ đưa ra 10 trang đầu tiên của câu truy vấn. Người dùng có thể yêu cầu hiển thị 10 trang bất kỳ trong số hàng trăm kết quả được trả về. Hình 4-4 Giao diện tài liệu liên quan của hệ thống Bạn cũng có thể lập chỉ mục tài liệu mà bạn vừa mới sưu tầm được vào hệ thống bằng cách sử dụng chức năng Administator: 55 Hình 4-5 Giao diện lập chỉ mục của hệ thống Bạn chỉ cần cho những tài liệu vào thư mục E:\test\data\, và gõ đường dẫn này vào form. Nếu bạn để trong một thư mục con nữa, nghĩa là bạn đã chọn category cho những tài liệu này. Còn không, hệ thống sẽ sử dụng bộ phân loại tự động để phân loại tài liệu cho bạn 56 KẾT LUẬN Qua luận văn này, chúng ta có thể thấy được sự quan trọng của một bộ máy tìm kiếm đối với sự phát triển của mỗi đất nước và của toàn nhân loại. Các chức năng quan trọng của máy tìm kiếm như lập chỉ mục, tìm kiếm tài liệu, xếp hạng tài liệu, phân loại tự động tài liệu đã được làm rõ và thực nghiệm thành công. Đây là đóng góp quan trọng của luận văn. Định hướng tương lai về mặt ứng dụng : Phát triển và hoàn thiện chức năng phân loại tự động văn bản , thuật toán tách từ để nâng cao hiệu năng . Triển khai các chức năng quan trọng khác như MapReduce, BigTable, …