[SQL] Tạo bảng lịch ảo bằng truy vấn (phần 1)

Lưu ý:

• Người đọc cần có kiến thức cơ bản về CSDL quan hệ và ngôn ngữ truy vấn SQL.
• Các truy vấn ví dụ sử dụng trong bài được viết bằng cú pháp T-SQL của SQL Server.
• Câu truy vấn tốt hơn được cung cấp tại phần 2.

Vấn đề

Khi phát triển hệ thống nghiệp vụ cho công ty, tôi hay được yêu cầu lập các bản báo cáo dựa trên trục ngày tháng, ví dụ như báo cáo số đơn hàng mỗi ngày trong tháng. Trong một bài viết trước, tôi đã giới thiệu giải pháp để tạo một danh sách ngày tháng dưới dạng bản ghi để giải quyết vấn đề đó.

Tuy nhiên nhiều khi người dùng yêu cầu thêm chức năng như hiển thị xem mỗi ngày trên báo cáo có phải ngày nghỉ hay ko, và nếu ko thì là ngày làm việc thứ mấy trong tháng. Nếu chỉ là nghỉ thứ Bảy Chủ Nhật thì quá đơn giản, nhưng người dùng muốn hiển thị cả các ngày nghỉ lễ Tết, thậm chí là cả các ngày nghỉ do công ty tự quy định, và muốn có thể thiết lập thêm ngày nghỉ một cách dễ dàng. Nói tóm lại tôi cần phải làm một bộ lịch dưới dạng bản ghi dành riêng cho công ty.

Giải pháp sơ cấp

Cũng như vấn đề ở bài viết trước, giải pháp đơn giản nhất là lưu các dữ liệu cần thiết thành bảng trong CSDL. Nếu tôi đã có sẵn một bảng tất cả các ngày tháng, thì tôi sẽ thêm một cột bit/boolean chứa thông tin ngày đó có phải ngày nghỉ hay ko.

Ngày	Nghỉ
2015/1/1	1
2015/1/2	0
...	...
2015/4/24	0
2015/4/25	1
2015/4/26	1
...	...

Khi người dùng muốn thêm bớt ngày nghỉ tôi sẽ để họ sửa cột đó cho từng ngày nghỉ mà họ muốn thiết lập. Đối với những ngày nghỉ định kỳ như thứ Bảy Chủ Nhật và lễ Tết, tôi có thể chạy một vài câu truy vấn UPDATE để thiết lập sẵn thông tin cho tất cả các ngày nghỉ có trong bảng.

UPDATE [Bảng ngày] SET [Nghỉ] = 1
WHERE DATEPART(weekday, [Ngày]) IN (1, 7) OR MONTH([Ngày]) = 1 AND DAY([Ngày]) = 1)

Giải pháp này đơn giản và cũng khá hiệu quả, cho phép tôi có thể chuyển giao việc bảo trì lịch nghỉ cho người dùng ko biết gì về CNTT. Tuy nhiên nó có một số vấn đề:

• Độ tin cậy thấp: Khỏi phải giải thích.
• Ko tận dụng được bảng ảo: Do giải pháp này gắn liền với việc lưu trữ một bảng thực chứa tất cả các ngày tháng, nên nó ko thể tận dụng được các giải pháp tạo bảng ngày tháng ảo dựa trên bảng số nguyên (ảo nốt) như ở bài viết trước.
• Hiệu suất thấp: Hiệu suất ở đây là hiệu suất sử dụng dữ liệu (lượng thông tin trên lượng dữ liệu). Điều này là do có rất nhiều bản ghi chứa ngày làm việc trộn lẫn giữa các bản ghi chứa ngày nghỉ, trong khi thông tin tôi cần là ngày nào là ngày nghỉ.

Giải pháp trung cấp

Xuất phát từ mục đích ban đầu là tôi chỉ muốn biết một ngày nào đó có phải ngày nghỉ hay ko, tôi cũng có thể tạo một bảng riêng chỉ chứa các ngày nghỉ. Khi người dùng muốn thêm bớt ngày nghỉ tôi sẽ để họ thêm một bản ghi mới vào bảng hoặc xóa một bản ghi cũ đi.

Ngày nghỉ
2015/1/1
...
2015/4/25
2015/4/26
...

Các ngày nghỉ định kỳ có thể được tạo sẵn bởi một vài câu truy vấn INSERT dựa trên dữ liệu gốc từ bảng ngày tháng hay bảng số nguyên có sẵn (tham khảo bài viết trước).

INSERT INTO [Bảng ngày nghỉ] ([Ngày], [Nghỉ]) VALUES (DATEADD(week, [Số] - 5000, '2015-04-25'), 1)
FROM [Bảng số] WHERE [Số] BETWEEN 0 AND 10000

INSERT INTO [Bảng ngày nghỉ] ([Ngày], [Nghỉ]) VALUES (DATEADD(year, [Số] - 100, '2015-01-01'), 1)
FROM [Bảng số] WHERE [Số] BETWEEN 0 AND 200

Câu truy vấn đầu tiên thêm vào bảng 10.001 ngày thứ Bảy từ 5000 tuần trước đến 5000 tuần sau ngày thứ Bảy chuẩn là 2015/4/25. Câu truy vấn tiếp theo thêm 201 ngày 1/1 của các năm từ 100 năm trước đến 100 năm sau năm chuẩn là 2015.

Khi đã có bảng ngày nghỉ, tôi có thể kết hợp nó với bảng ngày tháng để tạo ra bảng lịch nghỉ ảo giống như bảng thực ở giải pháp sơ cấp nói trên.

SELECT [Ngày], IIF([Ngày nghỉ] IS NULL, 0, 1) AS [Nghỉ] 
FROM [Bảng ngày] LEFT OUTER JOIN [Bảng ngày nghỉ] ON [Ngày] = [Ngày nghỉ]

Câu truy vấn trên liệt kê lại tất cả các ngày trong bảng ngày tháng sẵn có, và thiết lập đó là ngày nghỉ nếu tồn tại bản ghi chứa ngày đó trong bảng ngày nghỉ. Việc còn lại chỉ là lưu nó thành một khung nhìn để có thể hiển thị ra cho người dùng.

Giải pháp này đã khá tốt, và nếu kết hợp với bảng ngày tháng và số nguyên ảo thì có thể nói là nó đã đủ "số má" để áp dụng vào hệ thống thực tiễn. Tuy nhiên khi đi vào thực tế nó vẫn có một số vấn đề khá rõ ràng như sau:

• Hiệu suất vẫn ko cao: Tôi vẫn sẽ phải lưu hàng nghìn bản ghi chứa các ngày nghỉ định kỳ như thứ Bảy Chủ Nhật hay 1/1. Tôi cũng có thể xử lý thứ Bảy Chủ Nhật riêng khi tạo báo cáo cụ thể và chỉ lưu các ngày nghỉ khác, nhưng như vậy quá phức tạp và làm nảy sinh nhiều vấn đề hơn là hiệu quả mang lại.
• Khó bảo trì: Việc thay đổi các ngày nghỉ định kỳ, ví dụ như chuyển sang nghỉ thứ Tư Chủ Nhật thay vì thứ Bảy Chủ Nhật, đòi hỏi tôi phải thực hiện một loạt các câu truy vấn tạm bợ (ad-hoc) khá phức tạp để thêm bớt bản ghi. Điều này dãn đến rủi ro nhầm lẫn khá cao và hạn chế khả năng chuyển giao công việc bảo trì lịch nghỉ cho người dùng bình thường.

Giải pháp cao cấp (sang chảnh)

Để ý rằng khi người dùng muốn thiết lập ngày 1/1 làm ngày nghỉ, thông tin mà tôi có được và cần lưu trữ ko phải là "nghỉ ngày 2015/1/1, nghỉ ngày 2016/1/1, nghỉ ngày ..." mà là "nghỉ ngày 1/1 của tất cả các năm". Như vậy thay vì lưu thông tin dưới dạng bảng ngày nghỉ, tôi có thể lưu thông tin dưới dạng bảng quy luật nghỉ như sau:

Ngày chuẩn	Kiểu lặp	Giải thích
2015/4/25	w	Thứ Bảy
2015/4/26	w	Chủ Nhật
2015/1/1	y	Năm mới
2015/1/31	m	Tổng kết cuối tháng (quán anh Béo)
2015/3/21	n	Cưới con sếp tổng

Trong đó, kiểu lặp n, w, m, y lần lượt tương ứng với các ngày nghỉ ko lặp lại, lặp mỗi tuần, lặp mỗi tháng và lặp mỗi năm dựa trên một ngày được lấy làm chuẩn. Bằng cách này tôi có thể hạn chế lượng dữ liệu lưu trong CSDL đến rất gần với lượng thông tin thực tế cần lưu. Nhờ đó, tôi ko cần phải tạo sẵn dữ liệu ngày nghỉ cho vài trăm năm, hay thêm bớt hàng nghìn bản ghi khi cần chuyển ngày nghỉ từ thứ Bảy sang thứ Tư.

Vấn đề là tôi sẽ chuyển đổi quy luật nghỉ trên ra thành bảng (khung nhìn) lịch nghỉ như thế nào?

SELECT [Ngày], MAX(CASE [Kiểu lặp] 
WHEN 'n' THEN IIF([Ngày] = [Ngày chuẩn], 1, 0)
WHEN 'w' THEN IIF(DATEPART(weekday, [Ngày]) = DATEPART(weekday, [Ngày chuẩn]), 1, 0)
WHEN 'm' THEN IIF(DAY([Ngày]) = DAY([Ngày chuẩn]), 1, 0)
WHEN 'y' THEN IIF(DAY([Ngày]) = DAY([Ngày chuẩn]) AND MONTH([Ngày]) = MONTH([Ngày chuẩn]), 1, 0)
ELSE 0 END) AS [Nghỉ]
FROM [Bảng ngày], [Bảng quy luật] GROUP BY [Ngày]

Các bước để đi đến câu truy vấn trên như sau:

Trước hết nếu đây ko phải là SQL mà là một ngôn ngữ lập trình khác thì tôi sẽ dùng hai vòng for lồng vào nhau (nested), vòng ngoài chạy tất cả các ngày, và vòng trọng chạy tất cả các quy luật để đánh giá từng quy luật đối với ngày đang xét, rồi sau đó đi đến kết luận ngày đang xét có phải ngày nghỉ hay ko. Tóm lại là tôi làm một phép nhân giữa dãy ngày và dãy quy luật. Quay trở lại SQL, phép nhân đó tương ứng với phép nhân Đề-các thuần túy bảng ngày và bảng quy luật, còn gọi là CROSS JOIN. (tham khảo)

SELECT ... FROM [Bảng ngày], [Bảng quy luật]

Tiếp theo, trong vòng for thứ hai ở trên tôi sẽ phải xét từng trường hợp cụ thể của kiểu lặp để tính ra một giá trịboolean thể hiện quy luật đang xét có áp dụng được với ngày đang xét hay ko, tức là tôi sẽ phải làm một câu lệnh casehay switch. Điều này trong SQL tương ứng với cú pháp CASE WHEN. (tham khảo)

CASE [Kiểu lặp] WHEN 'n' THEN ... WHEN 'w' THEN ... WHEN 'm' THEN ... WHEN 'y' THEN ... ELSE ... END

Đến phần đánh giá cụ thể cho từng kiểu lặp, nếu tôi hiểu đơn giản ngày nghỉ lặp theo tuần là các ngày có cùng số thứ tự trong tuần với ngày chuẩn, ngày nghỉ lặp theo tháng là các ngày có cùng số ngày với ngày chuẩn, và ngày nghỉ lặp theo năm là các ngày có cùng số ngày và số tháng với ngày chuẩn, thì tôi có thể dùng các hàm DATEPART, DAY,MONTH để đánh giá. (tham khảo

CASE [Kiểu lặp] 
WHEN 'n' THEN IIF([Ngày] = [Ngày chuẩn] , 1, 0)
WHEN 'w' THEN IIF(DATEPART(weekday, [Ngày]) = DATEPART(weekday, [Ngày chuẩn]), 1, 0)
WHEN 'm' THEN IIF(DAY([Ngày]) = DAY([Ngày chuẩn]), 1, 0)
WHEN 'y' THEN IIF(DAY([Ngày]) = DAY([Ngày chuẩn]) AND MONTH([Ngày]) = MONTH([Ngày chuẩn]), 1, 0)
ELSE 0 END

Cuối cùng, tôi cần tổng hợp kết quả đánh giá của tất cả các quy luật đối với mỗi ngày để đưa ra kết luận ngày đó có phải ngày nghỉ hay ko. Với yêu cầu là chỉ cần có một quy luật áp dụng được thì ngày đó là ngày nghỉ, tôi sẽ phải sử dụng một hàm tổng hợp (aggregate) nào đó và GROUP theo ngày. Nếu là ngôn ngữ lập trình khác thì tôi sẽ dùng orcho kiểu boolean, nhưng đối với SQL thì tôi phải dùng các hàm MIN MAX.

SELECT [Ngày], MAX(CASE ... END) AS [Nghỉ] FROM [Bảng ngày], [Bảng quy luật] GROUP BY [Ngày]

Tổng hợp các bước lại tôi có được câu truy vấn hoàn chỉnh như đã trình bày ở trên.

Giải pháp này có rất nhiều ưu điểm so với các giải pháp lưu thông tin dưới dạng từng ngày nghỉ.

• Độ tin cậy cao: Các ngày nghỉ định kỳ, chiếm trên 90% tổng số ngày nghỉ trong năm, đều được tính toán tự động dựa trên một thuật toán thống nhất nên hạn chế được tối đa lỗi con người. Các quy luật được thể hiện rõ ràng tách khỏi các ngày nghỉ đơn lẻ, với số bản ghi có thể kiểm soát được bằng mắt người. Tôi sẽ ko phải phân vân vì sao ngày 2015/12/12 lại là ngày nghỉ, hay tại sao bỗng dưng 2016/1/1 lại trở thành ngày đi làm.
• Dễ bảo trì: Dù là thêm một ngày nghỉ, thêm một quy luật nghỉ, hay thay đổi một quy định nghỉ có sẵn, tôi đều chỉ cần thêm hoặc sửa đúng một bản ghi. Điều này cho phép một người dùng mù CNTT cũng có thể bảo trì lịch nhanh chóng và dễ dàng với một chút hướng dẫn hoặc một công cụ đơn giản.
• Dễ mở rộng: Chỉ cần sửa chữa một chút bảng quy luật và câu truy vấn, tôi có thể thêm chức năng thiết lập ngày nghỉ theo quý, theo 5 năm, hay thậm chí là ngày thứ x của tuần thứ y trong tháng.

Kết

Trên đây là một số giải pháp để tạo ra một bảng lịch các ngày nghỉ có thể ứng dụng cho doanh nghiệp lẫn cá nhân, trong đó chú trọng vào việc hạn chế tối đa sự phụ thuộc vào dữ liệu thực cũng như lỗi con người, đồng thời tạo nền tảng cho việc mở rộng chức năng về sau.

Hai giải pháp sơ cấp và trung cấp do tôi cóp nhặt từ người đi trước kết hợp với kinh nghiệm cá nhân. Đối với giải pháp cao cấp, tôi lấy ý tưởng về bảng quy luật từ gói phần mềm quản lý tài nguyên cho doanh nghiệp (ERP) Dynamics NAV của Microsoft. Tất nhiên giải pháp cuối cùng mà tôi đưa ra chưa phải là hoàn hảo và vẫn còn nhiều điểm có thể sửa chữa, nâng cấp mà tôi sẽ đề cập đến trong phần 2.

Hy vọng bài viết sẽ có ích cho mọi người và chúc mọi người thành công.

Nguồn: Hawkie

SQL and NULL

Khi sử dụng SQL, chắc hẳn các bạn đã biết có một cái gọi là NULL (mình gọi là cái vì NULL không phải là một giá trị)

Để so sánh với NULL thì các bạn sẽ dùng toán tử is và is not thay vì =(equal) hoặc là <>(not equal)

SELECT * WHERE field IS NULL

Bạn đã bao giờ tự hỏi tại sao lại không dùng (=) và (<>). Đầu tiên chúng ta hãy thử nhé

select "1" where 1 <> NULL;
select "2" where 1 IS NOT NULL;
select "3" where NULL = NULL;
select "4" where NULL <> NULL;
select "5" where NULL IS NULL;

và kết quả nhận được sẽ là "2" và "5". Từ đấy có thể thấy một điều đơn giản là: để so sánh với NULL chúng ta chỉ có thể dùng IS và IS NOT.
Vậy nếu bạn thực hiện các phép toán với NULL thì sao? Mọi phép toán như cộng ,trừ ,nhân ,chia ,concat mà có sự tham gia của NULL đều cho kết quả là NULL cả.

Đầu tiên để hiểu lý do thì chúng ta phải biết là tại sao lại có giá trị NULL. Giá trị NULL trong SQL mục đích chính là để nhằm tạo ra một cách thể hiện cho cái gọi là "không có thông tin hoặc thông tin không phù hợp" (missing information and inapplicable information). Do đó về mặt tự nhiên, bạn sẽ nói là field X không có thông tin, chứ sẽ không nói là field X bằng (equal) không có thông tin, đúng không. Tuy nhiên lý do trên không có giá trị về mặt giải thích.

Để giải thích cặn kẽ thì chúng ta phải đi lại một chút về khái niệm Logic. Về mặt toán học thì có rất nhiều loại LOGIC. Boolean logic được biết đến nhiều nhất. Bản chất của Boolean là chỉ tồn tại 2 giá trị TRUE, FALSE và các phép toán trên chúng. Do đó Boolean được xếp vào loại 2VL (2 valued logic). Tuy nhiên logic trong SQL rất tiếc lại không phải Boolean, vì trong SQL sẽ tồn tại 3 khái niệm logic: TRUE, FALSE, và Unknown ( hay chính là NULL ). Do đó logic trong SQL gọi là 3VL (3 valued logic). Trong Boolean chỉ có 2 phép so sánh là equal (=) và not(<>), tuy nhiên với 3VL như SQL sẽ có thêm phép so sánh là IS và IS NOT. Kết hợp 3 loại giá trị với các phép so sánh đó sẽ cho chúng ta kết quả là 3 loại bảng truth table dưới đây:

(trích dẫn từ Wikipedia)

Trên đây là những kiến thức hết sức basic về giá trị NULL trên SQL, hy vọng có thể giúp các bạn đỡ nhầm lẫn khi thực hiện các phép toán với NULL.

Full Text Search từ khái niệm đến thực tiễn (Phần 4)

Introduction

Trong phần 3, các bạn đã được tìm hiểu về việc sử dụng Boolean Logic để tìm ra các Document chứa các term trong query cần tìm kiếm.
Vậy sau khi tìm được các Document thích hợp rồi thì chỉ việc trả lại cho người dùng, hay đưa lên màn hình? Bài toán sẽ rất đơn giản khi chỉ có 5, 10 kết quả, nhưng khi kết quả lên đến hàng trăm nghìn, thì mọi việc sẽ không đơn giản là trả lại kết quả nữa. Lúc đó sẽ có vấn đề mới cần giải quyết, đó là đưa kết quả nào lên trước, hay chính là bài toán về
Ranking

Việc Ranking trong Full Text Search thông thường sẽ được thực hiện thông qua việc tính điểm các Document được tìm thấy, rồi Rank dựa vào điểm số tính được. Việc tính điểm thế nào sẽ được thực hiện thông qua các công thức, hay
thuật toán, mà mình gọi chung là Ranking Model

Ranking Model

Trong bài viết về Ranking news, mình đã nói về việc giải quyết một bài toán gần tương tự. Tuy nhiên bài toán lần này cần giải quyết khác một chút, đó là việc Ranking sẽ phải thực hiện dựa trên mối quan hệ giữa "query terms" và "document".

Ranking Model được chia làm 3 loại chính: Static, Dynamic, Machine Learning.
Dưới đây mình sẽ giới thiệu lần lượt về mỗi loại này.

Static

Static ở đây có nghĩa là, Ranking Model thuộc loại này sẽ không phụ thuộc vào mối quan hệ ngữ nghĩa giữa "query term"
và "document". Tại sao không phụ thuộc vào "query term" mà vẫn ranking được? Việc này được giải thích dựa theo quan điểm khoa học là độ quan trọng của document phụ thuộc vào mối quan hệ giữa các document với nhau.

Chúng ta sẽ đi vào cụ thể một Ranking Model rất nổi tiếng trong loại này, đó chính là PageRank.

PageRank là thuật toán đời đầu của Google, sử dụng chủ yếu cho web page, khi mà chúng có thể "link" được đến nhau.
Idea của PageRank là "Page nào càng được nhiều link tới, và được link tới bởi các page càng quan trọng, thì score càng cao". Để tính toán được PageRank, thì chúng ta chỉ cần sử dụng WebCrawler để crawl được mối quan hệ "link" giữa tất cả các trang web, và tạo được một Directed Graph của chúng.

Chính vì cách tính theo kiểu, tạo được Graph xong là có score, nên mô hình dạng này được gọi là "Static".

Ngoài PageRank ra còn có một số thuật toán khác gần tương tự như HITS đã từng được sử dụng trong Yahoo! trong thời gian đầu.

Dynamic

Ranking Model thuộc dạng Dynamic dựa chủ yếu vào Mối quan hệ giữa "query term" và "document".

Có rất nhiều thuật toán thuộc dạng này, có thuật toán dựa vào tần suất xuất hiện của "query term" trong document, có thuật toán lại dựa vào các đặc tính ngữ nghĩa (semantic) của query term , có thuật toán lại sử dụng những quan sát mang tính con người như thứ tự xuất hiện các từ trong "query term" và thứ tự xuất hiện trong "document".

Một trong những thuật toán được sử dụng nhiều nhất là TF-IDF (Term Frequency Inverse Document Frequency).
Thuật toán này dựa vào Idea là "query term" xuất hiện càng nhiều trong document, document sẽ có điểm càng cao.

Thuật toán này được biểu diễn dưới công thức sau
$$TF-IDF(t, d, D) = TF(t, d) * IDF (t, D)$$
Ở đây t là query term, d là document cần được score, và D là tập hợp "tất cả" các documents. Trong đó thì:
$$TF(t, d) = frequency(t, d)$$
$$IDF(t, D) = log{N \over |{d \in D : t \in d}|}$$

Một cách đơn giản thì:

• TF : tần suất xuất hiện của term t trong document d
• IDF : chỉ số này biểu hiện cho tần suất xuất hiện của term t trong toàn bộ các documents. t xuất hiện càng nhiều, chỉ số càng thấp (vì xuất hiện quá nhiều đồng nghĩa với độ quan trọng rất thấp)

Công thức của TF-IDF đã phối hợp một cách rất hợp lý giữa tần suất của term và ý nghĩa/độ quan trọng của term đó.

Trong thực tế thì người ta hay sử dụng thuật toán Okapi BM25 hay gọi tắt là BM25, là một mở rộng của TF-IDF, nhưng thêm một vài weight factor hợp lý.

Machine Learning

Ngoài việc sử dụng các mối quan hệ đơn giản giừa query term và document, hay giứa document với nhau, thì gần đây việc sử dụng học máy (Machine Learning) trong Ranking cũng đang trở nên rất phổ biến.

Để nói về Machine Learning thì không gian bài viết này có lẽ là không đủ, mình sẽ nói về ý tưởng của Model này.

Idea của việc sử dụng Machine Learning trong ranking là chúng ta sẽ sử dụng một mô hình xác suất để tính toán.
Cụ thể hơn là chúng ta sẽ sử dụng supervised learning, nghĩa là chúng ta sẽ có input là một tập dữ liệu X để training, một model M ban đầu, một hàm error để so sánh kết quả output X' có được từ việc áp dụng model M vào query term, và một hàm boost để từ kêt quả của hàm error chúng ta có thể tính lại được model M. Việc này được lặp đi lặp lại mỗi lần có query, hoặc lặp lại một cách định kỳ (1 ngày 1 lần, 1 tháng 1 lần..) để model M luôn luôn được cải thiện.

Thuật toán gần đây được sử dụng khá nhiều trong Ranking model chính là Gradient Boosting Decision Tree mà các bạn có thể tham khảo ở đây

Conclusion

Bài viết đã giới thiệu về 3 mô hình chính dùng để Ranking kết quả tìm kiếm trong Full Text Search.
Trong thực tế thì các công ty lớn nhưn Google, Yahoo, MS sẽ không có một mô hình cố định nào cả, mà sẽ dựa trên các kết quả có từ người dùng để liên tục cải thiện.
Không có một mô hinh nào là "đúng" hay "không đúng" cả, mà để đánh giá Ranking Model chúng ta sẽ phải dựa trên thông kê người dùng (như click rate, view time...).
Việc hiểu rõ Ranking Model sẽ giúp chúng ta build được một search engine tốt cho service của mình, đông thời cũng giúp ích rất nhiều cho việc SEO (Search Engine Optimization).

Tài liệu tham khảo:

• Yahoo! Learning to Rank Challenge Overview

Nguồn: Huydo - kipalog

Full Text Search, Từ Khái Niệm đến Thực Tiễn (Phần 3)

Introduction

Trong phần 2, chúng ta đã nắm được một kĩ thuật cơ bản và quan trọng để tạo ra search engine, đó chính là kĩ thuật tách chữ (Tokenize), thông qua 2 phương pháp chính là N-gram và Morphological Analysis. Nhờ có kĩ thuật này mà văn bản gốc sẽ được bóc tách thành các kí tự, sau đó sẽ được lưu trữ dưới dạng Inverted Index như đã giới thiệu ởphần 1.

Trong bài viết này, chúng ta sẽ tìm hiểu là làm thế nào, mà khi được cung cấp đầu vào là một chuỗi truy vấn (query string), search engine sẽ cung cấp được cho chúng ta kết quả phù hợp nhất. Về cơ bản, để tìm kiếm bên trong một khối dữ liệu khổng lồ đã được index dưới dạng "Inverted Index", search-engine sẽ sử dụng "Boolean Logic".

Boolean Logic và tại sao Search Engine lại sử dụng Boolean Logic

Khi nhắc đến Boolean Logic, các bạn sẽ hình dung ra trong đầu những hình ảnh như thao tác AND/OR/XOR với bit, mạch logic trong điện tử số, hay biểu đồ ven.
Đối tượng thao tác của Boolean Logic có thể là bit, cổng logic, hay là tập hợp (set).
Trong bài này, Boolean Logic sẽ được nhắc đến với đối tượng là tập hợp (set), và hình ảnh dễ hình dung nhất khi thao tác với đối tượng này chính là biểu đồ Ven.

Để tìm hiểu mối liên quan giữa Boolean Logic và Search Engine, chúng ta hãy thử hình dung cơ chế của Search Engine.
Khi được cung cấp một chuỗi truy vấn (query string), việc đầu tiên Search Engine sẽ phải sử dụng Parser module để bóc tách chuỗi truy vấn này theo một ngữ pháp đã được qui định trước, để tạo thành các token sử dụng cho logic tìm kiếm.
Việc sử dụng Parser này cũng giống như compiler hay intepreter sẽ sử dụng các cú pháp đã được định nghĩa trước của một ngôn ngữ bất kỳ để dịch một đoạn code ra mã máy hoặc là bytecode.
Ngữ pháp qui định trước càng phức tạp, không chỉ dẫn đến việc parse chuỗi truy vấn trở nên phức tạp hơn, việc viết ra một câu truy vấn phức tạp hơn (ảnh hưởng đến người dùng), mà còn khiến logic tìm kiếm cũng trở nên phức tạp, qua đó làm giảm hiệu suất của việc tìm kiếm.
Chính vì thế mà việc tận dụng một ngữ pháp gần giống với Boolean Logic không những sẽ giúp giữ cho độ phức tạp khi parse query string ở mức thấp, mà nó còn giúp cho người dùng tạo ra những câu truy vấn dễ hiểu hơn.

Sử dụng Boolean Logic trong Search Engine

Boolean logic sử dụng trong Search Engine thường sẽ gồm 3 phép toán chính là AND, NOT và OR
Hãy trở lại ví dụ gần giống trong phần 1, chúng ta có 5 documents {D1, D2, D3, D4, D5} đã được index như sau:

D1 = "This is first document"
D2 = "This is second one"
D3 = "one two"
D4 = "This one is great"
D5 = "This two is great!"

"this" => {D1, D2, D4, D5}
"is" => {D1, D2, D4, D5}
"first" => {D1}
"document" => {D1}
"second" => {D2}
"one" => {D2, D3, D4}
"two" => {D3, D5}

Giả sử chúng ta muốn query một câu truy vấn như sau : "This one". Sử dụng Morphological Analysis đã giới thiệu trong phần 2, chúng ta sẽ tách câu truy vấn đó thành 2 token là "This" và "one".
Bỏ qua yếu tố chữ hoa và chữ thường, thì "This" đã được index {D1, D2, D4, D5}, và "one" đã được index {D2, D3, D4}.

Thông thường để cho dễ hiểu và phù hợp với logic của người dùng, thì space sẽ tương đương với logic AND, hay là việc tìm kiếu "This one" sẽ tương đương với kết tìm kiếm "This" AND với kết quả tìm kiếm "one".
Hay như trong ví dụ này thì kết quả tìm kiếm sẽ là kết quả AND của 2 set {D1, D2, D4, D5} và {D2, D3, D4}.
Kết quả này có thể thấy dễ dàng là {D2, D4}

Vậy nếu người dùng input là "This OR one" thì sao? Lúc này kết quả tìm kiếm sẽ là

{D1, D2, D4, D5} OR {D2, D3, D4} = {D1, D3, D5}

Từ ví dụ trên chúng ta thấy rằng độ phức tạp của việc tìm kiếm lúc này sẽ chuyển thành

Độ phức tạp của parse query string(1) 
+ Độ phức tạp của Index lookup(2) 
+ Độ phức tạp của thao tác boolean Logic dựa trên kết quả của Index lookup(3)

• 1. thường sẽ không lớn do query string do user input khá ngắn, và trong trường hợp query string được generate phức tạp khi sử dụng lucene hoặc solr, thì việc sử dụng boolean logic rất đơn giản cũng làm độ phức tạp khi parse query string là không cao.
• 2. Độ phức tạp của Index lookup tương đương với việc tìm kiếm giá trị của một key trong Hash table, chỉ khác là trên HDD, tuy nhiên so sánh với việc tìm kiếm trên BTree của MySQL thì performance của xử lý này là hoàn toàn vuợt trội.
• 3. Thao tác này có thể được optimize rất nhiều dựa vào các lý thuyết tập hợp, hay các thư viện toán học cho big number.

Như vậy chúng ta có thể thấy bài toán tìm kiếm ban đầu đã được đưa về 3 bài toán nhỏ hơn, dễ optimize hơn.

Kết luận

Bài viết đã giới thiệu về việc sử dụng Boolean Logic trong Full Text Search Engine. Qua đó các bạn chắc đã hình dung ra phần nào khi các bạn gõ một câu lệnh tìm kiếm vào ô tìm kiếm của Google, những gì sẽ xảy ra đằng sau (mặc dù trên thực tế những gì google làm sẽ phức tạp hơn rất nhiều).

Tham khảo:

• Make Findspot

Nguồn: Huydo - kipalog

Full Text Search, Từ Khái Niệm đến Thực Tiễn (Phần 2)

Introduction

Trong phần 1, chúng ta đã tìm hiểu sơ qua về khái niệm Full Text Search, cũng như về Inverted Index.
Qua bài viết đầu tiên, các bạn đã nắm được tại sao Inverted Index lại được sử dụng để tăng tốc độ tìm kiếm trong một "Full Text Database".
Đồng thời ở ví dụ của phần một, các bạn cũng đã thấy, để tạo ra Inverted Index thì các bạn phải tách được một string ra thành các term, sau đó sẽ index string đó theo term đã tách được. Chính vì thế việc tách string, hay còn gọi làTokenize là một bài toán con quan trọng nằm trong bài toán lớn của Full Text Search.

Ở bài này, chúng ta sẽ tìm hiểu về 2 kĩ thuật Tokenize cơ bản là:

• N-Gram
• Morphological Analysis

N-gram

N-gram là kĩ thuật tokenize một chuỗi thành các chuỗi con, thông qua việc chia đều chuỗi đã có thành các chuỗi con đều nhau, có độ dài là N.
Về cơ bản thì N thường nằm từ 1~3, với các tên gọi tương ứng là unigram(N==1), bigram(N==2), trigram(N==3).
Ví dụ đơn giản là chúng ta có chuỗi "good morning", được phân tích thành bigram:

"good morning" => {"go", "oo", "od", "d ", " m", "mo", "or", "rn", "ni", "in", "ng"}

Từ ví dụ trên các bạn có thể dễ dàng hình dung về cách thức hoạt động của N-gram.
Để implement N-gram, chỉ cần một vài ba dòng code như sau, như ví dụ viết bằng python như sau:

def split_ngram(self, statement, ngram):
    result = []
    if(len(statement) >= ngram):
      for i in xrange(len(statement) - ngram + 1):
        result.append(statement[i:i+ngram])
    return result

Morphological Analysis

Morphological Analysis, rất may mắn có định nghĩa trên [wikipedia](http://vi.wikipedia.org/wiki/H%C3%ACnh_th%C3%A1i_h%E1%BB%8Dc_(ng%C3%B4n_ng%E1%BB%AF_h%E1%BB%8Dc) bằng tiếng Việt.
Định nghĩa khá dài dòng, các bạn có thể xem bằng [Tiếng Anh](http://en.wikipedia.org/wiki/Morphology_(linguistics)
Về cơ bản Morphological Analysis (từ bây giờ mình sẽ gọi tắt là MA), là một kĩ thuật phổ biến trong xử lý ngôn ngữ tự nhiên (Natural Language Processing).
Morphological chính là "cấu trúc" của từ, như vậy MA sẽ là "phân tích cấu trúc của từ", hay nói một cách rõ ràng hơn, MA sẽ là kĩ thuật tokenize mà để tách một chuỗi ra thành các từ có ý nghĩa. Ví dụ như cũng cụm từ "good morning" ở trên, chúng ta sẽ phân tích thành:

"good morning" => {"good", "morning"}

Để có được kết quả phân tích như trên, ngoài việc phải sở hữu một bộ từ điển tốt (để phân biệt được từ nào là có ý nghĩa, và thứ tự các từ thế nào thì có ý nghĩa), MA phải sử dụng các nghiên cứu sâu về xử lý ngôn ngữ tự nhiên, mà mình sẽ không đi sâu ở đây.

Thông thường các công ty lớn sở hữu các search engine của riêng họ(như Yahoo, Google, Microsoft..) sẽ có các đội ngũ nghiên cứu để tạo ra nhiều bộ thư viện MA riêng của họ, thích hợp với nhiều ngôn ngữ. Ngoài ra chúng ta cũng có thể sử dụng các bộ thư viện được open source, hoặc sử dụng các package có sẵn trong các bộ full text search engine mà tiêu biểu là lucene.

Mở rộng

Các bạn đọc đến đây chắc hẳn sẽ có suy nghĩ, để phân tách chuỗi, thì rõ ràng phân tích theo MA là quá hợp lý rồi, tại sao lại cần N-gram làm gì?

Như mình đã nói ở trên, để xây dựng MA thì cần một bộ từ điển tốt, để giúp cho máy tính có thể phân biệt được các từ có nghĩa.

Như thế nào là một từ điển tốt, thì về cơ bản, từ điển tốt là từ điển chứa càng nhiều từ (terms) càng tốt.
Tuy nhiên ngôn ngữ thì mỗi ngôn ngữ lại có đặc trưng riêng, và không ngừng mở rộng, không ngừng thêm các từ mới.

Việc chỉ sử dụng MA sẽ gây ra một tác dụng phụ là có rất nhiều từ không/chưa có trong từ điển, dẫn đến không thể index, và do đó sẽ không thể tiến hành tìm kiếm từ đó được.

Vậy cách giải quyết như thế nào?
Cách giải quyết tốt nhất là chúng ta sẽ kết hợp(hybrid) cả MA và N-gram. Cách hybrid thế nào thì sẽ tuỳ vào ngôn ngữ/ hoàn cảnh sử dụng, và cả performance cần thiết nữa. Về cơ bản thì những từ nào khó/không có thể phân tích được bằng MA, thì chúng ta sẽ dùng N-gram.

Kết luận

Qua bài viết lần này, các bạn đã hiểu thêm về 2 kĩ thuật tách từ (tokenize) cơ bản là N-gram và MA.

Sử dụng 2 kĩ thuật này như thế nào để index dữ liệu đầu vào, sẽ được giới thiệu trong các bài viết sắp tới.

Nguồn: Huydo - kipalog