문자열 편집 거리=1인 관계의 그래프를 생성하는 무차별 대입 알고리즘보다 더 나은 알고리즘이 있습니까?

Question

나는 정점이 문자열이고 가장자리가 주어진 문자열 메트릭에서 편집 거리가 1인 관계를 나타내는 그래프를 만드는 데 관심이 있습니다.

분명한 접근 방식은 모든 것을 만드는 것입니다. $\frac{n^2-n}{2}$ 간의 비교 $n$ 꼭지점, 우리에게 제공 $O(n^2)$ 시간 복잡도.

비교 병렬화를 제외하고 시간 복잡도 측면에서 더 나은 알고리즘이 있습니까?

길이가 다른 문자열이 허용되는 문자열 측정항목에 관심이 있습니다.

Answer 1

최악의 경우 그러한 알고리즘은 $ \ omega (n ^ 2) $ 이 작동합니다.>$ \ omega (n ^ 2) $ 가장자리.

그런데 특정 문자열 메트릭에 관심이 있습니까?

Answer 2

사용이 가능해요 BK-트리 속도를 높이려고요.삽입 $n$ 트리에 들어가는 요소는 $O(n \log n)$ 시간.그런 다음 편집 거리가 입력에서 정확히 1만큼 떨어진 모든 문자열에 대해 트리를 쿼리할 수 있습니다.모든 문자열에 대해 이 작업을 다시 수행하면 $O(n^2)$ 그러나 매우 작은 상수 요소(이 페이지 쿼리당 트리의 5~8%만 검사해야 한다고 언급합니다.)

작동 방식에 대한 간단한 설명은 다음과 같습니다.

데이터 구조

BK-트리는 다음 중 하나입니다.

• 비어 있는
• 루트 값이 있는 노드 $r$ 그리고 인덱싱된 하위 항목 세트 $c_i$, 각각 BK-트리(해시 맵, 동적 배열 등을 사용하여 구현됨)

미터법(중요!) 거리 함수 $d(x,y)$ 삽입 및 쿼리에 사용됩니다.

문자열 삽입 중 $s$

• 트리가 비어 있으면 다음을 사용하여 새 노드로 만듭니다. $s$ 루트 값으로, 자식은 없음
• 트리가 루트를 가진 노드인 경우 $r$ 그리고 아이들 $c_i$, 허락하다 $k=d(r,s)$.
  • 만약에 $k=0$, 다음으로 삽입 건너뛰기 $s$ 이미 루트에 있습니다
  • 그렇지 않으면 재귀적으로 삽입 $s$ 로 $k$-번째 자식 트리 $c_k$.

마지막 단계에서는 다음의 모든 노드가 $c_i$ 거리가 있다 $i$ 뿌리까지

문자열 쿼리 중 $s$

• 트리가 비어 있으면 결과가 반환되지 않습니다.
• 트리가 루트를 가진 노드인 경우 $r$ 그리고 아이들 $c_i$, 허락하다 $k=d(r,s)$.
  • 만약에 $k=1$, 추가하다 $r$ 결과적으로 (메모:이 단계는 일반적인 BK-Tree 쿼리와 다릅니다)
  • 또한, 재귀적으로 쿼리 $s$ 아이들에게서 $c_{d-1}$, $c_d$ 그리고 $c_{d+1}$.해당 쿼리의 모든 결과도 반환합니다.

마지막 단계는 BK-Trees의 마법입니다. 거리가 미터법이기 때문에 다른 어린이를 확인할 필요가 없기 때문입니다.다른 사람을 확인할 필요가 없는 이유에 대한 부분적인 증거는 다음과 같습니다.

문자열이 있다고 가정 해 봅시다 $x$ 이는 우리 쿼리와 거리가 1이므로 $d(s, x)=1$, 하지만 하위 트리에 있습니다. $c_{k+2}$.우리는 그것을 알고 있습니다 $d(r, x)=k+2$ 삽입 절차부터.그러나 이것은 (미터법 공간에 대한 삼각형 부등식을 사용하여) 다음을 제공합니다.

$$ k+2=d(r, x)\leq d(r, s)+d(s,x)=k+1 $$

그러나 이것은 모순이다!비슷한 일이 다음과 같은 모든 어린이에게 이루어질 수 있습니다. $i>k+1$ 그리고 $i<k-1$.즉, 다른 자식의 모든 문자열은 구성에 따라 거리가 하나도 없으므로 이를 확인할 필요도 없어 처리 시간이 절약됩니다.

편집하다:또 다른 설명: https://signal-to-noise.xyz/post/bk-tree/