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.
56 trang |
Chia sẻ: lylyngoc | Lượt xem: 2887 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Luận văn Nghiên cứu máy tìm kiếm qua hệ thống Greenstone, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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,
…
Các file đính kèm theo tài liệu này:
- LUẬN VĂN-NGHIÊN CỨU MÁY TÌM KIẾM QUA HỆ THỐNG GREENSTONE.pdf