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 tiếp xúc với các phương pháp đo độ giống nhau giữa hai chuỗi, rất nhiều bạn gặp một bối rối quen thuộc:

“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ự nhầm lẫn này thường đến từ việc có nhiều loại khoảng cách chuỗi khác nhau như Hamming, Damerau-Levenshtein, Jaro-Winkler… khiến người mới dễ trộn chúng lại.

Bài viết dưới đây giúp bạn hiểu Levenshtein đúng bản chất — gọn, đơn giản, không nặng công thức.

Levenshtein là gì?

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

Điều quan trọng nhất:

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

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

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

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

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ụ này thường xuất hiện trong bài toán:

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, so sánh chuỗi diễn ra liên tục:

Người dùng gõ sai tên
OCR nhận nhầm ký tự
Log chứa nhiều phiên bản gần giống nhau
Chatbot phải hiểu input sai chính tả

Levenshtein giúp định lượng mức độ khác biệt để xử lý hợp lý.

Thuật toán này gắn liền với nhiều nhóm kiến thức nền tảng:

Python – NumPy – toán cơ bản: xử lý chuỗi
ML cơ bản: tiền xử lý dữ liệu 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ó là “mảnh ghép nhỏ nhưng quan trọng” trong hệ thống xử lý ngôn ngữ.

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

Levenshtein chỉ dùng 3 phép: Insert – Delete – Substitute.
Không có swap, không reorder, không bước ẩn nào khác.

Lời khuyên để 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
Quan sát chuỗi thay đổi ra sao sau mỗi phép
So sánh với Hamming và Damerau-Levenshtein để thấy điểm khác biệt

Những thử nghiệm nhỏ giúp bạn nắm ý tưởng của thuật toán rõ hơn nhiều.

Hỏi đáp nhanh về chủ đề

Levenshtein có dùng phép hoán đổi ký tự không?
Không — hoán đổi thuộc Damerau-Levenshtein, không phải Levenshtein gốc.

Tại sao Levenshtein không tính swap?
Vì định nghĩa chuẩn chỉ gồm insert, delete, substitute.

Khoảng cách càng lớn nghĩa là gì?
Nghĩa là hai chuỗi càng khác nhau nhiều.

Levenshtein có dùng cho sửa lỗi chính tả không?
Có — đây là một trong các ứng dụng phổ biến nhất.

FAQ về chương trình AIO

Q1. Con số 0 thì học nổi không?
Ans: Chỉ cần bạn có thời gian học. Điều quan trọng nhất không phải giỏi hay không, mà là có học đều mỗi ngày. Kiến thức – tài liệu – môi trường đã có team lo. Nếu bạn không có thời gian thì nên cân nhắc.

Q2. Ai dạy AIO?
Ans: Đội admin dạy toàn bộ. Admin trực tiếp hướng dẫn và hỗ trợ mọi câu hỏi của bạn trong suốt quá trình học.

Q3. Admin có “xịn” không?
Ans: Admin đều là người làm nghề thật, mỗi người một cách dạy. Quan trọng là bạn cảm thấy hợp cách truyền đạt. Admin không dám nói xịn, chỉ dạy bằng hết sức.

Q4. AIO có gì khác những nơi khác?
Ans: AIO không phải trung tâm. Đây là dự án học tập cộng đồng, được cải tiến qua từng khóa. Tinh thần của AIO: Cùng nhau học – cùng nhau khổ – cùng nhau lớn. Nếu hợp tinh thần đó, bạn sẽ thấy phù hợp.