Bài 30.3: Bài tập thực hành tần suất ký tự trong C++

Chào mừng các bạn quay trở lại với chuỗi bài học lập trình C++ cùng FullhouseDev! Hôm nay, chúng ta sẽ cùng nhau giải quyết một bài toán thực hành kinh điển nhưng cực kỳ hữu ích: đếm tần suất xuất hiện của từng ký tự trong một chuỗi văn bản cho trước.

Tại sao bài toán này lại quan trọng? Việc phân tích tần suất ký tự có ứng dụng rộng rãi trong nhiều lĩnh vực:

Xử lý văn bản: Hiểu cấu trúc ngôn ngữ, phát hiện lỗi chính tả cơ bản.
Mật mã học: Phân tích tần suất là kỹ thuật cơ bản trong giải mã các mật mã cổ điển (như mật mã Caesar, Vigenère).
Nén dữ liệu: Các ký tự xuất hiện nhiều có thể được gán mã ngắn hơn (ví dụ: nén Huffman).
Phân tích dữ liệu: Thống kê đơn giản về dữ liệu dạng văn bản.

Bài tập này không chỉ giúp bạn rèn luyện kỹ năng xử lý chuỗi mà còn là cơ hội tuyệt vời để thực hành sử dụng các cấu trúc dữ liệu quan trọng trong C++ như map, unordered_map hoặc thậm chí là mảng (array).

Bài Toán: Đếm Tần Suất Ký Tự

Yêu cầu của chúng ta rất đơn giản: cho một chuỗi văn bản bất kỳ, hãy viết chương trình C++ để liệt kê từng ký tự duy nhất xuất hiện trong chuỗi đó cùng với số lần nó xuất hiện.

Ví dụ:

Chuỗi "hello world"
Kết quả mong muốn (thứ tự có thể khác nhau tùy cách triển khai):
- 'h': 1
- 'e': 1
- 'l': 3
- 'o': 2
- ' ': 1
- 'w': 1
- 'r': 1
- 'd': 1

Chúng ta sẽ cùng khám phá một số cách tiếp cận khác nhau để giải quyết bài toán này, mỗi cách sử dụng một cấu trúc dữ liệu khác nhau.

Cách 1: Sử Dụng `map`

map trong C++ Standard Library là một cấu trúc dữ liệu lưu trữ các cặp khóa-giá trị (key-value pairs) theo thứ tự của khóa. Nó rất phù hợp cho bài toán này vì mỗi ký tự duy nhất có thể là khóa (char) và tần suất của nó là giá trị (int).

Ưu điểm của map:

Tự động quản lý các ký tự duy nhất.
Dữ liệu được lưu trữ theo thứ tự của ký tự (theo mã ASCII), giúp việc in ra kết quả có thứ tự.
Dễ sử dụng.

Nhược điểm:

Tốc độ truy cập và chèn có thể chậm hơn so với unordered_map hoặc mảng trong trường hợp tốt nhất (average case).

Hãy xem code ví dụ:

#include <iostream>
#include <string>
#include <map>
#include <limits>

using namespace std;

int main() {
    string s;

    cout << "Nhap mot chuoi bat ky: ";
    getline(cin >> ws, s);

    map<char, int> tan_suat;

    for (char ky_tu : s) {
        tan_suat[ky_tu]++;
    }

    cout << "\nTan suat ky tu:\n";
    for (const auto& cap : tan_suat) {
        cout << "'" << cap.first << "': " << cap.second << "\n";
    }

    return 0;
}

Nhap mot chuoi bat ky: hello world

Tan suat ky tu:
' ': 1
'd': 1
'e': 1
'h': 1
'l': 3
'o': 2
'r': 1
'w': 1

Giải thích Code:

Chúng ta bao gồm các thư viện cần thiết: <iostream> cho nhập/xuất, <string> cho làm việc với chuỗi, và <map> cho map. <limits> được thêm vào để sử dụng ws giúp đọc dòng input sạch hơn sau các thao tác nhập liệu khác nếu có.
string input_string; khai báo biến để lưu chuỗi nhập từ người dùng.
getline(cin >> ws, input_string); đọc toàn bộ một dòng văn bản từ bàn phím vào input_string. ws được dùng để loại bỏ các ký tự khoảng trắng (whitespace) còn lại trong bộ đệm nhập liệu trước khi đọc dòng mới, đảm bảo getline hoạt động đúng.
map<char, int> frequency; tạo một map rỗng. Kiểu khóa là char (ký tự), kiểu giá trị là int (số lần đếm).
Vòng lặp for (char c : input_string) là cấu trúc lặp dựa trên phạm vi (range-based for loop), duyệt qua từng ký tự c trong input_string.
frequency[c]++; là phần cốt lõi. Đây là cách truy cập hoặc thêm một phần tử vào map.
- Nếu ký tự c chưa tồn tại làm khóa trong map, map sẽ tự động tạo một mục nhập mới với khóa là c và khởi tạo giá trị (value) tương ứng là 0 (giá trị mặc định cho int). Sau đó, toán tử ++ sẽ tăng giá trị này lên 1.
- Nếu ký tự c đã tồn tại, map sẽ truy cập đến giá trị hiện tại của khóa c và tăng giá trị đó lên 1.
Vòng lặp for (const auto& pair : frequency) dùng để duyệt qua tất cả các cặp khóa-giá trị trong map sau khi đã đếm xong. pair ở đây là một pair mà pair.first là khóa (char) và pair.second là giá trị (int).
cout << "'" << pair.first << "': " << pair.second << endl; in ra kết quả theo định dạng 'ký tự': số lần.

Kết quả khi chạy chương trình với input "hello world":

Nhap mot chuoi bat ky: hello world

Tan suat ky tu:
' ': 1
'd': 1
'e': 1
'h': 1
'l': 3
'o': 2
'r': 1
'w': 1

Bạn có thể thấy các ký tự được in ra theo thứ tự tăng dần của mã ASCII, đó là đặc điểm của map.

Biến Thể: Đếm Tần Suất Chỉ Chữ Cái (Không Phân Biệt Hoa Thường)

Đôi khi, chúng ta chỉ muốn đếm tần suất của các ký tự chữ cái và không quan tâm đến việc chúng là chữ hoa hay chữ thường, cũng như bỏ qua các ký tự khác (số, dấu câu, khoảng trắng...). Chúng ta có thể dễ dàng chỉnh sửa code trên.

Chúng ta cần thêm thư viện <cctype> để sử dụng các hàm kiểm tra và chuyển đổi ký tự.

#include <iostream>
#include <string>
#include <map>
#include <cctype>
#include <limits>

using namespace std;

int main() {
    string s;

    cout << "Nhap mot chuoi bat ky: ";
    getline(cin >> ws, s);

    map<char, int> tan_suat;

    for (char ky_tu : s) {
        if (isalpha(ky_tu)) {
            char ky_tu_thuong = tolower(ky_tu);
            tan_suat[ky_tu_thuong]++;
        }
    }

    cout << "\nTan suat chu cai (khong phan biet hoa thuong):\n";
    for (const auto& cap : tan_suat) {
        cout << "'" << cap.first << "': " << cap.second << "\n";
    }

    return 0;
}

Nhap mot chuoi bat ky: Hello World! 123

Tan suat chu cai (khong phan biet hoa thuong):
'd': 1
'e': 1
'h': 1
'l': 3
'o': 2
'r': 1
'w': 1

Giải thích Sự Thay Đổi:

#include <cctype> được thêm vào.
Trong vòng lặp, if (isalpha(c)) kiểm tra xem ký tự c có phải là một ký tự chữ cái (a-z, A-Z) hay không. Chỉ những ký tự này mới được xử lý.
Nếu là chữ cái, char lower_c = tolower(c); chuyển ký tự đó thành chữ thường. tolower trả về chữ thường tương ứng nếu đó là chữ hoa, hoặc trả về chính ký tự đó nếu nó đã là chữ thường hoặc không phải chữ cái.
frequency[lower_c]++; tăng bộ đếm cho ký tự chữ thường tương ứng.

Với input "Hello World! 123", output sẽ là:

Nhap mot chuoi bat ky: Hello World! 123

Tan suat chu cai (khong phan biet hoa thuong):
'd': 1
'e': 1
'h': 1
'l': 3
'o': 2
'r': 1
'w': 1

Các ký tự không phải chữ cái như khoảng trắng, dấu '!', số '1', '2', '3' đã bị bỏ qua.

Cách 2: Sử Dụng `unordered_map`

unordered_map cũng là một cấu trúc dữ liệu lưu trữ cặp khóa-giá trị, tương tự như map. Tuy nhiên, nó sử dụng kỹ thuật băm (hashing) để lưu trữ dữ liệu thay vì dựa trên thứ tự.

Ưu điểm của unordered_map:

Trung bình (average case), tốc độ truy cập, chèn và xóa phần tử nhanh hơn đáng kể so với map (thường là O(1)).

Nhược điểm:

Các phần tử không được lưu trữ theo thứ tự của khóa. Thứ tự khi duyệt qua unordered_map là không xác định và có thể thay đổi.
Trường hợp xấu nhất (worst case) cho truy cập/chèn có thể chậm hơn (O(n)) nếu có nhiều xung đột băm (hash collisions), mặc dù hiếm gặp với các kiểu dữ liệu chuẩn như char.

Code sử dụng unordered_map rất giống với map:

#include <iostream>
#include <string>
#include <unordered_map>
#include <limits>

using namespace std;

int main() {
    string s;

    cout << "Nhap mot chuoi bat ky: ";
    getline(cin >> ws, s);

    unordered_map<char, int> tan_suat;

    for (char ky_tu : s) {
        tan_suat[ky_tu]++;
    }

    cout << "\nTan suat ky tu (su dung unordered_map):\n";
    for (const auto& cap : tan_suat) {
        cout << "'" << cap.first << "': " << cap.second << "\n";
    }

    return 0;
}

Nhap mot chuoi bat ky: hello world

Tan suat ky tu (su dung unordered_map):
'l': 3
'o': 2
' ': 1
'w': 1
'r': 1
'd': 1
'h': 1
'e': 1

Giải thích Code:

Code này gần như giống hệt code sử dụng map, chỉ khác ở việc bao gồm thư viện <unordered_map> và khai báo unordered_map<char, int> frequency;. Logic đếm frequency[c]++; hoạt động tương tự.

Sự khác biệt chính sẽ nằm ở thứ tự xuất hiện của các ký tự khi in ra. Với cùng input "hello world", output có thể khác so với map:

Nhap mot chuoi bat ky: hello world

Tan suat ky tu (su dung unordered_map):
'l': 3
'o': 2
' ': 1
'w': 1
'r': 1
'd': 1
'h': 1
'e': 1

Lưu ý: Thứ tự này chỉ là một khả năng và có thể khác mỗi lần chạy hoặc trên các hệ thống khác nhau.

Khi nào nên dùng map và khi nào nên dùng unordered_map? Nếu bạn cần các phần tử được sắp xếp theo khóa hoặc cần đảm bảo hiệu suất trường hợp xấu nhất, hãy dùng map. Nếu bạn chỉ cần tra cứu nhanh và thứ tự không quan trọng, unordered_map thường là lựa chọn hiệu quả hơn về tốc độ trung bình.

Cách 3: Sử Dụng Mảng (Array)

Đối với bài toán đếm tần suất ký tự, đặc biệt nếu chúng ta chỉ làm việc với các ký tự trong bộ mã ASCII (có khoảng 256 ký tự khác nhau), chúng ta có thể sử dụng một mảng đơn giản. Mỗi chỉ số của mảng sẽ tương ứng với mã ASCII của một ký tự, và giá trị tại chỉ số đó sẽ là số lần xuất hiện của ký tự đó.

Bộ mã ASCII tiêu chuẩn sử dụng các giá trị từ 0 đến 127. Bộ mã ASCII mở rộng (extended ASCII) có thể lên đến 255. Một mảng kích thước 256 là đủ để bao phủ tất cả các ký tự có thể được biểu diễn bằng 1 byte.

Ưu điểm của mảng:

Rất hiệu quả về tốc độ truy cập (luôn là O(1)) vì chỉ cần tính toán địa chỉ dựa trên chỉ số.
Đơn giản cho các bộ ký tự có phạm vi nhỏ và cố định như ASCII.

Nhược điểm:

Kích thước mảng cố định, có thể lãng phí bộ nhớ nếu bộ ký tự rất lớn hoặc rất thưa thớt.
Không linh hoạt cho các bộ ký tự không có thứ tự liên tục hoặc quá lớn như Unicode (trừ khi dùng các kỹ thuật mapping phức tạp hơn).
Cần cẩn thận với kiểu dữ liệu char (có thể là signed hoặc unsigned tùy hệ thống) khi dùng làm chỉ số mảng.

Code sử dụng mảng:

#include <iostream>
#include <string>
#include <vector>
#include <cctype>
#include <limits>

using namespace std;

int main() {
    string s;

    cout << "Nhap mot chuoi bat ky: ";
    getline(cin >> ws, s);

    vector<int> tan_suat(256, 0);

    for (char ky_tu : s) {
        unsigned char chi_so = static_cast<unsigned char>(ky_tu);
        tan_suat[chi_so]++;
    }

    cout << "\nTan suat ky tu (su dung mang/vector):\n";
    for (int i = 0; i < 256; ++i) {
        if (tan_suat[i] > 0) {
            char ky_tu_in = static_cast<char>(i);
            if (isprint(ky_tu_in) || ky_tu_in == ' ') {
                 cout << "'" << ky_tu_in << "': " << tan_suat[i] << "\n";
            } else {
                 cout << "[ASCII " << i << "]: " << tan_suat[i] << "\n";
            }
        }
    }

    return 0;
}

Nhap mot chuoi bat ky: hello world

Tan suat ky tu (su dung mang/vector):
' ': 1
'd': 1
'e': 1
'h': 1
'l': 3
'o': 2
'r': 1
'w': 1

Lưu ý: Cần thêm #include <cctype> cho isprint nếu bạn muốn sử dụng điều kiện kiểm tra đó. Nếu không, bỏ qua dòng if (isprint...).

Giải thích Code:

#include <vector> được sử dụng để làm việc với vector, một dạng mảng động tiện lợi hơn mảng C-style truyền thống.
vector<int> frequency(256, 0); tạo một vector có kích thước 256 và khởi tạo tất cả các phần tử bằng 0. Kích thước 256 là để chứa tần suất của tất cả các giá trị có thể có của kiểu unsigned char (từ 0 đến 255).
Trong vòng lặp, unsigned char index = static_cast<unsigned char>(c); là bước quan trọng. Kiểu char trong C++ có thể là signed hoặc unsigned tùy thuộc vào trình biên dịch. Nếu char là signed và chứa một ký tự có mã ASCII > 127 (ví dụ các ký tự mở rộng), giá trị của nó có thể âm. Sử dụng giá trị âm làm chỉ số mảng sẽ gây lỗi. Ép kiểu sang unsigned char đảm bảo chúng ta có một giá trị từ 0 đến 255, an toàn để dùng làm chỉ số cho vector có kích thước 256.
frequency[index]++; tăng bộ đếm tại chỉ số tương ứng với mã của ký tự. Đây là thao tác rất nhanh.
Vòng lặp cuối cùng for (int i = 0; i < 256; ++i) duyệt qua toàn bộ vector.
if (frequency[i] > 0) kiểm tra xem chỉ số i (tức là mã ASCII i) có xuất hiện trong chuỗi hay không.
char character = static_cast<char>(i); chuyển chỉ số i trở lại thành kiểu char để hiển thị ký tự tương ứng.
Phần kiểm tra isprint và in mã ASCII là để xử lý các ký tự đặc biệt như xuống dòng, tab, chuông... mà việc in trực tiếp có thể không hiển thị đúng hoặc gây ra hành vi không mong muốn.

Với input "hello world", output (không dùng isprint để đơn giản) sẽ giống như map, nhưng thứ tự chắc chắn theo mã ASCII từ 0 đến 255 (chỉ in những ký tự có tần suất > 0).

Comments

There are no comments at the moment.