Khoảng cách Levenshtein được tính qua bao nhiêu phép biến đổi?

Vì sao nhiều bạn dễ nhầm khi học về Levenshtein?

Khi mới học NLP hoặc khi chạm vào các chủ đề đo độ giống nhau giữa hai chuỗi, nhiều bạn thường dừng lại ở một câu hỏi tưởng đơn giản:

“Levenshtein dùng bao nhiêu phép biến đổi để tính khoảng cách? Delete, insert, substitute… nhưng có thêm thao tác nào nữa không?”

Sự bối rối này thường đến từ việc có nhiều loại khoảng cách chuỗi khác nhau: Hamming, Damerau-Levenshtein, Jaro-Winkler… khiến người mới dễ gộp chúng lại.

Bài viết dưới đây giúp bạn nhìn Levenshtein từ đúng bản chất, tránh công thức nặng nề.

Levenshtein là gì? (Giải thích dễ hiểu)

Khoảng cách Levenshtein đo xem hai chuỗi khác nhau bao nhiêu bằng cách đếm số thao tác tối thiểu để biến chuỗi A thành chuỗi B.

Điểm quan trọng nhất:

Levenshtein chỉ dùng 3 phép biến đổi.

Cụ thể là:

Insert (chèn ký tự)
Delete (xóa ký tự)
Substitute (thay ký tự)

Mỗi thao tác tính 1 đơn vị.
Khoảng cách = tổng số thao tác ít nhất cần dùng.

Nhiều người thường nhầm rằng có thêm “swap ký tự”, nhưng swap chỉ thuộc về biến thể Damerau-Levenshtein, không phải Levenshtein gốc.

Ví dụ thực tế để hình dung rõ hơn

Ví dụ 1

CAT → CUT

Thay A → U
→ 1 phép substitute

Khoảng cách = 1

Ví dụ 2

BOOK → BACK

Một cách hợp lý:

O → A
O → C

Khoảng cách = 2

Những ví dụ như vậy thường gặp trong các bài toán NLP:

gợi ý sửa lỗi chính tả
tìm kiếm gần đúng
so khớp tên riêng
làm sạch dữ liệu bị nhiễu

Khi làm dự án AI/ML, Levenshtein xuất hiện ở đâu?

Trong dữ liệu thật, việc so sánh chuỗi là chuyện diễn ra liên tục:

người dùng nhập sai tên
dữ liệu OCR nhận nhầm ký tự
text log chứa nhiều phiên bản gần giống nhau
chatbot cần hiểu input bị gõ sai

Levenshtein giúp bạn định lượng sự khác biệt để ra quyết định hợp lý.

Thuật toán này thường xuất hiện cùng các chủ đề thuộc những nhóm kiến thức nền tảng mà người học AI hay đi qua, ví dụ:

Python – NumPy – toán cơ bản: xử lý chuỗi và dữ liệu nền
ML cơ bản: tiền xử lý văn bản
NLP – Transformer: xây dựng pipeline xử lý text
LLMs, RAG: fuzzy search trong retrieval
ETL – Data Engineering: làm sạch dữ liệu đầu vào

Nó giống như “mảnh ghép nhỏ nhưng không thể thiếu” trong các hệ thống xử lý ngôn ngữ.

Kết luận: Levenshtein dùng bao nhiêu phép biến đổi?

Tóm tắt thật ngắn:

Levenshtein được tính bằng đúng 3 phép: Insert – Delete – Substitute.

Không có hoán đổi, không có reorder, không có thêm bước ẩn.

Lời khuyên nhẹ nhàng để hiểu sâu hơn

Bạn có thể:

thử tạo vài cặp chuỗi ngắn và tự tính khoảng cách
xem điều gì thay đổi khi chỉnh sửa từng ký tự
so sánh với Hamming hoặc Damerau-Levenshtein để nhận ra điểm khác nhau

Những thử nghiệm nhỏ như vậy giúp bạn nắm bản chất thuật toán hơn mà không cần công thức phức tạp.