Ứng dụng SQL trong tìm kiếm văn bản dựa trên từ khóa

SQL Big Data

SQL Big Data

Trong bài viết này, ta sẽ ứng dụng ngôn ngữ truy vấn SQL vào phép tính nhân hai ma trận rời rạc (có nhiều giá trị bằng 0). Từ phép tính này, ta tiến hành xây dựng bộ máy tìm kiếm văn bản dựa trên từ khóa.

Bài viết sử dụng sqlite3, độc giả có thể tìm hiểu cách cài đặt ở trang web sau: http://www.tutorialspoint.com/sqlite/sqlite_installation.htm

Mọi tập tin liên quan đến bài viết có thể truy xuất tại Github: https://github.com/ongxuanhong/database-analysis

Khảo sát cơ sở dữ liệu reuters.db

Đầu tiên, ta sẽ thực hiện một vài truy vấn cơ bản trên cơ sở dữ liệu reuters.db chỉ gồm một table frequency(docid, term, count). Trong đó, docid là định danh cho tập tin văn bản, term là một từ tiếng Anh, và count là số lần xuất hiện của term này trong văn bản docid. Lấy ví dụ tập tin văn bản 10000_txt_earn.

"docid","term","count"
"10000_txt_earn","net",1
"10000_txt_earn","rogers",4
"10000_txt_earn","earnings",2
"10000_txt_earn","switch",1
"10000_txt_earn","conn",1
"10000_txt_earn","revenues",2
"10000_txt_earn","cts",1
"10000_txt_earn","company",1
"10000_txt_earn","ago",1
"10000_txt_earn","circuit",1
"10000_txt_earn","114000",1
"10000_txt_earn","dlrs",2
"10000_txt_earn","sale",2
"10000_txt_earn","26",1
"10000_txt_earn","line",1
"10000_txt_earn","first",2
"10000_txt_earn","said",4
...

Để chạy các câu truy vấn SQL bằng sqlite3. Tại thư mục chứa tập tin sql_filename, ta thực hiện câu lệnh sau

sqlite3 reuters.db < sql_filename

Ở đây, sql_filename là tập tin chứa các câu lệnh SQL. Ta tạo tập tin inspecting_the_reuters_dataset.sql chứa các truy vấn cơ bản.

-- a) xem nội dung văn bản 10398_txt_earn
select *
from frequency
where docid = "10398_txt_earn";

-- b) tìm những term trong văn bản 10398_txt_earn chỉ xuất hiện 1 lần
select term
from frequency
where docid = "10398_txt_earn" and count = 1

-- c) tìm những term chỉ xuất hiện 1 lần trong văn bản 10398_txt_earn và 925_txt_trade
select term
from frequency
where docid = "10398_txt_earn" and count = 1
union
select term
from frequency
where docid = "925_txt_trade" and count = 1;

-- d) term “parliament” xuất hiện trên bao nhiêu văn bản
select count(docid)
from frequency
where term = "parliament";

-- e) tìm những văn bản có số term phân biệt nhiều hơn 300
select docid, count(docid) as term_count
from frequency
group by docid
having term_count > 300;

-- f) tìm những văn bản chứa hai từ transactions và world.
select docid
from frequency
where term in ("transactions", "world")
group by docid
having count(docid) = 2;

Nhân hai ma trận với SQL

Giả sử a và b là hai ma trận rời rạc (có nhiều giá trị bằng 0). Ta cần thực hiện phép nhân hai ma trận như sau:

0 1 0 0 9 1 0 0 0 0 0
0 0 3 0 0 \ / 0 0 0 ----- 0 21 0
0 0 0 2 0 * 0 7 0 ----- 0 0 4
0 0 0 0 0 / \ 0 0 2 0 0 0
0 0 0

Ta có thể tạo một ma trận trong cơ sở dữ liệu quan hệ với table matrix_name (row_num, col_num, value). Mỗi phần tử khác 0 trên ma trận được biểu diễn bằng (i, j, value).

CREATE TABLE a (
row_num INT,
col_num INT,
value INT,
PRIMARY KEY(row_num, col_num)
);

CREATE TABLE b (
row_num INT,
col_num INT,
value INT,
PRIMARY KEY(row_num, col_num)
);

Tiếp theo, ta điền dữ liệu vào hai bảng a, b.

INSERT INTO a VALUES
(1, 2, 1),
(1, 5, 9),
(2, 3, 3),
(3, 4, 2);

INSERT INTO b VALUES
(1, 1, 1),
(3, 2, 7),
(4, 3, 2);

Cuối cùng, ta thực hiện phép nhân hai ma trận bằng câu truy vấn dưới đây

SELECT a.row_num, b.col_num, SUM(a.value*b.value)
FROM a, b
WHERE a.col_num = b.row_num
GROUP BY a.row_num, b.col_num;

2|2|21
3|3|4

Trong phép nhân hai ma trận, mỗi phần tử (i, j) được tính bởi công thức sum(a(i, k) * b(k, j)). Điều kiện kết bảng (join) a.col_num = b.row_num đảm bảo a.value và b.value có cùng giá trị k. Câu lệnh gom nhóm (group by) để tính tổng trên dãy số k.

Ngoài ra, bài viết còn cung cấp cơ sở dữ liệu matrix.db chứa hai table ab là hai ma trận 5×5 để ta thử nghiệm với truy vấn trên.

Ma trận Document-term

Tập dữ liệu trong reuters.db còn được gọi là ma trận document-term. Đây là một cách biểu diễn quan trọng trong phân tích văn bản (text analysis).

Term-document

Term-document

Mỗi dòng trong ma trận là một vector văn bản, mỗi cột tương ứng với các term xuất hiện trong ngữ liệu (corpus). Ma trận document-term thường rời rạc, vì có nhiều từ xuất hiện trong văn bản này nhưng không xuất hiện trong văn bản kia. Các phần tử trên ma trận là số lần xuất hiện của term j trong văn bản i.

Từ ma trận document-term D ta có thể tính độ tương tự (similarity) giữa các văn bản. Ta chỉ cần thực hiện phép tính nhân ma trận D với ma trận chuyển vị D’, S = DD’.

Ma trận S là ma trận vuông đối xứng chứa độ đo tương tự giữa các văn bản. Ý nghĩa giá trị của mỗi phần tử khá đơn giản: nếu hai văn bản cùng chứa một term, khi đó độ đo tương tự sẽ được nhân với nhau. Giá trị này tương đương với phép nhân hai vector văn bản (dot product).

Cosine distance

Cosine distance

Để chuẩn hóa về khoảng 0-1, ta có thể sử dụng khoảng cách cosine. Giá trị khoảng cách cosine là độ đo của góc tạo bởi hai vector văn bản. Tuy nhiên, trong bài viết này, để đơn giản hóa vấn đề, ta không cần tính khoảng cách cosine này.

Ta tiến hành tính ma trận tương tự giữa các văn bản bằng câu truy vấn sau. Tương tự ví dụ nhân hai ma trận, row_num tương đương với docid, col_num tương đương với term, value tương đương với count. Vì D nhân với ma trận chuyển vị D’ ta chỉ cần thay điều kiện kết (join) bằng a.term = b.term (a.row_ num = b.row_ num thay vì a.col_num = b.row_num như ban đầu). Vì S là ma trận đối xứng, ta chỉ cần tính nửa trên ma trận với điều kiện a.docid < b.docid để giảm số phép tính toán.

SELECT a.docid, b.docid, SUM(a.count*b.count)
FROM frequency a, frequency b
WHERE a.term = b.term and a.docid &lt; b.docid
GROUP BY a.docid, b.docid;

Từ kết quả trên, ta có thể tiến hành xây dựng bộ máy tìm kiếm văn bản dựa trên từ khóa. Giả sử ta gõ một chuỗi từ khóa tìm kiếm (keywords query) như trên Google. Ta có thể xem chuỗi từ khóa này là tập các từ trong một văn bản (bag of words in document).

Như vậy, ta có thể tính toán độ tương tự giữa hai văn bản, độ tương tự giữa một chuỗi tìm kiếm (lúc này cũng là một văn bản) với một văn bản khác. Ta thực hiện điều này bằng cách thêm vào table frequency ban đầu những dòng dữ liệu (docid, term, count) tương ứng với chuỗi tìm kiếm này. Sau đó, ta tính toán lại ma trận S và trả về danh sách các văn bản tương ứng với chuỗi tìm kiếm trên.

Ví dụ ta có chuỗi tìm kiếm “washington taxes treasury”. Ta thêm vào table frequency 3 dòng dữ liệu (docid, term, count) qua câu truy vấn sau.

CREATE VIEW keyword_search AS
SELECT * FROM frequency
UNION
SELECT 'q' as docid, 'washington' as term, 1 as count
UNION
SELECT 'q' as docid, 'taxes' as term, 1 as count
UNION
SELECT 'q' as docid, 'treasury' as term, 1 as count;

Sau cùng, ta tiến hành tính toán lại ma trận S và trả về danh sách các văn bản gần với chuỗi truy vấn ban đầu.

SELECT b.docid, SUM(a.count*b.count) as 'similarity'
FROM keyword_search a, keyword_search b
WHERE a.term = b.term and a.docid = 'q'
GROUP BY a.docid, b.docid;

Danh sách các văn bản gần đúng với chuỗi tìm kiếm được lưu vào file keyword_search.txt

Advertisements

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s