정규 표현식에서 Levenshtein 거리

Question

정규 표현식 질의에 levenshtein 거리를 포함시키는 방법이 있습니까?

순열 사이에 합집합을 만드는 것을 제외합니다. L.d.로 "hello"를 검색하는 것과 같습니다. 1

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

이것은 많은 수의 L.d에 대해 매우 바보이며 사용할 수 없습니다.

Answer 1

정규 표현식 쿼리에 levenshtein 거리를 포함시키는 방법은 있습니까?

아니요, 정상적인 방법이 아닙니다. 구현 - 또는 기존 - Levenshtein 거리 알고리즘을 사용하는 방법입니다.

Answer 2

프로그래밍 방식으로 정규식을 생성 할 수 있습니다. 먼저 일치하려고, 영어

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

: 난 당신이 문자열 같은 것을 원하는 ("단어"의 입력을 제공) 독자들에게 운동으로 떠날하지만,이 가상 함수의 출력됩니다 단어 자체, 모든 가능한 단일 치환, 모든 가능한 단일 삽입, 모든 가능한 단일 생략 또는 대체 (동시에 수행 될 수 있음)에 대해 설명합니다.

길이가 n 인 단어가 주어진 경우 해당 문자열의 길이는 n과 선형 (특히 지수가 아님)입니다.

어느 것이 합리적이라고 생각합니다.

정규 표현식 생성기 (Ruby와 같이 Regexp.new (str))와 bam을 전달하면 지정된 단어에서 Damerau-Levenshtein 거리가 1 인 단어에 대한 정규 표현식을 얻을 수 있습니다.

(2 Damerau-Levenshtein 거리가 훨씬 더 복잡하다.)

제 (> 비 역 추적의 각 순서를 의미 구조의

주 사용? |. 출력하는 물질의 'D 식

난에 "컴팩트"그 표현 방법 생각하지 못했습니다

편집 :. 나는 그것이 적어도 엘릭서에서 작동있어 https://github.com/pmarreck/elixir-snippets/blob/master/damerau_levenshtein_distance_1.exs

내가 반드시 교육을 제외하고 (이 생각을 권하고 싶지 않다! 우레탄 rposes) 그것은 단지 1의 거리로 당신을 얻을 것이다. 합법적 인 DL 라이브러리는 거리> 1을 계산하게 할 것입니다. 정규 표현식이긴하지만 일단 생성되면 꽤 빨리 작동 할 것입니다. (이 코드는 현재 모든 비교에서이 코드를 재구성하므로 어딘가에 "컴파일 된"정규 표현식을 저장해야합니다!)