Luận văn Bài toán tìm kiếm văn bản sử dụng giải thuật di truyền
ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
NGUYỄN VĂN QUYẾT
BÀI TOÁN TÌM KIẾM VĂN BẢN
SỬ DỤNG GIẢI THUẬT DI TRUYỀN
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
CHUYÊN NGÀNH KHOA HỌC MÁY TÍNH
Thái Nguyên - 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
®¹i häc Th¸i Nguyªn
Khoa C«ng nghÖ th«ng tin
NguyÔn v¨n quyÕt
Bµi to¸n t×m kiÕm v¨n b¶n
sö dông gi¶I thuËt di truyÒn
Chuyªn nghµnh: Khoa häc m¸y tÝnh
M· sè: 60.48.01
TÓM TẮT LUẬN VĂN THẠC SĨ
Th¸i Nguyªn - 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
LỜI CẢM ƠN
Trước hết em xin gửi lời cảm ơn chân thành đến toàn thể các thầy cô giáo
Viện Công nghệ Thông tin đã tận tình dạy dỗ chúng em trong suốt quá trình học
tập tại khoa Công nghệ thông tin - Đại học Thái Nguyên.
Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo TS Vũ Mạnh
Xuân - Trưởng Khoa Toán, Trưởng Phòng Công nghệ Thông tin - Thư viện
trường Đại học Sư phạm - Đại học Thái Nguyên đã quan tâm hướng dẫn và đưa
ra những gợi ý, góp ý, chỉnh sửa vô cùng quý báu cho em trong quá trình làm
luận văn tốt nghiệp.
Cuối cùng xin chân thành cảm ơn những người bạn đã giúp đỡ, chia sẽ với
em trong suốt quá trình làm luận văn.
Thái Nguyên, Ngày 01 tháng 10 năm 2009
Học viên
Nguyễn Văn Quyết
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của cá nhân tôi. Các số
liệu, kết quả có trong luận văn là trung thực và chưa được công bố trong bất kỳ
một công trình nào khác.
Thái Nguyên, ngày 10 tháng11 năm 2009
Tác giả luận văn
Nguyễn Văn Quyết
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
i
MỤC LỤC
Trang
Trang phụ bìa
Lời cam đoan
Mục lục ........................................................................................................ i
Danh mục các thuật ngữ............................................................................... iv
Danh mục các hình vẽ, bảng biểu................................................................. v
MỞ ĐẦU:.................................................................................................... 1
1. ĐẶT VẤN ĐỀ.................................................................................... 1
2. MỤC ĐÍCH CỦA LUẬN VĂN .............................................................. 2
3. NỘI DUNG CỦA LUẬN VĂN................................................................ 2
4. PHƯƠNG PHÁP NGHIÊN CỨU ............................................................ 2
NỘI DUNG .................................................................................................
CHƯƠNG 1. MỘT SỐ KỸ THUẬT TÌM KIẾM VĂN BẢN ...................... 3
1.1. Bài toán tìm kiếm văn bản..................................................................... 3
1.2. Các thuật toán........................................................................................ 4
1.2.1. Thuật toán Brute Force ....................................................................... 4
1.2.2. Thuật toán Knuth-Morris-Pratt ........................................................... 5
1.2.3. Thuật toán Deterministic Finite Automaton (máy automat hữu hạn)... 7
1.2.4. Thuật toán Boyer-Moore .................................................................... 10
1.2.5. Thuật toán Karp-Rabin ....................................................................... 15
1.2.6. Các thuật toán khác ............................................................................ 17
CHƯƠNG 2. GIỚI THIỆU VỀ GIẢI THUẬT DI TRUYỀN ....................... 20
2.1. Tổng quan về giải thuật di truyền .......................................................... 20
2.1.1. Giới thiệu ........................................................................................... 20
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ii
2.1.2. Sự khác biệt của giải thuật di truyền so với các giải thuật khác........... 21
2.1.3. Tính chất quan trọng của giải thuật di truyền...................................... 21
2.2. Giải thuật di truyền cổ điển ................................................................... 22
2.2.1. Giới thiệu ........................................................................................... 22
2.2.2. Các toán tử di truyền .......................................................................... 24
2.2.2.1. Toán tử chọn lọc.............................................................................. 24
2.2.2.2. Toán tử lai ghép............................................................................... 25
2.2.2.3. Toán tử đột biến............................................................................... 26
2.2.3. Các bước quan trọng trong việc áp dụng giải thuật di truyền cổ điển.. 26
2.2.4. Ví dụ .................................................................................................. 27
CHƯƠNG 3. SỬ DỤNG GIẢI THUẬT DI TRUYỀN ĐỂ TÌM KIẾM
VĂN BẢN.............................................................................33
3.1. Yêu cầu đặt ra cho bài toán tìm kiếm văn bản........................................ 33
3.2. Xây dựng hàm tìm kiếm văn bản........................................................... 34
3.3. Phát biểu bài toán tìm kiếm văn bản theo hướng tiếp cận di truyền ....... 35
3.4. Tìm độ dài xâu con chung lớn nhất bằng quy hoạch động ..................... 38
3.5. Áp dụng giải thuật di truyền .................................................................. 39
3.5.1. Biểu diễn nhiễm sắc thể...................................................................... 39
3.5.2. Khởi tạo quần thể ............................................................................... 40
3.5.3. Hàm mục tiêu ..................................................................................... 40
3.5.4. Các toán tử di truyền .......................................................................... 41
3.5.5. Các tham số........................................................................................ 42
3.5.6. Chi phí thời gian................................................................................. 42
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
iii
CHƯƠNG 4. KẾT QUẢ THỰC NGHIỆM VÀ PHÁT TRIỂN PHẦN
MỀM ỨNG DỤNG ...............................................................44
4.1. Các kết quả thử nghiệm......................................................................... 44
4.1.1. Kết quả thử nghiệm tìm kiếm tuyến tính............................................. 44
4.1.1.1. Tìm kiếm tuyến tính bằng so khớp chuỗi......................................... 44
4.1.1.2. Tìm kiếm tuyến tính sử dụng hàm quy hoạch động.......................... 45
4.1.2. Kết quả thử nghiệm tìm kiếm bằng giải thuật di truyền ...................... 46
4.2. Phát triển phần mềm ứng dụng .............................................................. 50
KẾT LUẬN VÀ ĐỀ NGHỊ ........................................................................ 51
TÀI LIỆU THAM KHẢO.......................................................................... 52
PHỤ LỤC.................................................................................................... 54
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
iv
CÁC THUẬT NGỮ SỬ DỤNG TRONG LUẬN VĂN
Heredity, Genetic
Genetic Algorithm (GA)
Individual
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
Di truyền
Thuật giải di truyền
Cá thể
Genome
Bộ gen
Mode
Chế độ
Multi Mode
Đa chế độ
Mutation
Đột biến
Renewable Resource
Nonrenewable Resource
Offstring 1
Tài nguyên tái sử dụng
Tài nguyên không tái sử dụng
Cá thể con trai
Cá thể con gái
Lai ghép một điểm
Cá thể cha
Offstring 2
One point crossover
Parent 1
Parent 2
Cá thể mẹ
Popuplation
Quần thể
Reproduction
Response surface
Two point crossover
Uniform Crossover
Sinh sản
Bề mặt đáp ứng
Lai ghép hai điểm
Lai ghép đồng nhất
Tối ưu tổ hợp
Lai ghép
combinatorial optimization :
Crossover
Fitness
:
:
Độ thích nghi, hàm thích nghi
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
NGUYỄN VĂN QUYẾT
BÀI TOÁN TÌM KIẾM VĂN BẢN
SỬ DỤNG GIẢI THUẬT DI TRUYỀN
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. VŨ MẠNH XUÂN
Thái Nguyên - 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1
MỞ ĐẦU
1. Đặt vấn đề
Ngày nay máy tính đã được sử dụng trong mọi lĩnh vực của đời sống,
vì vậy kho thông tin trong máy tính tăng trưởng không ngừng và thật khó
khăn cho công tác tìm kiếm (nhất là tìm kiếm trên các file văn bản). Hãng
Microsoft đã hỗ trợ tìm kiếm tự động bằng công cụ Search được tích hợp sẵn
trong hệ điều hành Windows, trong đó cho ta hai cách thức tìm kiếm file là:
tìm theo từ khoá tên file (All or part of the file name) – đưa ra các file có tên
chứa khoá tìm kiếm; và tìm theo từ khoá nội dung trong file (A word or
phrase in the file) – đưa ra các file văn bản có chứa một từ hoặc cụm từ giống
với từ khoá. Mặc dù Search trong Windows hỗ trợ mạnh chức năng tìm kiếm
theo tên file, nhưng tìm theo nội dung trong file vẫn còn có những hạn chế
nhất định, chẳng hạn: Search chỉ đưa ra các file văn bản có chứa chính xác từ
khoá tìm kiếm, như vậy sẽ rất khó khăn nếu người dùng không nhớ chính xác
từ khoá có trong nội dung văn bản mà chỉ nhớ gần đúng với từ khoá, hơn nữa
công cụ Search không chỉ ra được cụm từ khoá tìm được nằm ở đâu trong văn
bản và tần suất xuất hiện của chúng, nên nếu cần người dùng lại một lần nữa
phải đi dò tìm bằng các công cụ tìm kiếm khác.
Vì lẽ đó bài toán tìm kiếm văn bản là bài toán rất thiết thực đang được
nhiều người quan tâm, vấn đề cấp thiết đặt ra là giải quyết bài toán tìm kiếm
văn bản sao cho hiệu quả, đáp ứng được nhu cầu của người sử dụng. Luận văn
này định hướng nghiên cứu sử dụng giải thuật di truyền tìm trong file văn bản
các đoạn văn bản giống hoặc gần giống với mẫu (từ khoá) cần tìm kiếm.
Với mục tiêu đó, tôi lựa chọn đề tài nghiên cứu của luận văn là “Bài
toán tìm kiếm văn bản sử dụng giải thuật di truyền”. Đây là hướng tiếp cận
khá mới đối với bài toán này, hy vọng rằng kết quả đạt được sẽ có hiệu quả
đáng kể so với các phương pháp tìm kiếm khác.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2
2. Mục đích của luận văn
Mục đích của luận văn là: nghiên cứu các phương pháp tìm kiếm văn
bản và tìm cách ứng dụng giải thuật di truyền để giải quyết bài toán này, trên
cơ sở đó xây dựng phần mềm ứng dụng tìm kiếm văn bản một cách hiệu quả
và thiết thực.
3. Nội dung của luận văn
Đề tài tập trung vào bài toán tìm kiếm văn bản theo hướng tiếp cận sau:
Tìm các vị trí trong văn bản có xuất hiện chuỗi văn bản giống hoặc gần giống
với chuỗi văn bản mẫu (xuất hiện gần giống trong trường hợp văn bản tìm
kiếm không chứa chuỗi văn bản mẫu). Trên cơ sở đó, nội dung của luận văn
gồm bốn chương sau phần Mở đầu:
- Chương 1: Nghiên cứu khái quát về các kỹ thuật tìm kiếm văn bản.
- Chương 2: Tìm hiểu giải thuật di truyền, chú trọng đến các kỹ thuật có
liên quan đến bài toán tìm kiếm.
- Chương 3: Xây dựng và phát biểu bài toán, đề xuất phương pháp sử
dụng giải thuật di truyền trong tìm kiếm văn bản.
Chương 4: Kết quả thử nghiệm và phát triển phần mềm ứng dụng.
4. Phƣơng pháp nghiên cứu
Nghiên cứu tài liệu, đề xuất giải pháp và lập trình thử nghiệm.
Luận văn đã bước đầu đề xuất phương pháp ứng dụng giải thuật di
truyền vào giải quyết bài toán tìm kiếm văn bản, các chương trình thử nghiệm
đã minh chứng hướng tiếp cận là đúng đắn và có hiệu quả. Đặc biệt chương
trình đã chỉ ra được các vị trí xuất hiện đoạn văn bản giống văn bản mẫu hoặc
gần giống với văn bản mẫu (trong trường hợp văn bản không chứa văn bản
mẫu) cần tìm trong thời gian cho phép. Hiện nay chúng tôi đang trong quá
trình phát triển phần mềm ứng dụng dựa vào các kết quả nghiên cứu này.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
3
CHƢƠNG 1
MỘT SỐ KỸ THUẬT TÌM KIẾM VĂN BẢN
Trong phần này chúng ta sẽ quan tâm đến bài toán tìm kiếm văn bản
thông dụng và các thuật toán đã có để tìm kiếm tất cả các vị trí xuất hiện của
mẫu trên một văn bản. Các thuật toán này được chạy trên chương trình thử
nghiệm, cài đặt sẽ dùng một hàm ra : Output để thông báo các vị trí tìm thấy
mẫu.
1.1. Bài toán tìm kiếm văn bản
Dữ liệu trong máy tính được lưu trữ dưới rất nhiều dạng khác nhau,
nhưng sử dụng chuỗi vẫn là một trong những cách rất phổ biến. Trên chuỗi
các đơn vị dữ liệu không có ý nghĩa quan trọng bằng cách sắp xếp của chúng.
Ta có thể thấy các dạng khác nhau của chuỗi như ở các file dữ liệu, trên biểu
diễn của các gen, hay chính văn bản chúng ta đang đọc.
Một phép toán cơ bản trên chuỗi là đối sánh mẫu (pattern matching),
bài toán yêu cầu ta tìm ra một hoặc nhiều vị trí xuất hiện của mẫu trên một
văn bản.. Trong đó mẫu và văn bản là các chuỗi có độ dài M và N (M ≤ N),
tập các ký tự được dùng gọi là bảng chữ cái Σ, có số lượng là δ.
Việc đối sánh mẫu diễn ra với nhiều lần thử trên các đoạn khác nhau
của văn bản. Trong đó cửa sổ là một chuỗi M ký tự liên tiếp trên văn bản.
Mỗi lần thử chương trình sẽ kiểm tra sự giống nhau giữa mẫu với cửa sổ hiện
thời. Tùy theo kết quả kiểm tra cửa sổ sẽ được dịch đi sang phải trên văn bản
cho lần thử tiếp theo.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
4
1.2. Các thuật toán
1.21. Thuật toán Brute Force
Thuật toán Brute Force thử kiểm tra tất cả các vị trí trên văn bản từ 1
cho đến n-m+1. Sau mỗi lần thử thuật toán Brute Force dịch mẫu sang phải
một ký tự cho đến khi kiểm tra hết văn bản.
Thuật toán Brute Force không cần công việc chuẩn bị cũng như các
mảng phụ cho quá trình tìm kiếm. Độ phức tạp tính toán của thuật toán này là
O(n*m).
Thủ tục cài đặt:
function IsMatch(const X: string; m: integer;
const Y: string; p: integer): boolean;
var
i: integer;
begin
IsMatch := false;
Dec(p);
for i := 1 to m do
if X[i] <> Y[p + i] then Exit;
IsMatch := true;
end;
procedure BF(const X: string; m: integer;
const Y: string; n: integer);
var
i: integer;
begin
for i := 1 to n - m + 1 do
if IsMatch(X, m, Y, i) then
Output(i); { Thông báo tìm thấy mẫu tại vị trí i của văn bản }
end;
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
5
1.2.2. Thuật toán Knuth-Morris-Pratt
Thuật toán Knuth-Morris-Pratt là thuật toán có độ phức tạp tuyến tính
đầu tiên được phát hiện ra, nó dựa trên thuật toán brute force với ý tưởng lợi
dụng lại những thông tin của lần thử trước cho lần sau. Trong thuật toán brute
force vì chỉ dịch cửa sổ đi một ký tự nên có đến m-1 ký tự của cửa sổ mới là
những ký tự của cửa sổ vừa xét. Trong đó có thể có rất nhiều ký tự đã được so
sánh giống với mẫu và bây giờ lại nằm trên cửa sổ mới nhưng được dịch đi về
vị trí so sánh với mẫu. Việc xử lý những ký tự này có thể được tính toán trước
rồi lưu lại kết quả. Nhờ đó lần thử sau có thể dịch đi được nhiều hơn một ký
tự, và giảm số ký tự phải so sánh lại.
Xét lần thử tại vị trí j, khi đó cửa sổ đang xét bao gồm các ký tự
y[j…j+m-1] giả sử sự khác biệt đầu tiên xảy ra giữa hai ký tự x[i] và y[j+i-1].
Khi đó x[1…i]=y[j…i+j-1]=u và a=x[i]y[i+j]=b. Với trường hợp
này, dịch cửa sổ phải thỏa mãn v là phần đầu của xâu xkhớp với phần đuôi
của xâu utrên văn bản. Hơn nữa ký tự c ở ngay sau v trên mẫu phải khác với
ký tự a. Trong những đoạn như v thoả mãn các tính chất trên ta chỉ quan tâm
đến đoạn có độ dài lớn nhất.
U
u
v
b
c
a
x
Y
x
j
i + j - 1
Dịch cửa sổ sao cho v phải khớp với u và c a
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
6
Thuật toán Knuth-Morris-Pratt sử dụng mảng Next[i] để lưu trữ độ dài
lớn nhất của xâu v trong trường hợp xâu u=x[1…i-1]. Mảng này có thể tính
trước với chi phí về thời gian là O(m) (việc tính mảng Next thực chất là một
bài toán qui hoạch động một chiều).
Thuật toán Knuth-Morris-Pratt có chi phí về thời gian là O(m+n) với
nhiều nhất là 2n-1 lần số lần so sánh ký tự trong quá trình tìm kiếm.
Thủ tục cài đặt:
procedure preKMP(const X: string; m: integer;
var Next: array of integer);
var
i, j: integer;
begin
i := 1;
j := 0;
Next[1] := 0;
while (i <= m) do
begin
while (j > 0)and(X[i] <> X[j]) do j := Next[j];
Inc(i);
Inc(j);
if X[i] = X[j] then Next[i] := Next[j]
else Next[i] := j;
end;
end;
procedure KMP(const X: string; m: integer;
const Y: string; n: integer);
var
i, j: integer;
Next: ^TIntArr; { TIntArr = array[0..maxM] of integer }
begin
GetMem(Next, (m + 1)*SizeOf(Integer));
preKMP(X, m, Next^);
i := 1;
j := 1;
while (j <= n) do
begin
{dịch đi nếu không khớp}
while (i > 0)and(X[i] <> Y[j]) do i := Next^[i];
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
7
Inc(i);
Inc(j);
if i > m then
begin
Output(j - i + 1);
i := Next^[i];
end;
end;
FreeMem(Next, (m + 1)*SizeOf(Integer));
End;
1.2.3. Thuật toán Deterministic Finite Automaton (máy automat hữu
hạn)
Trong thuật toán này, quá trình tìm kiếm được đưa về một quá trình
biến đổi trạng thái automat. Hệ thống automat trong thuật toán DFA sẽ được
xây dựng dựa trên xâu mẫu. Mỗi trạng thái (nút) của automat lúc sẽ đại diện
cho số ký tự đang khớp của mẫu với văn bản. Các ký tự của văn bản sẽ làm
thay đổi các trạng thái. Và khi đạt được trạng cuối cùng có nghĩa là đã tìm
được một vị trí xuất hiện ở mẫu.
Thuật toán này có phần giống thuật toán Knuth-Morris-Pratt trong việc
nhảy về trạng thái trước khi gặp một ký tự không khớp, nhưng thuật toán
DFA có sự đánh giá chính xác hơn vì việc xác định vị trí nhảy về dựa trên ký
tự không khớp của văn bản (trong khi thuật toán KMP lùi về chỉ dựa trên vị
trí không khớp).
Với xâu mẫu là GCAGAGAG ta có hệ automat sau
0
2
1
3
4
5
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
8
6
7
8
G
G
G
G
G
C
C
C
G
C
A
G
A
G
A
G
Với ví dụ ở hình trên ta có:
* Nếu đang ở trạng thái 2 gặp ký tự A trên văn bản sẽ chuyển sang
trạng thái 3
* Nếu đang ở trạng thái 6 gặp ký tự C trên văn bản sẽ chuyển sang
trạng thái 2
* Trạng thái 8 là trạng thái cuối cùng, nếu đạt được trạng thái này có
nghĩa là đã tìm thất một xuất hiện của mẫu trên văn bản
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
9
* Trạng thái 0 là trạng thái mặc định (các liên kết không được biểu thị
đều chỉ về trạng thái này), ví dụ ở nút 5 nếu gặp bất kỳ ký tự nào khác G thì
đều chuyển về trạng thái 0
Việc xây dựng hệ automat khá đơn giản khi được cài đặt trên ma trận
kề. Khi đó thuật toán có thời gian xử lý là O(n) và thời gian và bộ nhớ để tạo
ra hệ automat là O(m*) (tùy cách cài đặt)
Nhưng ta nhận thấy rằng trong DFA chỉ có nhiều nhất m cung thuận và
m cung nghịch, vì vậy việc lưu trữ các cung không cần thiết phải lưu trên ma
trận kề mà có thể dùng cấu trúc danh sách kề Forward Star để lưu trữ. Như
vậy thời gian chuẩn bị và lượng bộ nhớ chỉ là O(m). Tuy nhiên thời gian tìm
kiếm có thể tăng lên một chút so với cách lưu ma trận kề.
Cài đặt dưới đây xin được dùng cách đơn giản (ma trận kề)
Type
TAut = array[0..maxM, 0..maxd] of integer;
procedure preAUT(const X: string; m: integer; var G: TAut);
var
i, j, prefix, cur, c, newState: integer;
begin
FillChar(G, SizeOf(G), 0);
cur := 0;
for i := 1 to m do
begin
prefix := G[cur, Ord(X[i])]; {x[1..prefix]=x[i-prefix+1..i]}
newState := i;
G[cur, Ord(X[i])] := newState;
for c := 0 to maxd do {copy prefix -> newState }
G[newState, c] := G[prefix, c];
cur := newState;
end;
end;
procedure AUT(const X: string; m: integer;
const Y: string; n: integer);
var
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
10
G: ^TAut;
state, i: integer;
begin
New(G);
preAUT(X, m, G^);
state := 0;
for i := 1 to n do
begin
state := G^[state, Ord(Y[i])]; {chuyển trạng thái}
if state = m then Output(i - m + 1);
end;
Dispose(G);
end;
1.2.4. Thuật toán Boyer-Moore
Thuật toán Boyer Moore là thuật toán có tìm kiếm chuỗi rất có hiệu quả
trong thực tiễn, các dạng khác nhau của thuật toán này thường được cài đặt
trong các chương trình soạn thảo văn bản.
Khác với thuật toán Knuth-Morris-Pratt (KMP), thuật toán Boyer-
Moore kiểm tra các ký tự của mẫu từ phải sang trái và khi phát hiện sự khác
nhau đầu tiên thuật toán sẽ tiến hành dịch cửa sổ đi Trong thuật toán này có
hai cách dịch của sổ:
Cách thứ 1: gần giống như cách dịch trong thuật toán KMP, dịch sao
cho những phần đã so sánh trong lần trước khớp với những phần giống nó
trong lần sau.
Trong lần thử tại vị trí j, khi so sánh đến ký tự i trên mẫu thì phát hiện
ra sự khác nhau, lúc đó x[i+1…m]=y[i+j...j+m-1]=u và
-1]=b
khi đó thuật toán sẽ dịch cửa sổ sao cho đoạn u=y[i+j…j+m-1] giống với một
đoạn mới trên mẫu (trong các phép dịch ta chọn phép dịch nhỏ nhất)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
11
u
b
c
a
x
y
x
u
dịch
u
Dịch sao cho u xuất hiện lại và c ≠ a
Nếu không có một đoạn nguyên vẹn của u xuất hiện lại trong x, ta sẽ
chọn sao cho phần đôi dài nhất của u xuất hiện trở lại ở đầu mẫu.
u
b
a
y
x
dịch
u
u
x
Dịch để một phần đôi của u xuất hiện lại trên x
Cách thứ 2: Coi ký tự đầu tiên không khớp trên văn bản là b=y[i+j-1] ta
sẽ dịch sao cho có một ký tự giống b trên xâu mẫu khớp vào vị trí đó (nếu có
nhiều vị trí xuất hiện b trên xâu mẫu ta chọn vị trí phải nhất).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
12
u
b
a
y
x
dịch
u
b
x
không chứa b
Dịch để ký tự b ăn khớp với văn bản.
Nếu không có ký tự b nào xuất hiện trên mẫu ta sẽ dịch cửa sổ sao cho ký tự
trái nhất của cửa sổ vào vị trí ngay sau ký tự y[i+j-1]=b để đảm bảo sự ăn
khớp
u
b
a
y
x
dịch
u
x
không chứa b
Dịch khi b không xuất hiện trong x
Trong hai cách dịch thuật toán sẽ chọn cách dịch có lợi nhất.
Trong cài đặt ta dùng mảng bmGs để lưu cách dịch 1, mảng bmBc để
lưu phép dịch thứ 2(ký tự không khớp). Việc tính toán mảng bmBc thực sự
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13
không có gì nhiều để bàn. Nhưng việc tính trước mảng bmGs khá phức tạp, ta
không tính trực tiếp mảng này mà tính gián tiếp thông qua mảng suff. Có
suff[i]=max{k | x[i-k+1…i]=x[m-k+1…m]}
Các mảng bmGs và bmBc có thể được tính toán trước trong thời gian tỉ
lệ với O(m+). Thời gian tìm kiếm (độ phức tạp tính toán) của thuật toán
Boyer-Moore là O(m*n). Tuy nhiên với những bản chữ cái lớn thuật toán thực
hiện rất nhanh. Trong trường hợp tốt chi phí thuật toán có thể xuống đến
O(n/m) là chi phí thấp nhất của các thuật toán tìm kiếm hiện đại có thể đạt
được.
Thủ tục cài đặt:
procedure preBmBc(const X: string; m: integer;
var bmBc: array of integer);
var
i: integer;
begin
for i := 0 to maxd - 1 do bmBc[i] := m;
for i := 1 to m - 1 do bmBc[Ord(X[i])] := m - i;
end;
procedure suffixes(const X: string; m: integer;
var suff: array of integer);
var
right, left, i: integer;
begin
suff[m] := m;
left := m;
for i := m - 1 downto 1 do
if (i > left)and(suff[i + m - right] < i -
left) then
suff[i] := suff[i + m - right]
else
begin
if (i < left) then left := i;
right := i;
while (left >= 1)and(X[left] = X[left + m -
right]) do
Dec(left);
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
14
suff[i] := right - left; {X[left…right] = X[m+left-
right…m]}
end;
end;
procedure preBmGs(const X: string; m: integer;
var bmGs: array of integer);
var
i, j: integer;
suff: ^TIntArr;
begin
GetMem(suff, (m + 1)*SizeOf(Integer));
suffixes(X, m, suff^); {Tính mảng suff}
for i := 1 to m do bmGs[i] := m;
j := 0;
for i := m downto 0 do
if (i = 0)or(suff^[i] = i) then
while (j < m - i) do
begin
{Nếu bmGs[j] chưa có giá trị thì điền vào}
if bmGs[j] = m then bmGs[j] := m - i;
Inc(j);
end;
for i := 1 to m - 1 do bmGs[m - suff^[i]] := m -
i; {đảo lại}
FreeMem(suff, (m + 1)*SizeOf(Integer));
end;
procedure BM(const X: string; m: integer;
const Y: string; n: integer);
var
i, j: integer;
bmBc, bmGs: ^TIntArr;
begin
GetMem(bmBc, (m + 1)*SizeOf(Integer));
GetMem(bmGs, (m + 1)*SizeOf(Integer));
preBmBc(X, m, bmBc^);
preBmGs(X, m, bmGs^);
j := 1;
while (j <= n - m + 1) do
begin
i := m;
while (i >= 1)and(X[i] = Y[i + j - 1]) do
Dec(i);
if (i < 1) then
begin
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
15
Output(j);
j := j + bmGs^[1];
end
else {chọn cách dịch được lợi nhất }
j := j + Max(bmGs^[i], bmBc^[Ord(Y[i + j -
1])] - m + i);
end;
FreeMem(bmBc, (m + 1)*SizeOf(Integer));
FreeMem(bmGs, (m + 1)*SizeOf(Integer));
end;
Thuật toán Boyer-Moore có thể đạt tới chi phí O(n/m) là nhờ có cách
dịch thứ 2 “ký tự không khớp”. Cách chuyển cửa sổ khi gặp “ký tự không
khớp” cài đặt vừa đơn giản lại rất hiệu quả trong các bảng chữ cái lớn nên có
nhiều thuật toán khác cũng đã lợi dụng các quét mẫu từ phải sang trái để sử
dụng cách dịch này.
Tuy nhiên chi phí thuật toán của Boyer-Moore là O(m*n) vì cách dịch
thứ nhất của thuật toán này không phân tích triệt để các thông tin của những
lần thử trước, những đoạn đã so sánh rồi vẫn có thể bị so sánh lại. Có một vài
thuật toán đã cải tiến cách dịch này để đưa đến chi phí tính toán của thuật toán
Boyer-Moore là tuyến tính.
1.2.5. Thuật toán Karp-Rabin
Karp-Rabin bài toán tìm kiếm chuỗi không khác nhiều so với bài toán
tìm kiếm chuẩn. Tại đây một hàm băm được dùng để tránh đi sự so sánh
không cần thiết. Thay vì phải so sánh tất các vị trí của văn bản, ta chỉ cần so
sánh những cửa sổ bao gồm những ký tự “có vẻ giống” mẫu.
Trong thuật toán này hàm băm phải thỏa mãn một số tính chất như phải
dễ dàng tính được trên chuỗi, và đặc biệt công việc tính lại phải đơn giản để ít
ảnh hưởng đến thời gian thực hiện của thuật toán. Và hàm băm được chọn ở
đây là:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
16
hash(w[i…i+m-1]) = h = (w[i]*dm-1 + w[i+1]*dm-2 + … w[i+m-
1]*d0) mod q
Việc tính lại hàm băm sau khi dịch cửa sổ đi một ký tự chỉ đơn gian
như sau:
h = ((h – w[i]*dm-1)*d + w[i+m]
Trong bài toán này ta có thể chọn d = 2 để tiện cho việc tính toán a*2
tương đương a shl 1. Và không chỉ thế ta chọn q = MaxLongint khi đó phép
mod q không cần thiết phải thực hiện vì sự tràn số trong tính toán chính là
một phép mod có tốc độ rất nhanh.
Việc chuẩn bị trong thuật toán Karp-Rabin có độ phức tạp O(m). Tuy
vậy thời gian tìm kiếm lại tỉ lệ với O(m*n) vì có thể có nhiều trường hợp hàm
băm của chúng ta bị lừa và không phát huy tác dụng. Nhưng đó chỉ là những
trường hợp đặc biệt, thời gian tính toán của thuật toán KR trong thực tế
thường tỉ lệ với O(n+m). Hơn nữa thuật toán KR có thể dễ dàng mở rộng cho
các mẫu, văn bản dạng 2 chiều, do đó khiến cho nó trở nên hữu ích hơn so với
các thuật toán còn lại trong việc xử lý ảnh.
procedure KR(const X: string; m: integer;
const Y: string; n: integer);
var
dM, hx, hy: longint;
i, j: integer;
begin
{$Q-} { Disable arithmetic overflow checking }
dM := 1;
for i := 1 to m - 1 do dM := dM shl 1;
hx := 0;
hy := 0;
for i := 1 to m do
begin
hx := (hx shl 1) + Ord(X[i]);
hy := (hy shl 1) + Ord(Y[i]);
end;
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
17
j := 1;
while j <= n - m do
begin
if hx = hy then
if IsMatch(X, m, Y, j) then Output(j);
{hàm IsMatch trong phần BruteForce}
hy := ((hy - Ord(Y[j])*dM) shl 1) + Ord(Y[j +
m]); {Rehash}
Inc(j);
end;
if hx = hy then
if IsMatch(X, m, Y, j) then Output(j);
end;
1.2.6. Các thuật toán khác
Một số thuật toán nêu trên chưa phải là tất cả các thuật toán tìm kiếm
chuỗi hiện có. Nhưng chúng đã đại diện cho đa số các tư tưởng dùng để giải
bài toán tìm kiếm chuỗi.
Các thuật toán so sánh mẫu lần lượt từ trái sang phải thường là các
dạng cải tiến (và cải lùi) của thuật toán Knuth-Morris-Pratt và thuật toán sử
dụng Automat như: Forward Dawg Matching, Apostolico-Crochemore, Not
So Naive, …
Các thuật toán so sánh mẫu từ phải sang trái đều là các dạng của thuật
toán Boyer-Moore. Phải nói lại rằng thuật toán BM là thuật toán tìm kiếm rất
hiệu quả trên thực tế nhưng độ phức tạp tính toán lý thuyết lại là O(m*n).
Chính vì vậy những cải tiến của thuật toán này cho độ phức tạp tính toán lý
thuyết tốt như: thuật toán Apostolico-Giancarlo đánh dấu lại những ký tự đã
so sánh rồi để khỏi bị so sánh lặp lại, thuật toán Turbo-BM đánh giá chặt chẽ
hơn các thông tin trước để có thể dịch được xa hơn và ít bị lặp, … Còn có một
số cải tiến khác của thuật toán BM không làm giảm độ phức tạp lý thuyết mà
dựa trên kinh nghiệm để có tốc độ tìm kiếm nhanh hơn trong thực tế. Ngoài
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
18
ra, một số thuật toán kết hợp quá trình tìm kiếm của BM vào hệ thống
Automat mong đạt kết quả tốt hơn.
Các thuật toán so sánh mẫu theo thứ tự đặc biệt
Thuật toán Galil-Seiferas và Crochemore-Perrin chúng chia mẫu thành
hai đoạn, đầu tiên kiểm tra đoạn ở bên phải rồi mới kiểm tra đoạn bên
trái với chiều từ trái sang phải.
Thuật toán Colussi và Galil-Giancarlo lại chia mẫu thành hai tập và tiến
hành tìm kiếm trên mỗi tập với một chiều khác nhau.
Thuật toán Optimal Mismatch và Maximal Shift sắp xếp thứ tự mẫu
dựa vào mật độ của ký tự và khoảng dịch được.
Thuật toán Skip Search, KMP Skip Search và Alpha Skip Search dựa
sự phân bố các ký tự để quyết đinh vị trí bắt đầu của mẫu trên văn bản.
Các thuật toán so sánh mẫu theo thứ tự bất kỳ
Đó là các thuật toán có thể tiến hành so sánh mẫu với cửa sổ theo một
thứ tự ngẫu nhiên. Những thuật toán này đều có cài đặt rất đơn giản và thường
sử dụng chiêu ký tự không khớp của thuật toán Boyer-Moore. Có lẽ loại thuật
toán này dựa trên ý tưởng càng so sánh loạn càng khó kiếm test chết. Vì dựa
hoàn toàn trên vị trí được lấy ngẫu nhiên nên kết quả chỉ là mong đợi ngẫu
nhiên chứ không có một cơ sở toán học nào để lấy vị trí ngẫu nhiên sao cho
khả năng xuất hiện mẫu cần tìm là lớn.
Hướng nghiên cứu của luận văn là tiếp cận giải thuật di truyền để giải
bài toán tìm kiếm văn bản được đề cập ở chương 3 cũng là phương pháp so
sánh mẫu với cửa sổ theo một thứ tự ngẫu nhiên, nhưng vị trí ngẫu nhiên đó
sẽ được hội tụ dần về vị trí xuất hiện của mẫu sau mỗi lần thực hiện, đó là
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
19
nguyên lý của giải thuật di truyền và cũng là cơ sở toán học cho vấn đề
nghiên cứu.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
20
CHƢƠNG 2
GIỚI THIỆU VỀ GIẢI THUẬT DI TRUYỀN
Phần này sẽ tìm hiểu cơ bản về giải thuật di truyền, trong đó chú trọng
đến các kỹ thuật có liên quan đến bài toán tìm kiếm.
2.1. Tổng quan về giải thuật di truyền
2.1.1 Giới thiệu
Thuật giải di truyền, cũng như các thuật toán tiến hoá nói chung, hình
thành dựa trên quan niệm cho rằng, quá trình tiến hoá tự nhiên là hoàn hảo
nhất, hợp lý nhất, và tự nó đã mang tính tối ưu. Quan niệm này có thể được
xem như là một tiên đề đúng, không chứng minh được, nhưng phù hợp với
thực tế khách quan. Quá trình tiến hoá thể hiện tính tối ưu ở chỗ, thế hệ sau
bao giờ cũng tốt hơn, phát triển hơn, hoàn thiện hơn thế hệ trước. Tiến hoá tự
nhiên được duy trì nhờ hai quá trình cơ bản: sinh sản và chọn lọc tự nhiên.
Xuyên suốt quá trình tiến hoá tự nhiên, các thế hệ mới luôn được sinh ra để
bổ xung thay thế thế hệ cũ. Cá thể nào phát triển hơn, thích ứng hơn với môi
trường sẽ tồn tại, cá thể nào không thích ứng với môi trường sẽ bị đào thải. Sự
thay đổi môi trường là động lực thúc đẩy quá trình tiến hoá. Ngược lại, tiến
hoá cũng tác động trở lại góp phần làm thay đổi môi trường.
Mục tiêu nghiên cứu của giải thuật di truyền (GA) là:
- Trừu tượng hóa và diễn đạt chính xác về các quá trình thích nghi trong
hệ thống tự nhiên.
- Thiết kế những phần mềm về hệ thống nhân tạo nhằm duy trì các cơ
chế quan trọng của hệ thống tự nhiên.
Những mục tiêu này đã dẫn đến những khám phá quan trọng trong hệ
thống khoa học tự nhiên lẫn nhân tạo.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Tải về để xem bản đầy đủ
156 trang
12/05/2025
160
Bạn đang xem 30 trang mẫu của tài liệu "Luận văn Bài toán tìm kiếm văn bản sử dụng giải thuật di truyền", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- luan_van_bai_toan_tim_kiem_van_ban_su_dung_giai_thuat_di_tru.pdf
