Khoảng cách Levenshtein trong biểu thức chính quy

Question

có khả năng bao gồm khoảng cách levenshtein trong truy vấn biểu thức chính quy không?

Ngoại trừ việc kết hợp giữa các hoán vị. Giống như tìm kiếm "hello" với L.d. 1

.ello | h.llo | he.lo | hel.o | hell. 

điều này thật ngu ngốc và không thể sử dụng được với số lượng lớn hơn L.d.

Answer 1

có khả năng bao gồm khoảng cách levenshtein trong truy vấn biểu thức chính quy không?

Không, không theo cách thông minh. Thực hiện - hoặc sử dụng một thuật toán khoảng cách hiện có - Levenshtein là cách để đi.

Answer 2

Bạn có thể tạo regex theo chương trình. Tôi sẽ rời khỏi đó như là một bài tập cho người đọc, nhưng đối với đầu ra của chức năng giả thuyết này (cho một đầu vào của "chữ"), bạn muốn một cái gì đó giống như chuỗi này:

"^(?>word|wodr|wrod|owrd|word.|wor.d|wo.rd|w.ord|.word|wor.?|wo.?d|w.?rd|.?ord)$" 

Trong tiếng Anh, đầu tiên bạn cố gắng để phù hợp với trên chính từ đó, sau đó trên mọi chuyển vị đơn lẻ có thể, sau đó trên mọi lần chèn đơn lẻ, sau đó trên mọi thiếu sót hoặc thay thế duy nhất có thể (có thể được thực hiện đồng thời).

Độ dài của chuỗi đó, với một từ có độ dài n, là tuyến tính (và đáng chú ý là không theo cấp số nhân) với n.

Điều gì là hợp lý, tôi nghĩ vậy.

Bạn chuyển điều này cho trình tạo regex (như trong Ruby nó sẽ là Regexp.new (str)) và bam, bạn có một đối sánh cho bất kỳ từ nào có khoảng cách Damerau-Levenshtein 1 từ một từ đã cho.

(Damerau-Levenshtein khoảng cách 2 còn lâu mới phức tạp hơn.)

Lưu ý sử dụng (> không quay lui xây dựng có nghĩa là thứ tự của các cá nhân |?. 'Biểu d trong đó vấn đề đầu ra

tôi không thể nghĩ ra một cách để "nhỏ gọn" biểu rằng

EDIT:. tôi đã nhận nó để làm việc, ít nhất là trong Elixir https://github.com/pmarreck/elixir-snippets/blob/master/damerau_levenshtein_distance_1.exs

tôi sẽ không nhất thiết phải đề nghị mặc dù điều này (trừ giáo dục! pu đề xuất) vì nó sẽ chỉ đưa bạn đến khoảng cách 1; một thư viện DL VN sẽ cho phép bạn tính toán khoảng cách> 1. Mặc dù vì đây là regex, nó có thể hoạt động khá nhanh khi được xây dựng (lưu ý rằng bạn nên lưu regex "biên dịch" ở đâu đó vì mã này hiện đang xây dựng lại nó trên MỌI so sánh!)