3

Khoảng cách Levenshtein là một số liệu chuỗi để đo sự khác biệt giữa hai chuỗi. Một cách không chính thức, khoảng cách Levenshtein giữa hai từ là số lần chỉnh sửa một ký tự tối thiểu (nghĩa là chèn, xóa hoặc thay thế) cần thiết để thay đổi một từ thành từ khác. Nó được đặt theo tên của Vladimir Levenshtein , người đã phát hiện ra phương trình này vào năm 1965.

Khoảng cách Levenshtein cũng có thể được gọi là khoảng cách chỉnh sửa , mặc dù nó cũng có thể biểu thị một họ số liệu khoảng cách lớn hơn. Nó liên quan chặt chẽ với sự sắp xếp chuỗi theo cặp.

Định nghĩa

Về mặt toán học, khoảng cách Levenshtein giữa hai chuỗi  a và  b (có độ dài  |a| và  |b| tương ứng), được đưa ra bởi lev a,b(|a|,|b|) :

Ở đây,  1(ai≠bi) là hàm chỉ thị bằng 0 khi  ai≠bi và bằng 1 nếu không, và  leva, b(i,j) là khoảng cách giữa các i ký tự  đầu tiên a và các j ký tự đầu tiên  của  b.

Lưu ý rằng phần tử đầu tiên trong mức tối thiểu tương ứng với việc xóa (từ a đến b), phần tử thứ hai để chèn và phần tử thứ ba khớp hoặc không khớp, tùy thuộc vào việc các ký hiệu tương ứng có giống nhau hay không.

Thí dụ

Khoảng cách Levenshtein giữa HOA FLOMAX 'và CÂU LẠC ĐÁM MÂY là 3, vì ba lần chỉnh sửa sau thay đổi lần này thành lần khác và không có cách nào thực hiện với ít hơn ba lần chỉnh sửa:

Khoảng cách Levenshtein giữa Nhật Bản GILY và và GEELY 'là 2.

Khoảng cách Levenshtein giữa Elite HONDA 'và HY HYAIAI là 3.

Ứng dụng

  • Kết hợp chuỗi.

  • Kiểm tra chính tả.

Phương pháp lập trình động

Thuật toán Levenshtein tính toán số lượng thao tác chỉnh sửa ít nhất cần thiết để sửa đổi một chuỗi để có được một chuỗi khác. Cách tính toán phổ biến nhất là phương pháp lập trình động:

  1. Một ma trận được khởi tạo đo trong ô (m, n) khoảng cách Levenshtein giữa tiền tố m-ký tự của một với tiền tố n của từ khác.
  2. Ma trận có thể được điền từ góc trên bên trái đến góc dưới bên phải.
  3. Mỗi bước nhảy theo chiều ngang hoặc chiều dọc tương ứng với một lần chèn hoặc xóa tương ứng.
  4. Chi phí thường được đặt thành 1 cho mỗi hoạt động.
  5. Nhảy chéo có thể có giá một, nếu hai ký tự trong hàng và cột không khớp với 0 khác, nếu chúng khớp nhau. Mỗi tế bào luôn giảm thiểu chi phí tại địa phương.
  6. Bằng cách này, số ở góc dưới bên phải là khoảng cách Levenshtein giữa cả hai từ.

Một ví dụ có tính năng so sánh giữa HON HONDA và và HYUNDAI Lần:

Sau đây là hai đại diện, khoảng cách Levenshtein giữa lối mòn của HONDADA và HYUNDAI là 3.

Ca sử dụng

Trong kết hợp chuỗi gần đúng, mục tiêu là tìm các kết quả khớp cho các chuỗi ngắn trong nhiều văn bản dài hơn, trong các tình huống sẽ có một số lượng nhỏ sự khác biệt. Các chuỗi ngắn có thể đến từ một từ điển, ví dụ. Ở đây, một trong các chuỗi thường ngắn, trong khi chuỗi còn lại dài tùy ý. Điều này có một loạt các ứng dụng, ví dụ, trình kiểm tra chính tả, hệ thống sửa lỗi để nhận dạng ký tự quang học và phần mềm để hỗ trợ dịch ngôn ngữ tự nhiên dựa trên bộ nhớ dịch.

Khoảng cách Levenshtein cũng có thể được tính giữa hai chuỗi dài hơn. Nhưng chi phí để tính toán nó, tỷ lệ xấp xỉ với sản phẩm của hai độ dài chuỗi, làm cho điều này không thực tế. Do đó, khi được sử dụng để hỗ trợ tìm kiếm chuỗi mờ trong các ứng dụng như liên kết bản ghi, các chuỗi so sánh thường ngắn để giúp cải thiện tốc độ so sánh.

|