- Đang điền
- Được đọc
- Đáp án
Khoảng cách chỉnh sửa (khoảng cách Levenshtein)
Cần bao nhiêu thay đổi một chữ cái để biến kitten thành sitting? Ba: thay k bằng s, thay e bằng i, và thêm g. Con số đó là khoảng cách chỉnh sửa; trình kiểm tra chính tả dùng nó để xếp hạng gợi ý, còn các nhà sinh học dùng nó để so sánh gen. Hãy nhập hai từ và xem một bảng tìm ra con số này. Nhấn Phát để xem bảng được điền dần, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Nhập hai từ: từ thứ nhất xếp dọc theo cạnh trái của bảng, từ thứ hai xếp ngang theo cạnh trên. Mỗi ô chứa số phép sửa ít nhất để biến các chữ cái tính đến hàng của ô thành các chữ cái tính đến cột của ô. Cuối cùng, các phép sửa được đọc ngược từ ô dưới cùng bên phải. Ví dụ mới chọn một cặp từ khác. Khi bảng đang được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.
Cách nó hoạt động
- Nhập hai từ: từ thứ nhất xếp dọc theo cạnh trái của bảng, từ thứ hai xếp ngang theo cạnh trên.
- Nhấn Phát, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu.
- Xem mỗi ô lấy giá trị rẻ nhất trong ba ô lân cận, rồi xem các phép sửa được đọc ngược bằng màu cam.
Cách bảng hoạt động
Mỗi ô chứa số phép sửa ít nhất để biến các chữ cái của từ thứ nhất tính đến hàng của ô thành các chữ cái của từ thứ hai tính đến cột của ô. Hàng đầu tiên đếm số phép chèn, dựng từ thứ hai từ chỗ trống, còn cột đầu tiên đếm số phép xóa. Nếu hai chữ cái của ô giống nhau, ô sao chép ô phía trên bên trái: không cần sửa. Nếu không, ô bằng giá trị nhỏ nhất trong ba ô lân cận cộng một: phía trên bên trái ứng với thay thế, phía trên ứng với xóa, và bên trái ứng với chèn.
Đọc ngược các phép sửa
Ô dưới cùng bên phải là khoảng cách chỉnh sửa. Bắt đầu từ đó, ứng dụng tìm xem giá trị của ô đến từ ô lân cận nào rồi bước sang ô đó: đi chéo với chữ cái được giữ hoặc bị thay, đi lên với chữ cái bị xóa, sang trái với chữ cái được chèn. Đọc từ góc trên bên trái, các bước này là một danh sách phép sửa ngắn nhất, hiển thị dưới bảng: chữ cái thường là được giữ, k→s là thay thế, −e là xóa và +g là chèn.
Câu hỏi thường gặp
Khoảng cách Levenshtein là gì?
Đó là tên khác của khoảng cách chỉnh sửa này: số phép chèn, xóa và thay thế một chữ cái ít nhất để biến một chuỗi thành chuỗi khác. Nó được đặt theo tên Vladimir Levenshtein, người mô tả nó vào năm 1965.
Khoảng cách chỉnh sửa giữa kitten và sitting là bao nhiêu?
3: thay k bằng s, thay e bằng i, và chèn g vào cuối. Bảng cho thấy không có danh sách phép sửa nào ngắn hơn.
Thuật toán khoảng cách chỉnh sửa nhanh đến mức nào?
Với hai từ có độ dài m và n, bảng có (m + 1)·(n + 1) ô, mỗi ô được điền trong một bước, nên mất thời gian O(m·n). Nếu chỉ cần khoảng cách, hai hàng của bảng là đủ.
Còn những khoảng cách chỉnh sửa nào khác?
Khoảng cách Damerau–Levenshtein còn tính việc đổi chỗ hai chữ cái liền kề là một phép sửa, phù hợp với lỗi gõ phím. Khoảng cách Hamming chỉ cho phép thay thế và dùng cho các chuỗi dài bằng nhau. Khoảng cách LCS chỉ cho phép chèn và xóa.
Có dữ liệu nào được gửi đi không?
Không. Mọi thứ đều được tính trong trình duyệt của bạn, và các thiết lập gần nhất được lưu trong bộ nhớ cục bộ của trình duyệt này.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Tới trình chỉnh sửa