Bir regexp ve bir dize arasındaki düzenleme mesafesini kalibre etmek mümkün mü?

Question

Öyleyse, nasıl olduğunu açıklayınız.

Re: mesafe nedir - "İki dizge arasındaki mesafe, diğerini dönüştürmek için gereken minimum düzenleme sayısı olarak tanımlanır." Örneğin, xyz'den XYZ'ye 3 düzenleme yapılacak, böylece xYZ dizisi XYZ ve xyz'ye daha yakın olacaktır. Desen [0-9] {3} veya örneğin 123 ise, o zaman a23, desene ab3'ten daha yakın olacaktır.

Bir regexp ile eşleşmeyen bir dize arasındaki en kısa mesafeyi nasıl bulabilirim?

Yukarıdakiler, Damerau–Levenshtein mesafe algoritmasıdır.

Answer 1

Verimli bir şekilde yapmak için Sonlu Durum Makinelerini kullanabilirsiniz (yani, zaman içinde doğrusal) . Bir dönüştürücü kullanırsanız, dönüşümün özelliklerini oldukça küçük bir şekilde yazabilir ve basitçe ekleme veya silme işleminden çok daha nüanslı dönüşümler yapabilirsiniz - başlangıç ​​noktası olarak Finite State Transducer için wikipedia'yi ve FSA araç seti veya FSA6 gibi yazılımları (bkz. Tamamen kararlı olmayan bir web-demo). FSA manipülasyonu için birçok kütüphane var; Önceki ikisini tek ya da en iyi seçeneğiniz, sadece iki tane duyduğumu söylemek istemiyorum. Ancak, sadece verimli, yaklaşık aramayı istiyorsanız

, daha az esnek ama önceden uygulanan-için-size seçenek var: TRE, maçın maliyetini döndüren bir approximate matching function olan - için, mesafeyi yani senin bakış açısından maç.

Answer 2

En yakın eşleştirilen dize ve örnek arasındaki en küçük levenshtein mesafesine sahip dizeyi kastediyorsanız, bu işlemin yapılabildiğinden eminim, ancak Regex'i bir DFA'ya dönüştürmeniz gerekir. eşleşmek için ve bir şeyler başarısız olduğunda, deterministik olmayan bir şekilde geçmiş gibi devam etmiş ve sayı farklılıklarını takip etmiştir. A * araması veya bunun için benzer bir şeyi kullanabilirsiniz, ancak (O (2^n) en kötü durum)