- Cây nhị phân đầy đủ. - Cây nhị phân tìm kiếm. - Kết quả thực hiện chƣơng trình tìm kiếm trên cây nhị phân……….....46 Hình 2.8. - Sau khi thêm nút 6 vào cây nhị phân tìm kiếm. - Sau khi xóa nút 9 trên cây nhị phân tìm kiếm. - Kết quả tìm kiếm có giá trị là “Anh Hình 4.7. - Kết quả tìm kiếm có giá trị là “Vân Hình 4.8. - Kết quả tìm kiếm theo số điện thoại MỤC LỤC MỞ ĐẦU. - TỔNG QUAN VỀ CÁC GIẢI THUẬT TÌM KIẾM CƠ BẢN. - 3 1.1.Tìm kiếm tuyến tính. - Tìm kiếm nhị phân. - Tìm kiếm thông tin trên bảng. - Tìm kiếm theo phƣơng pháp băm. - 27 1.6.Tìm kiếm xâu. - CÂY NHỊ PHÂN TÌM KIẾM. - 36 2.1 Cây nhị phân. - 38 2.2 Cấu trúc dữ liệu cây nhị phân tìm kiếm. - 43 2.2.1 Khái niệm cây nhị phân tìm kiếm. - Các thao tác trên cây nhị phân tìm kiếm. - Cây nhị phân tìm kiếm tối ƣu. - TÌM KIẾM INDEX TRONG CƠ SỞ DỮ LIỆU. - TÌM KIẾM XÂU MẪU. - 73 4.1 Bài toán đối sánh mẫu trong vấn đề tìm kiếm. - Giới thiệu tổng quan về bài toán đối sánh mẫu trong vấn đề tìm kiếm. - 85 4.4.2 Tiếp cận mờ cho bài toán tìm kiếm. - 89 4.5 Ứng dụng thuật toán tìm kiếm xâu. - Kết quả tìm kiếm. - Vậy nghiên cứu và ứng dụng Các cấu trúc dữ liệu và giải thuật hiệu quả cho bài toán tìm kiếm là rất cần thiết. - Mục đích nghiên cứu - Nghiên cứu cấu trúc dữ liệu lƣu trữ hiệu quả cho việc tìm kiếm. - Tìm hiểu các bài toán về tìm kiếm, nghiên cứu, cài đặt một số thuật toán tìm kiếm. - Phạm vi nghiên cứu Luận văn tập trung nghiên cứu các kỹ thuật cơ bản cho bài toán tìm kiếm, cấu trúc biểu diễn, các thao tác trên cây nhị phân tìm kiếm, tìm kiếm theo phƣơng pháp băm, kỹ thuật index trong cơ sở dữ liệu, tìm kiếm xâu. - Tổng quan về các giải thuật tìm kiếm cơ bản. - Chƣơng này trình bày: Tìm kiếm tuyến tính, Tìm kiếm nhị phân, Tìm kiếm thông tin trên bảng, Tìm kiếm theo phƣơng pháp băm, Phƣơng pháp địa chỉ mở, Tìm kiếm xâu. - Chƣơng này trình bày: khái niệm về cây, cây nhị phân tìm kiếm, cấu trúc dữ liệu biểu diễn cây nhị phân tìm kiếm, các thao 2 tác trên cây nhị phân tìm kiếm, khái niệm cây cân bằng AVL, cấu trúc dữ liệu biểu diễn cây nhị phân cân bằng, các thao tác trên cây nhị phân cân bằng và cây nhị phân tìm kiếm tối ƣu. - Tìm kiếm index trong cơ sở dữ liệu. - Tìm kiếm xâu mẫu. - Luận văn cài đặt thuật toán KMP thử nghiệm xây dựng một ứng dụng tìm kiếm trên danh bạ điện thoại. - Độ phức tạp của thuật toán Giải thuật tìm kiếm tuyến tính có độ phức tạp tính toán cấp n: T(n. - Tìm kiếm nhị phân Tìm kiếm nhị phân là một phƣơng pháp tìm kiếm khá thông dụng, dùng để tìm kiếm phần tử trong một danh sách đã đƣợc sắp xếp. - Nếu hai phần tử bằng nhau thì phép tìm kiếm thành công và thuật toán kết thúc. - Tìm kiếm sẽ kết thúc nếu X = ai. - Nếu X < ai tìm kiếm sẽ đƣợc thực hiện tiếp với a1, a2. - còn nếu X > ai tìm kiếm lại đƣợc làm với ai+1. - Tiếp tục sử dụng kỹ thuật tìm kiếm tƣơng tự trên dãy sau. - Quá trình tìm kiếm đƣợc tiếp tục cho đến khi tìm thấy khóa mong muốn hoặc không còn dãy khóa để xét. - tìm kiếm trên tất cả các phần tử} Bƣớc 3: mid. - Độ phức tạp của thuật toán Giải thuật tìm kiếm nhị phân có độ phức tạp tính toán cấp log2n: T(n. - Tìm kiếm thông tin trên bảng Tìm kiếm thông tin trên bảng([6]) là một phƣơng pháp tìm kiếm bắt đầu từ một khóa và tìm một phần tử chứa khóa này. - Tìm kiếm theo phƣơng pháp băm Các phép toán trên các cấu trúc dữ liệu nhƣ danh sách, cây nhị phân,… phần lớn đƣợc thực hiện bằng cách so sánh các phần tử của cấu trúc, do vậy thời gian truy xuất không nhanh và phụ thuộc vào kích thƣớc của cấu trúc. - Phần tìm kiếm theo phƣơng pháp băm này sẽ giúp hạn chế số lần so sánh, và vì vậy sẽ giảm thiểu đƣợc thời gian truy xuất thông tin. - Hàm băm đƣợc sử dụng chuyển đổi từ khóa thành chỉ số (giá trị băm) trong mảng lƣu trữ các giá trị tìm kiếm. - Để tìm kiếm một phần tử nào đó ta sẽ dựa vào khoá của nó và tra trong bảng chỉ mục, nếu tại vị trí đó có phần tử thì chính là phần tử cần tìm, nếu không có phần tử nào có nghĩa là phần tử cần tìm không có trong bảng chỉ mục. - Thời gian tìm kiếm là hằng số O(1. - Kết quả thực hiện chương trình chèn khóa k vào bảng Thuật toán 1.4 Thuật toán tìm kiếm khóa k trong bảng: HASH_SEARCH(T,k) i. - 1.6.Tìm kiếm xâu Tìm kiếm xâu hay chuỗi) (String searching) còn đƣợc gọi là đối sánh chuỗi (string matching). - Tìm kiếm chuỗi là bài toán tìm ra một mẫu (pattern) với một số đặc tính nào đó trong chuỗi các ký hiệu cho trƣớc, vì thế bài toán này còn đƣợc gọi là so xâu mẫu hay có thể gọi ngắn gọn là so mẫu (string pattren matching). - Tìm kiếm trên chỉ mục thực ra cũng dựa trên tìm kiếm on - line. - Tiếp cận thứ hai sử dụng một “cửa sổ trƣợt” trên xâu S và tìm kiếm mẫu trong cửa sổ này. - Tại mỗi vị trí trong cửa sổ, cần tìm kiếm một khúc cuối của cửa sổ mà là khúc cuối của xâu mẫu P. - Vấn đề tìm kiếm xâu sẽ đƣợc trình bày chi tiết trong Chƣơng 4. - CÂY NHỊ PHÂN TÌM KIẾM Cây nhị phân tìm kiếm là một dạng cây nhị phân đƣợc tổ chức theo một trật tự nào đó của các nút để thuận lợi cho việc tìm kiếm. - A C B E G F D I H J K 41 Sử dụng con trỏ tiết kiệm rất nhiều bộ nhớ nhƣng việc cài đặt không dễ chút nào vì cấu trúc con trỏ khó hiểu và mỗi khi thêm, xóa hay tìm kiếm một phần tử trong cây thì phải duyệt cây lại từ đầu (bắt đầu từ gốc). - 43 2.2 Cấu trúc dữ liệu cây nhị phân tìm kiếm Cây nhị phân tìm kiếm là một cấu trúc dữ liệu rất thuận lợi cho bài toán tìm kiếm. - Cấu trúc dữ liệu cơ bản của cây nhị phân tìm kiếm đƣợc sử dụng để xây dựng các cấu trúc dữ liệu trừu tƣợng hơn nhƣ các tập hợp, đa tập hợp, các dãy kết hợp,… 2.2.1 Khái niệm cây nhị phân tìm kiếm Cây nhị phân tìm kiếm là một cây nhị phân mà tại mỗi nút của nó thỏa mãn điều kiện: khóa của nút gốc lớn hơn khóa của tất cả các nút của cây con trái và nhỏ hơn khóa của tất cả các nút của cây con phải. - Các thao tác trên cây nhị phân tìm kiếm Trên cây nhị phân tìm kiếm có các thao tác sau. - Tìm một nút trên cây nhị phân tìm kiếm Bài toán Giả sử có một cây nhị phân tìm kiếm có nút gốc là root. - Hàm tìm kiếm trên cây nhị phân tìm kiếm trả về nút chứa khóa X cần tìm hoặc trả về nil nếu không tìm thấy. - Thuật toán 2.1 Hàm tìm kiếm nút X(val) trong cây tree Function search(tree: ^Tnode, val:integer):^Tnode. - Kết quả thực hiện chương trình tìm kiếm trên cây nhị phân 47 Thêm một nút vào cây nhị phân tìm kiếm Bài toán Cho một cây nhị phân tìm kiếm có nút gốc là root, thêm vào cây có một nút là X sao cho cây nhận đƣợc sau khi thêm cũng là cây nhị phân tìm kiếm. - Ví dụ 2.2 Thêm nút có giá trị là 6 vào cây nhị phân tìm kiếm. - Xóa một nút trên cây nhị phân tìm kiếm Giả sử ta muốn xóa một nút có khóa X. - Trƣớc hết ta phải tìm kiếm nút chứa khóa X trên cây. - Việc xóa nhƣ vậy phải đảm bảo không phá vỡ cấu trúc cây nhị phân tìm kiếm. - Bài toán Cho một cây nhị phân tìm kiếm có nút gốc là root, xóa nút có khóa là a trên cây sao cho sau khi xóa cây vẫn còn thỏa mãn các tính chất của cây nhị phân tìm kiếm. - Thuật toán 2.3 Thủ tục xóa khóa X khỏi cây nhị phân tìm kiếm Xóa nút X(val) khỏi cây có nút gốc root Procedure deletenode(var root: ^node. - Kết quả thực hiện chương trình xóa nút có hai cây con trái và phải trên cây nhị phân 59 2.3 Cây nhị phân cân bằng AVL (Adelson-Velskii và Landis) Với các thao tác trên cây nhị phân tìm kiếm đã tìm hiểu ở phần trƣớc, ta thấy các thao tác trên cây là tìm kiếm, chèn thêm và xóa phụ thuộc vào hình dạng của cây. - Điều này làm ảnh hƣởng rất lớn đến các thao tác trên cây nhị phân tìm kiếm. - Vậy các thao tác trên cây nhị phân tìm kiếm phải cài đặt nhƣ thế nào để hạn chế trƣờng hợp cây lệch hay phải điều chỉnh để cây cân bằng. - Cây nhị phân cân bằng (AVL) là một cây nhị phân tìm kiếm tự cân bằng và là cấu trúc dữ liệu đầu tiên có khả năng cân bằng. - Cây nhị phân tìm kiếm đƣợc giữ sao cho luôn ở trạng thái cân bằng, nếu việc thêm hay xóa dẫn đến mất tính cân bằng của cây thì cần tiến hành khôi phục ngay. - 2.3.1 Khái niệm cây cân bằng Cây cân bằng là một cây nhị phân tìm kiếm nếu và chỉ nếu với mọi nút của cây, số nút của cây con bên trái và số nút của cây con phải lệch nhau không quá một đơn vị. - Vậy một trong những lý do chính làm cho cây nhị phân tìm kiếm mất cân bằng là khi thêm một nút vào cây. - Xóa khỏi cây cân bằng Từ thao tác xóa trên cây nhị phân tìm kiếm và thao tác thêm trên cây cân bằng nên ta có thể thực hiện tƣơng tự cho thao tác xóa trên cây cân bằng. - Cây nhị phân tìm kiếm tối ƣu Cây nhị phân tìm kiếm tối ƣu là cây nhị phân tìm kiếm thỏa mãn yêu cầu: Cho trƣớc tập các khóa Ki. - Kn Xác định cây nhị phân tìm kiếm với tập các khóa trên sao cho biểu thức P sau đây có giá trị nhỏ nhất: P. - Ý tưởng: Ngƣời ta chứng minh đƣợc rằng số lƣợng các cây nhị phân tìm kiếm n nút có dạng khác nhau là: 62. - (Khi n khá lớn) Do đó việc chọn cây nhị phân tìm kiếm tối ƣu bằng cách lựa chọn trong các cây đó một cây có độ dài đƣờng đi có trọng số nhỏ nhất là khó thực hiện khi n lớn. - Đó là vì cây tối ƣu có tính chất đáng chú ý sau đây: Một cây nhị phân tìm kiếm tối ƣu thì bất kỳ một cây con nào của nó cũng phải là cây nhị phân tìm kiếm tối ƣu. - Nhƣ thế cây nhị phân tìm kiếm tối ƣu lớn dần lên bắt đầu từ một nút lá (từ cây con gồm một nút) mà ta gọi là kỹ thuật dựng cây nhị phân tìm kiếm tối ƣu theo kiểu từ đáy lên (bottom up). - TÌM KIẾM INDEX TRONG CƠ SỞ DỮ LIỆU 3.1 Khái niệm index Index([5]) là các mục lục chỉ thị, trong các chƣơng trình quản lý cơ sở dữ liệu, đây là một tệp thu gọn, chứa các thông tin (gọi là pointes) về vị trí thực của bản ghi trong một tệp cơ sở dữ liệu. - Nó cung cấp một phƣơng pháp giúp cho chúng ta nhanh chóng tìm kiếm dữ liệu dựa trên các giá trị trong các cột. - Khi chúng ta tạo ra một Index trên một khóa chính và sau đó tìm kiếm một dòng dữ liệu trên một trong các giá trị của cột này SQL Server sẽ thực hiện quá trình tìm kiếm nhƣ sau: đầu tiên SQL Server sẽ tìm giá trị này trong Index, sau đó 64 nó sử dụng Index để nhanh chóng xác định vị trí của dòng dữ liệu mà chúng ta cần tìm. - Ví dụ, ta cần tìm kiếm giá trị 123 trong một cột đƣợc tạo index, giả sử nhƣ cột ID chẳng hạn. - Tuy nhiên, nên sử dụng Index một cách khôn ngoan trên các bảng nhỏ vì cỗ máy truy vấn có thể mất nhiều thời gian và chi phí để tìm kiếm dữ liệu dựa trên các Index hơn là tìm kiếm dữ liệu dựa trên việc thực hiện một thao tác scan table. - Xem xét tạo Index trên các cột đƣợc sử dụng trong các truy vấn tìm kiếm chính xác. - Khi có yêu cầu từ ngƣời dùng yêu cầu tìm kiếm, Lucene sử dụng các searcher để truy cập vào vùng dữ liệu đã đƣợc đánh chỉ mục để tìm kiếm. - Nếu chọn đánh chỉ mục, ta có thể tìm kiếm trên Field đó. - TÌM KIẾM XÂU MẪU 4.1 Bài toán đối sánh mẫu trong vấn đề tìm kiếm 4.1.1. - tìm kiếm mẫu lặp trong nén dữ liệu. - tìm kiếm thông tin trong thứ việc điện tử, bách khoa toàn thƣ điện tử. - tìm kiếm tƣơng tự trong CSDL gen. - tìm kiếm tự động các luật trong CSDL. - Vậy việc tiếp tục nghiên cứu về các giải pháp tìm kiếm là rất cần thiết. - Tìm kiếm trên chỉ mục thực ra cũng dựa trên tìm kiếm on – line
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt