Đảo ngược khoảng cách Levenshtein

Question

Trong khoảng cách levenshtein bạn đặt câu hỏi, với hai chuỗi này, khoảng cách levenshtein của chúng là bao nhiêu. Làm thế nào bạn sẽ đi về lấy một chuỗi và một khoảng cách levenshtein và tạo ra tất cả các chuỗi trong khoảng cách levenshtein đó. (Nó cũng sẽ đưa vào một bộ ký tự). Vì vậy, nếu tôi vượt qua trong một chuỗi x và một khoảng cách d. sau đó nó sẽ cho tôi tất cả các chuỗi trong khoảng cách chỉnh sửa đó, bao gồm d-1 và d-2 .... d-n; (n < d).

mong đợi chức năng:

>>> getWithinDistance('apple',2,{'a','b',' '}) 
['applea','appleb','appel','app le'...] 

Xin lưu ý rằng chương trình có thể sản xuất app le như không gian được bao gồm trong bộ ký tự.

Answer 1

Có cấu trúc dữ liệu thực hiện điều này được gọi là Levenshtein automaton. Bạn xây dựng nó từ một tập hợp các chuỗi (có thể chỉ có một thành viên) và khoảng cách cố định k và sau đó bạn có thể truy vấn nó cho tất cả các chuỗi có khoảng cách tối đa là k của bất kỳ chuỗi nào mà nó lưu trữ. Việc triển khai Python được thảo luận here.

Ngoài ra, bạn có thể thực hiện tìm kiếm có giới hạn độ sâu bằng tính năng backtracking cho các chuỗi như vậy.