Chương 4: Các Thuật Toán Tìm Kiếm

Tìm kiếm là một thao tác cơ bản trong khoa học máy tính, liên quan đến việc tìm một mục cụ thể hoặc một tập hợp các mục trong một tập dữ liệu. Các thuật toán và cấu trúc dữ liệu tìm kiếm hiệu quả là rất quan trọng cho nhiều ứng dụng, từ cơ sở dữ liệu và hệ thống tệp đến thu thập thông tin và hình học tính toán. Trong chương này, chúng ta sẽ khám phá một số thuật toán và cấu trúc dữ liệu tìm kiếm quan trọng, bao gồm cây tìm kiếm nhị phân, cây tìm kiếm cân bằng và bảng băm. Chúng ta cũng sẽ thảo luận về các ứng dụng khác nhau của tìm kiếm trong các tình huống thực tế.

Bảng Ký Hiệu và Cấu Trúc Dữ Liệu

Một bảng ký hiệu là một kiểu dữ liệu trừu tượng liên kết các khóa với các giá trị, cung cấp các thao tác để chèn các cặp khóa-giá trị, tìm kiếm một giá trị dựa trên khóa của nó, và xóa các cặp khóa-giá trị. Bảng ký hiệu cũng được gọi là từ điển hoặc mảng kết hợp trong các ngôn ngữ lập trình khác nhau. Chúng là cấu trúc dữ liệu cơ bản được sử dụng trong một loạt các ứng dụng, chẳng hạn như:

Trình biên dịch, nơi bảng ký hiệu được sử dụng để lưu trữ thông tin về các biến, hàm và các định danh khác.
Cơ sở dữ liệu, nơi các chỉ mục được xây dựng bằng cách sử dụng bảng ký hiệu để cho phép tìm kiếm và truy xuất nhanh chóng các bản ghi.
Bộ định tuyến mạng, sử dụng bảng ký hiệu để lưu trữ thông tin định tuyến để chuyển tiếp gói tin hiệu quả.

Có nhiều cấu trúc dữ liệu có thể được sử dụng để triển khai bảng ký hiệu, mỗi cái đều có những ưu và nhược điểm riêng về hiệu suất tìm kiếm, chèn và xóa. Trong phần này, chúng ta sẽ tập trung vào hai cấu trúc dữ liệu quan trọng: cây tìm kiếm nhị phân và bảng băm.

Cây Tìm Kiếm Nhị Phân (BST)

Một cây tìm kiếm nhị phân (BST) là một cấu trúc dữ liệu phân cấp lưu trữ các cặp khóa-giá trị theo cách cho phép các thao tác tìm kiếm, chèn và xóa hiệu quả. Mỗi nút trong một BST chứa một khóa, một giá trị liên kết và các tham chiếu đến nút con bên trái và bên phải của nó. Khóa trong mỗi nút lớn hơn tất cả các khóa trong cây con bên trái và nhỏ hơn tất cả các khóa trong cây con bên phải.Đây là bản dịch tiếng Việt của tệp Markdown:

e. Thuộc tính này, được gọi là tính bất biến của cây nhị phân tìm kiếm (BST), cho phép tìm kiếm hiệu quả bằng cách thực hiện các quyết định nhị phân tại mỗi nút.

Dưới đây là ví dụ về một BST đơn giản:

      4
    /   \
   2     6
  / \   / \
 1   3 5   7

Tìm kiếm trong BST bao gồm việc so sánh khóa mục tiêu với khóa tại nút hiện tại và tìm kiếm đệ quy trong cây con trái hoặc phải dựa trên kết quả so sánh. Nếu khóa mục tiêu được tìm thấy, giá trị liên kết sẽ được trả về. Nếu khóa mục tiêu không được tìm thấy sau khi đến một tham chiếu null, quá trình tìm kiếm sẽ kết thúc không thành công.

Chèn vào BST cũng tuân theo một quy trình tương tự như tìm kiếm. Chúng ta so sánh khóa của nút mới với các khóa trong BST và di chuyển xuống cây cho đến khi tìm thấy một tham chiếu null, nơi chúng ta gắn nút mới như một lá. Xóa trong BST phức tạp hơn một chút, vì nó yêu cầu xử lý ba trường hợp: xóa một nút lá, xóa một nút có một con, và xóa một nút có hai con.

Độ phức tạp thời gian trường hợp trung bình cho tìm kiếm, chèn và xóa trong BST là O(log n), trong đó n là số nút trong cây. Tuy nhiên, trong trường hợp xấu nhất (ví dụ: khi BST bị thoái hóa thành một danh sách liên kết), độ phức tạp thời gian trở thành O(n). Để giảm thiểu vấn đề này, chúng ta có thể sử dụng các BST tự cân bằng, chẳng hạn như cây AVL hoặc cây đỏ-đen, những cây này duy trì cấu trúc cây gần như cân bằng và đảm bảo độ phức tạp thời gian O(log n) trong mọi trường hợp.

Bảng băm

Bảng băm là một cấu trúc dữ liệu cung cấp tìm kiếm, chèn và xóa trung bình nhanh bằng cách sử dụng hàm băm để ánh xạ các khóa vào các chỉ mục trong một mảng, được gọi là các bucket. Hàm băm nhận một khóa làm đầu vào và trả về một chỉ số nguyên, được sử dụng để định vị bucket tương ứng trong mảng. Lý tưởng, hàm băm nên phân bố các khóa một cách đều đặn trên các bucket để giảm thiểu các va chạm (tức là nhiều khóa ánh xạ vào cùng một bucket).

Khi xảy ra va chạm, có hai cách chính để giải quyết:

Liên kết riêng: Mỗi bucket được triển khai như mộtĐây là bản dịch tiếng Việt của tệp Markdown:

Danh sách liên kết, và tất cả các cặp khóa-giá trị được băm vào cùng một bucket được lưu trữ trong danh sách liên kết của bucket đó.

Địa chỉ mở: Khi xảy ra va chạm, bảng băm sẽ dò tìm các bucket khác trong một trình tự đã định trước cho đến khi tìm thấy một bucket trống. Các kỹ thuật dò tìm phổ biến bao gồm dò tìm tuyến tính, dò tìm bậc hai và băm kép.

Dưới đây là một ví dụ về bảng băm với chaining riêng biệt:

+---+    +-------+
| 0 |--->| (1,A) |
+---+    +-------+
| 1 |--->| (5,B) |---->| (9,C) |
+---+    +-------+     +-------+
| 2 |
+---+
| 3 |--->| (7,D) |
+---+    +-------+
| 4 |
+---+

Trong ví dụ này, các khóa 1, 5 và 9 đều được băm vào bucket 1, vì vậy chúng được lưu trữ trong một danh sách liên kết gắn với bucket đó. Khóa 7 được băm vào bucket 3 và là cặp khóa-giá trị duy nhất trong bucket đó.

Độ phức tạp thời gian trường hợp trung bình cho tìm kiếm, chèn và xóa trong một bảng băm được thiết kế tốt là O(1), khiến nó trở thành một trong những cấu trúc dữ liệu nhanh nhất cho các thao tác này. Tuy nhiên, độ phức tạp thời gian trường hợp xấu nhất có thể suy giảm xuống O(n) nếu hàm băm được chọn kém hoặc nếu có nhiều va chạm. Để duy trì hiệu suất tốt, việc sử dụng một hàm băm chất lượng cao và điều chỉnh lại kích thước bảng băm khi hệ số tải (tức là tỷ lệ giữa số cặp khóa-giá trị và số bucket) vượt quá một ngưỡng nhất định, thường khoảng 0,75, là rất quan trọng.

Cây tìm kiếm cân bằng

Mặc dù cây tìm kiếm nhị phân cung cấp các thao tác tìm kiếm, chèn và xóa hiệu quả về trung bình, nhưng hiệu suất của chúng có thể suy giảm đáng kể trong trường hợp xấu nhất. Cây tìm kiếm cân bằng là một họ các cấu trúc dữ liệu duy trì một cấu trúc cây gần như cân bằng, đảm bảo hiệu suất tốt trong trường hợp xấu nhất. Trong phần này, chúng ta sẽ thảo luận về hai loại cây tìm kiếm cân bằng phổ biến: cây AVL và cây đỏ-đen.

Cây AVL

Cây AVL, được đặt tên theo các nhà phát minh Adelson-Velsky và Landis, là một cây tìm kiếm nhị phân tự cân bằng trong đó chiều cao của cây con trái và cây con phải của bất kỳ nút nào cũng khác nhau tối đa một. Sự khác biệt về chiều cao nàyĐây là bản dịch tiếng Việt của tệp Markdown:

Độ cân bằng (balance factor) được gọi là chênh lệch giữa chiều cao của cây con bên trái và cây con bên phải của một nút. Khi một thao tác chèn hoặc xóa vi phạm tính chất AVL (tức là độ cân bằng lớn hơn 1 hoặc nhỏ hơn -1), cây sẽ được cân bằng lại thông qua một hoặc nhiều phép xoay.

Có bốn loại phép xoay được sử dụng để cân bằng lại cây AVL:

Xoay trái: Thực hiện khi độ cân bằng của một nút lớn hơn 1 và độ cân bằng của con phải của nó không âm.
Xoay phải: Thực hiện khi độ cân bằng của một nút nhỏ hơn -1 và độ cân bằng của con trái của nó không dương.
Xoay trái-phải: Thực hiện khi độ cân bằng của một nút lớn hơn 1 và độ cân bằng của con phải của nó âm.
Xoay phải-trái: Thực hiện khi độ cân bằng của một nút nhỏ hơn -1 và độ cân bằng của con trái của nó dương.

Bằng cách duy trì tính chất AVL, cây AVL đảm bảo độ phức tạp thời gian xấu nhất là O(log n) cho các thao tác tìm kiếm, chèn và xóa. Tuy nhiên, các hằng số liên quan đến các thao tác trên cây AVL hơi cao hơn so với cây nhị phân tìm kiếm thông thường do chi phí duy trì độ cân bằng và thực hiện các phép xoay.

Cây đỏ-đen

Cây đỏ-đen là một loại cây nhị phân tự cân bằng khác, duy trì một cấu trúc gần như cân bằng. Mỗi nút trong cây đỏ-đen được tô màu đỏ hoặc đen, và cây phải thỏa mãn các tính chất sau:

Nút gốc luôn màu đen.
Tất cả các nút lá (NIL) đều màu đen.
Nếu một nút màu đỏ, thì cả hai con của nó đều màu đen.
Mọi đường dẫn từ một nút đến bất kỳ nút lá nào của nó đều chứa cùng số lượng nút đen.

Những tính chất này đảm bảo rằng đường dẫn dài nhất từ gốc đến bất kỳ nút lá nào không quá gấp đôi đường dẫn ngắn nhất, đảm bảo độ phức tạp thời gian xấu nhất là O(log n) cho các thao tác tìm kiếm, chèn và xóa.

Khi một thao tác chèn hoặc xóa vi phạm bất kỳ tính chất nào của cây đỏ-đen, cây sẽ được cân bằng lại thông qua một loạt các thao tác đổi màu và xoay.Dưới đây là bản dịch tiếng Việt của tệp Markdown được cung cấp:

Quá trình cân bằng trong cây đỏ-đen thường hiệu quả hơn so với cây AVL, vì nó yêu cầu ít lần xoay hơn trung bình. Điều này khiến cây đỏ-đen trở thành lựa chọn phổ biến để triển khai cây tìm kiếm cân bằng trong thực tế, chẳng hạn như trong Thư viện Mẫu Tiêu chuẩn C++ (STL) và Khuôn khổ Bộ sưu tập Java.

Ứng dụng của Tìm kiếm

Các thuật toán và cấu trúc dữ liệu tìm kiếm có nhiều ứng dụng trong các lĩnh vực khác nhau. Trong phần này, chúng ta sẽ thảo luận một số ví dụ để minh họa tầm quan trọng và tính đa dạng của tìm kiếm trong các tình huống thực tế.

Cơ sở dữ liệu và Truy xuất Thông tin

Cơ sở dữ liệu và hệ thống truy xuất thông tin rất phụ thuộc vào các kỹ thuật tìm kiếm hiệu quả để cung cấp truy cập nhanh chóng đến dữ liệu. Trong cơ sở dữ liệu quan hệ, các chỉ mục được xây dựng bằng cách sử dụng các cấu trúc dữ liệu như B-tree hoặc bảng băm để cho phép tra cứu nhanh chóng các bản ghi dựa trên các thuộc tính cụ thể. Những chỉ mục này cho phép cơ sở dữ liệu thực hiện các truy vấn hiệu quả với các điều kiện trên các thuộc tính được lập chỉ mục, giảm đáng kể không gian tìm kiếm và cải thiện hiệu suất truy vấn.

Trong các hệ thống truy xuất thông tin, chẳng hạn như các công cụ tìm kiếm trên web, các chỉ mục ngược được sử dụng để ánh xạ các thuật ngữ với các tài liệu chứa chúng. Một chỉ mục ngược thực chất là một bảng ký hiệu, trong đó các khóa là các thuật ngữ và các giá trị là danh sách các định danh tài liệu. Khi người dùng gửi một truy vấn, công cụ tìm kiếm tra cứu các thuật ngữ truy vấn trong chỉ mục ngược và lấy các danh sách tài liệu tương ứng, sau đó kết hợp và xếp hạng chúng để tạo ra kết quả tìm kiếm cuối cùng.

Thiết kế Trình biên dịch

Trình biên dịch sử dụng bảng ký hiệu rộng rãi để theo dõi các định danh (ví dụ: tên biến, tên hàm) và các thuộc tính của chúng (ví dụ: kiểu dữ liệu, phạm vi) trong quá trình biên dịch. Khi trình biên dịch gặp một định danh trong mã nguồn, nó tìm kiếm bảng ký hiệu để xác định ý nghĩa và thuộc tính của nó. Tìm kiếm hiệu quả là rất quan trọng đối với hiệu suất của trình biên dịch, vì một trình biên dịch điển hình có thể cần xử lý hàng triệu định danh trong một### Sinh học Tin học và Sinh học Tính toán

Trong sinh học tin học và sinh học tính toán, các thuật toán tìm kiếm đóng vai trò quan trọng trong việc phân tích và hiểu dữ liệu sinh học. Một số ví dụ bao gồm:

Căn chỉnh trình tự: Các thuật toán như BLAST (Basic Local Alignment Search Tool) và Smith-Waterman được sử dụng để tìm kiếm sự tương đồng giữa các trình tự DNA, RNA hoặc protein. Các thuật toán này sử dụng các kỹ thuật tìm kiếm khác nhau để tìm ra những phù hợp tốt nhất giữa các trình tự, giúp các nhà nghiên cứu xác định các mối quan hệ tiến hóa, sự tương đồng chức năng và các đột biến tiềm năng.
Lắp ráp bộ gen: Các thuật toán tìm kiếm được sử dụng để tìm vị trí chồng chéo giữa các mảnh DNA ngắn (đọc) được tạo ra bởi các máy giải trình tự, cho phép tái tạo lại trình tự bộ gen gốc. Tìm kiếm hiệu quả là điều cần thiết để xử lý khối lượng dữ liệu khổng lồ được tạo ra trong các dự án giải trình tự hiện đại.
Tìm kiếm gen và motif: Các nhà nghiên cứu sử dụng các thuật toán tìm kiếm để tìm các mẫu hoặc motif cụ thể trong các trình tự DNA hoặc protein, chẳng hạn như các vị trí gắn yếu tố điều hòa phiên mã, các vị trí nối, hoặc các miền bảo tồn. Những mẫu này có thể cung cấp thông tin về sự điều hòa gen, chức năng protein và sự bảo tồn tiến hóa.

An ninh mạng và Mật mã học

Các thuật toán tìm kiếm được sử dụng trong các khía cạnh khác nhau của an ninh mạng và mật mã học, bao gồm:

Phát hiện xâm nhập: Các hệ thống phát hiện xâm nhập mạng thường sử dụng các thuật toán tìm kiếm như Aho-Corasick hoặc Boyer-Moore để hiệu quả so khớp các mẫu lưu lượng mạng với cơ sở dữ liệu các chữ ký tấn công đã biết. Điều này cho phép phát hiện và ngăn chặn các mối đe dọa an ninh trong thời gian thực.
Phá mật khẩu: Các kẻ tấn công có thể sử dụng các thuật toán tìm kiếm để hiệu quả tìm kiếm qua các từ điển mật khẩu lớn hoặc tạo ra các tổ hợp mật khẩu tiềm năng khi cố gắng phá các băm mật khẩu. Các kỹ thuật như bảng cầu vồng và trao đổi thời gian-bộ nhớ dựa trên việc tìm kiếm hiệu quả để tăng tốc quá trình khôi phục mật khẩu.Đây là bản dịch tiếng Việt của tệp Markdown:
Phân tích mã hóa: Trong mật mã học, các thuật toán tìm kiếm được sử dụng để phân tích và có thể khai thác các điểm yếu trong các hệ thống mật mã. Ví dụ, các thuật toán như baby-step giant-step hoặc Pollard's rho được sử dụng để giải quyết bài toán logarit rời rạc, là nền tảng an ninh của một số lược đồ mật mã.

Kết luận

Các thuật toán tìm kiếm và cấu trúc dữ liệu là những công cụ cơ bản trong khoa học máy tính, với các ứng dụng bao trùm một phạm vi rộng lớn các lĩnh vực. Từ cơ sở dữ liệu và truy xuất thông tin đến tính toán khoa học, sinh học tin học và an ninh mạng, khả năng tìm kiếm và định vị dữ liệu một cách hiệu quả là rất quan trọng để giải quyết các vấn đề phức tạp và trích xuất các thông tin có giá trị.

Bằng cách hiểu các nguyên tắc và kỹ thuật đằng sau các thuật toán tìm kiếm, chẳng hạn như cây tìm kiếm nhị phân, cây tìm kiếm cân bằng và bảng băm, các nhà phát triển có thể đưa ra quyết định sáng suốt khi thiết kế và triển khai các hệ thống dựa trên khả năng tìm kiếm hiệu quả. Lựa chọn thuật toán tìm kiếm và cấu trúc dữ liệu phù hợp phụ thuộc vào các yếu tố như kích thước và bản chất của dữ liệu, tần suất của các thao tác tìm kiếm và các yêu cầu cụ thể của ứng dụng.

Khi lượng dữ liệu được tạo ra và xử lý tiếp tục tăng lên theo cấp số nhân, tầm quan trọng của các thuật toán tìm kiếm hiệu quả sẽ chỉ tăng lên. Các nhà nghiên cứu và chuyên gia trong các lĩnh vực khác nhau sẽ tiếp tục dựa vào những công cụ cơ bản này để đối phó với những thách thức do dữ liệu lớn đặt ra và để mở khóa các cơ hội mới cho khám phá và đổi mới.

Chapter 3 Sorting Algorithms Chapter 5 Graphs