Chương 8: Kỹ thuật Phân tích Thuật toán

Trong các chương trước, chúng ta đã khám phá một loạt các thuật toán và cấu trúc dữ liệu cơ bản, bao gồm các chủ đề như sắp xếp, tìm kiếm, đồ thị, chuỗi và các ứng dụng khác. Trong khi việc triển khai và hiểu các thuật toán này là rất quan trọng, việc phân tích đặc điểm hiệu suất của chúng cũng rất quan trọng để đưa ra các quyết định sáng suốt khi lựa chọn thuật toán cho các vấn đề cụ thể. Trong chương này, chúng ta sẽ đi sâu vào các kỹ thuật được sử dụng để phân tích và đánh giá các thuật toán, tập trung vào các mô hình toán học, nghiên cứu thực nghiệm và trực quan hóa thuật toán.

Các Mô hình Toán học và Phân tích

Phân tích toán học là một công cụ mạnh mẽ để hiểu hành vi và hiệu suất của các thuật toán. Bằng cách phát triển các mô hình toán học nắm bắt các đặc điểm cốt lõi của một thuật toán, chúng ta có thể lý luận về hiệu quả và khả năng mở rộng của nó. Các mô hình này cho phép chúng ta dự đoán về thời gian chạy, sử dụng bộ nhớ và các chỉ số hiệu suất khác của một thuật toán, cho phép chúng ta so sánh các thuật toán khác nhau và chọn ra cái phù hợp nhất cho một nhiệm vụ cụ thể.

Ký hiệu Big-O

Một trong những ký hiệu được sử dụng rộng rãi nhất để mô tả hiệu suất của một thuật toán là ký hiệu Big-O. Ký hiệu Big-O cung cấp một giới hạn trên của tốc độ tăng trưởng của một hàm, cho phép chúng ta đặc trưng hóa kịch bản tệ nhất của thời gian chạy hoặc độ phức tạp không gian của một thuật toán.

Trong ký hiệu Big-O, chúng ta biểu diễn hiệu suất của một thuật toán dưới dạng một hàm của kích thước đầu vào, thường được ký hiệu là n. Ví dụ, hãy xem xét hàm đơn giản sau tính tổng của n số nguyên dương đầu tiên:

public static int sum(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

Thời gian chạy của hàm này tăng tuyến tính với kích thước đầu vào n. Chúng ta có thể biểu diễn điều này bằng ký hiệu Big-O là O(n), cho biết thời gian chạy tỷ lệ với kích thước đầu vào. Điều này có nghĩa là khi kích thước đầu vào tăng lên, thời gian chạy cũng tăng tương ứng.Kích thước đầu vào tăng, thời gian chạy của thuật toán tăng nhiều nhất tuyến tính.

Ký hiệu Big-O cho phép chúng ta bỏ qua các hệ số hằng số và các thuật ngữ bậc thấp, tập trung vào thuật ngữ chủ đạo quyết định tốc độ tăng trưởng của hàm. Ví dụ, hãy xem xét hàm sau:

public static int sumOfSquares(int n) {
    // Khởi tạo biến tổng bằng 0
    int sum = 0;
    // Lặp từ 1 đến n
    for (int i = 1; i <= n; i++) {
        // Lặp từ 1 đến i
        for (int j = 1; j <= i; j++) {
            // Cộng j vào tổng
            sum += j;
        }
    }
    // Trả về tổng
    return sum;
}

Thời gian chạy của hàm này tỉ lệ với bình phương của N. Để chính xác hơn, số lần thực hiện câu lệnh sum += j là 1 + 2 + ... + N ~ N^2/2.

Nói chung, chúng ta có thể biểu diễn thời gian chạy của một chương trình dựa trên kích thước đầu vào bằng ký hiệu Big-O. Điều này cho phép chúng ta bỏ qua các hệ số dẫn đầu và các thuật ngữ bậc thấp, và tập trung vào phần quan trọng: bậc tăng trưởng của thời gian chạy.

Thuật toán Knuth-Morris-Pratt

Thuật toán Knuth-Morris-Pratt (KMP) là một thuật toán tìm kiếm chuỗi con hiệu quả sử dụng một "hàm lỗi" được tính trước để tránh các so sánh không cần thiết.

Hàm lỗi cho chúng ta biết độ dài của tiền tố đúng dài nhất của mẫu cũng là hậu tố của đoạn mẫu mà chúng ta đã khớp. Điều này cho phép chúng ta "nhảy về phía trước" trong văn bản khi tìm thấy một sự không khớp, thay vì quay lại.

Dưới đây là một ví dụ về thuật toán KMP:

Văn bản:    "abacadabrabracabracadabrabrabracad"
Mẫu: "abracadabra"
Kết quả:  [13]

Thuật toán KMP có thời gian chạy O(n + m), khiến nó hiệu quả hơn nhiều so với phương pháp vét cạn đối với các văn bản và mẫu lớn.

Thuật toán Boyer-Moore

Thuật toán Boyer-Moore là một thuật toán tìm kiếm chuỗi con hiệu quả khác, hoạt động bằng cách tiền xử lý chuỗi mẫu. Khác với KMP, bắt đầu so sánh từ đầu mẫu, Boyer-Moore bắt đầu từ cuối và làm việc ngược lại.

Ý tưởng chính của Boyer-Moore là sử dụng hai hàm được tính trước: "hậu tố tốt"Đây là bản dịch tiếng Việt của tệp Markdown:

Hàm Boyer-Moore và hàm "ký tự xấu". Những hàm này cho phép chúng ta bỏ qua văn bản khi tìm thấy sự không khớp, tương tự như KMP.

Dưới đây là một ví dụ về thuật toán Boyer-Moore:

Văn bản:    "abacadabrabracabracadabrabrabracad"
Mẫu:        "abracadabra"
Kết quả:    [13]

Boyer-Moore có thời gian chạy tốt nhất là O(n/m) và thời gian chạy tệ nhất là O(n * m), nhưng trong thực tế, nó thường là thuật toán tìm kiếm chuỗi con nhanh nhất cho các bảng chữ cái lớn.

Biểu thức chính quy

Biểu thức chính quy là một công cụ mạnh mẽ để mô tả các mẫu trong chuỗi. Chúng cung cấp một cú pháp ngắn gọn và linh hoạt để khớp, tìm kiếm và thao tác văn bản.

Một biểu thức chính quy là một chuỗi ký tự định nghĩa một mẫu tìm kiếm. Dạng đơn giản nhất của một biểu thức chính quy là một chuỗi ký tự, chẳng hạn như "hello", khớp chính xác với chuỗi "hello". Tuy nhiên, biểu thức chính quy cũng bao gồm các ký tự đặc biệt và cấu trúc cho phép các mẫu phức tạp hơn:

. (dấu chấm) khớp với bất kỳ ký tự đơn lẻ nào.
* (dấu sao) khớp với không hoặc nhiều hơn các lần xuất hiện của ký tự hoặc nhóm trước đó.
+ (dấu cộng) khớp với một hoặc nhiều hơn các lần xuất hiện của ký tự hoặc nhóm trước đó.
? (dấu hỏi) khớp với không hoặc một lần xuất hiện của ký tự hoặc nhóm trước đó.
^ (mũ) khớp với đầu dòng.
$ (đô la) khớp với cuối dòng.
[] (dấu ngoặc vuông) định nghĩa một lớp ký tự, khớp với bất kỳ ký tự đơn lẻ nào trong dấu ngoặc.

Dưới đây là một số ví dụ về biểu thức chính quy và các mẫu chúng khớp:

a.b khớp với bất kỳ chuỗi ba ký tự nào bắt đầu bằng "a" và kết thúc bằng "b", chẳng hạn như "acb", "a5b" hoặc "a b".
a*b khớp với bất kỳ chuỗi nào bao gồm không hoặc nhiều hơn các ký tự "a" theo sau bởi một ký tự "b", chẳng hạn như "b", "ab", "aab" hoặc "aaab".
a+b khớp với bất kỳ chuỗi nào bao gồm một hoặc nhiều hơn các ký tự "a" theo sau bởi một ký tự "b", chẳng hạn như "ab", "aab" hoặc "aaab", nhưng không phải "b".
a?b khớp với "ab" hoặc "b".
^a khớp với bất kỳ chuỗi nào bắt đầu bằng "a".Đây là bản dịch tiếng Việt của tệp Markdown:
a$ khớp với bất kỳ chuỗi nào kết thúc bằng "a".
[aeiou] khớp với bất kỳ ký tự nguyên âm đơn lẻ nào.

Biểu thức chính quy được hỗ trợ bởi nhiều ngôn ngữ lập trình và công cụ, bao gồm Java, Python và các tiện ích Unix như grep và sed. Chúng được sử dụng rộng rãi cho các tác vụ như xác thực dữ liệu, xử lý văn bản và phân tích nhật ký.

Nén dữ liệu

Nén dữ liệu là quá trình mã hóa thông tin bằng ít bit hơn so với biểu diễn ban đầu. Điều này hữu ích để giảm yêu cầu lưu trữ và thời gian truyền. Có hai loại nén chính: không mất mát và mất mát. Nén không mất mát cho phép tái tạo lại dữ liệu gốc từ dữ liệu đã nén, trong khi nén mất mát cho phép một số thông tin bị mất để đổi lấy tỷ lệ nén cao hơn.

Mã hóa độ dài chuỗi

Mã hóa độ dài chuỗi (RLE) là một kỹ thuật nén không mất mát đơn giản, thay thế các chuỗi lặp lại của các ký hiệu giống nhau (chuỗi) bằng một ví dụ duy nhất của ký hiệu và một số đếm số lần nó được lặp lại.

Đây là một ví dụ về RLE:

Đầu vào:  "AAAABBBCCCDDDEEE"
Đầu ra: "4A3B3C3D3E"

RLE hiệu quả cho dữ liệu có nhiều chuỗi dài, chẳng hạn như hình ảnh đồ họa đơn giản. Tuy nhiên, nó thực sự có thể làm tăng kích thước dữ liệu nếu có ít hoặc không có chuỗi.

Mã hóa Huffman

Mã hóa Huffman là một thuật toán nén không mất mát, gán mã có độ dài thay đổi cho các ký hiệu dựa trên tần suất của chúng trong dữ liệu đầu vào. Các ký hiệu thường xuyên hơn được gán mã ngắn hơn, trong khi các ký hiệu ít thường xuyên hơn được gán mã dài hơn.

Thuật toán này hoạt động bằng cách xây dựng một cây nhị phân, được gọi là cây Huffman, từ dưới lên trên. Mỗi nút lá đại diện cho một ký hiệu và tần suất của nó, trong khi mỗi nút nội bộ đại diện cho tổng của tần suất của các con của nó. Cây được xây dựng bằng cách liên tục hợp nhất hai nút có tần suất thấp nhất cho đến khi chỉ còn lại một nút.

Một khi cây đã được xây dựng, mã cho mỗi ký hiệu được xác định bởi đường dẫn từ gốc đếnĐây là bản dịch tiếng Việt của tệp Markdown:

Mã hóa Huffman

Nút lá tương ứng, với nhánh trái biểu thị "0" và nhánh phải biểu thị "1".

Đây là một ví dụ về mã hóa Huffman:

Đầu vào:  "AAAABBBCCCDDDEEE"
Đầu ra: "000010011001011100101"

Cây Huffman:
      (15)
     /    \
   (7)    (8)
   / \    / \
 (4) (3) (3) (5)
 /\  /\  /\  /\
A B  C D E

Trong ví dụ này, "A" được gán mã "00", "B" được gán "01", "C" được gán "10", "D" được gán "110", và "E" được gán "111". Đầu ra được nén được thu được bằng cách thay thế mỗi ký tự trong đầu vào bằng mã tương ứng của nó.

Mã hóa Huffman là một mã tiền tố tối ưu, có nghĩa là không có mã nào là tiền tố của bất kỳ mã nào khác. Điều này cho phép giải mã không mơ hồ dữ liệu được nén. Mã hóa Huffman được sử dụng rộng rãi trong các định dạng tệp và công cụ nén khác nhau, chẳng hạn như JPEG, MP3 và ZIP.

Nén Lempel-Ziv-Welch (LZW)

Nén Lempel-Ziv-Welch (LZW) là một thuật toán nén dựa trên từ điển, xây dựng một từ điển (hoặc sổ mã) các chuỗi trong khi nén đầu vào. LZW được sử dụng rộng rãi trong các tiện ích nén tệp và được sử dụng trong định dạng ảnh GIF.

Ý tưởng chính của LZW là thay thế các chuỗi ký tự bằng các mã đơn. Nó đọc chuỗi đầu vào ký tự theo ký tự và mã hóa chuỗi thành một biểu diễn gọn gàng bằng cách thay thế mỗi mã có độ dài cố định bằng mã có độ dài thay đổi. Càng dài chuỗi, càng tiết kiệm được không gian bằng cách mã hóa nó thành một số đơn.

Dưới đây là mô tả từng bước về cách hoạt động của nén LZW:

Khởi tạo từ điển để chứa tất cả các chuỗi ký tự đơn.
Tìm chuỗi dài nhất W trong từ điển khớp với đầu vào hiện tại.
Phát ra chỉ mục từ điển cho W vào đầu ra và xóa W khỏi đầu vào.
Thêm W theo sau ký tự tiếp theo trong đầu vào vào từ điển.
Quay lại Bước 2.

Hãy xem xét một ví dụ. Giả sử chúng ta muốn nén chuỗi "ABABABABA" bằng LZW.

Khởi tạo từ điển để chứa "A" và "B".
Khớp dài nhất là "A". Phát ra chỉ mục của nó...Đây là bản dịch tiếng Việt của tệp Markdown:
Chỉ mục (0) và loại bỏ nó khỏi đầu vào. Từ điển bây giờ chứa "A", "B" và "AB".
Khớp dài nhất là "B". Phát ra chỉ mục của nó (1) và loại bỏ nó khỏi đầu vào. Từ điển bây giờ chứa "A", "B", "AB" và "BA".
Khớp dài nhất là "AB". Phát ra chỉ mục của nó (2) và loại bỏ nó khỏi đầu vào. Từ điển bây giờ chứa "A", "B", "AB", "BA" và "ABA".
Khớp dài nhất là "ABA". Phát ra chỉ mục của nó (4) và loại bỏ nó khỏi đầu vào. Từ điển bây giờ chứa "A", "B", "AB", "BA", "ABA" và "ABAB".
Khớp dài nhất là "BA". Phát ra chỉ mục của nó (3). Đầu vào bây giờ đã trống.

Biểu diễn nén của "ABABABABA" là chuỗi các chỉ mục [1], yêu cầu ít bit hơn để biểu diễn so với biểu diễn ASCII gốc.

Giải nén hoạt động tương tự, nhưng theo chiều ngược lại:

Khởi tạo từ điển chứa tất cả các chuỗi ký tự đơn.
Đọc một mã X từ đầu vào.
Xuất chuỗi cho X từ từ điển.
Nếu mã trước đó tồn tại, thêm chuỗi trước đó được nối với ký tự đầu tiên của chuỗi cho X vào từ điển.
Chuyển đến Bước 2.

Nén LZW đơn giản và nhanh, khiến nó trở thành một lựa chọn tốt cho nhiều ứng dụng. Tuy nhiên, nó cũng có một số hạn chế. Kích thước của từ điển có thể tăng lên rất lớn, tiêu tốn một lượng bộ nhớ đáng kể. Ngoài ra, từ điển được đặt lại sau mỗi khối đầu vào, điều này có thể làm giảm tỷ lệ nén đối với các tệp nhỏ.

Mặc dù có những hạn chế này, LZW vẫn là một thuật toán nén phổ biến và hiệu quả, đặc biệt là cho các ứng dụng nơi tốc độ quan trọng hơn đạt được tỷ lệ nén cao nhất có thể.

Kết luận

Trong chương này, chúng ta đã khám phá một số thuật toán xử lý chuỗi quan trọng, bao gồm sắp xếp chuỗi, trie, tìm kiếm chuỗi con, biểu thức chính quy và nén dữ liệu. Những thuật toán này là nền tảng cho nhiều ứng dụng thực tế và là công cụ thiết yếu cho bất kỳ lập trình viên nào làm việc với dữ liệu văn bản.

Chúng ta bắt đầu bằng việc thảo luận về sắp xếp chuỗi, là các thuật toán...Đây là bản dịch tiếng Việt của tệp Markdown:

Các thuật toán sắp xếp được tối ưu hóa tận dụng các đặc tính đặc biệt của chuỗi ký tự. Đếm theo chỉ số chính, sắp xếp LSD radix và sắp xếp MSD radix cung cấp các phương pháp hiệu quả để sắp xếp chuỗi ký tự dựa trên các ký tự riêng lẻ của chúng.

Tiếp theo, chúng ta đã xem xét tries, một cấu trúc dữ liệu dạng cây để lưu trữ và truy xuất chuỗi ký tự. Tries cho phép khớp tiền tố nhanh chóng và thường được sử dụng trong các ứng dụng như hoàn thành tự động và bảng định tuyến IP.

Các thuật toán tìm kiếm chuỗi con, như Knuth-Morris-Pratt và Boyer-Moore, cho phép chúng ta tìm kiếm hiệu quả các mẫu trong các chuỗi lớn hơn. Các thuật toán này có nhiều ứng dụng trong chỉnh sửa văn bản, sinh học tính toán và thu thập thông tin.

Biểu thức chính quy cung cấp một cách mạnh mẽ và linh hoạt để mô tả các mẫu chuỗi ký tự. Chúng tôi đã thảo luận về cú pháp cơ bản của biểu thức chính quy và cách chúng có thể được sử dụng để khớp mẫu và thao tác chuỗi trong các ngôn ngữ và công cụ lập trình khác nhau.

Cuối cùng, chúng tôi đã khám phá các thuật toán nén dữ liệu, giúp giảm kích thước dữ liệu bằng cách khai thác sự d冀 thừa và các mẫu trong đầu vào. Chúng tôi đã đề cập đến mã hóa chiều dài chuỗi, mã hóa Huffman và nén Lempel-Ziv-Welch, mỗi loại đều có những điểm mạnh và ứng dụng riêng.

Hiểu biết về các thuật toán và cấu trúc dữ liệu xử lý chuỗi này là rất quan trọng đối với bất kỳ ai làm việc với dữ liệu văn bản. Khi lượng dữ liệu không cấu trúc tiếp tục tăng lên, khả năng thao tác, tìm kiếm và nén chuỗi ký tự một cách hiệu quả sẽ càng trở nên có giá trị hơn. Bằng cách nắm vững các kỹ thuật được đề cập trong chương này, bạn sẽ được trang bị tốt để giải quyết các thách thức xử lý chuỗi trong các dự án và ứng dụng của riêng mình.

Chapter 7 Context Chapter 9 Algorithm Design Paradigms Divide and Conquer