Thuật Toán Brute Force - TaiLieu.VN

Có thể bạn quan tâm

OPTADS360 intTypePromotion=1 zunia.vn

Tuyển sinh 2024 dành cho Gen-Z zunia.vn

Danh mục
- - Tài Liệu Tham Khảo
    - Kinh Doanh-Marketing
    - Kinh Tế - Quản Lý
    - Tài Chính - Ngân Hàng
    - Công Nghệ Thông Tin
    - Ngoại Ngữ
    - Kỹ Thuật - Công Nghệ
    - Khoa Học Tự Nhiên
    - Khoa Học Xã Hội
    - Văn Hoá - Nghệ Thuật
    - Biểu mẫu - Văn bản
    - Sáng kiến kinh nghiệm
    - Ôn thi ĐH-CĐ
    - Giáo án điện tử
    - Bài giảng điện tử
    - Đề thi - Kiểm tra
    - Bài tập SGK
  - Bộ Tài Liệu 4.0
  - Bộ Sưu Tập
  - Luận Văn & Đề Tài
  - Mẫu Slide Powerpoint
  - Khóa Học Online
  - Tài Liệu Phổ Thông
    - Bài học SGK
    - Giải SGK
    - Soạn văn
    - Văn mẫu
    - Đề Thi
    - Trắc nghiệm Online
  - Học trực tuyến
    - Học Online
    - Đề thi Online
    - Tư liệu
  - Trắc Nghiệm MBTI
  - Trắc Nghiệm Holland

NÂNG CẤP

Đăng Nhập | Đăng Ký Chủ đề »

Ngôn ngữ lập trình
Lập trình hướng đối tượng
Lập trình Android
Lập trình Java
Lập trình IOS

HOT
- CEO.24: Bộ 240+ Tài Liệu Quản Trị Rủi...
- CMO.03: Bộ Tài Liệu Hệ Thống Quản Trị...
- CEO.27: Bộ Tài Liệu Dành Cho StartUp...
- FORM.07: Bộ 125+ Biểu Mẫu Báo Cáo...
- FORM.04: Bộ 240+ Biểu Mẫu Chứng Từ Kế...
- LV.11: Bộ Luận Văn Tốt Nghiệp Chuyên...
- TL.01: Bộ Tiểu Luận Triết Học
- LV.26: Bộ 320 Luận Văn Thạc Sĩ Y...
- FORM.08: Bộ 130+ Biểu Mẫu Thống Kê...
CEO.29: Bộ Tài Liệu Hệ Thống Quản Trị Doanh...

TUYỂN SINH

YOMEDIA ADSENSE Trang Chủ » Công Nghệ Thông Tin » Kỹ thuật lập trình Thuật toán Brute Force

Chia sẻ: Trần Ngọc Dũng | Ngày: | Loại File: DOC | Số trang:6

Thêm vào BST

Báo xấu 1.153 lượt xem 107 download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Có lẽ cái tên Brute force đã nói lên tất cả thuật toán. Về cơ bản Brute Force là một thuật toán vét. Bằng cách dịch chuyển biến đếm j 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. So sá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.

AMBIENT/ Chủ đề:

phần mềm máy tính
mẹo lập trình
kinh nghiệm lập trình
thủ thuật lập trình
Tài liệu về thuật toán brute force

Bình luận(0) Đăng nhập để gửi bình luận!

Đăng nhập để gửi bình luận! Lưu

Nội dung Text: Thuật toán Brute Force

I. Mở đầu 1. 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ự '\0' (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 Force II. giới thiệu 1. Có lẽ cái tên Brute force đã nói lên tất cả thuật toán. Về cơ bản Brute Force là một thuật toán vét. Bằng cách dịch chuyển biến đếm j 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. So sá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 X H D R H J Vớ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 đơn vị Vị trí J A G H D R H J D A Q E R M N X H D R H J Vớ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 X H D R H J
Quá 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ạp củ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 P Procedure 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ến 3. 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ưu Do đó các yếu tố cải tiến dành cho Brute Force thường có xu hướ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ếu như không duyệt tới đó). Từ đấy ta có thể suy ra việc nâng cấp chỉ 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ếm nhị phân”. Trong quá trình so sánh, chúng ta dễ dàng thấy chuỗi AB giống chuỗ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ặc BD 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 ại quá trình trên cho đến khi độ dài mỗi chuỗi so sánh bằng 1. Mặt khác, nếu trong một công đoạn so sánh nào đấy mà ta phát hiện thấy sự khác nhau thì có thể dừng ngay quá trình và báo “không giống”. A G H D R H J D A Q E R M N X H D R H J H D R H J Với k=3, ta thấy s[k]=r[k]. tại đây. Ta chia s và r thành: s1, s2, r1, r2. (1) H D H D Tiếp tục. lúc này s:=s1; r:=r1; k:=1. s[k]=r[k]. quá trình chia tiếp tục. (2) Lúc này, s1, s2 là chuỗi con của s ở quá trình (2). R1, r2 là chuỗi con của r ở quá trình (2). Mặt khác s1=r1, s2=r2 và length(s1)=length(r1)=1.; length(s2)=length(r2)=1  dừng quá trình và báo s=r (2). Thực hiện tương tự đối với s2 và r2 của (1): R H J R H J
Mặt khác: nếu s[k]r[k] ngay từ đầu, ta có thể dừng thuật toán lại: G H D R H H D R H J Vì thực hiện theo nguyên tắc chia để trị nên độ phức tạp của thuật toán sẽ giảm xuống trong đa số cá trường hợp: O((m-n+1)log(m)). Code thực hiện: Procedure compare(r,s:ansstring):longint; Var k:longint; Begin K:=length(s) div 2; If s[k]r[k] then then compare:=0 Else If length(s)>1 then Begin S1:=copy(s,1,k); R1:=copy(r,1,k); S2:=copy(s,k+1,n-k); R2:=copy(r,k+1,n-k); If compare(s1,r1)=0 then compare:=0 Else compare:=compare(s2,r2); End Else compare:=1; End; Procedure Brute_force_advanced(s,p:ansistring); Var r:ansistring;co,I,j:longint; Begin For j:=1 to length(p)-length(s)+1 do Begin R:=copy(p,j,length(s)); Co:=0; Co:=Compare(r,s); If co=1 then writeln(f,j);
End; End; Tuy nhiên, nếu thay đổi một số đặc điểm cơ bản của Brute Force. Đồng thời với 2 điều kiện: chuỗi P không quá dài và trong S không có cặp ký tự nào giống nhau thì ta có thể áp dụng phương pháp sau (quy hoạch động). Gọi f[i] là độ dài lớn nhất của chuỗi r với s (f[i] ký tự đầu tiên của s và r bắt đầu từ vị trí i-f[i]+1, tạm gọi vị trí này là k, thuộc P). khi đó nếu P[i]=S[f[i-1]+1] thì f[i]:=f[i-1]+1 ( tăng độ dài chuỗi giống nhau tại k lên) trái lại f[i]:=0 (bắt một chuỗi mới). điểm ưu việt của thuật toán này là do trong s không có ký tự nào giống nhau nên thuật toán chỉ duyệt theo độ dài tuyến tính N. Độ phức tạp của thuật toán trên là: O(n); Không gian: mảng lưu trữ F ( số lượng phần tử cần lưu trữ là khá lớn). Cách nay tuy hiệu quả nhưng không phải lúc nào cũng có thể sử dụng được do có tương đối nhiều yêu cầu. Code tham khảo: Procedure compare(s,p:ansistring); Var a:mang1;i:longint; Begin For i:=1 to length(p) do Begin If p[i]=s[a[i-1]+1] then a[i]:=a[i-1]+1 else a[i]=0; If f[i]=length(s) then Begin Writeln(f,i-length(s)+1); A[i]=0; End; End; End;

ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

sổ tay xử lý sự cố poket chm C1P4

16 p | 77 | 7
Bài giảng Cấu trúc dữ liệu & giải thuật: Đối sách chuỗi

26 p | 31 | 6
Bài giảng Cấu trúc dữ liệu và giải thuật: Đối sánh chuỗi

41 p | 16 | 5
Bài giảng Cấu trúc dữ liệu và giải thuật: Đối sánh chuỗi - Đậu Ngọc Hà Dương

41 p | 26 | 3

Thêm tài liệu vào bộ sưu tập có sẵn:

Đồng ý Thêm vào bộ sưu tập mới:

*Tên bộ sưu tập Mô Tả: *Từ Khóa: Tạo mới Báo xấu

Hãy cho chúng tôi biết lý do bạn muốn thông báo. Chúng tôi sẽ khắc phục vấn đề này trong thời gian ngắn nhất.
Không hoạt động
Có nội dung khiêu dâm
Có nội dung chính trị, phản động.
Spam
Vi phạm bản quyền.
Nội dung không đúng tiêu đề.

Hoặc bạn có thể nhập những lý do khác vào ô bên dưới (100 ký tự): Vui lòng nhập mã xác nhận vào ô bên dưới. Nếu bạn không đọc được, hãy Chọn mã xác nhận khác.. Đồng ý LAVA AANETWORK THÔNG TIN