Một số vần đề chọn ỉọc cùa Công nghệ thông tỉn và truvền thông, Hưng Yên, ĩ 9-20 tháng 08 năm 20ĩ 0
MỘT PHƯƠNG PHÁP XỬ LÝ
KÉT QUẢ TÌM KIẾM TRÊN WEB
Trần Ngọc Hà *, Hoàng Xuân Huấn Nguyễn Phương Chi^
(1) Khoa Toán, Đại học Sư phạm, Đại học Thái Nguyên
(2) Khoa Công nghệ thông tin, Đại học Công nghệ, Đại học Quốc Gia Hà Nội
(3)Khoa Cơ bản, Đại học Ngoại thương
Khí sử dụng các công cụ tìm kiếm thông dụng hiện nay, kết quả tìm idem
thicờng là rất nhiều tài liệu và các kết quả được đảnh giá là cỏ liên quan tời từ
khỏa nhiều nhất sẽ được iru tiên hiển thị trước. Phương pháp này nhiều khi
không tiện lợi cho người dùng, thậm chí người dùng có thể bỏ qua các kết quả
cần tìm vì chủng không cỏ thứ hạng cao trong tập kết quả tìm kiếm. Để giải
quyết vẩn đề này, báo cáo đề xuất hiển thị kết quả tìm kiếm web theo chủ đề.
Để xác định chủ đề cho tài liệu, tnrởc hết sử dụng mô hĩnh tập thô dung sai để
tăng chất lượng việc biểu diễn các tài liệu và các cụm từ nhằm tăng hiệu qitả
phân cụm; sau đó sử dụng phương pháp phân cụm bán giảm sát Seeded -
KMeans vào việc phân cụm và xác định chủ đề tài liệu. Nhờ cách xử lý này,
người dùng dựa trên từ khỏa cỏ thể tìm tài liệu theo chủ đề.
Từ khóa: tập thô dung sai, đồng xuất hiện, phân cụm bán giám sát, Seeded -
KMeans, tìm kiếm web
1. Giới thiệu
Cùng với sự phát triển rộng rãi của Internet, các máy tìm kiếm hiệu quả trên web
đang được nhiều người quan tâm nghiên cứu (xem [2],[3],[8]).
Mỗi khi cần tìm kiếm một thông tin nào đó, người dùng sẽ cung cấp cho máy tìm
kiếm một số từ khóa, các máy tìm kiếm sẽ trả về cho người dùng các tài liệu có chứa từ
khóa này. Thường thì có hàng trăm hoặc hàng ngàn tài liệu như vậy, điều này gây khó
khăn cho người dùng trong việc tìm đúng tài liệu cần tìm. Thực tể cho thấy nếu các kết quả
tìm kiếm được chia thành các chủ đề sẽ giúp người dùng dễ xác định được tài liệu mình
cần tìm hơn. Điều này gợi ra cách tiếp cận mới là phân cụm kết quả tìm kiểm theo chủ đề
và hiển thị kết quả dựa trên chủ đề theo lựa chọn của người dùng.
Việc phân cụm kết quả tim kiếm web gặp phải một số khó khăn sau:

lựa chọn tài liệu có chứa các từ trong câu hỏi tray vấn, hoặc dựa trên phương pháp xếp
hạng tài liệu (Document Ranking) liên quan đến câu hỏi truy vấn. Do đó hầu hết các máy
tìm kiếm đều sử dụng biến dữ liệu có cấu trúc chỉ mục ngược (inverted index) để hỗ trợ
thực hiện công việc này.
Lưu trữ tài liệu (Document Cache): Hiện nay có nhiều máy tìm kiếm vừa lưu trữ
bảng chỉ số tài liệu như ở phần trên, vừa lưu trữ tài liệu gốc.
Tính hạng tài liệu (Document Ranking) World Wide Web càng ngày càng phát
triển do vậy lượng thông tin ngày càng lớn, số kết quả tìm kiếm với một từ khóa bất kỳ đều
rất lớn, ngay cả với những câu hỏi truy vấn hoàn thiện và chính xác, số kết quả tìm kiếm
vẫn có thể lên đến hàng ngàn hoặc hàng triệu. Chính vì vậy cần có module tính hạne; tài
182
Một sẩ vấn đề chọn lọc cùa Công nghệ thông tin và truyền thông, Hưng Yên, 19-20 tháng 08 năm 2010
liệu để xác định được tài liệu nào có độ liên quan đến các từ khóa mà người dùng tìm
kiểm nhất.
Xử lí truy vấn là thành phần có nhiệm vụ phân tích cú pháp tìm kiếm của người
dùng thông qua các toán tử và cú pháp được định nghĩa, sau đó bộ xử lí truy vấn kết hợp
với bảng chỉ số tài liệu, các tài liệu được lưu trừ, và thành phần tính hạng tài liệu để đưa ra
tập kết quả tìm kiếm thỏa mãn cú pháp tìm kiếm của người dùng.
Giao diện biểu diễn kết quả là thành phần quan trọng trong máy tìm kiếm và trực
tiếp tương tác với người sử dụng. Do vậy giao diện biểu diễn kết quả tìm kiếm là yểu tố
đầu tiên được xem xét khi đánh giá chất lượng của một chương trình tìm kiếm, nó có vai
trò vô cùng quan trọng và có ảnh hưởng rất lớn đến toàn bộ chất lượng của máy tìm kiểm.
3. Phân cụm kết quả tìm kiếm web và mô hình tập thô dung sai.
Trong mục này chúng tôi giới thiệu tóm tắt bài toán phân cụm kết quả tìm kiếm
trên web, phương pháp phân cụm bán giám sát Seeded-Kmeans và mô hình tập thô dung
sai (chi tiết hơn xem [1], [4], [5], [6])
3.1. Bài toán phân cụm kết quả tìm kiếm web
Phân cụm dữ liệu là bài toán học không giám sát được phát biểu như sau:
Giả sử ta có tập các đối tượng D={dl,d2, )dn} và ô(di; dj) là độ tương tự giữa hai
đối tượng di và dj. Phân cụm là chia tập đối tượng D thành K cụm C={cl,c2, ,ck} sao

dựa trên mật độ, Đối với bài toán phân cụm tài liệu, phương pháp phân cụm phân hoạch
thường được lựa chọn. Trong báo cáo này chúng tôi cũng sử dụng phương pháp phân cụm
phân hoạch cho việc phân cụm kết quả tìm kiếm web.
3.2. Thuật toán phân cụm bán giám sát Seeded - Kmeans
Đối với phương pháp phân cụm nửa giám sát dựa trên tập dữ liệu được gán nhãn,
để hình thành nên các cụm giống nhằm khởi tạo cho một thuật toán phân cụm hoặc để sinh
ra các ràng buộc dẫn dắt quá trình phân cụm, người ta sẽ sử dụng tập dữ liệu được
gán nhãn.
Seeded-KMeans là thuật toán phân cụm bán giám sát điển hình dựa trên tập dữ liệu
đã được người dùng gán nhãn được Basu đề xuất năm 2002 (xem [1]). Thuật toán này sử
dụng tập con ^ được gọi là tập giống gồm các đối tượng đã được gán nhãn để khởi
tạo cho thuật toán KMeans. Trên thực tế tập giống s thường chỉ chiếm một phần nhỏ trong
tập đối tượng X. Do vậy khi tập giống không đầy đủ thì các cụm còn lại được khởi tạo
ngẫu nhiên trên phần bù của s trong X. Dưới đây là thể hiện chi tiết của thuật toán Seeded
- KMeans.
Thuật toán Seeded-KMeans
Input; - Tập các đối tượng dừ liệu X = e
Số lượng cụm: K
- Tập giống S = [Jt\Sh
Output: K phân hoạch tách rời: của X sao cho hàm mục tiêu được tối ưu.
Thuật toán:
Bưó'c 1: Khởi tạo các cụm: ^ JC , với h = t«-0.
Bước 2: Gán cum; Gán mỗi đối tương dữ liêu X vào cum h' (tức là tâp ) với /i* = argmin
* l /j J /l=l
184
Một sổ vẩn đề chọn lọc của Công nghệ thông tin và truyền thông, Hưng Yên, 19‘20 tháng 08 năm 20ì 0
Bước 3: ước lượng tâm:
*
Bước 4: t <-t+l
Bước 5: Dừng nếu hội tụ hoặc quay lại bước 2.

Một số vẩn đề chọn lọc cùa Công nghệ thống tin và truyền thông, Hưng Yên, 19-20 thảng 08 năm 2010
Giả s ử mỗi đối tượng X có thể hiểu được bởi các thông tin Inf(x) về nó. Hàm không
chắc chắn I xác định một lớp dung sai I(x) của các đối tượng được coi là có thông tin
tương tự với X. Hàm này có thể là một hàm bất kỳ thỏa mãn 2 điều kiện xe I(x) và xe I(y)
<=> ye I(x) V x,ye u. Dễ thấy I(x) là lớp dung sai của X bởi vi quan hệ xRy<=^ yG I(x) là một
quan hệ dung sai.
Hàm tính độ mập mờ V được dùng để xác định mức độ bao phủ giữa các tập hợp. V
có thể là bất cứ hàm đơn điệu đối với 2 tham sổ của nó v(X,Y) < v(X,Z) V X,Y,ZeU và
YcZ.
Hàm cấu trúc p phân lóp I(x) với mỗi xe ư thành 2 lớp là các tập con có cấu trúc
(P(I(x))=l) và các tập con không có cấu trúc (P(I(x))=0). xấp xỉ trên và xấp xỉ dưới của
mọi đối tượng xeU trong được định nghĩa là:
• LR(X) = {XG U| P(I(x))= 1 & v(I(x),X)= 1} {f)
• UR(X)={ xe UI P(I(x))=l& v(I(x),X)>0} (4)
Vấn đề cơ bản của việc sử dụng không gian dung sai là làm thế nào để xác định
được I, V và p cho phù hợp.
4. Thuật toán phân cụm bán giám sát dựa trên TRSM
Trước khi trình bày thuật toán, chúng tôi giới thiệu tóm tắt về không gian dung sai
(chi tiết xem [4],[6])
4.1. Không gian dung sai
Giả sử D = {dl, d2, dn} là tập các tài liệu và T={tl, là tập các từ chỉ
mục của tập tài liệu D. Trong TRSM, không gian dung sai được ký hiệu qua một vũ trụ của
tất cả các từ chỉ mục
U = (5)
Đe xác định được mối quan hệ giữa các từ chỉ mục trong các lớp, quan hệ dung sai
R được xác định là sự xuất hiện đồng thời của các từ trong tất cả các tài liệu từ tập D. Quan
hệ đồng xuất hiện của các từ chỉ mục giúp xác định mối quan hệ ngữ nghĩa và làm sáng tỏ
ý nghĩa thực sự của các từ trong ngữ cảnh của các tài liệu và việc tính toán trở lên đơn giản
và hiệu quả.
Giả sử fD(ti, tj) là số lượng các tài liệu trong D xuất hiện cả hai từ ti và tj. Hàm

là các từ chi mục của di:
ư.(rf,) = {í,E r|v(/,(/,,),rf,)> 0)
Để có cái nhìn trực quan hơn về lớp dung sai của các từ chỉ mục và xấp xỉ trên của
tài liệu ta đi xét 1 ví dụ gồm 10 tài liệu được biểu diễn bời các tà chỉ mục như trong bảng
2. Với ngưỡng đồng xuất hiện 0=2, sử dụng công thức (6) ta tính được lớp dung sai của các
từ chỉ mục là: I2(tl)={tl, t2, t5, tl6}, I2(t2)={tl, t2, t4, t5, t26}, I2(t4)={ t2, t4}, I2(t5)={
tl, t2, t5}, I2(t6)={ t6, t7 }, I2(t7)={t6,t7}, I2(tl6)={ tl, tl6}, I2(t26)={t2, t26}, với các từ
còn lại thì lớp dung sai chỉ gồm 1 phần tử là chính nó.
Tài liêu
Từ khóa Xâp xỉ trên
d,
Uĩ hĩ t3, Í4,
th hĩ ^3) U, U. t[6, Í26
d2
1?3 h, tg
Uĩ t?, tg,
- d3
th tsí ^10» t||, Ì2
t|» Í2, Í4, ts, t|0, tii, t|6, Í26
¿4
hi ^7» tl2j tl3> ti4
tóí t?) ti2, t|3, ti4
ds
hĩ t|5> U
tl) Í2, t4,ts, ÍỊ5, Í26
d6 t|í tl6) t|7í tig, t|9, Í20
tl, Í2, ts, t|6, t]7, t|8, ti9, Ì2Ồ
187
Một số vấn đề chọn lọc của Cổng nghệ thông tin và truyền thông, Hưng Yên, ¡9-20 tháng 08 năm 2010
d y

trên thuật toán Seeded - KMeans được giới thiệu ở trên; do vậy thuật toán đảm bảo hoạt
động tương đối nhanh (phù hợp với phân cụm kết quả online) trong khi vẫn đảm bảo được
chất lượng của các cụm. Việc sừ dụng không gian dung sai và xấp xỉ trên để tăng mối quan
hệ giữa các tài liệu và giữa tài liệu với cụm cho phép thuật toán phát hiện ra sự tương tự
khó phát hiện mà các thuật toán khác không làm được. Trong phân cụm kết quả tìm kiếm,
việc gán nhãn tốt cũng quan trọng như chất lượng nội dung cụm. Chúng tôi đã sử dụng các
chủ đề của tập dữ liệu giống để làm nhãn cho các cụm dữ liệu.
Thuật toán TRS-SK gồm 5 bước: Tiền xử lý tài liệu, xây dựng cách biểu diễn tài
liệu, tạo ra các lớp dung sai, phân CVUII, gán nhãn cho cụm. Dưới đây là các bước chính của
thuật toán.
4.2.1. Tiền x ử lý
Tiền xử lý dữ liệu văn bản trước khi đưa vào các thuật toán phân cụm là rất cần
thiết và có thể làm tăng hiệu xuất của thuật toán. Đầu tiên ta loại bỏ khỏi kết quả tìm kiếm
những ký tự không phải là chữ cái (ví dụ: $,@,.• •)> các thẻ HTML và các mã ký tự đặc biệt
188
Một so vấn đề chọn lọc của Công nghệ thông tin và truvền thông, Hưng Yên, Ĩ9-20 tháng 08 năm 2ỒỈỒ
như &amp, &quot, .Sau bước này ta sử dụng các thuật toán tách từ tiếng Việt để tách tài
liệu thu được thành các từ có nghĩa. Bước tiếp theo là loại bỏ các từ dừng (stop words là
những từ xuất hiện nhiều nhưng ko có giá trị trong việc phân cụm)
4.2.2. Xãy dự ng ma trận từ - tài liệu
Thuật toán TRSM sử dụng mô hình không gian vector để xây dựng ma trận từ - tài
liệu biểu diễn các tài liệu
Bảng đồng xuất hiện được xây dựng sau khi tập tài liệu đã qua pha tiền xử lí và nó
được trích chọn theo quy luật sau:
• Bỏ qua số, các từ có ít hơn hai kí tự và các từ xuất hiện trong câu hỏi truy
vấn vì chúng xuất hiện hầu hết trong các kết quả.
• Sử dụng bộ lọc để loại bỏ các từ có tần xuất thấp (nhỏ hơn 1 ngưỡng nào đó
cho trước) vì những từ này sẽ làm tăng số đặc tính của tài liệu.
Sau khi trích chọn ta xây dựng ma trận tò - tài liệu theo luợc đồ trọng sổ TF*IDF
(xem [6])

}
foreach(Ck){
Tính lại biểu diễn cụm Ri(
Until thỏa mãn điều kiện dửng
______
Bảng 3 - Thuật toán TRS-SK
Trong bước phân cụm này, với mỗi cụm CK ta xây dựng được biểu diễn cụm RK
theo qui tắc sau:
1. Khởi tạo RK=(Ị).
2. Các từ xuất hiện trong các tài liệu trong cụm với tần số cho phép (được điều
khiển bởi ngưỡng ơ) được thêm vào RX.
3. Chọn các từ có trọng số cao nhất từ các tài liệu trong cụm mà chưa có từ nào
được thêm vào RK để thêm vào cách biểu diễn cụm RK.
Trọng số của các từ ti trong Rk được tính là giá trị trung bình các trọng số của tất cả
Ằ Á .1* A . / •»
các lân xuât hiện trong các tài liệu của Ck:
(14)
Độ tương tự giữa các tài liệu và giữa các tài liệu với các cụm được tính theo độ
đo cosin
5 (^ ,y )=
J t -ỉ + í //
V - (15)
Việc áp dụng TRSM vào thuật toán phân cụm sẽ có 2 ưu điểm chính là:
1. Làm giảm các hệ số có giá trị bằng 0 khi ta biểu diễn các tài liệu bời các từ liên
quan đến nó trong các lớp dung sai.
2. Có khả năng phát hiện ra các tài liệu mà có ít từ chung (hoặc thâm chí ko có) với
tập các từ phổ biến.
190
Một sô vân đê chọn lọc cùa Công nghệ thông tin và truvên thông, Hưng Yên, ¡9-20 thảng 08 năm 2010
Thuật toán phân cụm mà chúng tôi áp dụng là thuật toán phân cụm bán giám sát

200 kết quả trả về thì các kết quả đó được phân vào 18 cụm trong đó nhiều nhất là các bài
viết thuộc chủ đề “Tư vấn sức khỏe”, tiếp theo là các chủ đề như “kiến thức giới tính”, “vi
tính”, “điện thoại”, “Người Việt trẻ”, Chúng tôi đã so sánh các kết quả đó với các
website gốc chứa các bài viết đó thì thấy việc phân cụm kết quả này đạt độ chính xác khá
cao so với các chủ đề của chúng trên các website gốc.
191
Một số vẩn đề chọn lọc cùa Công nghệ thông tin và truvền thông, Hung Yên, 19-20 tháng 08 năm 2010
Qua nhiều lần thử nghiệm chúng tôi thấy việc lựa chọn ngưỡng đồng xuất hiện của
các từ trong ứng dụng bằng 3 và ngưỡng tương tự giữa các tài liệu với các biểu diễn cụm
bằng 0.2 sẽ cho kết quả tốt nhất.
Phương pháp tiếp cận của chúng tôi phù hợp với xu hướng xây dựng các máy tìm
kiếm hay các trang web tổng hợp tin hiện nay vì chúng đều có các trang tin tổng hợp để
làm tập dữ liệu giống cho việc phân cụm kết quả tìm kiếm.
Kết luân
•
Báo cáo của chúng tôi đề xuất phương pháp áp dụng mô hình tập thô dung sai vào
thuật toán phân cụm bán giám sát Seeded-KMeans để phân cụm kết quả tìm kiếm web
tiếng Việt. Việc áp dụng mô hình tập thô dung sai với quan hệ dung sai là quan hệ đồng
xuất hiện của các từ trong tài liệu giúp phát hiện ra mối quan hệ giữa các từ trong tập kết
quả tìm kiếm làm tăng chất lượng phân cụm. Thuật toán Seeded-KMeans được sử dụng để
phân cụm kết quả với tập dừ liệu giống được thu thập tà các website tiếng Việt phổ dụng
kết hợp sử dụng phương pháp tách từ tiếng Việt để tách từ đã làm tăng chất lượng phân
cụm và sinh ra nhãn của các cụm kết quả chính xác hơn so với các phương pháp khác.
Chúng tôi dự định phát triển hoàn thiện ứng dụng của mình để sử dụng trong thực
tế, so sánh cách tiếp cận của chúng tôi với các phương pháp phân cụm khác trên tiếng Anh
đồng thời thử nghiệm với các tập dữ liệu lớn hơn để cải tiến thuật toán phân cụm sao cho
hiệu quả. Đó sẽ là cơ sở để hình thành một hệ thống tìm kiểm web theo nội dung.
Tài ỉiệu tham khảo
1] s. Basu, A. Banerjee and R. J. Mooney, (2002). Semi-supervised clustering by
seeding. In Proceedings of 19th International Conference on Machine Learning

nhằm tăng tốc độ thực hiện của thuật toán bằng việc thay thế các phép nhân,
chia bởi các phép dịch chuyển bít. Bên cạnh đó, bài bảo cũng trình bcty cơ sở
tocin học cho phương pháp mã hóa số học giúp cho việc tìm hiểu, nghiên cứu
phương pháp này trở nên dễ dcing. Phần tiếp theo của bài báo được trình bciy
như sau: mục 1 trình bảy một số định nghĩa và khái niệm, mục 2 nội dung thuật
íoán mã hỏa số học gốc, mục 3 thuật toán mã hóa sổ học cải tiến, mục 4 kết
qiủĩ thực nghiệm và mục 5 là kết luận.
1. Một số định nghĩa và khái niệm
Trong suốt bài báo này ta xem đoạn [0,D] là miền không gian và mọi điểm, mọi
đoạn thẳng đều nằm trong miền này.
1.1. Phép chiếu một điểm lên đoạn thẳng
1.1.1. Phép chiếu thu nhỏ đồng dạng
Hình chiếu y của X lên [a,b] (xem hình vẽ) được xác định theo công thức:
y -a - b-a n X D
x-0 D-O
hay
y = (1.1) a —
D y
Ta gọi y là ảnh của X lên [a,b] và ký hiệu:
y = [ a ,b ] ^ x (1.2)
193
Một sổ vấn đề chọn lọc của Công nghệ thông tin
V’ c)
truyền thông, Hưng Yên, 19-20 ihcing 08 nàm 2010
1.1.2. Phép biến đỏi ngirực
Khi biết hình chiếu y, thì X được xác định theo công thức:
b-a
và X eọỉ là nghịch ảnh của y theo [a,b] và ký hiệu;
X = [a,b]-> y (1.4)
1.2. Phép chiếu một đoạn thẳng lên một đoạn thẳng

2
] lên [a,b] luôn luôn thuộc [a,b] hay nói cách khác:
Ncu: [yi,y2] = [a,b] [X1,X2] thì [yi,y2] c [a,b] (1.9)
194
Một sô vân đê chọn lọc của Công nghệ thông tin và tniỵén thông, Hưng Yên, 19-20 tháng os năm 2010
1.3.3. Tỉnh chất chửa trong của phép biến đổi ngược
Néu
y eY
X = B ^ Y (X là nghịch ảnh của Y theo B)
thì
B-^y e X (nghịch ảnh của y theo B thuộc X)
2. Thuật toán mã hóa số học gốc
Trong mục này sẽ dùng phép chiếu thu nhỏ đồng dạng để mô tả thuật toán mã hóa
số học, dùng phép biến đổi ngược để diễn đạt thuật toán giải mã và sử dụng các tính chất
của phép chiếu để chứng minh tính đúng đắn của thuật toán giải mã. So với cách trình bày
về mã hóa số học gốc trong các tài liệu trước đây (ví dụ như [2] và [7]), cách trình bày và
cách chứng minh trong bài báo này ngắn gọn và dễ hiểu hơn.
2.1. T huật toán mã hóa
Để thực hiện thuật toán mã hóa số học, trước tiên cần xác định miền phân bố của
tập ký tự khác nhau của bản rõ.
2.1.1. Thống kê tần suất và xác định miền phân bố của các kỷ tự trong bân rõ
Vấn đề này được trình bày thông qua một ví dụ. Giả sử bản rõ là một chuỗi ký tự:
"CABAB" thì kết quả thống kê tần suất như sau:
STT
Ký tự
Tân suât
1
A 2
2
B 2

2.1.2. Ỷ tưởng của thuậ t toán mã hóa
Xem bản rõ là một chuỗi gồm n ký tự. Gọi kt[i] là ký tự thứ i của bản rõ tính từ trái
qua phải, i = l,2, ,n (trong ví dụ trên: kt[l] = ‘C’, kt[3] = ‘B’). Gọi Sk (k = 1,2, ,n) là
chuỗi con gồm k ký tự đầu tiên, tức Sk gồm các ký tự kt[l], kt[2], kt[k]. Với bản rõ như
trên thì các chuồi con là:
s, = "C" ; S2 = "CA" ;S3 = "CAB"; S4 = "CABA" ; S s = "CABAB"
Mỗi chuỗi con sẽ có miền mã là một đoạn thẳng (kín đầu trái, hở đầu phải) nằm
trong đoạn [0, D]. G ọi;
Ti = [low_code[i], hi_code[i]) là miền mã của chuỗi con Si
Các đoạn Ti được xác định như sau :
Với i= l, chuỗi s 1 gồm một ký tự, thì T1 chính là miền phân bố của ký tự này:
T, =P(kt[l])
low_code[l] = low_range[kt[l]] (2.1)
hi_code[l] = hi_range[kt[l]] (2.2)
Với i=2, ,n thì Ti được xác định theo công thức lặp:
T, = Ti., ^ P(kt[i]) (2.3)
(Ti là hình chiếu của P(kt[i]) lên Ti-i)
2.1.3. T huật toán mã hóa
Input:
n: độ dài theo ký tự của bản rõ
dãy ký tự của bản rõ kt[i] (i=l,2 ,n)
m: số ký tự của bảng phân bổ
low_range(ch[i]), hi_range(ch[i]) ứng với mỗi ký tự ch[i] trong bảng phân bố
(i=l, m)
Output:
- code; mã của bản rõ
Thuật toán:
low_code[l] = low_range[kt[l]];
hi_code[l] = hi_range[kt[l]];
for(i = 2; i < n; i++)

code[l] = code (2.7)
z[l] =g(code[l]) (2.8)
Với i=2, ,n thì
code[i] = P(z[i-1]) -> code[i-l] (2,9)
(code[i] là nghịch ảnh của code[i-l] theo [Iow_range(z[i-l]), hi_range(z[i-l])] )
z[i] = g(code[i]) (2.10)
2.2.3. Thuật toán giải mã
Input:
code: là mã của bản rõ
n; số ký tự của bản rõ
bảng phân bố của các ký tự khác nhau trong bản rõ (bảng 2)
Output:
z[i] với i=l,2,.,.,n
197
Một số vấn để chọn lọc cúa Công nghệ thông tin VCI truyền thông, Hưng Yên, J9'20 thảng 08 năm 2010
Thuật toán:
code[l] = code //theo (2.7)
z[ 1 ] = g(code[ 1 ]) //theo (2.8)
for(i=2; i < n; i++)
{
, {cocíe[i-\]-low_rang^z[i-\]])*D
hi_rang(ịz[i-l]]-low_rang^z[i-\]]
(2.11)
z[i] = g(code[i]) // xác định các ký tự tiếp theo
}
(Công thức (2.11) được xác định dựa vào (1.3), (1.6) và (2.9))
Nhận xét: Trong các công thức của thuật toán mã hóa và giải mã chứa giá trị cận
trôn và cận dưới của miền phân bố. Vì vậy bằng cách chọn các giá trị này một cách hợp lý
có thể làm giảm khối lượng tính toán của các thuật toán. Ý tưởng này sẽ được thực hiện
trong mục 3.

3. Thuât toán mã hóa số hoc cải tiến
• •
Trong các công thức (2.4) và (2.5) của thuật toán mã hóa và công thức (2.11) của
thuật toán giải mã phải thực hiện các phép nhân, chia trên các số lớn làm tốc độ tính toán
chậm, hạn chế khả năng ứng dụng của thuật toán này. Để giảm khối lượng tính toán, chúng
tôi đề xuất giải pháp thay các phép nhân, chia bàng các phép dịch bit. Điều này có thể thực
hiện được bằng cách chọn các miền phân bố một cách hợp lý.
3.1 T huật toán m ã hóa cải tiến
Chọn D và xác định bảng phân bố (bảng 2) như sau;
- D = 2* (3.1)
- low_range(ch[i]) = (i=l, ,m) (3.2)
- hi_range(ch[i]) - low_range(ch[i]) = (i=l, ,m) (3.3)
Trong đó s, h[i], k[i] cần thỏa mãn điều kiện:
2h[m]__^ < 2^
Với cách chọn trên thì:
hi_range(ch[i]) = (3.4)
Nhận xét: Với mỗi ký tự kt[i] của bàn rõ (1 < i < n), luôn tồn tại chỉ số duy nhất f(i)
trong khoảng từ 1 đến m sao cho:
kt[i] = ch[f(i)] ^ (3.5)
Sử diing hàm f(i), từ (3.2)-(3.4) có thể xác định miền phân bố của ký tự kt[i] bất kỳ
của bản rõ như sau:
low_range(kt[i]) = (i=l, ,n) (3.6)
hi_range(kt[i]) = (3.7)
Với cách chọn miền phân bố như các công thức (3.1), (3.2), (3.4) và dựa vào (3.6),
(3.7) thi (2.4)-(2.5) trong thuật toán mã hoá số học gốc được cải tiến như sau:
low_code[l] = Iow_range[kt[l]
hi_codc[l] = hi_rangc[kt[l]] ;
for(i=2; i<n; i++)
low_codc[i]=low_code[i-1 ]+(hi_codc[i-1 ]-low_code[i- l])»(s-h[f(i)])
hi_code[i]=low_code[i]+(hi_code[i-l]-low_code[i-l])»(s-h[f(i)])

Vậy tổng số phép toán cần thực hiện là:
256x size^xn phép nhân bit (3.11)
b. Thuật toán giải mã
Bằng cách phân tích tương tự ta suy ra tổng số phép toán cần thực hiện:
128x size ^Xn phép nhân bit (3.12)
3.3.2. Thuật toán m ã hóa số học cải tiến
a. Thuật toán mã hóa
Theo (3.8) và (3.9) trong mỗi bước lặp của thuật toán mã hóa cần thực hiện 3 phép
dịch bit trên các số nguyên có độ dài size byte. Mỗi phép dịch bit yêu cầu tối đa 8x size
phép gán bit. Vì vậy số phép toán cần thực hiện của n phép lặp là:
3x8x size xn = 24xsizexn phép gán bit (3,13)
200
Một số vấn để chọn lọc của Công nghệ thông tin và truyền thông, Hưng Yên, 19-20 tháng 08 năm 2010
b. Thuật toán giải mã
Bang cách phân tích tương tự ta suy ra tổng số phép toán cần thực hiện là:
16x sizexn phép gán bit (3.14)
3.2.3 So sánh độ p hứ c tạp của 2 phươ ng pháp
Troníỉ phương pháp mã hóa số học gốc chọn phép toán nhân bit làm phép toán cơ
sở, trong khi đó phương pháp mã hóa số học cải tiến chọn phép gán bit làm phép toán cơ
sở. Thực tế phép gán bit thực hiện nhanh hơn phép nhân bit. Trong trường hợp này để tiện
so sánh ta giả sử 2 phép toán này là tương đương về độ phức tạp. Khi đó từ các công thức
(3.11) và (3.13) thi tốc độ tính toán giữa 2 phương pháp có thể được so sánh qua phép
tính sau:
Sô phép tinh cùa thuật toán ni<5 hóa gỏc 256 X size^ X n
- 7

— ^ ^

— = 10.7 X siz e
Sỏ phép tính cùa thuật toán tìiâ hóa cài tiên 24 X size X n

A[l] = hi_code[l] - iow_code[l];
u[l] = h;
for(i=2; i< n; ++i)
{
A[i] = A[i-1] » (s-h);
u[i] = u[i-l] - (s-h);
low_code[i] = low_code[i-l] + (f(i)-l) « u[i];
hi_code[i] = low_code[i] + A[i];
}
Nhận xét: Điều kiện (3.18) chẳng những đảm bảo miền phân bố của các ký tự thuộc
0,D] mà còn cho phép các phép dịch chuyển trong thuật toán luôn thực hiện được (u[i]>0).
3.4.3. Thuật toán giải mã cải tiến
Với cách chọn miền phân bố theo (3.15)-(3.17) và để ý thêm rằng kt[i] = ch[f(i)] thì
thuật toán giải mã tại mục 2.2.3 được cải tiến như sau:
code[l] = code
z[ 1 ] = g(code[ 1 ]); //xác định được ký tự đầu tiên của bản rõ
for(i=2; i < n; i++)
{
code[i] = (code[i-1 ]«(s-h)) - (f(i)-1 ) « s
z[i] = g(code[i]) // xác định các ký tự tiếp theo
}
Nhận xét; Tại mồi bước trong thuật toán mã hóa 3.4.2 chứa 2 phép dịch bit vì vậy
tốc độ của thuật toán này nhanh hơn tốc độ của thuật toán mã hóa cải tiến tại mục 3.1.
4. Kết quả thử nghiệm trên máy
Đc cài đặt các thuật toán chúng tôi đã sử dụng kiểu nguyên lớn size byte (size<200)
từ [1], với size được chọn linh hoạt bời người sử dụng (ở đây chọn size = 25). Bản rõ được
chia thành các khối với độ dài 25-30 ký tự (ứng với size =25). Viộc mã hóa được tiến hành
202
Một sổ vấn dề chọn lọc cùa Công nghệ thông tin vc) truyền thông, Hưng Yên, 19-20 tháng 08 năm 2010
theo từng khối. Chương trình được viết bàng ntỊÔn ngữ VC++ 6.0, được cài đặt cho thuật

128 680000,83 0.003 680000,56 0,028
3 4418 136 1700000,23 0,017
1700000,03 2000
4
8856 136
-
0,027
-
2000,13
5
22240 144
-
0,061
-
2400,29
6 32233 144
-
0,081
-
2700,15
7
232409 256
-
7000,579
-
8000,266
Trong các kết quà trên bản rõ trong dòng thứ 7 là Đe thi tuyển sinh đại học năm
2010 môn Hóa học. Các ô để trống trong các dòng từ 4 đến 7 không có kết quả do thời
gian chạy máy quá lâu.
Kết luận

[4] Hai Mei, Zhang Jian-jun, NI Xing-fang, An improved Arithmetic Coding
Algorithm Journal of Shanhai University, 2004.
[5] Rissanen J.J, Generalized kraft inequality and arithmetic coding, IBM J. Res.
Develop, 1976.
[6] Rissanen JJ, Arithmetic codings as number representations, Acta Polytech.
Scand. Math, 1979.
[7] Rissanen J J and Langdon G.G, Arithmetic coding, IBM J. Res. Dev, 1979.
[8] Witten I.H, Radford M. Neal, and John G. Cleary, Arithmetic coding for data
compression. Communications of the ACM, No.6, Vol.30, June 1987
204
Một số vắn để chọn Ịọc của Công nghệ thông tin và truvền thông, Hưng Yên, 19-20 thảng 08 năm 2010
MỘT SỐ CẢI TIẾN THUẬT TOÁN SONG SONG PHÂN
CỤM DỮ LIỆU LỚN, NHIÈƯ CHIÈU DựA TRÊN LƯỚI
THÍCH NGHI PMAFIA
Nguyễn Mạnh Hùng, Phạm Thị Bích Vân, Đỗ Thị Mai Hường
Khoa Công nghệ thông tin, Học viện Kỹ thuật Quân sự
Phân cụm dữ liệu trong không gian dữ liệu lớn, nhiều chiều và không đầy đủ là
một trong những bài toán rất quan trọng của lĩnh vực khai phả dữ liệu. Đã có
nhiều nhà nghiên cínt quan tâm và để xuất các thuật toán giải quyết vấn đề này
như: CLIQUE, MAFIA, pMAFIA, Trong bài báo này, chúng tôi đề xuất
thuật toán pMAIFA-TID trên cơ sở cải tiến thuật toán song song phân cụm dựa
trên hỉới thích nghi pMAFIA. Thuật toán pMAFIA-TID tăng tốc độ thực hiện
so với thuật toán pMAFIA trên cơ sở bổ sung một sổ điểm sau đây:
- Không duyệt qua dữ liệu nhiều lần để đếm các bản ghi thỏa mãn khối mật độ
cao dự kiến (CDU- candỉdate dense unit) CDUij.
- Đem các bản ghi thỏa mãn CDUij thông qua sổ bản ghi thỏa mãn khối mật
độ cao (Dư - dense unit) DUi và cũng thỏa mãn DUj.
- Trên mỗi bộ xử lý sau khỉ xây dựng được một CDU s ẽ tiến hành loại lặp cục
bộ luôn, sau đó mới tổng hợp và loại lặp toàn cục.
Kết quả thử nghiệm trên bộ dữ liệu về bệnh xơ vữa động mạch STULONG cho