Xây dựng hệ thống thông tin tra cứu từ điển chuyên ngành có ngữ cảnh

Nội dung text: Xây dựng hệ thống thông tin tra cứu từ điển chuyên ngành có ngữ cảnh

1. Science & Technology Development, Vol 18, No Q3 - 2015 XÂY DỰNG HỆ THỐNG THƠNG TIN TRA CỨU TỪ ĐIỂN CHUYÊN NGÀNH CĨ NGỮ CẢNH BUILDING A INFORMATION SYSTEM FOR LOOKING UP CONTEXTUAL TECHNICAL DICTIONARY Hồ Trung Thành, Trần Thị Ánh Trường Đại học Kinh tế - Luật, ĐHQG HCM - Email: thanhht@uel.edu.vn Nguyễn Khánh Hồ Trường Đại học RMIT (Bài báo nhận ngày 28 tháng 07 năm 2015, hồn chỉnh sửa chữa ngày 12 tháng 09 năm 2015) TĨM TẮT Ngữ cảnh của từ điển chuyên ngành là rất quan trọng. Ngữ cảnh là một phần thơng tin bằng văn bản giúp cho người tra từ hiểu rõ nội dung ý nghĩa của từ khố nhằm giúp việc sử dụng từ đúng vào từng trường hợp cụ thể trong văn bản chuyên ngành, đặc biệt là trong học tập, nghiên cứu. Tuy nhiên, các hệ thống tra cứu từ hiện tại thường tập trung hỗ trợ tra cứu từ và giải thích từ mà chưa quan tâm đến ngữ cảnh của từ. Khi cĩ được ngữ cảnh của từ, câu hỏi đặt ra là làm thế nào để cĩ thể tìm kiếm được chính xác ngữ cảnh hoặc hiển thị kết quả tìm kiếm gợi ý cĩ liên quan đến từ khố trong kho dữ liệu văn bản ngữ cảnh? Trong bài báo này, chúng tơi đề xuất xây dựng phương pháp và mơ hình tra từ điển chuyên ngành cĩ ngữ cảnh trên cơ sở phân tích, đánh giá và lựa chọn giải thuật tối ưu trong các phương pháp so khớp văn bản. Sau đĩ, chúng tơi áp dụng giải thuật vào kỹ thuật tra từ của hệ thống. Tích hợp mơ hình đề xuất trên hệ thống website và thực nghiệm trên 1500 từ chuyên ngành cùng với ngữ cảnh thuộc lĩnh vực Hệ thống thơng tin quản lý và Thương mại điện tử. Hệ thống cĩ thể hỗ trợ cùng lúc việc tra từ điển bằng tiếng Anh và tiếng Việt. Từ khố: Giải thuật so khớp mẫu, hệ thống thơng tin, từ điển, chuyên ngành, ngữ cảnh. ABSTRACT The context of technical terms is very important. It is part of information in text which supports users in understanding the exact meaning of technical terms in particular specialized circumstances, especially in education and research. However, most of current dictionary systems only focus on the lookup function and the standard meaning of terms without considering related contexts. In this paper, we proposed the model for searching technical terms and context of terms based on analyzing, evaluating and choosing an optimal algorithm in pattern matching technique. Then, the model was integrated on a dictionary system and experimented on 1500 terms in the context of information system and electronic commerce. This dictionary system supports searching with technical terms both in Vietnamese and English. Keywords: Pattern - matching algorithm, information system, dictionary, technical term, context. 1. GIỚI THIỆU nghĩa của từ tiếng Anh và nhiều ngơn ngữ Dựa trên nền tảng phát triển Internet, hiện khác. Tại Việt Nam, cĩ thể dễ dàng tìm thấy nay cĩ rất nhiều cơng cụ hỗ trợ việc tra cứu nhiều sách từ điển Anh - Việt được xuất bản, Trang 82
2. TẠP CHÍ PHÁT TRIỂN KH & CN, TẬP 18, SỐ Q3 - 2015 các phần mềm tra cứu như Lạc Việt1, hay nhiều nhiên, hầu như vẫn chưa cĩ hệ thống website website hỗ trợ tra cứu online như: Vdict2, nào hỗ trợ tra từ điển Anh - Việt, Việt - Anh Google translate3, tratu.soha4, oxford thuộc chuyên ngành thương mại điện tử và hệ dictionaries.com5, Dictionary.com6 Các thống thơng tin quản lý, đây là một trong website này cĩ thể cung cấp đầy đủ từ điển mà những đĩng gĩp của chúng tơi trong nghiên người dùng cần. Đa phần các website đều cĩ cứu này. cấu trúc tương đối giống nhau với giao diện Bên cạnh đĩ, các website hỗ trợ tra từ hiện thân thiện, dễ sử dụng. Các hệ thống website tại chỉ dừng lại ở mức độ giải thích nghĩa của này hỗ trợ tra cứu trên nhiều bộ từ điển như: từ hay định nghĩa từ mà chưa quan tâm đến Anh - Việt, Việt - Anh, Anh - Anh và một số ngữ cảnh của từ chuyên ngành giúp hiểu rõ ngơn ngữ khác như: Trung Quốc, Nhật, Pháp cách sử dụng từ trong trường hợp cụ thể. Để Các hệ thống website từ điển hầu hết đều hỗ trợ hiểu rõ được từ chuyên ngành, chúng tơi đề dịch nghĩa của một từ và cả đoạn văn dài. xuất xây dựng một hệ thống dữ liệu ngữ cảnh Người dùng cĩ thể truy cập vào hệ thống, thực văn bản tương ứng với từng từ chuyên ngành. hiện tra từ và hệ thống sẽ cung cấp một danh Tuy nhiên, việc xây dựng hệ thống dữ liệu ngữ sách các nghĩa của từ, kể cả từ đồng nghĩa, từ cảnh của từ sẽ làm hạn chế tốc độ xử lý trên hệ liên quan, Trong số các website tra từ điển thống website tra từ điển vì phải tìm kiếm trên tác giả đã khảo sát trên, trong đĩ một số hệ thống dữ liệu ngữ cảnh để trả lời kết quả website cho phép tra cứu từ chuyên ngành như cho yêu cầu tìm kiếm từ người dùng. Vì thế, thefreedictionary.com, whatis.techtarget.com, ngồi những yếu tố ảnh hưởng đến kết quả tìm cambridge.org7 Các website này cĩ cơng cụ kiếm như phần cứng, băng thơng, thiết kế lọc theo từng lĩnh vực chuyên ngành cụ thể. yêu cầu đặt ra của một hệ thống tìm kiếm là tốc Trong đĩ, whatis.techtarget.com là một website độ xử lý và sự chính xác. Chúng tơi quan tâm hỗ trợ tra cứu và cho kết quả là định nghĩa các đến việc xử lý bên trong hệ thống để cĩ kết quả từ liên quan đến kỹ thuật và cơng nghệ; chính xác hơn. Để xử lý trên bộ ngữ liệu tiếng tudienthuoc.net8 và ykhoanet.com là các Việt (gồm từ chuyên ngành và ngữ cảnh của website từ điển chuyên ngành về thuốc, y khoa; từ) và quá trình tìm kiếm, chúng tơi phải tìm ra latin-phrases.co.uk/9 là từ điển về câu thành sự liên kết giữa các từ dựa trên các ngữ cảnh ngữ; fetp, tratu.soha là các website hỗ trợ tra từ khác nhau. Vì thế, giải thuật tìm kiếm là một chuyên ngành về kinh tế; trong những yếu tố quan trọng để đáp ứng yêu www.lawyerintl.com/law-dictionary10 chuyên cầu về tốc độ trong tra cứu từ. Trong nghiên về lĩnh vực luật học; và một số website như cứu này, dựa trên cơ chế tìm kiếm từ cĩ ngữ tratu.soha, Vdict, hỗ trợ tra từ thuộc nhiều cảnh hay nĩi cách khác là tìm kiếm từ trong lĩnh vực như tin học, kinh tế, luật, Tuy văn bản, chúng tơi lựa chọn bài tốn so sánh mẫu để giải quyết yêu cầu tìm kiếm đặt ra. Các 1 giải thuật tìm kiếm như KMP [5], Nạve [7], 2 Rubin – Karp [12] được chúng tơi khảo sát và 3 so sánh để tìm ra giải thuật phù hợp nhất trong =0 4 việc giải quyết yêu cầu. Chi tiết của việc khảo 5 sát và so sánh các thuật giải sẽ được trình bày 6 7 trong phần 2. 8 9 www.lawyerintl.com/law-dictionary 10 Trang 83
3. Science & Technology Development, Vol 18, No Q3 - 2015 Mục tiêu tiếp theo trong hệ thống tìm kiếm giải thuật so sánh chuỗi cho bài tốn của hệ từ điển chuyên ngành của chúng tơi là hỗ trợ thống từ điển chuyên ngành cĩ ngữ cảnh. chức năng tìm các từ chuyên ngành cĩ liên Bài tốn đặt ra, với một bộ dữ liệu từ điển quan. Để đạt được mục tiêu này, ngồi phương cĩ số lượng từ khĩa lớn, kèm theo đĩ là ngữ pháp sử dụng giải thuật, cĩ thể sử dụng câu cảnh trong từng trường hợp sử dụng từ, làm sao truy vấn thơng thường như SQL. Tuy nhiên để xác định mối liên hệ giữa các từ với nhau? việc phải so sánh từ chuyên ngành với số lượng Ngồi ra, việc tra từ cĩ ngữ cảnh địi hỏi ngữ cảnh lớn sẽ dẫn đến tốc độ xử lý chậm phương pháp tra từ phải làm việc trên một trong quá trình tìm kiếm [5][11][15]. Việc trả lượng dữ liệu lớn là văn bản (ngữ cảnh). Vậy về các dữ liệu khơng cần thiết (nếu khơng tìm làm sao để cĩ thể tra từ nhanh và trả về nghĩa thấy từ khĩa trong ngữ cảnh) cũng là một và ngữ cảnh của từ tìm kiếm chính xác? Để giải nguyên nhân khiến những câu truy vấn chậm quyết các vấn đề trên, trong phần này chúng tơi [5]. Chính vì vậy, trước khi đưa dữ liệu vào tập trung khảo sát các phương pháp, giải thuật quá trình tìm kiếm, chúng tơi phải thực hiện so khớp mẫu với ba giải thuật để từ đĩ chọn ra trước việc lọc những từ trong stopwords11 để một phương pháp hỗ trợ tốt cho việc xây dựng cải thiện tốc độ tìm kiếm. Phần 2 của bài báo sẽ hệ thống từ điển chuyên ngành cĩ ngữ cảnh. trình bày về các nghiên cứu liên quan. Trong Cụ thể, chúng tơi đã khảo sát các giải thuật phần 2, các giải thuật sẽ được so sánh và giải Naive [7], giải thuật Rabin - Karp [3], [12] và thuật phù hợp sẽ được chọn. Trong phần 3, giải thuật Knuth – Morris - Pratt (KMP)[5] dựa chúng tơi đề xuất mơ hình và phương pháp tra trên một mơ tả bài tốn sau: từ cĩ ngữ cảnh. Phần 4 sẽ trình bày việc thử nghiệm và thảo luận kết quả. Cuối cùng là kết “Cho mẫu P cĩ độ dài M và văn bản S cĩ luận và hướng phát triển nghiên cứu. độ dài N trên cùng bảng chữ A. Tìm một (hoặc tất cả) các lần xuất hiện của mẫu P trong S”. 2. CÁC NGHIÊN CỨU LIÊN QUAN Với việc xuất hiện một bài tốn so sánh mẫu Trong phần này, chúng tơi tập trung khảo như trên, giải thuật nào là phù hợp để giải bài sát các kỹ thuật và phương pháp liên quan đến tốn với thời gian tìm kiếm cĩ giới hạn? tìm kiếm và so sánh mẫu từ trong văn bản tiếng Trong bài tốn trên, giả sử ta cĩ tập văn bản Việt. Từ đĩ, chúng tơi lựa chọn kỹ thuật phù hợp áp dụng và mơ hình đề suất cho hệ thống S’= [S, S1, S2 Sn], lúc này bài tốn sẽ được thực hiện đối với mỗi cặp [P,S] [P,S ] [P,S ] tra từ chuyên ngành cĩ ngữ cảnh. 1 2 Trong trường hợp độ dài N của văn bản Sx là Phương pháp so sánh chuỗi là phương pháp rất lớn và tập S’ cĩ n phần tử con (n rất lớn) thì tìm kiếm tất cả các lần xuất hiện của một chuỗi thời gian tìm kiếm sẽ rất tốn kém. Do đĩ, việc mẫu (pattern) trong một chuỗi khác [1], [2], tìm hiểu một giải thuật để giải quyết vấn đề là [8], [15], [17], [20]. Quá trình so sánh chuỗi là cần thiết. Dựa vào việc phân tích, thiết kế, xây hoạt động diễn ra rất thường xuyên trong các dựng bộ dữ liệu, chúng tơi cĩ một số nhận xét chương trình chỉnh sửa văn bản, các trình duyệt sau: web, các bộ máy tìm kiếm, và các hệ thống gợi ý trên các trang thương mại điện tử [9][16]. Độ dài N của văn bản Sx (phần tử của tập ngữ cảnh) là khơng quá lớn. Trong nghiên cứu này, chúng tơi khảo sát các Tập S’ gồm khoảng 1000 phần tử (và cĩ thể phát triển nhiều hơn). 11 Stopwords là những từ, cụm từ phổ biến hay nĩi chung chung khơng cĩ ý nghĩa trong kết quả tìm kiếm Trang 84
4. TẠP CHÍ PHÁT TRIỂN KH & CN, TẬP 18, SỐ Q3 - 2015 2.1. Giải thuật Naive Mặt khác, ta cĩ thể tính p và t0 theo 2 cơng Đây là giải thuật cơ bản và đơn giản nhất, thức: sử dụng nguyên lý vét cạn. Giải thuật Naive [7] p = P[m] * 100 + P[m-1]*101 + .+ (1) m-1 kiểm tra tất cả các khả năng của chuỗi mẫu P[1]*10 P[1 m] nằm trong chuỗi S[1 n] bằng cách t = T[1]*10m-1 +T[2]*10m- duyệt từ đầu tới cuối chuỗi S. 0 2+ .+T[m]*100 (2) Giải thuật 1. Naive Algorithm [7] Hai cơng thức trên cho cùng tiêu tốn thời NAIVE-STRING-MATCHER(S, P) gian là O(m). Sau khi tính t0 , việc tính 1. n = S.length các t1,t2, tn-m-1 trở nên đơn giản hơn và chỉ tiêu 2. m = P.length tốn O(1) cho mỗi ti. Ta tính các t1,t2, .tn-m-1 lần lượt theo cơng thức sau: 3. for s = 0 to n-m do m-1 4. j = 1 ti = 10*(ti-1 – 10 *T[i]) + T[i+m] (3) 5. while (j m) này cĩ nghĩa là tìm sự xuất hiện của p trong ti . 8. “Tìm thấy mẫu với độ dịch chuyển s” Vì vậy để tính được tất cả các giá trị p và ti, Nhận xét: Vịng lặp while bên trong chạy hay nĩi cách khác là tìm được chuỗi P trong T tối đa m lần, vịng lặp for bên ngồi chạy tối đa sẽ cĩ độ phức tạp là O(m) + O(n-m-1). Và điều n-m+1 lần. Do vậy, thời gian chạy của giải này cũng cho thấy giải thuật Rabin - Karp với thuật này là S(n) = O((n-m+1)*m) = O(n*m). thời gian tiêu tốn là O(m) cho tiền xử lí và O(n- Rõ ràng, giải thuật này khơng hiệu quả vì bỏ m-1) để so sánh chuỗi. qua mọi thơng tin hữu ích cĩ được trong quá Nhận xét: trình so sánh chuỗi tại từng giá trị của S. Quá trình tiền xử lý với giải thuật tiêu tốn 2.2. Giải thuật Rabin - Karp O(m) thời gian, với 1 vịng lặp là for i =1 to n. Giải thuật này do Rabin và Karp đề xuất Quá trình so sánh trong trường hợp tốt nhất trong [3][12]. Giải thuật với độ phức tạp O(m) là p’! = t’ với mọi i thì việc so sánh với thời để tiền xử lý các dữ liệu nhập, và thời gian i gian tiêu tốn là O(n-m). Tuy nhiên, trong chạy tệ nhất là O((n-m+1)m). Mặc dù vậy, trường hợp xấu nhất khi p’ = t’ thì việc so sánh trung bình các trường hợp đều tiêu tốn thời I phải thực hiện thêm lệnh kiểm tra P[1 m] và gian ít hơn. T[i+1,i+m], điều này cĩ thời gian tiêu tốn là Ta nhận thấy rằng mỗi chuỗi S cĩ thể số O(m). Như vậy, độ phức tạp của Rabin - Karp hĩa thành một số. Ví dụ S = {0,1,2 ,9}, S = là O((n-m+1)*m). “1234” thì ta sử dụng hàm digit(S) = 1,234. Giải thuật Knutt – Morris - Pratt được trình Gọi p là giá trị số hĩa của P, hay nĩi cách khác bày trong các phần sau tỏ ra tốt hơn nhiều so p là giá trị thập phân tương ứng của P. Gọi ts là với Nạve và Rabin - Karp Algorithm vì tận giá trị thập phân tương ứng của T[s+1, ,s+m] dụng các thơng tin hữu ích khi tìm kiếm. , s<n-m+1. Ta nhận thấy rằng tS =p khi và chỉ khi P = T[s+1, ,s+m]. Trang 85
5. Science & Technology Development, Vol 18, No Q3 - 2015 2.3. Giải thuật Knuth – Morris - Pratt 7. do q ← π[q] //Ký tự khơng trùng nhau (KMP) 8. if P[q + 1] = S [i ] Giải thuật KMP [5] với độ phức tạp tuyến 9. then q ← q + 1 //Ký tự trùng nhau tính này được Knuth, Morris và Pratt phát hiện 10. if q = m //Nếu đã kiểm tra tồn bộ chuỗi P ra nhờ việc phân tích chặt chẽ giải thuật 11. then print “Mẫu xuất hiện với độ dịch Naive[8]. Giả sử ta muốn tìm chuỗi mẫu chuyển” i – m P[1 m] trong S[1 n], đến một lúc nào đĩ thì ta 12. q ← π[q] //Tìm ký tự trùng nhau tiếp theo sẽ cĩ P[i] != S[j]. Giải thuật 3. Compute – Prefix - Function[5] Xét về độ phức tạp và chạy thực tế với 4 Compute - Prefix - Function(P) mẫu thử ngẫu nhiên cho 3 giải thuật (Nạve, 1. m ← length[P] Rabin - Karp và KMP), nhận thấy KMP cĩ 2. π[1] ← 0 những ưu điểm vượt trội so với 2 giải thuật cịn 3. k ← 0 lại là Naive và Rabin - Karp, kết quả thử 4. for q ← 2 to m do nghiệm thực tế cũng nĩi lên rằng, dù kích cỡ 5. while k > 0 and P[k + 1] ≠ P[q] Text (T) và từ khĩa (Paragraph - P) cĩ khác 6. do k ← π[k] nhau giữa các mẫu thử thì giải thuật KMP luơn 7. if P[k + 1] = P[q] đạt hiệu suất trung bình tốt nhất. 8. then k ← k + 1 Trong quá trình tiền xử lý chuỗi P, mỗi p[i], 9. π[q] ← k 1 ≤ i ≤ m, lưu lại độ dài của biên rộng nhất của 10. return π P[1 i]. Vì chuỗi rỗng khơng cĩ biên nên ta gán: Nhận xét: Độ phức tạp của giải thuật tiền xử p[0] = -1. Giả sử các giá trị p[0], , p[i] đã lý Compute – Prefix - Function là O(m) bởi vì biết, giá trị p[i+1] sẽ được tính bằng cách kiểm vịng lặp while bên trong sẽ khơng bao giờ thực tra xem biên của chuỗi P[1 i] cĩ thể được mở hiện quá m lần. Tương tự, giải thuật tìm rộng bằng ký tự P[i+1] hay khơng. Ta sử dụng kiếm KMP - Matcher cũng chỉ cĩ độ phức tạp biến k lưu trữ các p[i]. Nếu P[i+1] = P[k] thì là O(n). khi đĩ ta gán p[i+1] = k+1, ngược lại ta xét k = p[k] và quay lại các bước so sánh P[i+1] với 2.4. Đánh giá các giải thuật P[k] ở trên. Sau khi phân tích các giải thuật trên, cần Giải thuật so khớp chuỗi KMP - đánh giá và lựa chọn giải thuật phù hợp với yêu Matcher được trình bày trong đoạn mã giả sau cầu đặt ra một cách tổng quát như sau: đây. Giải thuật này gọi tới giải thuật tiền xử Bảng 1. Kết quả đánh giá các giải thuật lý Compute - Prefix - Function để tính p. Thực Tên giải Giải thuật 2. KMP - Matcher [5] hiện Độ phức tạp thuật tiền xử KMP - Matcher(S, P) lý 1. n ← length[S ] Nạve No O((n-m+1)*m) = O(n*m) 2. m ← length[P] Rubin-Karp Yes O((n-m+1)*m) 3. π ← Compute – Prefix - Function(P) 4. q ← 0 //Số lượng ký tự trùng nhau KMP Yes O(n) 5. for i ← 1 to n //Duyệt chuỗi S từ trái qua phải 6. do while q > 0 and P[q + 1] ≠ S [i ] Trang 86
6. TẠP CHÍ PHÁT TRIỂN KH & CN, TẬP 18, SỐ Q3 - 2015 Xét về độ phức tạp nhận thấy rằng, KMP cĩ trên là dựa vào ngữ cảnh từ, từ đĩ người dùng độ phúc tạp thấp hơn với 2 giải thuật cịn lại. cĩ thể hiểu hơn về cách sử dụng từ khĩa cần Thơng qua những phân tích và so sánh trên, tìm trong từng trường hợp, và gia đình từ (word trong nghiên cứu này chúng tơi chọn giải thuật family) của từ khĩa đĩ. KMP để làm cơ sở giải quyết bài tốn đã đặt ra Một ý nghĩa quan trọng nữa trong mơ hình cho việc tìm kiếm từ điển và ngữ cảnh từ. đề xuất (xem giải thuật 4) là khai thác ngữ cảnh 3. ĐỀ XUẤT MƠ HÌNH KHAI THÁC NGỮ để tìm ra từ gợi ý giúp cho người tra từ mở CẢNH VÀ TÌM TỪ GỢI Ý rộng thêm kiến thức liên quan đến từ đã tra Trong phần này, chúng tơi trình bày bài cứu. tốn về khai thác ngữ cảnh của từ điển. Chúng Giải thuật 4. Khai thác ngữ cảnh từ điển ta xét bài tốn cụ thể sau, giả sử ta cĩ từ khĩa chuyên ngành và tìm từ gợi ý. cần tìm “tiếp thị”, và cĩ 2 ngữ cảnh cĩ liên Đầu vào: từ khĩa và ngữ cảnh của từ. quan đến từ “tiếp thị” như sau : Ngữ cảnh (1) cĩ chứa cụm từ “tiếp thị trực Đầu ra: thơng tin liên quan từ khố, tập những từ khĩa được gợi ý cĩ chứa từ khĩa đầu vào và tiếp”: “Thị trường sản phẩm và dịch vụ Dell là ngữ cảnh từ các doanh nghiệp từ nhỏ đến trung bình và người tiêu dùng chính qua các kênh quảng cáo Xử lý: Bài tốn tra từ điển cĩ ngữ cảnh và tìm trên truyền hình và Internet, qua các phương từ gợi ý được chuyển về một dạng tốn kinh tiện truyền thơng in ấn, và bằng cách gởi các ấn điển trong giải thuật so sánh mẫu. phẩm tiếp thị trực tiếp, như các mẩu quảng cáo, Ý tưởng, nếu người dùng nhập từ khĩa gồm hai catalog, và các bản tin khách hàng. Tại các địa chữ hoặc nhiều hơn hai chữ, quy trình xử lý điểm nhất định, chúng cũng được đưa vào cửa như sau: hàng Dell hay những ki-ốt nằm trong trung tâm mua sắm. Điều đĩ cho phép khách hàng cĩ thể Bước 1: Lọc những từ khơng cĩ ý nghĩa, xem sản phẩm và mua hàng trực tuyến với sự sau đĩ tìm kiếm theo những từ cịn lại. trợ giúp của một chuyên gia Dell”. Việc này sẽ xảy ra trường hợp cĩ thể cĩ nhiều từ cĩ ý nghĩa. Ngữ cảnh (2) cĩ chứa cụm từ “tiếp thị tương tác”: “Một tính năng quan trọng của tính Bước 2: Thực hiện tách từ tìm kiếm tương tác truyền thơng tiếp thị là chúng cĩ thể Bước 2.1: Nếu trong một ngữ cảnh cĩ được thiết kế cho cá nhân, khơng giống như tất cả những từ được tách sẽ trả về kết các phương tiện truyền thơng truyền thống, nơi quả từ gợi ý hay gọi là từ tương cùng một thơng điệp cĩ xu hướng được phát đương. Qua bước 2.3. sĩng đến tất cả mọi người. Quá trình thiết kế riêng cũng được gọi là cá nhân hĩa và là một Bước 2.2: Nếu những từ được tách khía cạnh quan trọng của việc đạt được quản lý khơng xuất hiện trong ngữ cảnh, thì quan hệ khách hàng trực tuyến”. kết quả sẽ khơng trả về từ gợi ý hay từ tương đương. Quan bước 3. Hai nội dung ngữ cảnh trên liên quan đến từ khĩa “tiếp thị”, tuy nhiên lại theo từng ngữ Bước 2.3: Bổ sung danh sách từ gợi ý cảnh và ý nghĩa khác nhau thuộc 2 lĩnh vực: cĩ liên quan và hiển thị ngữ cảnh của “tiếp thị trực tiếp”, và “tiếp thị tương tác”. Vậy, từ. cơ sở chúng tơi đưa ra cách giải quyết bài tốn Bước 3: Kết thúc tìm kiếm từ Trang 87
7. Science & Technology Development, Vol 18, No Q3 - 2015 Hình 2 trình bày quy trình khai thác ngữ chuyên ngành cần tìm, (3) gồm các từ chuyên cảnh và tìm kiếm từ gợi ý, gồm bốn thành ngành cĩ chứa từ khố cần tìm và (4) trình bày phần: (1) trình bày về từ khố cần tìm, (2) trình kết quả tìm kiếm các từ liên quan đến từ khố bày về nội dung ngữ cảnh cĩ liên quan đến từ và cĩ chứa từ khố cần tìm. (1) (2) (3) (4) Ngữ cảnh từ khĩa Từ khĩa Kết quả Ngữ cảnh 1 cĩ chứa từ khĩa Từ khĩa 1 cần tìm Từ khĩa cần Ngữ cảnh 1 khơng chứa từ tìm khĩa cần tìm Từ khĩa 1 Từ khĩa 2 Ngữ cảnh 2 cĩ chứa từ khĩa Từ khĩa 2 cần tìm Ngữ cảnh 2 khơng chứa từ khĩa cần tìm Hình 2. Quy trình khai thác ngữ cảnh và tìm kiếm từ gợi ý Trên thực tế bài tốn so sánh mẫu nhằm xác định vị trí của một “từ” hoặc “cụm từ” trong một đoạn văn bản cho trước. Với cách xác định 4. THỬ NGHIỆM VÀ THẢO LUẬN này, chúng tơi sẽ sử dụng giải thuật để xác định KẾT QUẢ ngữ cảnh nào cĩ chứa từ khĩa, từ đĩ đưa ra từ gợi ý. Bên cạnh đĩ, dạng phổ biến nhất của bài 4.1. Dữ liệu từ điển và ngữ cảnh từ tốn so khớp chuỗi như sau: cho trước nguồn Mục tiêu đặt ra là xây dựng bộ từ điển tìm kiếm là một tập D các văn bản. Cho một q - chuyên ngành cĩ ngữ cảnh trong lĩnh vực một từ, hoặc một cụm từ, tìm tất cả các văn bản HTTTQL và TMĐT. Dữ liệu được xây dựng từ thuộc D mà cĩ chứa q. Để thực hiện bài tốn, các giáo trình, sách và bài viết chính thức của hệ thống phải kiểm tra văn bản xem q cĩ là một từng chuyên ngành. Trong quá trình xây dựng cụm từ thuộc các văn bản thuộc tập D hay bộ dữ liệu phục vụ cho việc tìm kiếm từ điển, khơng và đưa ra các văn bản gợi ý. chúng tơi sử dụng các “bản thuật ngữ” của các sách chuyên ngành HTTTQL và TMĐT [6], Trong phần tiếp theo, chúng tơi áp dụng mơ hình, ý tưởng đề xuất trên và sử dụng các kỹ [10], [13], [18]. Tất cả sách trên được viết bằng tiếng Anh. Với mỗi từ tiếng Anh, “bản thuật thuật để xây dựng hệ thống thơng tin website ngữ” cũng cung cấp các giải thích ý nghĩa của hỗ trợ tra cứu từ điển chuyên ngành cĩ ngữ cảnh. từ bằng tiếng Anh. Tuy nhiên, để phục vụ nhu cầu tra từ theo nghĩa tiếng Việt, cần tiến hành dịch thuật những giải thích bằng tiếng Anh nêu trên sang tiếng Việt. Quá trình tìm hiểu ngữ nghĩa của từ, cụm từ và thuật ngữ chuyên ngành khơng chỉ dựa trên cơ sở ngữ nghĩa của Trang 88
8. TẠP CHÍ PHÁT TRIỂN KH & CN, TẬP 18, SỐ Q3 - 2015 “bản thuật ngữ” cung cấp mà cịn địi hỏi phải cĩ những hiểu biết nhất định về chuyên ngành ấy. Do đĩ, trong quá trình dịch thuật, bên cạnh tìm hiểu thơng tin liên quan đến từ, cụm từ và thuật ngữ trong các giáo trình liên quan và trên Internet, chúng tơi cũng nhận được sự hỗ trợ rất lớn từ các chuyên gia về ngơn ngữ và các chuyên gia trong lĩnh vực chuyên ngành. Hiện tại, bộ dữ liệu được xây dựng với hơn 1500 từ cùng với nghĩa của từ và 1500 ngữ cảnh (bằng văn bản) tương ứng từng từ. Mỗi từ sẽ được Hình 3. Giao diện hệ thống tra từ điển cung cấp các thơng tin cần thiết cho nhu cầu tra chuyên ngành từ cĩ ngữ cảnh như từ tiếng Anh, từ tiếng Việt, giải thích nghĩa bằng tiếng Anh, giải thích Bước 3: Người dùng nhấn nút “Search” để nghĩa bằng tiếng Việt, từ viết tắt và ngữ cảnh tra cứu từ (hình 3). Hệ thống xử lý truy vấn từ của từng từ. Hệ thống từ được chúng tơi tổ CSDL và hiển thị kết quả tìm kiếm trên giao chức và quản lý trên Hệ quản trị CSDL SQL diện chi tiết. Trong quá trình xử lý truy vấn kết Server 2012. quả, hệ thống ứng dụng giải thuật tìm kiếm KMP (hình 4). Trong phần tiếp theo, chúng tơi sẽ trình bày kết quả xây dựng hệ thống thơng tin website tìm kiếm từ điển chuyên ngành cĩ ngữ cảnh. 4.2. Hệ thống website từ điển chuyên ngành Trong phần này, chúng tơi trình bày kết quả xây dựng hệ thống website theo từng bước thực hiện tra từ trên hệ thống. Bước 1: Truy cập vào hệ thống website12 để tra từ điển chuyên ngành Bước 2: Người dùng nhập từ vào khung tìm kiếm (xem hình 3). Hệ thống xử lý để đưa ra các dự đốn từ khi người dùng chưa nhập hồn Hình 4. Giao diện chi tiết trình bày kết chỉnh một từ nhằm giúp cho người dùng chọn quả tra từ điển chuyên ngành nhanh từ cần tra. Bước 4: Người dùng xem kết quả trả về trên hình 4. Kết quả tìm kiếm thể hiện trên hình 4 bao gồm 2 nội dung: (1) nghĩa của từ được tra, (2) ngữ cảnh của từ được tra. Ngữ cảnh này được thể hiện ở cả hai ngơn ngữ tiếng Việt và 12 Website này chúng tơi đang trong quá trình hồn thiện về tiếng Anh. Phần ngữ cảnh cũng giúp cho việc hạ tầng kỹ thuật bảo mật cũng như kiểm định cơ sở dữ liệu từ điển. Bên cạnh đĩ, chúng tơi sẽ phát triển tiếp những phân tích để tìm ra những từ điển bổ sung vào ứng dụng tiện ích liên quan được tích hợp trên website và danh sách từ gợp ý cĩ liên quan đến từ được ra. tiến hành đưa website cơng bố lên Internet. Trang 89
9. Science & Technology Development, Vol 18, No Q3 - 2015 Ngồi ra phần bên phải của hình 4, thể hiện chuyên ngành, chỉnh sửa nội dung liên quan danh sách các từ thường được người dùng tìm đến từ chuyên ngành. kiếm “Most popular”, người dùng cĩ thể chọn 4.3. Thảo luận kết quả và xem chi tiết ngữ cảnh của từ đĩ trong danh sách đĩ. Hệ thống xử lý và trả kết quả chi tiết Ngồi những yếu tố ảnh hưởng đến kết quả tìm kiếm như phần cứng, băng thơng, thiết tra cứu liên quan đến từ, đồng thời gợi ý tiếp kế, yêu cầu đặt ra của một cơng cụ tìm kiếm các từ liên quan được trình bày trong mơ hình đề xuất trong phần 3 để thực hiện khai thác ngữ là tốc độ xử lý và sự chính xác. Vì vậy, việc xử lý bên trong để cĩ thể cho ra kết quả tốt nhất là cảnh của từ và đưa ra các từ gợi ý liên quan rất quan trọng. Để xử lý một tập ngữ liệu lớn đến từ cần tìm nhằm giúp người dùng hiểu rõ và rộng hơn ý nghĩa của từ đã tra. Trên hình 4 và tìm sự liên kết giữa các từ dựa trên cơ sở ngữ cảnh, giải thuật được tính đến như một giải cũng thể hiện chức năng cho người dùng thảo pháp đạt hiệu quả cao. Với cơ sở tìm kiếm dựa luận. Mục đích chúng tơi xây dựng chức năng này nhằm giúp người dùng cĩ thể trao đổi về từ trên ngữ cảnh, bài tốn so sánh mẫu được chọn để giải quyết yêu cầu đặt ra, giải thuật tìm kiếm điển, về các từ mới hoặc người dùng cĩ thể như KMP được chúng tơi áp dụng vì những ưu đĩng gĩp ý kiến cho nội dung liên quan đến từ điển và hệ thống tra từ. điểm và sự linh hoạt trong tìm kiếm mà giải thuật mang lại. Dù chưa phải là lựa chọn tối ưu Bên cạnh hỗ trợ tra từ điển chuyên ngành nhất nhưng việc áp dụng giải thuật KMP đã và tìm kiếm từ gợi ý được trình bày trong hình mang lại hiệu quả nhất định trong nghiên cứu. 3 và hình 4. Trên hệ thống website, chúng tơi Bằng việc kết hợp với cơng cụ tìm kiếm tối ưu cịn xây dựng thêm các chức năng tiện ích khác được trang bị từ Microsoft SQL Server là SQL nhằm giúp cho người dùng cĩ thể tìm hiểu Full Text Search hay cịn được gọi là FTS thêm những vấn đề, thơng tin liên quan đến [4][5], mỗi kỹ thuật được áp dụng nhằm tùy ngành nghề như trang tin tức, thảo luận (hình biến kết quả tìm kiếm, nhưng vẫn đáp ứng 5). được những yêu cầu đặt ra trong tìm kiếm chính xác từ theo ngữ cảnh. Việc đánh giá tính chính xác kết quả thực hiện của mơ hình và hệ thống đề xuất, chúng tơi thực hiện theo phương pháp kiểm tra trực tiếp để đối chiếu từng dữ liệu kết quả với dữ liệu được lưu trữ trong hệ thống từ điển. Bên cạnh đĩ, chúng tơi đã kiểm tra kết quả bằng cách thực hiện các kỹ thuật truy vấn trực tiếp trên dữ liệu để so sánh với kết quả tìm kiếm trên hệ thống website. Kết quả cho độ chính xác 100% giữa kết quả thực hiện mơ hình đề xuất trên hệ thống website so sánh với kiểm tra Hình 5. Giao diện trang tin tức về trực tiếp dữ liệu. chuyên ngành HTTTQL và TMĐT Tĩm lại, dựa trên mơ hình và phương pháp Ngồi ra, một tính năng quan trọng khác đề xuất, việc sử dụng SQL Full Text Search được xây dựng trên hệ thống website là chức [11] để tìm kiếm từ khĩa ban đầu, đồng thời năng giúp người dùng tham gia bổ sung mới từ Trang 90
10. TẠP CHÍ PHÁT TRIỂN KH & CN, TẬP 18, SỐ Q3 - 2015 kết hợp giải thuật KMP để đưa ra từ gợi ý dựa trả về kết quả mong muốn nhưng khả năng truy trên cơ sở ngữ cảnh là ý tưởng chính trong việc xuất dữ liệu tốt hơn đặc biệt là khi dữ liệu đã xử lý tìm kiếm từ hoặc cụm từ trong hệ thống thật sự lớn, (3) phân tích và đánh giá các giải dữ liệu từ điển chuyên ngàh Hệ thống thơng tin thuật để lựa chọn giải thuật KMP áp dụng trong quản lý và Thương mại điện tử và đã đạt hiệu phần xử lý trên hệ thống tìm kiếm, (4) xây quả tốt về tốc độ xử lý và tính chính xác dữ dựng và triển khai hệ thống website tra từ liệu. chuyên ngành cĩ ngữ cảnh thuộc lĩnh vực Hệ thống thơng tin quản lý và Thương mại điện tử. Được xây dựng nhằm hỗ trợ tra cứu thuật Hiện tại, hệ thống website đang trong quá trình ngữ thuộc chuyên ngành HTTTQL và TMĐT, hồn thiện về hạ tầng kỹ thuật bảo mật cũng hệ thống CSDL dùng cho hệ thống website tra như kiểm định cơ sở dữ liệu từ điển. Chúng tơi cứu từ điển chuyên ngành đã tương đối đáp sẽ tiến hành sớm đưa website lên Internet để ứng được các yêu cầu tra từ theo chuyên ngành cơng bố rộng rãi đến người dùng. HTTTQL và TMĐT, bao gồm tra từ theo các loại từ điển Anh - Việt, Việt - Anh, hoặc Anh - Trong nghiên cứu tiếp theo, chúng tơi sẽ Anh, hoặc tất cả, tra từ viết tắt và hỗ trợ lưu trữ tiếp tục cải thiện hệ thống tra từ điển chuyên hình ảnh minh họa trực quan cho từ. ngành để mở rộng lĩnh vực tra cứu và tốc độ xử lý bằng những giải thuật cải tiến cĩ kết quả tìm 5. KẾT LUẬN VÀ HƯỚNG PHÁT kiếm nhanh hơn để hướng đến mở rộng cơ sở TRIỂN dữ liệu từ điển và ngữ cảnh của từ. Chúng tơi Trong bài báo này, chúng tơi tập trung cũng sẽ bổ sung từ và ngữ cảnh của từ, đồng nghiên cứu và giải quyết bốn vấn đề chính thời phát triển việc khai thác ngữ cảnh bằng nhằm đạt được mục tiêu đặt ra là xây dựng hệ cách thu thập dữ liệu từ Internet để cĩ kết quả thống tra từ chuyên ngành cĩ ngữ cảnh trong đa dạng hơn trong nhiều lĩnh vực ứng với từ lĩnh vực Thương mại điện tử và Hệ thống chuyên ngành cụ thể. Bên cạnh đĩ, việc phát thơng tin quản lý, và đây cũng là 4 đĩng gĩp triển hệ thống website giúp truy cập ứng dụng của chúng tơi trong nghiên cứu, bao gồm: (1) trên điện thoại thơng minh nhằm tạo điều kiện xây dựng được trên 1500 từ điển chuyên ngành dễ dàng nhất cho người dùng khi cần tra cứu cùng với hệ thống dữ liệu ngữ cảnh của từng cũng sẽ được chúng tơi quan tâm. từ, (2) thiết kế index cho các cột thường xuyên được truy vấn, xử lý các câu truy vấn sao cho TÀI LIỆU THAM KHẢO [1]. Akinul Islam Jony, Analysis of Multiple String Pattern Matching Algorithms, International Journal of Advanced Computer Science and Information Technology (IJACSIT), Vol. 3, No. 4, 2014, pp. 344-353 (2014). [2]. Akhtar Rasool Amrita Tiwari, et al, String Matching Methodologies:A Comparative Analysis, International Journal of Computer Science and Information Technologies, Vol. 3 (2) ,3394-3397 (2012). [3]. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford [1990]. The Rabin- Karp algorithm. Introduction to Algorithms (2nd ed.). Cambridge, Massachusetts: MIT Press. pp. 911-916. ISBN 978-0-262-03293-3 (2001). [4]. D.E. KNUTH, J.H. MORRIS, V.R. PRATT, Fast Pattern Matching in Strings. SIAM Journal of Computing 6, 2, 323-350 (1977). Trang 91
11. Science & Technology Development, Vol 18, No Q3 - 2015 [5]. Dana Shapira, et al, Adapting the Knuth–Morris–Pratt algorithm for pattern matching in Huffman encoded texts, Information Processing and Management 42, 429-439 (2006). [6]. Dave Chaffey, E-book: E–Business and E–Commerce Management, Prentice Hall, ISBN: 978- 0273752011 (2010). [7]. Domingos, Pedro; Pazzani, Michael, On the optimality of the simple Bayesian classifier under zero-one loss. Machine Learning 29: 103-137. 7 (1997). [8]. D. Sunday, Very Fast Substring Search Algorithm, Comm. ACM, vol 33, issue 8, pp. 132-142 (1990). [9]. Ellard, Daniel J. String Searching. S-Q Course Book. [Online] [Cited: 06 10, 2011.] (2011). [10]. Jane P.Laudon & Kenneth C.Laudon, E-book: Essentials of Management Information Systems, PEARSON, ISBN: 978-0136025818 (2010). [11]. Full-Text Search (SQL Server) [12]. Karp, Richard M.; Rabin, Michael O. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development 31 (2), pp. 249-260 (March 1987). [13]. Laudon, E-book: E–Commerce, Pearson Education, ISBN-13: 978-0135090787 (2010). [14]. Michael Coles, Hilary Cotter, Pro Full-Text Search in SQL Server 2008, Spinger-Verlag New York, Inc (2009). [15]. Muhammad, Rashid Bin. String Matching Agorithm. Design and Analysis of Computer Algorithms. [Online] Kent State University. [Cited: 06 20, 2011.] [16]. R. Boyer, J. Moore, A fast string searching algorithm, Comm. ACM vol 20, pp. 762-772 (1977). [17]. Siam J. Comput, et al, Fast pattern matching in strings, donald e. Knuth, Vol. 6, No. 2, (June 1977). [18]. Ralph Stair & George Reynolds, E-book: Principle of Information Systems, Cengage Learning, ISBN: 0324665288 (2009). [19]. Vidya SaiKrishna, et al, String Matching and its Applications in Diversified Fields, IJCSI International Journal of Computer Science Issues, Vol. 9, Issue 1, No 1, January 2012 (2012). [20]. Yanbing Liu et al, A factor-searching-based multiple string matching algorithm for intrusion detection, Communications (ICC), 2014 IEEE International Conference, pp. 653-658 (2014). Trang 92