Chương 6: Chuỗi trong Thuật toán

Chuỗi là một kiểu dữ liệu cơ bản trong khoa học máy tính, đại diện cho các chuỗi ký tự. Nghiên cứu các thuật toán và cấu trúc dữ liệu để xử lý chuỗi là một phần quan trọng của bất kỳ chương trình đào tạo khoa học máy tính nào. 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, tries, 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 có nhiều ứng dụng thực tế, từ chỉnh sửa văn bản và truy xuất tài liệu đến sinh học tin học và xử lý ngôn ngữ tự nhiên.

Sắp xếp chuỗi

Sắp xếp là một thao tác cơ bản trong khoa học máy tính, và sắp xếp chuỗi là một nhiệm vụ phổ biến trong nhiều ứng dụng. Mặc dù các thuật toán sắp xếp dùng chung như quicksort và mergesort có thể được sử dụng để sắp xếp chuỗi, nhưng có những thuật toán hiệu quả hơn có thể tận dụng các đặc tính đặc biệt của chuỗi.

Đếm theo chỉ số khóa

Đếm theo chỉ số khóa là một thuật toán đơn giản và hiệu quả để sắp xếp chuỗi được tạo từ một tập hợp nhỏ các ký tự khác nhau. Ý tưởng cơ bản là đếm số lần xuất hiện của mỗi ký tự và sau đó sử dụng các số đếm này để xác định vị trí của mỗi chuỗi trong thứ tự sắp xếp.

Dưới đây là một ví dụ về đếm theo chỉ số khóa:

Đầu vào:  ["dab", "cab", "fad", "bad", "dad", "ebb", "ace"]
Đầu ra: ["ace", "bad", "cab", "dab", "dad", "ebb", "fad"]

Thuật toán hoạt động như sau:

Đếm tần suất của mỗi ký tự trong các chuỗi.
Tính chỉ số bắt đầu cho mỗi ký tự trong mảng đã sắp xếp.
Sao chép các chuỗi vào mảng đã sắp xếp, sử dụng các số đếm để xác định các vị trí.

Đếm theo chỉ số khóa chạy trong thời gian O(n + R), trong đó n là tổng số ký tự trong các chuỗi và R là kích thước của bảng chữ cái (số lượng ký tự khác nhau). Điều này khiến nó trở thành một thuật toán rất hiệu quả để sắp xếp chuỗi với kích thước bảng chữ cái nhỏ.

Sắp xếp Radix LSD

Sắp xếp Radix LSD (Least-significant-digit-first) là một phần mở rộng của đếm theo chỉ số khóaĐây là bản dịch tiếng Việt của tệp Markdown:

Sắp xếp đếm có thể sắp xếp chuỗi có độ dài bằng nhau trên một bảng chữ cái lớn. Ý tưởng cơ bản là sắp xếp các chuỗi ký tự theo từng ký tự, bắt đầu từ ký tự cuối cùng và di chuyển về phía đầu tiên.

Đây là một ví dụ về sắp xếp LSD radix:

Đầu vào:  ["4PGC938", "2IYE230", "3CIO720", "1ICK750", "1OHV845", "4JZY524", "1ICK750", "3CIO720", "1OHV845", "1OHV845", "2RLA629", "2RLA629", "3ATW723"]
Đầu ra: ["1ICK750", "1ICK750", "1OHV845", "1OHV845", "1OHV845", "2IYE230", "2RLA629", "2RLA629", "3ATW723", "3CIO720", "3CIO720", "4JZY524", "4PGC938"]

Thuật toán hoạt động như sau:

Sắp xếp các chuỗi theo ký tự cuối cùng bằng cách sử dụng đếm theo khóa.
Lặp lại bước 1 cho mỗi ký tự di chuyển về phía đầu tiên.

Sắp xếp LSD radix chạy trong thời gian O(w * n), trong đó w là độ dài của các chuỗi và n là số lượng chuỗi. Điều này khiến nó trở thành một lựa chọn hiệu quả để sắp xếp các chuỗi có độ dài cố định.

Sắp xếp Radix MSD

Sắp xếp Radix MSD (Most-significant-digit-first) là một biến thể đệ quy của sắp xếp radix có thể xử lý các chuỗi có độ dài khác nhau. Giống như quicksort, sắp xếp Radix MSD phân chia mảng thành các mảng con có thể được sắp xếp độc lập.

Đây là một ví dụ về sắp xếp Radix MSD:

Đầu vào:  ["she", "sells", "seashells", "by", "the", "sea", "shore", "the", "shells", "she", "sells", "are", "surely", "seashells"]
Đầu ra: ["are", "by", "sea", "seashells", "seashells", "sells", "sells", "she", "she", "shells", "shore", "surely", "the", "the"]

Thuật toán hoạt động như sau:

Phân chia mảng thành các mảng con dựa trên ký tự đầu tiên của mỗi chuỗi.
Sắp xếp đệ quy từng mảng con.

Sắp xếp Radix MSD có thời gian chạy tệ nhất là O(n * w), nhưng trong thực tế, nó thường nhanh hơn sắp xếp Radix LSD đối với các chuỗi có độ dài khác nhau.

Tries

Trie (phát âm là "try") là một cấu trúc dữ liệu dạng cây để lưu trữ các chuỗi, cho phép tìm kiếm tiền tố và tìm kiếm chuỗi hiệu quả. Mỗi nút trong Trie đại diện cho một ký tự, và đường dẫn từ gốc đến một nút đại diện cho một tiền tố của chuỗi.Đây là bản dịch tiếng Việt của tệp Markdown:

Ví dụ về một trie lưu trữ các chuỗi "sea", "sells", "she", "shells", và "shore":

     (root)
    /  |  \
   s   h   o
  / \     / \
 e   h   r   t
 |   |   |   |
 a   e   e   h
     |       |
     l       e
     |       |
     l       r
     |
     s

Tries hỗ trợ các thao tác sau:

Chèn một chuỗi vào trie.
Tìm kiếm một chuỗi trong trie.
Xóa một chuỗi khỏi trie.
Tìm tất cả các chuỗi có tiền tố cho trước.

Độ phức tạp thời gian của các thao tác này là O(w), trong đó w là độ dài của chuỗi được chèn, tìm kiếm hoặc xóa. Điều này khiến tries trở thành một cấu trúc dữ liệu rất hiệu quả cho các tác vụ liên quan đến chuỗi.

Tìm kiếm chuỗi con

Tìm kiếm chuỗi con là bài toán tìm tất cả các vị trí xuất hiện của một chuỗi mẫu trong một chuỗi văn bản lớn hơn. Đây là một bài toán cơ bản trong xử lý chuỗi, với các ứng dụng trong chỉnh sửa văn bản, sinh học tin học và nhiều lĩnh vực khác.

Tìm kiếm vét cạn

Cách tiếp cận đơn giản nhất cho tìm kiếm chuỗi con là thuật toán vét cạn, trong đó kiểm tra từng vị trí có thể trong văn bản để tìm sự khớp với chuỗi mẫu.

Dưới đây là ví dụ về tìm kiếm vét cạn:

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

Thuật toán vét cạn có độ phức tạp thời gian xấu nhất là O(n * m), trong đó n là độ dài của văn bản và m là độ dài của chuỗi mẫu. Mặc dù đơn giản để thực hiện, nhưng có thể không hiệu quả với các văn bản và chuỗi mẫu lớn.

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 biết độ dài của tiền tố đúng dài nhất của chuỗi mẫu, cũng là hậu tố của đoạn chuỗi 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à ví dụ về thuật toán KMP:

Văn bản:  "abacadabrabr
```Dưới đây là bản dịch tiếng Việt của tệp Markdown:

"acabracadabrabrabracad"
Mẫu: "abracadabra"
Đầu ra: [13]

Thuật toán KMP có thời gian chạy là 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 con chuỗi 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 đằng sau Boyer-Moore là sử dụng hai hàm được tính trước: hàm "hậu tố tốt" và hàm "ký tự xấu". Những hàm này cho phép chúng ta bỏ qua trong văn bản khi tìm thấy một 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"
Đầu ra: [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 con chuỗi 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 văn bản, 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ự và cấu trúc đặc biệt 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 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.


Đây là một số ví dụ về các biểu thức chính quy và các mẫu mà 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 "a" ký tự, theo sau là mộ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 "a" ký tự, theo sau là mộ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".
- `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ào.

Các 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 khôi phục 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 để đổ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 (độ dài chuỗi) bằng một ký hiệu duy nhất 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ả với dữ liệu có nhiều độ dài chuỗi dài, chẳng hạn như hình ảnh đơ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ó độ dài 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.Đây là bản dịch tiếng Việt của tệp Markdown:

Tần suất trong dữ liệu đầu vào. Các ký tự thường xuyên hơn được gán mã ngắn hơn, trong khi các ký tự ít thường xuyên hơn được gán mã dài hơn.

Thuật toán 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ý tự 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ý tự được xác định bằng đường dẫn từ gốc đến nút lá tương ứng, với nhánh trái đại diện cho "0" và nhánh phải đại diện cho "1".

Dưới đâ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 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ã 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 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 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ủa 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 hơn bằng cách thay thế mỗi mã độ dài cố định bằng mã độ 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àĐây là bản dịch tiếng Việt của tệp Markdown:

1. Khởi tạo từ điển để chứa tất cả các chuỗi ký tự đơn.
2. Tìm chuỗi dài nhất W trong từ điển khớp với đầu vào hiện tại.
3. Phát ra chỉ số từ điển cho W vào đầu ra và xóa W khỏi đầu vào.
4. Thêm W theo sau ký tự tiếp theo trong đầu vào vào từ điển.
5. 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.

1. Khởi tạo từ điển chứa "A" và "B".
2. Khớp dài nhất là "A". Phát ra chỉ số (0) của nó và xóa nó khỏi đầu vào. Từ điển bây giờ chứa "A", "B" và "AB".
3. Khớp dài nhất là "B". Phát ra chỉ số (1) của nó và xóa nó khỏi đầu vào. Từ điển bây giờ chứa "A", "B", "AB" và "BA".
4. Khớp dài nhất là "AB". Phát ra chỉ số (2) của nó và xóa nó khỏi đầu vào. Từ điển bây giờ chứa "A", "B", "AB", "BA" và "ABA".
5. Khớp dài nhất là "ABA". Phát ra chỉ số (4) của nó và xóa nó khỏi đầu vào. Từ điển bây giờ chứa "A", "B", "AB", "BA", "ABA" và "ABAB".
6. Khớp dài nhất là "BA". Phát ra chỉ số (3) của nó. Đầu vào bây giờ đã trống.

Biểu diễn nén của "ABABABABA" là chuỗi các chỉ số [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:

1. Khởi tạo từ điển để chứa tất cả các chuỗi ký tự đơn.
2. Đọc một mã X từ đầu vào.
3. Xuất chuỗi cho X từ từ điển.
4. 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.
5. Quay lại 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, nhưng LZW vẫn là một kỹ thuật nén hiệu quả và được sử dụng rộng rãi.Dưới đây là bản dịch tiếng Việt của tệp Markdown này. Đối với mã, không dịch mã, chỉ dịch các bình luận.

## 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, cây 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 tạo 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 tôi bắt đầu bằng việc thảo luận về sắp xếp chuỗi, là những 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. Đếm theo khóa, sắp xếp theo cơ số thấp nhất (LSD) và sắp xếp theo cơ số cao nhất (MSD) cung cấp các phương pháp hiệu quả để sắp xếp chuỗi dựa trên các ký tự riêng lẻ của chúng.

Tiếp theo, chúng tôi đã xem xét cây trie, một cấu trúc dữ liệu dạng cây để lưu trữ và truy xuất chuỗi. Cây trie 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ư thuật toán 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. Những 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. 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ã Huffman và nén Lempel-Ziv-Welch, mỗi cái đều có những điểm mạnh và ứng dụng riêng.

Hiểu biết về những 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ó 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 dữ liệu một cách hiệu quả trở nên ngày càng quan trọng.Dưới đây là bản dịch tiếng Việt của tệp Markdown:

Các chuỗi ép sẽ chỉ 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ị đầy đủ để giải quyết một loạ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 5 Graphs Chapter 7 Context