Run-length encoding bằng Python: nén chuỗi lặp
Bài 3/10 · Chương 25
Bài tập phỏng vấn Python
- 7 phút
- Trung cấp
- Python 3.14
- Cập nhật
Trong bài này · 11
Run-length encoding (nén theo loạt) ghi mỗi đoạn ký tự giống nhau liền nhau thành ký tự đó kèm số lần lặp, nên "aaabbc" thành "a3b2c1". Nó hợp với dữ liệu có nhiều đoạn lặp dài như sơ đồ ghế của rạp phim. Trang này viết hàm nén, chỉ ra chỗ hàm giải nén hay sai, rồi để bạn tự viết hàm giải nén được chấm ngay trên trang.
Cần biết trước: duyệt chuỗi, biến tích lũy và f-string.
Đề bài
Rạp phim gửi sơ đồ ghế của từng hàng về máy bán vé: X là ghế đã bán, O là ghế trống. Một hàng 19 ghế viết thẳng ra là "XXXXOOXXXXXXXXXXXXO", dài và khó đọc. Viết hàm nen(s) trả về bản nén: mỗi nhóm ký tự giống nhau liền nhau thành ký tự đó rồi số lần lặp.
Ví dụ vào ra: nen("aaabbc") trả về "a3b2c1", nen("XXXXOOXXXXXXXXXXXXO") trả về "X4O2X12O1".
Câu hỏi làm rõ trước khi viết code:
Nhóm chỉ một ký tự có ghi số
1không? Có,"c"thành"c1".Chuỗi gốc có chữ số không? Không, nếu có thì không ai đọc được
"a12"là mười hai chữahay chữa, chữ1, chữ2.Chữ hoa và chữ thường có là hai ký tự khác nhau không? Có.
Một ký tự xuất hiện ở hai nhóm cách nhau thì sao? Ghi hai nhóm:
"aabaa"thành"a2b1a2".Chuỗi rỗng nén ra gì? Chuỗi rỗng.
Nén một lượt: đếm từng nhóm ký tự liền nhau
Hàm giữ hai biến: ký tự của nhóm đang đếm và số lần đã gặp nó. Gặp lại đúng ký tự đó thì tăng biến đếm, gặp ký tự khác thì ghi nhóm cũ vào kết quả rồi bắt đầu nhóm mới:
def nen(s):
if s == "":
return ""
ket_qua = ""
ky_tu, dem = s[0], 0
for c in s:
if c == ky_tu:
dem += 1
else:
ket_qua += f"{ky_tu}{dem}"
ky_tu, dem = c, 1
return ket_qua + f"{ky_tu}{dem}"
print(nen("aaabbc"), nen("XXXXOOXXXXXXXXXXXXO"), repr(nen("")))KẾT QUẢ
a3b2c1 X4O2X12O1 ''ky_tu bắt đầu bằng s[0] và dem bằng 0, nên lượt lặp đầu tiên đếm luôn ký tự đầu. Chuỗi rỗng không có s[0], vì vậy dòng if đầu hàm trả về ngay. Hàm đi qua chuỗi đúng một lượt, mỗi ký tự một phép so.
Khi nào bản nén dài hơn chuỗi gốc
Người phỏng vấn hay hỏi: nén có luôn làm chuỗi ngắn đi không? Đo thử ba hàng ghế, cột cuối là độ dài trước và sau khi nén:
def nen(s):
if s == "":
return ""
ket_qua = ""
ky_tu, dem = s[0], 0
for c in s:
if c == ky_tu:
dem += 1
else:
ket_qua += f"{ky_tu}{dem}"
ky_tu, dem = c, 1
return ket_qua + f"{ky_tu}{dem}"
for hang in ["XXXXXXXXXXXXOO", "XOXOXO", "XXOO"]:
ma = nen(hang)
print(f"{hang:<15}{ma:<14}{len(hang):>3}{len(ma):>4}")KẾT QUẢ
XXXXXXXXXXXXOO X12O2 14 5
XOXOXO X1O1X1O1X1O1 6 12
XXOO X2O2 4 4Mỗi nhóm tốn ít nhất hai ký tự trong bản nén, nên chuỗi mà các ký tự đổi liên tục, như "XOXOXO", dài gấp đôi sau khi nén. Kiểu nén này chỉ có lợi khi nhóm dài. Đổi "XOXOXO" thành "XXXXXX" rồi chạy lại: dòng giữa in X6.
Giải nén: đọc ký tự rồi gom các chữ số
Máy bán vé nhận "X4O2X12O1" và phải dựng lại hàng ghế. Mỗi nhóm của mã là một ký tự rồi một số, nên cách nghĩ ra đầu tiên là đọc từng cặp hai ký tự. Cách đó chỉ đúng khi mọi số lần lặp có một chữ số:
Cách đúng đi qua mã từng ký tự một và giữ hai biến: ký tự của nhóm đang đọc, và một chuỗi gom các chữ số của nó. c.isdigit() của bài phương thức chuỗi cho biết c có phải chữ số không. Gặp chữ số thì nối vào chuỗi gom. Gặp ký tự khác thì nhóm trước đã đủ: đổi chuỗi gom sang số bằng int(), lặp ký tự bằng toán tử * của bài nối chuỗi, rồi bắt đầu nhóm mới. Giống hàm nén, nhóm cuối không có ký tự nào đứng sau báo hết, nên phải ghi riêng sau vòng lặp. Bài tập ở cuối trang để bạn viết hàm này.
Nói gì với người phỏng vấn
Mở đầu bằng các câu hỏi của mục Đề bài, nhất là chuyện chuỗi gốc có chữ số không và nhóm một ký tự có ghi 1 không. Rồi bạn trình bày:
"Hàm nén đi một lượt, giữ ký tự đang đếm và số lần gặp, gặp ký tự khác thì ghi nhóm cũ. Nhóm cuối được ghi riêng sau vòng lặp."
"Hàm giải nén cũng một lượt, gom các chữ số liền nhau thành số lần lặp, nên số từ 10 trở lên vẫn đúng."
"Cả hai hàm có số bước tăng cùng nhịp với độ dài chuỗi."
"Kiểu nén này chỉ có lợi khi nhóm dài: chuỗi đổi ký tự liên tục thì bản nén dài gấp đôi."
"Tôi đã xét chuỗi rỗng, chuỗi một ký tự, nhóm từ 10 ký tự trở lên và một ký tự xuất hiện ở hai nhóm."
Kiểm tra nhanh
Hàm
nencủa mục nén một lượt biến"XXOOOX"thành chuỗi ____.Trong hàm
nen, vì sao dòng cuối làreturn ket_qua + f"{ky_tu}{dem}"thay choreturn ket_qua?- Để chuỗi rỗng nén ra chuỗi rỗng
- Vì
ket_quachỉ được nối trong nhánhif - Vì một nhóm chỉ được ghi khi gặp ký tự khác, mà sau nhóm cuối không còn ký tự nào
Bộ giải nén đọc từng cặp hai ký tự của khung bẫy báo lỗi với những mã nào?
"X12O1""a3b2c1""X10""O9X9"
Bài tập
Giải nén sơ đồ ghế của rạp phim
Máy bán vé nhận sơ đồ ghế đã nén. Viết hàm giai_nen(ma) trả về chuỗi gốc. Mã luôn đúng dạng: một ký tự không phải chữ số rồi số lần lặp từ 1 trở lên, và số có thể có nhiều chữ số ("X12" là 12 ghế X). Ký tự có thể là chữ hoa, chữ thường, chữ có dấu hay dấu cách. Mã rỗng cho chuỗi rỗng. Không dùng module re.
Ví dụ: giai_nen("X4O2X12O1") trả về "XXXXOOXXXXXXXXXXXXO".
Trả về: hàng ghế đã giải nén, một str.
Ôn lại: duyệt chuỗi.
def giai_nen(ma):
pass # Viết thân hàm thay cho dòng nàyCâu hỏi thường gặp
Nén chuỗi trong Python có cách nào ngắn hơn tự đếm không?
Có: groupby() của module itertools gom sẵn các phần tử liền nhau bằng nhau, mỗi nhóm cho bạn ký tự và các phần tử của nhóm, như bài itertools cho thấy. Ở buổi phỏng vấn, người hỏi thường muốn thấy bạn tự đếm, nên viết cách một lượt trước rồi mới nhắc tới groupby().
Chuỗi gốc có chữ số thì nén thế nào?
Mã kiểu a3b2 không còn đọc được, vì chữ số của dữ liệu lẫn với số lần lặp. Một cách là ghi số lần lặp với độ rộng cố định bằng f-string, như f"{c}{dem:03d}" cho "1003", rồi đọc mỗi nhóm đúng bốn ký tự. Cách này giới hạn mỗi nhóm dưới 1.000 ký tự.
Có cần trả về chuỗi gốc khi bản nén dài hơn không?
Đề phỏng vấn hay thêm luật này: nén xong mà không ngắn hơn thì trả về chuỗi gốc. Chỉ cần so len() của hai chuỗi trước khi trả về, như ví dụ ba hàng ghế. Người nhận khi đó phải biết chuỗi nào đã nén, nên luật này chỉ hợp khi dữ liệu gốc không chứa chữ số.
Chủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE
- Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
- Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
- Xây hệ thống AI cho doanh nghiệp tại VietPlatform.