Ters Levenshtein mesafesi

Question

Levenshtein mesafesinde, bu iki dizeye göre, levenshtein mesafeleri ne olduğu sorusunu sorarsınız. Bir dize ve bir levenshtein mesafesi almayı ve o levenshtein mesafesindeki tüm ipleri oluşturmayı nasıl istersin? (Aynı zamanda bir karakter kümesini de alır). Yani eğer bir x dizgesini ve mesafeyi geçersem d. o zaman d-1 ve d-2 de dahil olmak üzere bu düzenleme mesafesindeki tüm dizeleri verirdi .... d-n; (n < d).

Beklenen işlevsellik:

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

boşluk karakteri setini içeren gibi program app le üretmek mümkün olduğuna dikkat edin.

Answer 1

Bunu yapan bir veri yapısı var Levenshtein automaton. Bir dizi dizeden (yalnızca bir üyeye sahip olabilir) ve sabit bir uzaklık k'dan oluşturursunuz ve daha sonra depoladığı dizelerden en fazla k ile tüm dizeleri sorgulayabilirsiniz. Bir Python uygulaması here tartışılmıştır.

Alternatif olarak, bu tür dizeler için ayrıntılı bir geri arama ile arama yapabilirsiniz.