Thuật toán Brute Force

Có lẽ cái tên Brute force đã nói lên tất cả thuật toán. Về cơ bảnBrute Force là một thuật toán vét. Bằng cách dịch chuyển biến đếmj qua phải lần lượt từng kí tự của file văn bản. Sau đó lấy m ký tựliên tiếp trong P (bắt đầu từ vị trí j) tạo thành một chuỗi phụ r. Sosánh r với s, nếu giống nhau thì xuất kết quả. Thực hiện lại quátrình trên cho đến khi jn-m+1.
Nội dung trích xuất từ tài liệu:
Thuật toán Brute ForceI. Mở đầu1. Giới thiệu chung 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. Chuỗi ký tự là một dãy gồm các ký tự hoặc một mảng các ký tự được kết thúc bằng ký tự (còn được gọi là ký tự NULL trong bảng mã Ascii). Các hằng chuỗi ký tự được đặt trong cặp dấu nháy kép “ ”2. Đặt vấn đề Trong thực tế chúng ta thường gặp phải một số vấn đề đơn giản như: tìm kiếm một chuỗi con nhỏ trong một đoạn văn bản lớn hơn. Đặc biệt trong microsoft word, việc tìm kiếm một chuỗi con nhằm để thay thế (replace) hoặc xóa đi (delete) rất phổ biến. Tuy nhiên, do yêu cầu về kích thước, chúng ta thường không thể tự làm điều này bằng tay được. do đó sẽ có một số công cụ hổ trợ được cài đặt sẵn trong máy tính (hoặc đính kèm trong các chương trình có liên quan). Xuất phát từ yêu cầu trên, nhiều thuật toán tìm kiếm chuỗi đã ra đời và nâng cao về tính ưa việt :  Brute force  Knuth-Morris-Pratt  Deterministic Finite Automaton (máy automat hữu hạn)  Boyer-Moore  Karp-Rabin v.v….. ta có thể phát biểu thành bài toán như sau: Cho một chuỗi ký tự s có độ dài m và một file văn bản P có dộ dài n. Hãy tìm tất cả các vị trí mà s xuất hiện trong P. Input: gồm 2 file: Chuoi.inp: chuỗi s Chuoi.txt: văn bản P Output: gồm nhiều dòng. Mỗi dòng là số chỉ vị trí của ký tự đầu tiên của s xuất hiện trong P Thuật toán Brute ForceII. giới thiệu1.Có lẽ cái tên Brute force đã nói lên tất cả thuật toán. Về cơ bảnBrute Force là một thuật toán vét. Bằng cách dịch chuyển biến đếmj qua phải lần lượt từng kí tự của file văn bản. Sau đó lấy m ký tựliên tiếp trong P (bắt đầu từ vị trí j) tạo thành một chuỗi phụ r. Sosánh r với s, nếu giống nhau thì xuất kết quả. Thực hiện lại quátrình trên cho đến khi j>n-m+1.A G H D R H J D A Q E R M N XH D R H JVới j=2, chuỗi phụ r khác với s. Ta tiếp tục tịnh tiến j qua phải 1 đơnvị Vị trí JA G H D R H J D A Q E R M N XH D R H JVới j=3 , ta thấy chuỗi phụ r giống với s. Tại đây, xuất kết quả vàtiếp tục quá trình.A G H D R H J D A Q E R M N XH D R H JQuá trình tiếp tục cho đến khi j=n-m+1 (trong trường hợp này là 11),bởi tại j>n-m+1, ta không thể tạo ra được chuỗi r có độ dài bằng s.Do quá trình so sánh phải đi hết độ dài chuỗi s nên độ phức tạpcủa thuật toán là: O((n-m+1)*m).Code thực hiện (pascal):file văn bản là chuỗi PProcedure brute_force(s,p:ansistring); Var i,j,co:longint; r:ansistring; Begin For j:=1 to length(p)-length(s)+1 do Begin Co:=0; R:=copy(p,j,length(s)); For i:=1 to length(s) do If s[i]r[i] then co:=1; If co=0 then writeln(f,j); End; End; Cải tiến3.Xuất phát từ ý tưởng vét cơ bản nến Brute Force có một số đặcđiểm sau:  Ít tốn không gian nhớ  Không sử dụng thêm mảng phụ để lưuDo đó các yếu tố cải tiến dành cho Brute Force thường có xuhướng cải tiến quá trình tìm và so sánh chuỗi. Tuy nhiên, ta dễdàng thấy việc tìm kiếm chuỗi s trong P là không thể thay đổi. nóiđúng hơn là ta buộc phải duyệt hết độ dài chuỗi P (ta không thểbiết được từ vị trí j có tạo thành chuỗi r giống s hay không nếunhư không duyệt tới đó). Từ đấy ta có thể suy ra việc nâng cấpchỉ có thể thuộc về công đoạn so sánh hai chuỗi sao cho độphức tạp giảm xuống thấp nhất có thể.Để giải quyết yêu cầu trên chúng ta sẽ áp dụng kĩ thuật “tìm kiếmnhị phân”.Trong quá trình so sánh, chúng ta dễ dàng thấy chuỗi AB giốngchuỗi CD khi và chỉ khi A=C và B=D. Ngược lại, nếu nhưABCD thì suy ra AC hoặc BD và nếu như AC hoặcBD thì ABCD.Theo đó, để so sánh hai chuỗi s và r thì ta chỉ việc so sánh hai kýtự đại diện của s và r (ký tự đứng giũa chuỗi k:=length(s) div 2).Khi đó, nếu s[k]r[k] thì ta có thể thoát ngay khỏi quá trình.Ngược lại, nếu s[k]=r[k] thì ta sẽ chia s và r thành các chuỗi con:s1, s2,r1,r2 sao cho length(s1)=length(r1) vàlength(s2)=length(r2). Và thông thường ta sẽ chia s1={s[1],s[2],…s[k]}; s2={s2[k+1], s[k+2],…s[n]}; r1={r[1], r[2],…,r[k]}; r2={r[k+1],r[k+2],…,r[n]}. Sau đó so sánh các cặp s1 và r1, s2 và r2. Lặp l ạiquá trình trên cho đến khi độ dài mỗi chuỗi so sánh bằng 1. Mặtkhác, nếu trong một công đoạn so sánh nào đấy mà ta phát hiệnthấy sự khác nhau thì có thể dừng ngay quá trình và báo “khônggiống”.A G H D R H J D A Q E R M N X H D R H J H D ...