Tìm kiếm mờ và ứng dụng tìm kiếm thông tin trong các văn bản nén

ật toán so đơn mẫu chính xác, xấp xỉ theo tiếp cận mờ sẽ được đưa ra ở chương 2. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 27 Chương 2. BÀI TOÁN SO MẪU THEO CÁCH TIẾP CẬN OTOMAT MỜ 2.1. Bài toán so mẫu chính xác 2.1.1. Phát biểu bài toán Cho xâu mẫu P độ dài m (P = P1P2 ... Pm) và xâu đích S độ dài n (S = S1S2 ... Sn) trên cùng bảng chữ A. Tìm tất cả các vị trí xuất hiện của mẫu P trong xâu S. Từ việc giải bài toán trên dễ dàng thống kê được tần suất xuất hiện mẫu P trong một văn bản. 2.1.2. Độ mờ của mô hình Bài toán đặt ra ở đây là tìm kiếm chính xác mẫu, nhiều lần lặp mẫu. Độ mờ là một giá trị nguyên thuộc khoảng [0,...,m] cho biết độ dài của khúc đầu dài nhất của mẫu P đã xuất hiện trên S. Đây cũng có thể xem như một mô hình “lỗi”, rất phù hợp với tìm kiếm xấp xỉ khúc đầu trong các từ điển lớn. Định nghĩa 2.1. Cho xâu mẫu P độ dài m và xâu đích S độ dài n. Độ mờ xuất hiện mẫu P trên S tại vị trí j là giá trị nguyên   0 thoả mãn: -  = 0 nếu Sj  P1 -  là số lớn nhất sao cho P1P2 ...P = Sj-+1Sj-+2..... Sj Trong các thuật toán so mẫu theo tiếp cận mờ ở đây, mỗi khi đọc được một kí tự Sj sẽ cho biết ngay độ mờ xuất hiện mẫu. Giả sử đã biết độ mờ tại vị trí j là , khi đọc được ký tự Sj+1 = a, độ mờ mới sẽ được xác định như một hàm kiến thiết của cặp (,a). Gọi AP là tập các kí tự có trong mẫu P, # là một kí tự đại diện cho các kí tự thuộc A nhưng không xuất hiện trong P. Khi đó độ mờ được xác định thông qua hàm TFuzz: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 28 TFuzz: {0,1, ...,m} × (AP  #)  {0,1, ...,m} (,a)  ‟ = TFuzz (,a)  gọi là độ mờ cũ, ‟ gọi là độ mờ mới khi gặp kí tự a. Hàm TFuzz được xây dựng dựa vào bảng next như trong thuật toán KMP tìm nhiều lần lặp mẫu đã trình bày ở Mục 1.5.1. Dựa vào Định nghĩa 1.3, bằng phương pháp quy nạp, ta nhận được ngay kết quả sau: Bổ đề 2.1. Giả sử độ mờ xuất hiện mẫu P tại vị trí Sj là , khi đó độ mờ mới ’ tại Sj+1 được xác định bởi một hàm ’ = TFuzz (, Sj+1), với TFuzz được xác định như sau: + TFuzz (0, ) =      1 1 ,1 ,0 Px Px + TFuzz (i, #) = 0, i = 0..m i+1, nếu  = Pi+1    mi xiTFuzz ..1 , j, j  i và j là số lớn nhất sao cho P1P2...Pj-1 = Pi-j+2Pi-j+3...Pi và Pj = , nếu   {Pi+1, #} Việc xác định j dựa vào bảng next và một vòng lặp. 2.1.3. Thuật toán KMP mờ 2.1.3.1. Otomat so mẫu Do ý nghĩa của độ mờ là độ dài khúc đầu dài nhất của mẫu P đã xuất hiện trên S nên otomat sẽ có tập trạng thái là tập số nguyên {0, 1,..., m}. Hoạt động của otomat mờ so mẫu sẽ như sau: - Khởi đầu con trỏ trên S là j = 0. Tại đó chưa xuất hiện khúc đầu nào của mẫu nên trạng thái khởi đầu của otomat là q0 = 0. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 29 - Duyệt S, mỗi lần một kí tự, bắt đầu từ S1. Giả sử trạng thái của otomat là q thì khi đọc được kí tự Sj, trạng thái mới (ứng với vị trí j trên S) sẽ là q‟ = (q,Sj) ( là hàm chuyển của otomat). - Tại vị trí j trên S, nếu trạng thái của otomat là q, có nghĩa khúc đầu dài nhất xuất hiện trên S của P có độ dài q. Nếu q = m, báo hiệu một lần xuất hiện mẫu, bắt đầu từ vị trí j -m+1. Mô hình otomat mờ cần được xây dựng một cách thích hợp để đáp ứng được yêu cầu sánh mẫu như trên. Định nghĩa 2.2. Otomat mờ so mẫu là bộ A(P) = (A, Q, q0, , F) trong đó: + Bảng chữ vào A = AP  {#} + Tập trạng thái Q = {0,1,...,m} + Trạng thái khởi đầu q0 = 0 + Trạng thái kết thúc F = m. + Hàm chuyển : Q  A  Q (q,a) = TFuzz (q,a), với hàm TFuzz được xác định như trong Bổ đề 2.1. 2.1.3.2. Tính đúng đắn của thuật toán Định lý 1.1. Cho xâu mẫu P độ dài m. A(P) là otomat mờ được xác định theo định nghĩa 2.2. Giả sử q = (q0, w), w  A * . Nếu q = F thì P là khúc cuối của w. Chứng minh. Dựa vào Bổ đề 2.1. và định nghĩa 2.2., tiến hành quy nạp theo độ dài của từ w, dễ dàng nhận được điều phải chứng minh. 2.1.3.3. Thuật toán Khi cài đặt thuật toán cần lưu ý lựa chọn cấu trúc dữ liệu phù hợp để có thể truy nhập nhanh chóng trong bảng TFuzz. Gọi A[0..k] là mảng lưu giữ bảng chữ A của otomat, trong đó k là số kí tự phân biệt trong mẫu P. Màng được sắp theo chiều tăng của các kí Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 30 tự và A[k] = „#‟. Để thuận tiện khi truy nhập đến các chữ cái trong A, có thể sử dụng mảng index xác định vị trí của chữ trong bảng. i, nếu c = A [i] index [c] = k, nếu c  {A[0], A[1], ...A[k-1]} TFuzz là mảng [0..m, 0..k], trong đó TFuzz [i, j] là độ mờ mới khi độ mờ i gặp kí tự x có index [] = j. Khi đó chi tiết thuật toán tạo lập bảng TFuzz và tìm kiếm dựa vào bảng TFuzz sẽ như sau: Thuật toán 2.1. Tạo lập TFuzz procedure initTFuzz() var i, j, t: integer; begin for i: = 0 to m do TFuzz [i,m]:=0; for j: = 0 to k do TFuzz [0, j] := 0; TFuzz [0, index [P1]]:=1; for i: = 0 to m do for t: = 0 to k-1 do begin if i = m then j:= next [i+1] elsse j:=i+1; while (j > 0) and (Pj  A([t]) do j:=next [j]; TFuzz [i, index [A[t]]:= j; end; end; Thuật toán 2.2. Tìm kiếm mẫu dựa vào bảng TFuzz procedure FPM(); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 31 var j, counter: integer; fuz: array [1..50] of integer; {* độ mờ*} begin j :=1; counter :=0; fuz[0] = 0; while (còn đọc được Sj) do begin fuz [j] = TFuzz [fuz[j-1], index [Sj]]; if fuz [j] = m then begin counter :=counter+1; Ghi nhận vị trí j-m+1; end; end; {while} Ghi nhận counter; if counter = 0 then Ghi nhận vị trí 0; end; Ví dụ 2.1. Với mẫu P = aababaab, A = {a, b, #}, AP = {a,b}. Bảng TFuzz được tính toán dựa trên mảng next (ví dụ 1.1, Mục 1.5.1) cho kết quả như sau: A Q a b # 0 1 0 0 1 2 0 0 2 0 3 0 3 4 0 0 4 2 5 0 5 6 0 0 6 7 0 0 7 2 8 0 8 4 0 0 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 32 Quá trình so mẫu trên dòng dữ liệu S = aabaababaababaababaab sẽ như sau: j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 S a a b a a b a b a a b a b a a b a b a a b j 1 2 3 4 2 3 4 5 6 7 8 4 5 6 7 8 4 5 6 7 8 ghi nhận ghi nhận ghi nhận 11-8+1=4 168+1=9 21-8+1=14 2.1.3.4. So sánh KM P và thuật toán KMP mờ Hình 2.1. Dịch chuyển con trỏ trên mẫu Giả sử đã xuất hiện khúc đầu độ dài i-1 của P trên S, tính tới vị trí j, có nghĩa đã có P(i - 1) = sufi - 1(S(j - 1)) hay độ mờ tại vị trí j - 1 là j-i = i - 1. Xét ký tự Sj, có thể xảy ra hai khả năng: + Trường hợp 1: Sj = Pi (hay độ mờ tại vị trí j là j = i) Tăng i, j lên 1. Với trường hợp này tốc độ thao tác của thuật toán KMP như trong tiếp cận mờ. + Trường hợp 2: Sj  Pi (hay độ mờ tại vị trí j là j  i) Trong KMP, con trỏ j trên S giữ nguyên, chỉ dịch chuyển con trỏ trên mẫu (dùng lệnh i:= next[i] (Hình 2.1). Vì vậy phải mất thời gian dịch chuyển theo bảng next, thậm chí nhiều lần. Ví dụ như: ? next [i] P P S i i j-i = i - 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 33 Với P = aababaab, sử dụng bảng next (ví dụ 1.1, mục 1.5) để tìm sự xuất hiện của mẫu trong dòng ký tự S như sau: S = a a c ... j = 3 P = a a b a b a a b i = 3 dịch lần thứ nhất a a b a b a a b i = next[i] = 2 dịch lần thứ 2 a a b a b a a b i = next[i] = 0 Ta thấy có 2 lần dùng i:= next[i] và 2 lần so sánh Sj và Pi (i khác nhau). Nói chung có thể xảy ra nhiều lần dùng next trong khi con trỏ trên S vẫn giữ nguyên. Điều này làm chậm đáng kể so với tiếp cận mờ: mỗi lần nhận một ký tự Sj là một lần điều chỉnh giá trị mờ theo otomat: j = TFuzz (j-1, Sj). Lệnh này thực hiện rất nhanh nếu TFuzz được biểu diễn dưới dạng một mảng và được tính toán cẩn thận trước theo thông tin trên mẫu P. Kết quả sau so sánh tốc độ thực hiện việc tìm sự xuất hiện mẫu P trong tệp dữ liệu lớn S theo hai thuật toán KMP và tiếp cận mờ trên máy PC IBM tốc độ 233MHz. Mẫu P Kích thước tệp S TKMP TFuzzy-KMP 1) aababcab 1400 KB 17% s 11% s 2) MDSVF6V 140.000 KB 35 s 30 s 3) bacabccaa 1200 KB 16% s 10% s 4) S068FAB50 140.000 KB 37 s 30 s 2.1.4. Thuật toán KMP - BM mờ 2.1.4.1. Ý tưởng của thuật toán Trong thuật toán Boyer - Moore (BM), các ký tự trên mẫu P được duyệt từ phải sang trái, bắt đầu từ Pm. Tại thời điểm gặp ký tự không trùng khớp, chẳng hạn Pi = a còn Sj = b, khi đó sẽ quyết định dịch con trỏ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 34 trên mẫu. Phép dịch chuyển ứng với mỗi ký tự trên P, nếu sự không trùng khớp xảy ra ở đó, được xác định trong bước tiền xử lý mẫu P. Trong thuật toán “ký tự không khớp” này của BM, có một trường hợp cho phép dịch chuyển tốt nhất (xa nhất) là khi ký tự b không xuất hiện trong mẫu P. Từ chi tiết này, kết hợp với kiểu sánh mẫu như trong KMP, ta sẽ có một “thuật toán theo tiếp cận mờ tổng quát kiểu KMP và BM”, trong đó độ mờ vẫn được tính toán dựa trên hàm TFuzz, đồng thời sẽ có những bước nhảy dài trên xâu đích, đem lại hiệu quả tìm kiếm cao. Ý tưởng của thuật toán này là [11]: gọi ptr là con trỏ trên xâu đích S (khởi đầu ptr = 0 và độ mờ tại đó bằng 0 báo hiệu chưa tìm thấy mẫu). Mỗi lần xét một khối w gồm m + 1 ký tự liên tục trên S, bắt đầu từ vị trí ptr, ta gọi khối này là “khối ký tự quan sát” và ký hiệu wi là ký tự thứ i trong w (với w1 = Sptr). Dựa trên bảng TFuzz, tính độ mờ xuất hiện mẫu khi gặp ký tự w1 (hay chính là Sptr), ký hiệu độ mờ này là n1, đồng thời xác định bước nhảy tiếp theo để từ đó sẽ xét khối ký tự w mới, ký hiệu bước nhảy là n2. Nếu n1 là độ mờ tại Sptr thì có nghĩa sufn1(S(ptr)) = P(n1) (Hình 2.2). Xảy ra các khả năng sau: + Nếu n1 = m, chứng tỏ đã xuất hiện mẫu bắt đầu từ vị trí ptr - m + 1 trên S. Để không bỏ sót sự xuất hiện lồng nhau của mẫu, đặt n2 = 1. + Nếu n1 lớn hơn độ mờ tại vị trí được xét trước vị trí ptr, có nghĩa đang có hy vọng tìm thấy mẫu nên n2 = 1. + Trong các trường hợp còn lại của n1, chỉ mới xuất hiện khúc đầu P(n1) khớp với khúc cuối độ dài n1 của S(ptr). Nếu việc khớp mẫu thành công với khối ký tự quan sát w, thì ký tự Pm sẽ khớp với ký tự Sptr+m-n1 (hay w1+m-n1). Do đó, nếu Sptr+m-n1 không phải là một ký tự xuất hiện trong P thì có thể thực hiện bước nhảy xa để đọc w mới bắt đầu từ vị trí ptr+m- n1+1 trên S mà vẫn đảm bảo không bỏ sót sự xuất hiện nào của mẫu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 35 Hình 2.2. Ý tưởng chung của thuật toán KMP-BM mờ 2.1.4.2. Otomat mờ so mẫu Định nghĩa 2.3. Cho P là xâu mẫu độ dài m trên bảng chữ A. Ap là bảng các ký tự xuất hiện trong P. Otomat mờ so mẫu là A(P) = (Ak, Q, q0, F, ), trong đó: + A k là bảng chữ vào, mỗi chữ là một xâu ký tự độ dài k trên A, k=m+1 + Q là tập hữu hạn các trạng thái, Q = {q=(n1,n2)| n1, n2  N, 0  n1  m, 1  n2  k}  n1 gọi là độ mờ tại vị trí đang xét  n2 gọi là bước nhảy tiếp theo vị trí đang xét + q0 là trạng thái khởi đầu, q0 = (0,1) + F là trạng thái kết thúc, F = (m,1) + Hàm chuyển : Q × Ak  Qs (q, w)  q‟ = (q, w) Với q = (n1, n2) thì q‟ = (n1‟, n2‟) được xác định như sau:  Nếu n2 > 1 thì đặt n1 = 0  Tính n1‟ = TFuzz (n1, w1)  Nếu n1‟ = m hoặc n1‟ > n1 thì n2‟ = 1, ngược lại (n1‟ < m và n1‟  n1) thì xét: Nếu w1+m-n1‟  Ap thì n2‟ = 1, ngược lại n2‟=1+m-n1‟ ptr P(n1) ptr+m-n1 1+m-n1 m+1 S Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 36 Hoạt động của otomat mờ so mẫu như sau: Cho mẫu P độ dài m và xâu đích S độ dài n trên bảng chữ A. A(P) là otomat được xác định theo định nghĩa 2.3. Ta sẽ dùng otomat A(P) để đoán nhận tất cả các vị trí xuất hiện mẫu P trong xâu S và tổng số lần xuất hiện mẫu. Thuật toán cơ bản dựa trên otomat được mô tả như sau: Thuật toán 2.3. Ta dùng các ký hiệu: + j là con trỏ quan sát trên S + q.n1, q.n2 là hai thành phần của trạng thái q + w là khối ký tự quan sát bắt đầu từ vị trí j trên xâu đích S, giả sử đã bổ sung thêm m ký tự # vào cuối S. + qold là trạng thái của otomat tại vị trí trước khi đọc w + q là trạng thái otomat sau khi tác động w, q = (qold, w) + Counter là biến đếm số lần xuất hiện mẫu. Bước 1: Khởi tạo j: = 0; counter := 0; qold.n1 :=0; qold.n2 :=1; Bước 2: While j  n do j: = j + qold.n2 Đọc khối ký tự quan sát w; {w1 Sj} {Tính q = (qold, w)} if qold.n2 > 1 then qold.n1:= 0; endif; q.n1: = TFuzz (qold.n1, w1); q.n2: = 1; if q.n1= m then Ghi nhận vị trí xuất hiện mẫu là j - m + 1; Counter: = counter + 1; else if q.n1 < m and q.n1 < qold.n1 then Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 37 if w1+m-q.n1  Ap then q.n2: = 1+m-q.n1; endif; endif; endif; qold := q; endwhile; 2.1.4.3. Thuật toán 2.4 procedure GFSearching (); {tìm kiếm mẫu dựa trên định nghĩa 2.3} var apr: array [1..N] of integer; counter, j, n1, n2, n1’, n2’: integer; begin j:= 0; n1:= 0; n2 := 1; while j <= n do begin j := j + n2; if n2 > 1 then n1:= 0; n1’ := TFuzz [n1, index [S[j]]]; n2’: = 1; if n1’ = m then begin counter := counter + 1; apr[counter]:= j - m + 1; end else if n1’ < m and n1’ <= n1 then begin if j + m - n1’ > n then return; if index [S[j + m - n1’]] = k then n2’ : = 1 + m - n1’; end; n1:=n1’; n2: = n2’; end; end; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 38 2.2. Bài toán so mẫu xấp xỉ 2.2.1. Đặt vấn đề Để tìm kiếm xấp xỉ, cần sử dụng một hàm khoảng cách (distance function) đo độ tương tự giữa hai xâu. Tương tự ở đây được hiểu là giữa hai xâu kí tự có một vài sai khác ở những lỗi có thể nhận ra bằng mắt thường, không xét về khía cạnh ngữ nghĩa (OCR - optical character recognition errors), chẳng hạn “Việt Nam” và “Việt Nan” hay “Việtt Nan”,... Có thể kể ra một số kỹ thuật phổ biến đo độ tương tự giữa hai xâu: xâu con chung dài nhất, dãy con chung dài nhất, khoảng cách soạn thảo (Edit Distance). Các kỹ thuật trên chủ yếu chỉ hiệu quả khi có những sai khác về mặt chính tả: có sự bổ sung, xoá hay thay thế một số kí tự. Trong nhiều tình huống, những kỹ thuật này chưa đáp ứng đầy đủ yêu cầu thực tế, như khi cần tìm kiếm theo tên người nước ngoài (chẳng hạn “christian Charras” và “Charas C”), khi có sự sai khác do biến đổi hình thái từ, cấu trúc câu (“approximate searching” và “search approximately”), một số trường hợp thứ tự ghép từ khác nhau nhưng mang ngữ nghĩa giống nhau (“toán logic” và “logic toán”) hoặc do thứ tự sai song vẫn hiểu được đúng nghĩa (“toán giải tích” và “giải tích toán”,...). Phương pháp xác định độ tương tự giữa hai xâu kí tự theo “độ gần tựa ngữ nghĩa” được đề xuất trong luận văn sẽ đáp ứng nhu cầu tìm kiếm như trên. Xét một tình huống khác. Khi ứng dụng trong thực tế, mỗi từ theo nghĩa thông thường có thể xem là một kí tự hình thức. Chẳng hạn câu “bạn Minh giỏi Toán” được xem là một „xâu‟ gồm 4 „kí tự‟, có thể hình thức hoá là P = derq và S là “Ở trường tôi bạn Minh được đánh giá là một trong những sinh viên học Toán giỏi nhất", hình thức hoá là S = abcdefghiklmnopqrs. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 39 Tính độ tương tự giữa hai xâu bằng các kĩ thuật trên được kết quả như sau: + Độ dài dãy con chung dài nhất: 3, độ tương tự có thể xem là 3/18 + Độ dài xâu con chung dài nhất: 2, độ tương tự có thể xem là 2/18 + Khoảng cách Levenshtein: 14. + Khoảng cách Hamming: 18 (đúng bằng độ dài xâu S). Độ tương tự giữa hai xâu kí tự P và S theo những độ đo kinh điển kể trên là rất nhỏ, mặc dù hai xâu rất gần nhau về mặt ngữ nghĩa. Để đáp ứng nhu cầu tìm kiếm trong những tình huống như trên, một mô hình lỗi phản ánh độ tương tự giữa hai xâu kí tự là “Độ bảo toàn thứ tự xuất hiện các kí tự” được đề xuất. Do độ tương tự xác định theo hai cách này phản ánh được độ gần gũi ngữ nghĩa giữa hai xâu, xét về mặt thống kê, nên được gọi là “độ tương tự tựa ngữ nghĩa”. Một mô hình lỗi kinh điển là dựa vào độ dài khúc con chung dài nhất song với cách tiếp cận otomat mờ được đề xuất ở đây sẽ đem lại một thuật toán nhanh, đặc biệt hiệu quả khi cần so mẫu P với rất nhiều xâu S. 2.2.2. Bài toán Bài toán được phát biểu: Cho xâu nguồn P độ dài m và xâu đích S độ dài n. Xác định dộ tương tự giữa hai xâu P và S. Bài toán này có thể coi là cốt lõi để cài đặt tính năng tìm kiếm xấp xỉ tựa ngữ nghĩa trong cơ sở dữ liệu và trong các hệ thống trích rút văn bản. Trường hợp S là một dòng dữ liệu văn bản (trong các máy tìm kiếm của hệ thống khai phá text, khai phá web,...), xâu mẫu P thường ngắn còn xâu đích S dài hơn rất nhiều so với P nên để phản ánh ngữ nghĩa được tốt cần phải chặt khúc dòng dữ liệu S và sánh từng khúc với P Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 40 (chẳng hạn, việc ngắt câu có thể xem là một cách chặt khúc). Khi đó độ tương tự sẽ được tổng hợp từ các kết quả so sánh P và các khúc của S. Khi áp dụng trong các hệ thống xử lý văn bản, rất hay gặp những lỗi nhỏ về mặt chính tả (như: “Việt Nam” và “Việt Nan”, “vật lý” và “vật lí” ...) hoặc do dùng các từ đồng nghĩa hay có nghĩa tương tự nhau (như „yêu‟ và „thích‟, „mê‟,...) do sự biến đổi về hình thái từ (trong một số ngôn ngữ: Anh, Pháp, ... “approximate” và “aproximately”). Để đáp ứng nhu cầu tìm kiếm được tốt hơn, có thể dùng các thuật toán tìm kiếm xấp xỉ nhưng tính tới độ tương tự của các kí tự, về mặt chính tả hoặc về mặt ngữ nghĩa. Khi đó khái niệm “xuất hiện” hay “thuộc xâu P” của một kí tự c được hiểu như sau: - Sử dụng một hàm đo độ tương tự với ngưỡng mờ  nào đó do người sử dụng chọn. - Tìm kí tự hình thức trong P có độ tương tự cao nhất so với c và nằm ở bên trái nhất. - Nếu độ tương tự đó lớn hơn ngưỡng  thì coi như c chính là kí tự tương ứng trên P, nếu không thì coi như c không xuất hiện trên P. 2.2.3. Độ tương tự dựa trên độ dài khúc con chung của hai xâu 2.2.3.1. Phát biểu bài toán Bài toán: Cho xâu mẫu P = P1P2 ...Pm (độ dài m) và xâu đích S = S1S2 ... Sn (đo độ dài n) trên bảng chữ A. Tìm khúc con chung dài nhất giữa hai xâu P và S. Bài toán có thể hiểu là tìm khúc con dài nhất của P xuất hiện trên S. Để giải quyết bài toán, trước hết ta đưa vào một số ký hiệu. Cho bảng chữ A, với mỗi xâu u = u1u2...uk, ui A: + prefm(u) = u1u2..um (hay gọn hơn là u(m), là khúc đầu gồm m chữ của u. + sufm(u) = uk-m+1uk-m+2...uk là khúc cuối gồm m chữ của u. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 41 + Quy ước pref0(u) = suf0(u) =  (từ rỗng) + Với hai số tự nhiên f, d, ||u||  d  f  0, đặt u(f,d) = suff(prefd(u)) là khúc cuối độ dài f của một khúc đầu gồm d kí tự của u. Quy ước u(0,d) = . + Với mỗi xâu y là khúc con của u, đặt lid(y,u) = (|y|, Min {dN| f  0: u(f,d) = y}). + Cho hai xâu u, v, kí hiệu lfact(v, u) là khúc cuối y dài nhất của v mà y là khúc con nào đó của u, độ dài của xâu y như vậy được ký hiệu là lfuz(v, u). Ví dụ 2.2. Cho u = drabcgaba, pref6(u) = drabcg, suf2(drabcg) = cg, do vậy u(2,6) = cg, lid(ab, u) = (2,4) vì ab là khúc con trái nhất của u kết thúc tại vị trí 4 trên u và ab có độ dài 2. Cho v = ghbacabc, lfact(v,u) = abc, lfuz (v,u) = 3, lfact (u,v) = ba, lfuz(u,v) = 2. Với xâu P độ dài m đã cho, trên các cặp số (f,d), với m  d  f  0, xác định một quan hệ tương đương như sau: (f,d) tương đương với (f‟,d‟) nếu P(f,d) = P(f‟,d‟) (khi đó hiển nhiên f = f‟). Lớp tương đương của một cặp (f,d) được kí hiệu là [f,d]. Cặp số (f,d) được gọi là có nghĩa (với P) nếu (f,d) là cặp có d nhỏ nhất trong lớp, nghĩa là có khúc con y của P sao cho lid(y,P) = (f,d). Ví dụ 2.3. Cho u = drabcgaba, các cặp (2,4), (2,8) tương đương vì u (2,4) = u(2,8) = ab, cặp (f,d) = (2,8) là không có nghĩa vì y = ab có vị trí kết thúc trái nhất trên u là ở vị trí 4, không phải ở vị trí 8 mặc dù u (2,8) = y = ab. Phương pháp giải quyết Độ mờ xuất hiện mẫu P tại vị trí j trên S là lfuz(S(j),P) (chính là độ dài khúc cuối dài nhất w của S(j) mà w là khúc con nào đó của P). Bản chất thuật toán cần được xây dựng là: duyệt S từ trái sang phải, ở vị trí thứ j, sau khi đọc được kí tự Sj, cho biết ngay cặp giá trị (f,d) có nghĩa Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 42 của P, sao cho P(f,d) = lfact (S(j), P), do đó f = lfuz (S(j), P). Sử dụng biến LenMax để đánh dấu độ dài của khúc con dài nhất tìm được, tính tới vị trí j trên S. Sau khi duyệt xong S, LenMax cho biết độ dài khúc con chung dài nhất của P và S. Thuật toán 2.4 (Mục 2.2.3) được xây dựng dựa trên một mô hình otomat mờ sẽ đáp ứng được yêu cầu trên. Để xây dựng thuật toán chi tiết, sau đây ta sẽ xét hai hệ hình thức otomat, hệ hình thức thứ nhất đóng vai trò bổ trợ nhằm giúp thể hiện bản chất của hệ thức sau. 2.2.3.2. Otomat so mẫu Định nghĩa 2.4. Otomat trạng thái các khúc con của P có: + Bảng chữ vào A = Ap {#}, Ap gồm các ký tự xuất hiện trong mẫu P và ký tự #  Ap đại diện cho các ký tự không có mặt trong P, + Tập trạng thái là tập tất cả các khúc con của P, mỗi trạng thái là một khúc con của P (bao gồm cả xâu rỗng), + Với mỗi chữ a, mỗi khúc con u của P, hàm chuyển T cho bởi: T(u,a):= lfact(ua,P) Ta mở rộng tác động cho xâu w=a1a2...ak tuỳ ý T(u,w):= T(..T(T(T(u,a1),a2),a3),...ak), quy ước T(u, ) = u. Ví dụ 2.4. P = bcgabcdbabed T(ab, c) = abc, T(ab, e) = abe, T(ab, z) = , T(ab, zebcd) = bcd. Dựa vào các tính chất đã được chứng minh trong [11], chúng ta có thuật toán sau: Thuật toán 2.5. Tìm khúc con chung dài nhất giữa hai sâu Vào: Mẫu P độ dài m; xâu đích S độ dài n Dựa vào thông tin trên P, đã xây dựng otomat mờ so mẫu với hàm chuyển TFuzz. Ra: Khúc con chung dài nhất giữa P và S Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 43 + LenMax: độ dài của khúc con chung dài nhất + LF_P: vị trí (kết thúc) xuất hiện trên P + LF_S: vị trí (kết thúc) xuất hiện trên S Phương pháp (f,d) := (0,0); f_max := 0; LenMax := 0; LF_P := 0, LF_S := 0; for j:=1 to n do (f’,d’) := TFuzz((f,d),Sj); (f,d):= (f’,d’); if f > f_max then f_max := f else {đã tìm được một khúc con dài nhất của P độ dài f_max và là khúc cuối của S(j)} if LenMax < f_max then LenMax := f_max; LF_P := d; LF_S := j; endif; f_max := f; endif; endfor; Return(LF_P, LF_S, LenMax); 2.2.4. Độ gần tựa ngữ nghĩa 2.2.4.1. Ý tưởng về độ gần Độ gần của xâu S so với xâu P được xác định thông qua số khúc con của P xuất hiện trong S. Bài toán: Cho xâu kí tự P (xâu nguồn hay mẫu) độ dài m (P = P1P2..Pm) và S (xâu đích) độ dài n (S = S1S2...Sn). Hãy xác định độ gần tựa ngữ nghĩa của S so với P. Độ gần ở đây được hiểu là giá trị thực nằm trong khoảng [1,0] thoả mãn: + độ gần càng lớn nếu số khúc con của P xuất hiện trong S càng nhiều Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 44 + độ gần bằng 1 nếu xâu P xuất hiện trong S + độ gần bằng 0 nếu không có một phần nào của P xuất hiện trong S. 2.2.4.2. Thuật toán sơ bộ tính độ gần 2.2.4.2.1. Ý tưởng Hình 2.3. Một ví dụ với các khối độ dài t = 3 - Gọi PiPi+1...Pi+t-1 là một khối độ dài t của mẫu P và kí hiệu khối này là (t,i). - Lần lượt xét tất cả các khối độ dài t, t = 1,2,..,m, và kiểm tra xem khối đó có xuất hiện trong S hay không (xem Hình 2.3). - Tính hàm giá H(S, P) =   m t tk 1 * , trong đó k là số khối độ dài t có xuất hiện trong xâu đích S. - Gọi M là giá trị cực đại của hàm giá (khi S = P), M = H(P, P) =     m 1t t*1tm (2.1). - Độ gần của s so với P là tỷ số H/M 2.2.4.2.2. Thuật toán chi tiết Thuật toán 2.6. Tính độ gần tựa ngữ nghĩa của xâu S độ dài n so với mẫu P độ dài m. {Tính độ gần tối đa M = Hmax = H(P, P)} (3,1) (3,3) (3,5) (3,2) (3,4) P (3,2) (3,1) S (3,5) (3,1) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 45 M= H(P,P) =     m 1t t*1tm ; {Xây dựng hàm giả H(P, S) H:=0; for t:=1 to m do for i:=1 to m - t + 1 do if (khối (t, i) xuất hiện trong S) then H:=H + t; (2.2) {Tính độ gần của S so với P} F := H/M; 2.2.4.3. Giải thích độ mờ của mô hình Giá trị mờ P(S) = H/M cho biết độ gần tựa ngữ nghĩa của P trong S. Tập nền X là tập rõ bao gồm tập tất cả các xâu S trong cơ sở dữ liệu. Khi P(S) = 1 nghĩa là có mẫu P trong S hay toàn bộ thông tin của P được phản ánh trong S. Khi P(S) = 0 thì không có bất kỳ một phần nào của mẫu P trong S (xem Hình 2.4). Hình 2.4. Tập mờ mô tả độ gần tựa ngữ nghĩa của mẫu P so với xâu đích S Độ phức tạp khi so sánh mỗi khối (t,i) của mẫu được cắt với S có thể sử dụng thuật toán theo tiếp cận mờ xác định nhiều lần lặp mẫu (xem S1 S S2 S3 độ gần 1,0 0,8 0,4 0,0 0(S) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 46 mục 2.1.3), cỡ là n, chưa tính khâu tiền xử lý cho cấu trúc bảng chuyển của otomat. Số khối được xét với mọi t là: m+(m-1) + ... + 1 = m(m+1)/2. Vì mẫu đưa vào thường ngắn từ 3 đến 30 ký tự nên giá trị này có thể coi là hằng số C. Do đó độ phức tạp thời gian của thuật toán là T = n.m(m+1)/2+Tpt, với Tpr là thời gian tiền xử lý để tính m(m+1)/2 cấu trúc otomat. Thời gian tiền xử lý này là hằng số và không lớn nếu so với n = |S| (rất lớn) nên xem độ phức tạp của thuật toán là O(n). Nhưng nếu S nhỏ và tìm nhiều lần trên nhiều S khác nhau, mỗi S là giá trị trên trường text của bản ghi trong cơ sở dữ liệu, mà phải bắt đầu lại quá trình tìm mẫu thì quá là con số không nhỏ: cỡ k.T, với k là số bản ghi cần duyệt. 2.3. Kết luận chương 2 Chương này trình bày hai bài toán so mẫu xấp xỉ và chính xác theo tiếp cận otomat mờ. Bài toán so mẫu xấp xỉ và chính xác trình bày hệ hình thức cụ thể của otomat mờ tổng quát đã giới thiệu ở Mục 1.2. Hệ hình thức otomat thứ nhất có trạng thái mờ là một số tự nhiên (chính là một vectơ gồm 1 thành phần), làm cơ sở cho thuật toán so mẫu KMP mờ. Thuật toán này có thể xem như một tiếp cận mới cho thuật toán kinh điển KMP - tiếp cận otomat mờ. Hình thức thứ hai có trạng thái mờ là một bộ gồm hai thành phần, làm cơ sở cho thuật toán so mẫu KMP - BM mờ, với ý tưởng có bước dịch chuyển xa trên xâu đích S như trong thuật toán BM. Quan niệm về “độ mờ xuất hiện mẫu” trong cả hai thuật toán này đều là độ dài khúc đầu dài nhất của mẫu P đã xuất hiện trên xâu đích S, tính tới vị trí đang xét. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 47 Chương 3. TÌM KIẾM MẪU TRONG VĂN BẢN NÉN VÀ MÃ HOÁ 3.1. Tiếp cận tìm kiếm tổng quát trên văn bản nén và mã hoá Khi tìm kiếm trên văn bản nén hoặc mã hoá, bài toán bơ bản đặt ra như sau: Cho mẫu P là một xâu độ dài m (P = P1,P2,...Pm) trên bảng chữ A. Xâu vào S được nén hoặc mã hoá thành xâu Y = Y1Y2...Yn trên bảng chữ B bằng một phương pháp nén (hoặc mã hoá) đã biết trước. Tìm tất cả các xuất hiện của mẫu P trên Y. Đối với những văn bản nén, mặc dù đem lại hiệu quả rõ rệt về mặt lưu trữ, quản lý, tổ chức và chuyển tải, song lại làm mất đi phần lớn cấu trúc của dữ liệu, dẫn đến khó khăn cho việc tìm kiếm và trích rút thông tin. Cách đơn giản nhất rất tốn thời gian (và khó khả thi với những văn bản quá lớn) là giải nén toàn bộ rồi tiến hành tìm kiếm bằng một thuật toán so mẫu kinh điển. Hiện nay đã có nhiều giải pháp tốt hơn cho phép tìm kiếm trực tiếp trên dữ liệu nén mà không cần giải nén hoặc chỉ giải nén một phần. Tìm kiếm không giải nén được gọi là so mẫu nén (full- compressed pattern matching hay còn gọi là compressed pattern matching), trong đó mẫu được nén rồi đem so với văn bản nén. Tuy nhiên phương pháp này nhiều khi không khả thi, đặc biệt là với những thuật toán nén có sử dụng các biểu diễn khác nhau cho cùng một xâu con, tuỳ thuộc vào ngữ cảnh của xâu con đó. Một kỹ thuật khác là so mẫu trên miền nén (compressed-domain pattern matching), trong đó sử dụng biện pháp giải nén bộ phận trên văn bản, nhờ đó mà tránh được một số hạn chế của phương pháp so mẫu nén mà vẫn đảm bảo không phải giải nén toàn bộ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 48 Hình 3.1. Phương pháp so mẫu trên miền nén có sử dụng otomat mờ Cải tiến từ thuật toán so mẫu KMP - BM mờ được giới thiệu ở Chương 1, một thuật toán theo kiểu so mẫu trên miền nén được đưa ra. Giải pháp này phù hợp với những văn bản đã được nén bằng bất kỳ phương pháp nén nào mà có giải nén là một khối kí tự. Ưu điểm quan trọng của việc sử dụng thuật toán KMP-BM mờ trên dữ liệu giải nén cục bộ so với các thuật toán kinh điển (như KMP, BM,...) là không cần lưu lại bất kỳ kí tự nào mà đã duyệt qua, đồng thời có tốc độ nhanh nhờ những bước dịch chuyển xa trên khối dữ liệu tìm kiếm, song việc cài đặt lại đơn giản. Ý tưởng chung của các thuật toán so mẫu trên miền nén có sử dụng tiếp cận otomat mờ được mô tả trong Hình 3.1. Văn bản nén Vùng đệm Otomat so mẫu Mẫu P Tiền xử lý Độ mờ xuất hiện mẫu P Giải nén cục bộ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 49 Hình 3.2. Phương pháp so mẫu không giải mã Nén dữ liệu text thực chất là một quá trình mã hóa, vì vậy thuật toán tìm kiếm trên văn bản nén có thể áp dụng đối với văn bản mã hóa dạng khối kí tự. Tuy nhiên, đối với các văn bản mã hóa, yêu cầu về tính bảo mật là rất quan trọng. Mặc dù dữ liệu giải nén cục bộ chỉ được lưu giữ một thời gian ngắn trên bộ nhớ trong, song không thể chắc chắn đây không là một sơ hở để lộ thông tin. Để nâng cao tính bảo mật, tránh rò rỉ thông tin ngay trong quá trình tìm kiếm, ý tưởng tìm kiếm xâu mẫu trong văn bản mã hóa mà không cần giải mã cục bộ được đưa ra. Phương pháp này được gọi là so mẫu không giải mã. Khả năng này có được chính là nhờ sử dụng tiếp cận otomat cho quá trình tìm kiếm. Hình 3.2 mô tả ý tưởng chung của các phương pháp so mẫu không giải mã. Trong Mục Tiền xử lý Mẫu P Nếu được 1 từ mã Đọc một ký tự thuộc bản mã Văn bản mã hoá Otomat đoán nhận một từ mã Otomat so mẫu Đọc một ký tự thuộc bản mã Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 50 3.2.3.3 sẽ trình bày một ứng dụng cụ thể kiểu so mẫu không giải mã, áp dụng trên văn bản mã hóa bởi mã đàn hồi (đây là một dạng mã dựa trên tích đàn hồi được giới thiệu trong [HN]). Với tiếp cận otomat mờ, các thuật toán tìm kiếm chính xác trên văn bản nén và mã hóa được trình bày ở đây có thể dễ dàng chuyển đổi sang tìm kiếm gần đúng bằng cách sử dụng những otomat so mẫu xấp xỉ đã giới thiệu ở trên. 3.2. Tìm kiếm trên văn bản nén 3.2.1. Các mô hình nén văn bản Nén dữ liệu là một lĩnh vực của lý thuyết thông tin mà mục đích chính là làm giảm thiểu khối lượng dữ liệu được lưu trữ và trao đổi. Nén dữ liệu text thực chất là một quá trình mã hóa, chuyển các thông báo nguồn (trong bảng chữ nguồn A) thành các bản mã (trong bảng chữ mã B) và ngược lại là quá trình giải mã. Các dạng mã hóa có thể là block - block, block - variable, variable - block và variable - variable , trong đó block - block là các thông báo nguồn và các bản mã đều có thể thay đổi. Một cách phân loại khác chỉ ra 2 phương pháp nén là tĩnh và động. Trong phương pháp tĩnh, ánh xạ từ tập thông báo nguồn đến tập từ mã được xác định trước khi bắt đầu quá trình chuyển đổi nên với một thông báo cho trước thì tất cả các lần xuất hiện của nó đều tương ứng với một bản mã. Với phương pháp động, ánh xạ từ tập thông báo đến tập bản mã thay đổi theo thời gian. Cho đến nay đã có nhiều thuật toán nén dữ liệu text được đưa ra [15], như nén Hufman, LZ, LZW,... 3.2.2. Thuật toán tìm kiếm trên dữ liệu nén dạng text Thuật toán theo tiếp cận mờ đã nêu ở mục 2.2 có thể áp dụng trên các tệp dữ liệu nén mà không cần giải nén toàn bộ. Ý tưởng cơ bản là đọc tuần tự trên tệp nén và mở nén một số mã nén, lưu kết quả giải nén Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 51 cục bộ vào vùng đệm và áp dụng thuật toán theo tiếp cận mờ trên vùng đệm này. Khi đó một số vấn đề đặt ra là: (i) Vùng đệm phải có độ dài đáp ứng được yêu cầu: - Luôn có thể đọc được một khối kí tự w độ dài m+1 (với m là độ dài xâu mẫu). - Kích thước phải đủ lớn để vùng đệm không bị tràn khi gặp trường hợp một mã nén tương ứng với một đoạn văn bản dài (chẳng hạn như trong thuật toán Run - length, giải nén mã nén a256 sẽ được 256 kí tự a liên tiếp). (ii) Truy xuất đến các phần tử trên vùng đệm nhanh, thuận tiện. Để đáp ứng yêu cầu (i), ta đưa ra hai điều kiện cho vùng đệm: - Điều kiện dưới: Dữ liệu trên vùng đệm phải có > m+1 kí tự (nếu chưa đọc hết văn bản). - Điều kiện trên: Dữ liệu trên vùng đệm phải có độ dài nhỏ hơn hoặc bằng kích thước của vùng đệm, trong đó kích thước của vùng đệm bằng độ dài tối đa khi giải nén của một mã nén cộng với m+1. Ở đây ta cần xem như độ dài tối đa của một mã nén khi giải nén đã được xác định cụ thể trong từng phương pháp giải nén khác nhau. Để đáp ứng yêu cầu (ii) ta sử dụng cấu trúc dữ liệu dạng hàng đợi vòng tròn (circular queue) dựa trên vùng đệm là một mảng kí tự như sau: buffer: array[1...bur_len] of char; trong đó buf_len = max_encode_len+m-1, với max_encode_len là độ dài tối đa khi mở nén của một mã nén. Hàng đợi vòng tròn trên vùng đệm được xác định bởi 2 con trỏ: F trỏ vào đầu lấy ra một phần tử trong queue, B trỏ vào đầu đưa một phần tử vào hàng đợi. Độ dài của hàng đợi (ký hiệu là len_queue) bằng số phần tử trên hàng đợi, cụ thể được tính theo công thức sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 52 len_queue =      FB,1FBlen_buf)1BF_(len_buf FB,1FB Hoạt động của queue Phép định vị con trỏ T trên hàng đợi sau bước nhảy qua k phần tử được xác định theo chiều kim đồng hồ bởi công thức: Tk =      len_bufkT,len_bufkT len_fbukT,kT Khi vùng đệm không thỏa mãn điều kiện dưới, cần phải bổ sung thêm một đoạn dữ liệu giải nén. Ta đặt giả thiết là từng phương pháp giải nén đều có thể xây dựng được thủ tục Decompress (buffer, B, len_queue) theo yêu cầu sau: (Hình 3.3) + Đọc một số mã nén, giải nén và lưu vào buffer bắt đầu từ vị trí b 1 + Kết thúc thủ tục, B trỏ vào kí tự cuối cùng được ghi vào buffer + Kết thúc thủ tục thì vùng đệm thỏa mãn điều kiện trên và dưới, có nghĩa m+1 < len_queue  buf_len. Nếu đã đọc hết văn bản mà điều kiện dưới vẫn chưa được đáp ứng thì chấp nhận len_queue  m+1. Hình 3.3. Queue trước (a) và sau (b) khi thực hiện thủ tục Decompress B Decompress B F len_queue len_queue m+1 (a) (b) m+1 F Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 53 Ở đây ta chỉ xét loại hình thức giải nén mà một mã nén cho ra một khối kí tự (như Hufman, LZ, LZW...). Với những giải thuật nén mà dữ liệu giải nén không ở dạng khối kí tự thì chỉ cần thay đổi nguyên tắc họat động của thủ tục Decompress. Có thể tăng thêm cơ chế quản lý buffer nếu dữ liệu là mảng các bit thì phải có con trỏ quản lý tới bit. Thuật toán 3.1. Vào: Mẫu P độ dài m, dòng dữ liệu S ở dạng nén, AP là bảng các kí tự xuất hiện trong mẫu P. Ra: - Mảng apr lưu vị trí xuất hiện của mẫu trên văn bản sau khi mở nén. - Counter lưu số lần xuất hiện mẫu P. Hình 3.4. Queue trước (a) và sau (b) bước nhảy n2‟ Phương pháp : (Hình 3.4) Begin F := 0; B := 0; lenqueue := 0; counter := 0; j := 0; n1 := 0; n2 := 1; repeat F := F  n2; j := j + n2; if len_queue <= m +1 then B F len_queue m+1 (a) B len_queue (b) F new = F old  n2‟ F old m+1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 54 Decompress (buffer, B, len_queue); if n2 > 1 then n1 := 0; n1’ := TFuzz (n1, buffer [F]); n2’ := 1; if n1’ = m then begin counter: =counter + 1; apr [counterr]:=j - m+1; end else if n1’ < m and n1’ < n1 then begin t:=F (m-n1’) if t > B then return; if buffer[t]  Ap then n2’:= 1 + m - n1’; end; len_queue := len_queue - n2’; n1:=n1’; n2:= n2’; until len_queue <= 0; End. Khả năng mở rộng của phương pháp Trong từng giải thuật nén và giải nén cụ thể, với những cấu trúc cụ thể, chẳng hạn dạng cây (Hufman, LZW) ta có thể dựa trên giải thuật trên, cải biên để xây dựng các giải thuật sử dụng một danh sách của vài con trỏ, trỏ vào những điểm thích hợp trên cây để tận dụng ngay cấu trúc cây trực tiếp, thay cho việc cần một hàng đợi thực sự, nhằm tăng hiệu quả của chương trình. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 55 3.3. Tìm kiếm trên văn bản mã hóa 3.3.1. Tìm kiếm trên văn bản mã hóa dạng khối kí tự Nén dữ liệu text thực chất là một quá trình mã hóa, vì vậy thuật toán tìm kiếm trên văn bản nén có thể áp dụng đối với văn bản mã hóa dạng khối kí tự, trong đó thủ tục giải nén Decompress được thay thế bằng thủ tục giải mã. 3.3.2. Mã đàn hồi Trong mã thông thường, tích hai từ là phép đặt 2 từ cạnh nhau và tập X là mã nếu một từ bất kỳ có sự phân tích thành tích của các từ mã trong X thì sự phân tích đó là duy nhất. Đã có nhiều phương pháp mở rộng khái niệm tích sử dụng kỹ thuật khác nhau để từ đó đề xuất xây dựng các lớp mã mới. Một trong những hướng nghiên cứu mở rộng trong lý thuyết mã là sử dụng các yếu tố điều khiển để đề xuất tích mới của các từ mã, nhằm xây dựng các lớp mã mới. Những hình thức mã mới như mã zigzag, mã điều khiển theo tích trộn đã được nhiều tác giả trên thế giới nghiên cứu, còn mã đàn hồi (spring product) được giới thiệu lần đầu tiên trong [16]. Ở đây ta giới hạn xem xét các ngôn ngữ xây dựng từ bảng chữ nhị phân B = {0,1} có độ dài như nhau, X  Bk = [0,1}k. Ý tưởng xây dựng tích đàn hồi là trong quá trình mã hóa, tích của các từ không ghép như tích thông thường mà có thể “co lại” hoặc “kéo dãn”. Ta sẽ sử dụng đồ thị để xây dựng khái niệm tích đàn hồi (được gọi là đồ thị xác định mã đàn hồi). Mỗi phần tử b = b1b2,...,bk  B k được mô tả bằng 1 đỉnh có tên tương ứng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 56 Từ mỗi đỉnh b = b1b2,...,bk có 2 cung đi ra đến 2 đỉnh c, d được xác định như sau: + Cung từ đỉnh b = b1b2,...,bk đến đỉnh c = b2...bk1 sẽ có nhãn 1 + Cung từ đỉnh b = b1b2,...,bk đến đỉnh d = b2...bk0 sẽ có nhãn 0 Ví dụ 3.1. Với k = 3, ta có đồ thị mô tả cho B3 = {0,1}3 như sau (Hình 3.5) Hình 3.5. Đồ thị xây dựng khái niệm tích đàn hồi Với việc sử dụng biểu diễn bằng đồ thị như trên, có thể định nghĩa tích đàn hồi của hai từ x,y B như sau. Định nghĩa 3.1. Cho ngôn ngữ X  Bk = {0,1}k, hai từ x, y  X, mà hai đỉnh tương ứng trong đồ thị của Bk là xB, yB. Tích đàn hôi của x, y kí hiệu x.py là một đường đi p từ xB đến yB không qua các đỉnh trung gian thuộc X: xB yB. 111 011 110 101 001 010 000 100 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 57 Chú ý rằng qua cách thể hiện bằng đồ thị ở trên, có thể có nhiều đường đi p: XB yB, tức là có thể có nhiều phương án mã hóa khác nhau (mã hóa đa trị). Một cách quy nạp ta định nghĩa: x1.px2.p....pxn = (x1.px2.p....pxn-1).p.xn Từ khái niệm tích đàn hồi, khái niệm mã đàn hồi được xây dựng như sau. Ví dụ 3.2. Cho X = {000,010,110,101] và ánh xạ mã a000, b010, c 110, d 101 ab được mã bởi 00(0)10 với tính chất “co lại” thay vì như tích ghép là 000010. Có thể thấy 00010 phân tích duy nhất thành các từ trong X. Tuy nhiên nếu mã ab bởi 000101 theo kiểu tích ghép thì giải mã theo kiểu tích đàn hồi sẽ không duy nhất, chẳng hạn. 000101 = (000)(101) = ad = (000) (010) (101) = abd. Để tránh tình huống này, khi mã hóa ad ta sẽ “kéo dãn” thành 0001101, khi đó 0001101 được giải mã thành (000)(001)(011)(101) = 000.00001.0101110101( sự phân tích là duy nhất qua các từ a, d trong X). Định nghĩa 3.2. Cho ngôn ngữ X  Bk = {0,1}k, X là mã tích đàn hồi nếu một từ bất kỳ được phân tích theo tích đàn hồi bởi các từ trong X thì sự phân tích đó là duy nhất. Ví dụ 3.3. Cho B 3, ngôn ngữ X ={000,010, 101, 111}. Giả sử có ánh xạ mã: a  000, b 010, c 111, d 1010 Tích ab được mã hóa bởi đường đi từ đỉnh 000 đến đỉnh 010 qua đỉnh 001: ab 00010. Tích abd được mã hóa bởi đường đi từ đỉnh 000 qua 001, 010 đến 101: abd 000101. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 58 Việc giải mã được tiến hành bằng việc duyệt theo con đường xác định bởi các nhãn. Chẳng hạn 000101 được giải mã như sau: + Từ đỉnh 000 = a theo nhãn 1: đến đỉnh 001. + Tiếp tục theo nhãn 0 đến đỉnh 010 = b, + Cuối cùng theo nhãn 1 đến đỉnh 101 = d. Kết quả được từ abd. Hình 3.6. Đồ thị xác định mã đàn hồi Mệnh đề 3.1. Cho ngôn ngữ X  Bk. X là mã đàn hồi khi và chỉ khi với mọi cặp đỉnh x, y  X, tồn tại ít nhất một đường đi từ x tới y không qua bất kỳ đỉnh trung gian nào khác thuộc X. 3.3.3. Tìm kiếm trên văn bản mã hóa bởi mã đàn hồi 3.3.3.1. Ý tưởng chung Giải pháp - Xây dựng otomat đoán nhận mã của một ký tự 111 011 110 101 001 010 000 100 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 59 - Kết hợp với otomat tìm kiếm theo mẫu tiếp cận mờ xác định độ mờ xuất hiện mẫu. Khi độ mờ này bằng độ dài mẫu, báo hiệu một lần xuất hiện mẫu. Yêu cầu: - Thuật toán tìm chính xác sự xuất hiện mẫu, không bỏ sót. - Không giải mã cục bộ mà vẫn thống kê được tần suất xuất hiện mẫu, mặc dù phương pháp mã hóa đàn hồi là đa trị. 3.3.3.2. Phương pháp đánh giá độ mờ xuất hiện mẫu trên văn bản mã hóa 3.3.3.2.1. Bài toán Giả sử: A là bảng chữ rõ; B là bảng chữ mã Hàm mã E: A  Bk Để thuận tiện cho việc trình bày, không mất tính tổng quát, có thể giả sử A = {a,b,c,d]=, b = {0,1}, k = 1, hàm mã hóa theo phương pháp mã đàn hồi xác định như sau (xem đồ thị Hình 3.4.): A a b c d E(A) 000 010 101 111 Xác định hàm bin: {0,...,2k} Bk, bin(i) cho xâu nhị phân của i. Bài toán đặt ra là: Cho xâu mẫu P = P1P2...Pm trên bảng chữ A. Xâu đích S được mã hóa thành Y = Y1Y2...Yn theo phương pháp mã đàn hồi. Thống kê tần suất xuất hiện mẫu P trong xâu mã hóa Y. 3.3.3.2.2. Mô tả phương pháp - Đổi sánh các kí tự đã mã hóa của mẫu P với xâu đích Y - Dùng otomat A0 tìm kiếm mẫu rõ để tìm vị trí đầu tiên gặp mã E(P1) của kí tự đầu của mẫu P; Otomat A1 đoán nhận mã; Otomat A2 đoán nhận độ mờ xuất hiện mẫu rõ P. Mỗi giá trị trạng thái ra của otomat A1 nếu là trạng thái kết thì sẽ là trạng thái vào của otomat A2. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 60 3.3.3.2.3. Chi tiết hóa các otomat trong thuật toán Otomat A1 đoán nhận mã A1(P) = (1, Q1,Q10, Q1F, 1), trong đó: 1 = {0,1}: bảng chữ vào Q1 = {0,1, ..., 2 k -1}: là tập trạng thái Q10: là tập trạng thái khởi đầu Q1F là tập trạng thái kết Q10 = Q1F = bin -1 (E(A)) = (A), với hàm  = bin-1.E Hàm chuyển 1 được xây dựng theo đồ thị xác định mã đàn hồi (xem Hình 3.6) Ví dụ 3.5: Với hàm mã hóa ở Mục (a), ta có : Q = {0,1,..,7}; Q10 = Q1F = {0,2,5,7} Hàm chuyển 1 được xây dựng là: A Q 0 1 0 0 1 1 2 3 2 4 5 3 6 7 4 0 1 5 2 3 6 4 5 7 6 7 Otomat A2 đoán nhận độ mờ xuất hiện mẫu rõ P Otomat A2 có quan hệ đẳng cấp với otomat mờ A(P) = (A,Q,q0,,F) tìm kiếm mẫu rõ (xem Định nghĩa 1.4, Mục 1.6.3.1); Bảng chữ vào là 2 = (AP){#}; Hàm chuyển là 2‟. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 61 Ví dụ 3.6. Với mẫu P = ababa, hàm chuyển 2‟ như sau: 2 Q 0 2 # 0 1 0 0 1 1 2 0 2 3 0 0 3 1 4 0 4 5 0 0 5 1 4 0 3.3.3.2.4. Thuật toán tìm kiếm mẫu dựa trên otomat Vào: Xâu mẫu rõ P, xâu mã Y = Y1Y2...Yn Ra: counter đếm số lần xuất hiện mẫu P + Giả sử đã xây dựng ba otomat A0, A1, A2 + Biến q ghi giá trị trạng thái của otomat A1 đoán nhận mã. Nếu q là một trạng thái kết, báo hiệu đoán nhận được mã của một ký tự trong bảng chữ A. + Biến f ghi giá trị độ mờ xuất hiện mẫu rõ P + Hàm AoSeek(P1,j) tìm vị trí (kết thúc) trên xâu mã hóa Y đọc được ký tự P1 lần đầu tiên, kể từ vị trí j trở đi. Phương pháp counter:= 0; j:=1; f:=0; j: = AoSeek(P1,j); {P1 là ký tự đầu tiên trng mẫu} if j = 0 then return (0); j:=J+1; f:=1; q = (P1); while j 0 do q:= 1(q,Yj); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 62 if q Q1F then f:=2(f,q); if f=m then counter:=counter+1; endif; endif; j:=j+1; andwhile; until j>=n; return (counter); Ví dụ 3.7. Với mẫu P=ababa, xâu đích S=aacdababab được mã hóa thành Y a b b b b Y = 0000110111000100011001001100010 a c a a b a Quá trình duyệt trên Y để thống kê tần suất xuất hiện mẫu P như sau: Khởi đầu 1 1 0 0 j Yj AoSeek(P1,j) q=1(q,Yj) f=2‟(f,q) counter 1 1 0 1 4 0 0 1 5 1 1 6 1 3 7 0 6 8 1 5 0 13 0 1 14 1 1 15 0 2 2 16 0 4 17 0 0 3 18 1 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 63 19 1 3 20 0 6 21 0 4 22 1 1 23 0 2 4 24 0 4 25 1 1 26 1 3 27 0 6 28 0 4 29 0 0 5 1 30 1 1 31 0 2 4 3.3.4. Tìm kiếm trên văn bản mã hóa hai tầng Trong một hệ thống bảo vệ dữ liệu cá nhân, việc sử dụng mã hóa đàn hồi và giải thuật so mẫu không giải mã sẽ đáp ứng tốt nhu cầu bảo mật mà vẫn có thể tìm thấy thông tin cần thiết. Tuy nhiên, để nâng cao mức độ bảo mật, tùy thuộc các nhu cầu ứng dụng và sử dụng được các sản phẩm mã hóa dữ liệu chất lượng cao sẵn có, phần này tác giả đưa ra giải pháp mã hóa hai tầng. Giả sử C1 là hàm mã hóa theo mã đàn hồi với hàm giải mã D1, C2 là hàm mã hóa hoặc hàm nén theo một giải thuật nào đó (như các hệ mã đối xứng AES, IDEA, SEFER; các hệ mã công khai RSA [16] [17]; nén Huffman, LXW,... [15], có hàm giải mã là D2. Quá trình mã hóa hai tầng được mô tả trong Hình 3.7 và Hình 3.8 là quá trình giải mã. Khi đó, giải thuật tìm kiếm mẫu trong văn bản mã hóa bởi mã hai tầng được thể hiện qua sơ đồ Hình 2.9. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 64 Bản rõ X C1 Y1 = C1(X) C2 Bản mã Y = C2(C1(X)) Hình 2.7. Quá trình mã hóa hai tầng Bản rõ X= D1(D2(Y)) D1 Y1 = D2(Y) D2 Bản mã Y Hình 2.8. Quá trình giải mã hai tầng Hình 2.9. Quá trình tìm kiếm mẫu trên văn bản mã hóa hai tầng 3.4. Kết luận chương 3 Chương này đã trình bày các kết quả của luận văn về vấn đề tìm kiếm mẫu trên môi trường văn bản nén và mã hóa, bao gồm: - Giới thiệu sơ đồ tìm kiếm tổng quát - Trình bày một thuật toán theo kiểu so mẫu miền nén, được cải tiến từ thuật toán KMP-BM (xem mục 2.4), để áp dụng cho văn bản nén dạng khối kí tự. Với những giải thuật nén mà dữ liệu giải nén không ở dạng khối kí tự, có thể cải biên thuật toán này bằng cách thay đổi nguyên tắc họat động của thủ tục giải nén. Giải mã Y bởi D2 Y: Văn bản mã hóa hai tầng Y1: Văn bản mã hóa bởi C1 Đọc 1 ký tự thuộc bản mã Otomat đoán nhận một từ mã Nếu được 1 từ mã Otomat so mẫu Độ mờ xuất hiện mẫu P Tiền xử lý Mẫu P Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 65 KẾT LUẬN Luận văn đã tìm hiểu về otomat mờ, một số thuật toán tìm kiếm và đã giới thiệu hai bài toán so mẫu xấp xỉ - chính xác. Trình bày những thuật toán so mẫu của hai bài toán trên đều dựa vào độ tương tự giữa hai xâu theo một mô hình "lỗi" kinh điển. Ngoài ra, luận văn trình bày thuật toán so mẫu cho văn bản nén và mã hoá dạng text thu được những kết quả dưới. Các kết quả đạt được của luận văn:  Trình bày được tổng quan về tìm kiếm mẫu trên văn bản, từ đó đưa ra các dạng tìm kiếm mẫu.  Giới thiệu hệ mờ, ý tưởng chung của tiếp cận otomat mờ. Sau đó đưa ra một số thuật toán so mẫu như KMP, BM.  Trình bày thuật toán so mẫu chính xác và xấp xỉ theo tiếp cận otomat mờ và thuật toán tìm kiếm mẫu trong văn bản nén và mã hoá. Một số hạn chế của luận văn:  Chưa cài đặt được chương trình tìm kiếm mẫu trong văn bản nén và mã hoá.  Thuật toán đưa ra còn chưa tối ưu.  Trình bày luận văn còn lủng củng. Hướng nghiên cứu tiếp theo:  Cài đặt chương trình tìm kiếm mẫu trong văn bản nén, mã hoá và ứng dụng trong các chương trình tìm kiếm thông tin.  Giới thiệu thuật toán tối ưu hơn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 66 Do thời gian và khả năng có hạn, luận văn còn thiếu sót nhiều, em rất mong nhận được sự góp ý, chỉ dẫn thêm của các Thầy Cô, bạn bè để em có thể xây dựng được ứng dụng hoàn thiện hơn. Một lần nữa em xin chân thành cảm ơn Thầy hướng dẫn PGS.TS. Đoàn Văn Ban, các Thầy Cô trong khoa đã tạo mọi điều kiện thuận lợi để em có thể hoàn thành luận văn đúng thời hạn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 67 TÀI LIỆU THAM KHẢO Tiếng Anh [1]. Gonzalo Navarro, Mathieu Raffinot (2000), Fast and Flexible String Matching by Combining Bit - Parallelism and Suffix Automata, ACM Journal of Experimental Algorithmics (JEA). [2]. Gonzalo Navarro, Mathieu Raffinot (2002), Flexible Pattern Matching in Strings, Cambridge University Press, ISBN 0-521-81307-7. [3]. Heikki Hyyro (2002), A Bit - Vector Algorithm for Computing Levenshtein and Damerau Edit Distances, Proceedings of the Prague Stringology Conference '02, pp. 44-54. [4]. Aho A.V.(1992), Algorithms for finding patterns in strings, Chapter 5 of Jan Van Leeuwen (ed.), Handbook of Theoretical Computer Science "Algorithms and Complexity", The MIT Press, pp. 255-300. [5]. Christian Charras, Thierry Lecroq (2000), Handbook of Exact Stringmatching Algorithms. Tiếng Việt [6]. Phan Trung Huy và Nguyễn Quý Khang (2002), "A New Algorithm For LCS Problem", Kỷ yếu Hội nghị Toán học Toàn quốc 9/2002. [7]. Robert Sedgewick (1994), Cẩm nang thuật toán, Tập 1: Các thuật toán thông dụng, NXB Khoa học và Kỹ thuật, tr. 324 - 351. [8]. Vũ Thành Nam, Phan Trung Huy, Nguyễn Thị Thanh Huyền (2005), Mã tích đàn hồi và tìm kiếm trên văn bản mã hoá sử dụng thuật toán so mẫu theo tiếp cận mờ, Báo cáo khoa học tại Hội nghị Ứng dụng toán học toàn quốc lần 2, Hà Nội, 12/2005. [9]. Nguyễn Thị Thanh Huyền (2006), Luận án Tìm kiếm mờ, phân cụm mờ và ứng dụng trên mạng tại trường Đại học Bách khoa Hà Nội.