sweet_lovelycat_42019
New Member
Download 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
MỤC LỤC
MỞ ĐẦU . 1
Chương 1. TÌM KIẾM MẪU TRONG VĂN BẢN THEO CÁCH
TIẾP CẬN OTOMAT MỜ . 5
1.1. Tổng quan về tìm kiếm mẫu trên văn bản . 5
1.1.1 Giới thiệu chung về vấn đề tìm kiếm văn bản . 5
1.1.2. Các dạng tìm kiếm và các kết quả nghiên cứu . 7
1.1.2.1. Tìm đơn mẫu . 7
1.1.2.2. Tìm đa mẫu . 8
1.1.2.3. Tìm mẫu mở rộng . 9
1.1.2.4. Tìm kiếm xấp xỉ . 10
1.1.2.4.1. Phát biểu bài toán . 10
1.1.2.4.2. Các tiếp cận tìm kiếm xấp xỉ . 11
1.1.2.4.3. Độ tương tự giữa hai xâu . 12
1.1.3. Tìm kiếm trong văn bản nén và mã hoá . 14
1.2. Hệ mờ . 15
1.3. Ý tưởng chung của tiếp cận otomat mờ . 15
1.4. Khái niệm otomat mờ . 17
1.5. Một số thuật toán so mẫu . 18
1.5.1. Thuật toán KMP ( Knuth- Morris- Pratt) . 18
1.5.2. Thuật toán BM ( Boyer- Moor) . 22
1.6. Kết luận chương 1 . 26
Chương 2. BÀI TOÁN SO MẪU THEO CÁCH TIẾP CẬN OTOMAT MỜ. 27
2.1. Bài toán so mẫu chính xác . 27
2.1.1. Phát biểu bài toán . 27
2.1.2. Độ mờ của mô hình . 27
2.1.3. Thuật toán KMP mờ . 28
2.1.3.1. Otomat so mẫu . 28
2.1.3.2. Tính đúng đắn của thuật toán . 29
2.1.3.3. Thuật toán . 29
2.1.3.4. So sánh KM P và thuật toán KMP mờ . 32
2.1.4. Thuật toán KMP - BM mờ . 33
2.1.4.1. Ý tưởng của thuật toán . 33
2.1.4.2. Otomat mờ so mẫu . 35
2.1.4.3. Thuật toán 2.4 . 37
2.2. Bài toán so mẫu xấp xỉ. 38
2.2.1. Đặt vấn đề. 38
2.2.2. Bài toán . 39
2.2.3. Độ tương tự dựa trên độ dài khúc con chung của hai xâu . 40
2.2.3.1. Phát biểu bài toán. 40
2.2.3.2. Otomat so mẫu . 42
2.2.4. Độ gần tựa ngữ nghĩa. 43
2.2.4.1. Ý tưởng về độ gần . 43
2.2.4.2. Thuật toán sơ bộ tính độ gần . 44
2.2.4.2.1. Ý tưởng . 44
2.2.4.2.2. Thuật toán chi tiết . 44
2.2.4.3. Giải thích độ mờ của mô hình . 45
2.3. Kết luận chương 2 . 46
Chương 3. TÌM KIẾM MẪU TRONG VĂN BẢN NÉN VÀ MÃ HOÁ . 47
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á . 47
3.2. Tìm kiếm trên văn bản nén . 50
3.2.1. Các mô hình nén văn bản . 50
3.2.2. Thuật toán tìm kiếm trên dữ liệu nén dạng text . 50
3.3. Tìm kiếm trên văn bản mã hóa. 55
3.3.1. Tìm kiếm trên văn bản mã hóa dạng khối kí tự . 55
3.3.2. Mã đàn hồi . 55
3.3.3. Tìm kiếm trên văn bản mã hóa bởi mã đàn hồi . 58
3.3.3.1. Ý tưởng chung . 58
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 . 59
3.3.3.2.1. Bài toán . 59
3.3.3.2.2. Mô tả phương pháp . 59
3.3.3.2.3. Chi tiết hóa các otomat trong thuật toán . 60
3.3.3.2.4. Thuật toán tìm kiếm mẫu dựa trên otomat . 61
3.3.4. Tìm kiếm trên văn bản mã hóa hai tầng . 63
3.4. Kết luận chương 3 . 64
KẾT LUẬN . 65
TÀI LIỆU THAM KHẢO . 67
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
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 cô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) hay 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 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
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 = nexti, 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:
+ nexti 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ó nextm + 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 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í Phần mềm 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 Phần mềm 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ử Phần mềm 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 Phần mềm 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ộ...
Download miễn phí 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
MỤC LỤC
MỞ ĐẦU . 1
Chương 1. TÌM KIẾM MẪU TRONG VĂN BẢN THEO CÁCH
TIẾP CẬN OTOMAT MỜ . 5
1.1. Tổng quan về tìm kiếm mẫu trên văn bản . 5
1.1.1 Giới thiệu chung về vấn đề tìm kiếm văn bản . 5
1.1.2. Các dạng tìm kiếm và các kết quả nghiên cứu . 7
1.1.2.1. Tìm đơn mẫu . 7
1.1.2.2. Tìm đa mẫu . 8
1.1.2.3. Tìm mẫu mở rộng . 9
1.1.2.4. Tìm kiếm xấp xỉ . 10
1.1.2.4.1. Phát biểu bài toán . 10
1.1.2.4.2. Các tiếp cận tìm kiếm xấp xỉ . 11
1.1.2.4.3. Độ tương tự giữa hai xâu . 12
1.1.3. Tìm kiếm trong văn bản nén và mã hoá . 14
1.2. Hệ mờ . 15
1.3. Ý tưởng chung của tiếp cận otomat mờ . 15
1.4. Khái niệm otomat mờ . 17
1.5. Một số thuật toán so mẫu . 18
1.5.1. Thuật toán KMP ( Knuth- Morris- Pratt) . 18
1.5.2. Thuật toán BM ( Boyer- Moor) . 22
1.6. Kết luận chương 1 . 26
Chương 2. BÀI TOÁN SO MẪU THEO CÁCH TIẾP CẬN OTOMAT MỜ. 27
2.1. Bài toán so mẫu chính xác . 27
2.1.1. Phát biểu bài toán . 27
2.1.2. Độ mờ của mô hình . 27
2.1.3. Thuật toán KMP mờ . 28
2.1.3.1. Otomat so mẫu . 28
2.1.3.2. Tính đúng đắn của thuật toán . 29
2.1.3.3. Thuật toán . 29
2.1.3.4. So sánh KM P và thuật toán KMP mờ . 32
2.1.4. Thuật toán KMP - BM mờ . 33
2.1.4.1. Ý tưởng của thuật toán . 33
2.1.4.2. Otomat mờ so mẫu . 35
2.1.4.3. Thuật toán 2.4 . 37
2.2. Bài toán so mẫu xấp xỉ. 38
2.2.1. Đặt vấn đề. 38
2.2.2. Bài toán . 39
2.2.3. Độ tương tự dựa trên độ dài khúc con chung của hai xâu . 40
2.2.3.1. Phát biểu bài toán. 40
2.2.3.2. Otomat so mẫu . 42
2.2.4. Độ gần tựa ngữ nghĩa. 43
2.2.4.1. Ý tưởng về độ gần . 43
2.2.4.2. Thuật toán sơ bộ tính độ gần . 44
2.2.4.2.1. Ý tưởng . 44
2.2.4.2.2. Thuật toán chi tiết . 44
2.2.4.3. Giải thích độ mờ của mô hình . 45
2.3. Kết luận chương 2 . 46
Chương 3. TÌM KIẾM MẪU TRONG VĂN BẢN NÉN VÀ MÃ HOÁ . 47
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á . 47
3.2. Tìm kiếm trên văn bản nén . 50
3.2.1. Các mô hình nén văn bản . 50
3.2.2. Thuật toán tìm kiếm trên dữ liệu nén dạng text . 50
3.3. Tìm kiếm trên văn bản mã hóa. 55
3.3.1. Tìm kiếm trên văn bản mã hóa dạng khối kí tự . 55
3.3.2. Mã đàn hồi . 55
3.3.3. Tìm kiếm trên văn bản mã hóa bởi mã đàn hồi . 58
3.3.3.1. Ý tưởng chung . 58
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 . 59
3.3.3.2.1. Bài toán . 59
3.3.3.2.2. Mô tả phương pháp . 59
3.3.3.2.3. Chi tiết hóa các otomat trong thuật toán . 60
3.3.3.2.4. Thuật toán tìm kiếm mẫu dựa trên otomat . 61
3.3.4. Tìm kiếm trên văn bản mã hóa hai tầng . 63
3.4. Kết luận chương 3 . 64
KẾT LUẬN . 65
TÀI LIỆU THAM KHẢO . 67
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung:
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 cô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) hay 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 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
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 = nexti, 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:
+ nexti 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ó nextm + 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 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í Phần mềm 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 Phần mềm 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ử Phần mềm 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 Phần mềm 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ộ...