Luận văn 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

otomat mờ Một số nghiên cứu về otomat mờ có thể xem trong 9, …. Mô hình otomat mờ dạng tổng quát có mỗi trạng thái mờ là một tập con mờ trên tập nền X = 1, …, n (X hữu hạn), có hàm thuộc mở rộng là f: X  R. Ta có thể biểu diễn f dưới dạng vector rõ (f(1), f(2),…,f(n)). Như vậy, trạng thái mờ được xem như là một véctor n chiều toạ độ thực. Tuỳ theo từng ứng dụng cụ thể mà có thể xem f(i)  0,1 hay f(i)  N hay f(i)  R,…. Định nghĩa 1.2. Một otomat mờ tổng quát là bộ A(P) = (A, Q, qo, , F), trong đó: + Bảng chữ vào A = A0 t , trong đó mỗi chữ là một xâu gồm t ký tự trên bảng chữ cơ sở A0. + Q là tập hữu hạn các trạng thái mờ có dạng q = (v1, v2,….vk) trên tập nền X = 1,…, k với giá trị mờ nguyên + q0  Q là trạng thái khởi đầu + F là tập các trạng thái kết thúc + Hàm chuyển : Q × A  Q Hàm chuyển có thể được mở rộng trong đó tín hiệu tác động là một xâu thuộc A*: (q, wa) = ((q, w),a), w  A*, a  A. Số thành phần trong trạng thái mờ và tập giá trị mờ phụ thuộc vào quan điểm về “độ mờ xuất hiện mẫu” và nhu cầu tìm kiếm trong từng bài toán cụ thể. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 18 Để thuận lợi cho việc trình bày sau này, quy định một số ký hiệu như sau: Với w, w1, w2 là các xâu ký tự, + wi là ký tự thứ i của xâu w + w(f,d) là xâu con (hay khúc con) độ dài f của xâu w, kết thúc ở vị trí d trên w. + w1  s w2 nếu w1 là khúc đuôi của w2 + w1  ls w2 nếu w1 là khúc đuôi dài nhất của w2 + Với w = w1, w2….wm, 0  t  m w(t) hoặc preft(w) là khúc đầu độ dài t của w, w(t) = w1 w2….wt Suft(w) là khúc cuối độ dài t cuả w, Suft(w) = wm - t+1 w m-t+2....wm Quy ước pref0(w) = suf0(w) =  ( là xâu rỗng) + Với a là một ký tự, w = w1w2…wm, ký hiệu wa = w1w2…wma 1.5. Một số thuật toán so mẫu 1.5.1. Thuật toán KMP ( Knuth- Morris- Pratt) Thuật toán KMP được trình bày chi tiết trong 4, 5, 14 nội dung như sau: Duyệt từ trái sang phải trên S và P, mỗi lần một ký tự. Gọi con trỏ trên P là i, con trỏ trên S là j. Giả sử đã xuất hiện khúc đầu độ dài i - 1 của mẫu P và việc khớp mẫu thất bại tại vị trí j trên S, có nghĩa: P1P2…Pi -1  Sj - i + 1Sj - i + 2…S j - 1 và Pi  Sj Khi đó cần phải bắt đầu đối sánh mẫu từ vị trí j - h +1 trên S (trường hợp xấu nhất h = i - 1 trong thuật toán Brute - Force). Nếu tồn tại h > 0 sao cho h - 1 ký tự đầu của mẫu khớp với h - 1 ký tự cuối của đoạn S(j - 1) hay có nghĩa đã khớp với h - 1 ký tự cuối của P(i - 1) thì ta có thể bỏ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 19 h=next[i] S P P i j m m +1 j h=next[m+1] P S P qua h - 1 phép so sánh và tiếp tục so sánh 2 ký tự Ph và Sj (hình 1.1). Do h phụ thuộc vào i nên ký hiệu h = nexti, i = 1,…,m. ? Hình 1.1. Ý nghĩa của mảng next Nếu Sj  Ph thì phải tiếp tục lùi con trỏ trên mẫu. Để khắc phục nhược điểm do tình huống này gây ra, cần cố gắng tìm h sao cho Ph có nhiều khả năng bằng Sj. Vì Sj  Pi nên cần tìm h thoả mãn Ph  Pi . Trong KMP, khi i > m ta được một xuất hiện của mẫu bắt đầu từ vị trí j - m trên S. Để tìm xuất hiện tiếp theo, nếu bắt đầu đối sánh từ P1 và Sj thì có thể bỏ sót mẫu khi có mẫu xuất hiện lồng nhau. Vì vậy, khi con trỏ trên S dừng ở vị trí j, cần trượt mẫu đi một số vị trí sao cho h - 1 ký tự đầu của mẫu khớp với h - 1 ký tự cuối của S(j - 1) hay chính là khớp với h - 1 ký tự cuối của P(m). Do đó cần mở rộng mảng next với i = m + 1. (Hình 1.2). Hình 1.2. Ý nghĩa của mảng next tại vị trí m + 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 20 Như vậy, với mỗi vị trí i trên P, i = 1..m + 1, cần xác định next i thoả mãn: + nexti là số h lớn nhất sao cho h - 1 ký tự đầu của mẫu khớp với h - 1 ký tự cuối của P(i- 1). + Pi  Pnext i (để có nextm + 1, tưởng tượng như đã bổ sung thêm ký tự  vào cuối P, với  là một ký tự không xuất hiện trong P). Ví dụ 1.1. Với P = aababaab ta có bảng next như sau: i 1 2 3 4 5 6 7 8 9 next[i] 0 0 2 0 2 0 0 2 4 Thuật toán 1.1. Xây dựng mảng next procedure Initnext(); var i, j: Integer; begin i: = 1; j: = next 1: = 0; while i< = m do begin while j > 0 and Pi  P j do j: = next j; i: = i + 1; j: = j + 1; if ( i < = m) and (Pi = P j) then next i := next j else next i : = j; end; end; Thuật toán 1.2. KMP tìm nhiều lần lặp mẫu proedure KMP(); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 21  Tìm mọi vị trí xuất hiện xâu mẫu P độ dài m trong xâu đích S độ dài n, đồng thời thống kê tần suất xuất hiện mẫu var i, j: Integer; counter: Integer; begin Initnext (); i:= 1; j:= 1; counter: = 0; repeat while i < = m and j < = n do begin while (i > 0) and (Sj  Pi) do i: = next i; i: = i + 1; j = j + 1; end; if( i > m) then begin Ghi nhận vị trí xuất hiện mẫu là j - m; counter: =counter + 1; end; i: = next m + 1; until j > n; Ghi nhận counter; end; Độ phức tạp của thuật toán 4, 5 - Pha tiền xử lý mẫu: Độ phức tạp thời gian và không gian để xây dựng bảng next là O(m). - Pha tìm kiếm: Thời gian xấu nhất là O(m+n). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 22 1.5.2. Thuật toán BM ( Boyer- Moor) Một tiếp cận phổ biến trong các thuật toán so đơn mẫu là duyệt tuần tự qua tất cả các ký tự trên xâu vào S, mỗi lần một ký tự. Nhưng trong thuật toán BM, có thể có những bước nhẩy xa trên S được thực hiện, nhờ vậy BM được đánh giá là thuật toán nhanh nhất về thực hành, đây là lựa chọn hiệu quả cho những ứng dụng thông thường như các trình soạn thảo văn bản. Ý tưởng cơ bản của thuật toán là sử dụng một “Cửa sổ trượt” như sau: “Cửa sổ” thực ra là một khúc độ dài m trên xâu vào S (m là độ dài của mẫu P) được đối sánh với mẫu tại một thời điểm nào đó. Mỗi lần đối sánh mẫu P với một cửa sổ trên S bằng cách so sánh từng ký tự từ phải sang trái. Khi gặp ký tự không khớp, cửa sổ trượt sang phải qua một đoạn trên S (tương ứng với việc dịch mẫu P sang phải). Trường hợp tốt nhất khi sự không khớp xảy ra tại vị trí Pm và ký tự không khớp là Sk lại không phải là một ký tự trong mẫu P, lúc đó có thể an toàn trượt cửa sổ sang phải qua m vị trí trên S và bắt đầu quá trình tìm kiếm mới bởi việc so sánh Pm và Sk+ m. Giả sử tại một thời điểm đang xét cửa sổ Sk - m+ 1Sk - m + 2 .... Sk và bắt đầu so sánh Pmvới Sk. (1) Giả sử Pm  Sk có hai khả năng: a) Nếu vị trí xuất hiện phải nhất của ký tự Sk trong P là m - g, ta có thể dịch mẫu P sang phải g vị trí sao cho Pm-g dóng thẳng với Sk rồi bắt đầu lại quá trình đối sánh bởi phép so sánh Pm và S k+ g b) Nếu ký tự Sk không có mặt trong P, ta có thể dịch mẫu P sang phải m vị trí. Đây là bước dịch chuyển xa nhất có thể mà vẫn không bỏ sót sự xuất hiện nào của mẫu. (2) Giả sử m - i ký tự cuối của mẫu P đã khớp với m - i ký tự cuối của S(k). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 23 Nếu i = 0, ta đã tìm được một xuất hiện của mẫu P. Ngược lại, nếu i > 0 và Pi  Sk -m+i, xét hai khả năng: a) Nếu vị trí xuất hiện trái nhất của ký tự Sk -m+i trong P là i - g, khi đó mẫu P được dịch sang phải g vị trí sao cho Pi-g dóng thẳng với Sk-m+i và sẽ bắt đầu quá trình đối sánh mới, bắt đầu từ Pm so với Sk+g. Nếu Pi-g nằm bên phải của Pi (khi g < 0) thì mẫu P chỉ dịch sang phải 1 vị trí. b) Giả sử sufi(P) là một xâu con của Pi+1-gPi+2-g....Pm-gvà Pi-g  Pi (nếu có nhiều xuất hiện như vậy của sufi(P) thì chọn vị trí phải nhất). Khi đó sẽ dịch mẫu P sang phải một đoạn dài hơn so với trường hợp (2a) sao cho khúc Pi+1-gPi+2-g....Pm-g dóng thẳng với khúc Sk-m+i+1Sk-m+i+2...Sk và bắt đầu quá trình đối sánh mới từ Pm so với Sk+g. Như vậy, khi Pi  Sj, mẫu P sẽ dịch sang phải đi một số vị trí. Thuật toán sử dụng hai bảng d1và d2 để tính toán bước địch chuyển này. Bảng d1 bao hàm trường hợp (1) và (2a): Với mỗi ký tự c, d1c là số i lớn nhất sao cho c = Pi hoặc dc = m nếu c không xuất hiện trong mẫu P. Bảng d2 bao hàm trường hợp (2b): Với mỗi i, 1 i  m, d2i được xác định là: d2i = ming + m - i| g  1 và (g  i hoặc Pi-g  Pi) và ((g  k hoặc Pk-g = Pk) với i  k  m) Có nhiều cách tính toán bảng d2 được đưa ra. Thuật toán 1.3. tính bảng dịch chuyển d2 là của Knuth, có sự sửa đổi của Mehlhorn. Trong thuật toán 1.3 sử dụng hàm f có tính chất f[m] = m+1 và với 1  j < m, fj = mini j < i < m và Pi+1Pi+2....Pm = Pj+1Pj+2....Pm+j-i. Thuật toán 1.3. Tính bảng dịch chuyển d2 procedure computed 2(); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 24 begin for i: = 1 to m do d2i : = 2 *m- i; j := m; k: = m+ 1; while j > 0 do begin fj: = k; while k <= m and Pj  Pi do begin d2k:= mind2k, m- j ; k: = fk]; end; j := j - 1; k := k - 1; end; for i: = 1 to k do d2i : = mind2i, m +k - i j: = fk; while k < = m do begin while k <=j do begin d2k := mind2k, j-k + m  k := k + 1; end; j: = fj; end; end; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 25 Thuật toán 1.4. Thuật toán BM tìm sự xuất hiện của mẫu P trong xâu vào S procedure BM(); var i, j: integer; counter: integer; begin j:= m; counter: = 0; while j <= n do begin i: = m; while i >0 and Sj  Pi do begin i: = i - 1; j: = j - 1; end; if i: = 0 then begin Ghi nhận một lần xuất hiện mẫu tại vị trí j + 1; counter: = counter + 1; j := j + m + 1; end; else j: =j+ maxd1Sj, d2i; end; Ghi nhận counter; end; Độ phức tạp của thuật toán 4, 5 Độ phức tạp thời gian là O(m + n) và độ phức tạp không gian là O(m). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 26 1.6. Kết luận chương 1 Chương này đã trình bày tổng quan về vấn đề tìm kíêm văn bản, phát biểu và tổng kết các hướng nghiên cứu cho các dạng bài toán tìm kiếm. Nội dung của luận văn tập trung giải quyết bài toán so đơn mẫu, chính xác, xấp xỉ theo hướng tiếp cận sử dụng một số hệ hình thức otomat mờ. Ý nghĩa của tiếp cận này cũng như mô hình otomat mờ tổng quát được giới thiệu ở mục 1.2. Cuối cùng là hai thuật toán kinh điển nổi tiềng cho bài toán so đơn mẫu chính xác là KMP và BM được trình bày. Việc tính toán bảng next trong KMP và ý tưởng về bước dịch chuyển xa trong BM là nguồn gốc cho 2 thuậ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