편집 거리가 최대 3 인 문자열의 평균 수 (더 큰 알파벳)
길이 문자열 고려 $n \geq 3$ 알파벳 위에 $\{1,\dots, \sigma\}$. 편집 작업은 단일 기호 삽입, 삭제 또는 대체입니다. 두 문자열 사이의 편집 거리는 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 편집 작업 수입니다. 주어진 문자열$S$ 길이 $n$ 와 $S_i \in \{1,\dots, \sigma\}$, 내 질문은 최대 편집 거리 인 고유 한 문자열의 수와 관련이 있습니다. $3$ ...에서 $S$.
쓰자 $g_{k, \sigma}(S)$ 알파벳 위의 고유 한 문자열 수 $\{1,\dots, \sigma\}$ 최대 편집 거리 $k$ ...에서 $S$, 즉 $g_{k,\sigma}(S) = |\{S' : d(S', S) \leq k\}|$ 어디 $d(-,-)$ 편집 거리입니다.
허락하다 $X_n$ 알파벳 위의 임의 문자열을 나타내는 임의 변수 $\{1,\dots, \sigma\}$ 길이 $n$, 기호가 균일하고 독립적으로 선택됩니다.
이것은 내 질문으로 직접 연결됩니다.
허락하다 $X_n$ 길이의 임의 문자열을 나타내는 임의 변수 $n$, 기호가 균일하고 독립적으로 선택됩니다. 뭐가:
$$\mathbb{E}(g_{3, \sigma}(X_n))\;?$$
에 대한 $\sigma=2$우리 는 명시적인 공식을 얻을 수 있습니다 $(40+6n-4n^2)/2^n-83/2+(331/12)n-6n^2+(2/3)n^3$. 그래서 제 질문은 알파벳 크기에 대한 의존성은 무엇입니까?$\sigma$ 처럼?
답변
가변 v. 변경되지 않은 문자열 길이
내 의견에 대한 응답으로 처음에 언급했듯이 변환 된 문자열의 길이가 원본의 길이와 다를 수있는 경우 고유 한 편집 작업 집합 (잠재적으로 고유 한 결과를 생성 할 수있는 작업) 때문에이 문제가 훨씬 더 어려워집니다. )에는 다음 항목 18 개가 모두 포함됩니다.
- 길이 +3 = 3 회 삽입
- 길이 +2 = 2 개의 삽입 및 0 또는 1 개의 대체
- 길이 +1 = 1 개의 삽입 및 0, 1 또는 2 개의 대체
- 변경되지 않은 길이 = 0, 1, 2 또는 3 개의 치환; 삭제 1 회, 삽입 1 회, 대체 0 또는 1 회
- 길이 -1 = 1 회 삭제 및 0, 1 또는 2 개의 대체
- 길이 -2 = 2 개의 삭제 및 0 또는 1 개의 대체
- 길이 -3 = 삭제 3 회
여러 번 삽입하거나 여러 번 삭제하면 계산이 지나치게 어려워집니다. 반면에 길이를 변경하지 않고 유지해야하는 경우에는 고려할 편집 조합이 6 개 뿐이며 이러한 6 개 조합 중 어느 것도 다중 삽입 또는 다중 삭제를 포함하지 않기 때문에 문제가 더 다루기 쉬워집니다. 실제로 6 가지 사례 각각에 대한 계산은 비교적 간단합니다. 가장 까다로운 부분은 두 가지 다른 편집 작업이 동일한 문자열을 생성 할 때 이중 계산 인스턴스를 피하기 위해 할인하는 것입니다.이 문제는 다른 질문 에 대한 답변으로 해결됩니다 .
6 가지 사례와 초과 계산의 위험
처음에 우리 의 입장 을 파악 하기 위해 다음 논리를 일반화 할 수 있습니다 .
- 문자열은 유지해야합니다. $n$ 기호.
- 동일한 기호의 예상 그룹 수는 다음과 같습니다. $\frac{n+1}{\sigma}$
- 인접한 동일한 기호 쌍의 예상 수는 다음과 같습니다. $\frac{n-1}{\sigma}$
- 끝의 수는 2입니다.
5 가지 가능한 단일 편집 유형을 세밀하게 고려하면 다음과 같은 결과를 얻을 수 있습니다.
- 가능한 대체 수는 다음과 같습니다. $n(\sigma-1)$
- 동일한 기호 그룹의 예상 수축 횟수는 다음과 같습니다. $\frac{n+1}{\sigma}$
- 동일한 기호를 가진 동일한 기호 그룹의 예상 확장 수는 다음과 같습니다. $\frac{n+1}{\sigma}$
- 동일한 기호를 가진 동일한 기호 그룹에 대한 예상 삽입 수는 다음과 같습니다. $\frac{n-1}{\sigma}$
- 시작 또는 끝에 다른 문자를 삽입 할 수있는 횟수는 다음과 같습니다. $2(\sigma-1)$
이제 기본 논리를 6 가지 경우 각각에 적용 할 수 있습니다.
아무 편집도
수행하지 않으면 원래 문자열 만 생성되므로이 경우 1 개의 결과가 생성됩니다.하나의 대체
가 있습니다$n$ 다른 기호 및 $\sigma-1$ 각각 다른 기호로 대체 될 수있는 방법을 $n(\sigma-1)$ 결과.두 개의 대체
가 있습니다$\binom{n}{2}$ 다른 쌍과 $(\sigma-1)^2$ 각각을 수정하는 방법 : $\binom{n}{2}(\sigma-1)^2$ 결과.세 가지 대체
가 있습니다$\binom{n}{3}$ 다른 트리오와 $(\sigma-1)^3$ 각각을 수정하는 방법 : $\binom{n}{3}(\sigma-1)^3$.하나의 삭제, 하나의 삽입, 대체 없음
이 경우에 대해이 솔루션 을 일반화 할 수 있습니다.$\sigma=2$ 아무에게나 $\sigma$, 동일한 논리를 사용하여 두 개의 대체가 하나의 삭제 및 하나의 삽입으로 동일한 결과를 산출하는 인스턴스를 이중 계산하지 않도록합니다.
삽입이 삭제의 왼쪽에있는 경우를 계산 한 다음 2를 곱해 봅시다. 삽입과 삭제의 결합 된 효과는 첫 번째 비트를 교체하고 마지막 비트를 제거하면서 그들 사이의 모든 𝑘 비트를 오른쪽으로 이동하는 것입니다. . 이 결과는 최대 𝑘 대체로도 얻을 수 있으므로 𝑘> 2가 필요합니다. 𝑥 실행에 𝑥을 삽입하는 것은 실행이 끝날 때 𝑥을 삽입하는 것과 동일한 효과가 있습니다. 따라서 우리는 항상 삽입 오른쪽에있는 비트를 보완하는 비트를 삽입하여 다른 효과를 가진 모든 삽입을 한 번 계산할 수 있습니다. 마찬가지로, 실행 내 삭제는 실행 시작시 삭제와 동일한 효과를 가지므로 0과 1 사이의 변경에 따른 삭제 만 계산해야합니다. 그러면 다음과 같은 초기 개수가 제공됩니다.
$2\cdot\frac12\sum_{k=3}^n(n+1-k)=\sum_{k=1}^{n-2}k=\frac{(n-1)(n-2)}2\;$
이중 계산을 방지하는 까다로운 논리가 직접 전달되기 때문에 필요한 유일한 수정은 변수를 대체하는 것입니다. $\sigma$ 고정 용 $\sigma=2$:
$2\cdot\frac{1}{\sigma}\sum_{k=3}^n(n+1-k)=2\cdot\frac{1}{\sigma}\sum_{k=1}^{n-2}k=\frac{(n-1)(n-2)}{\sigma}\;$
이미 두 개의 대체로 집계 된 결과의 초과 개수는 다음과 같이 계산할 수 있습니다. $\sigma=2$:
삭제 이전의 비트 이외의 𝑘 시프트 된 비트에 추가 변경이 없으면 삽입 및 삭제 옆의 비트 만 변경되며 2 개의 대체로이를 달성 할 수 있으므로 빼야합니다.
$\sum_{k=3}^n\left(\frac12\right)^{k-2}(n+1-k)=\sum_{k=1}^{n-2}\left(\frac12\right)^{n-k-1}k=n-3+2^{-(n-2)}\;$
다시 말하지만, 우리의 유일한 수정은 $\sigma$ 2 인 경우 :
$\sum_{k=3}^n\left(\frac1{\sigma}\right)^{k-2}(n+1-k)=\sum_{k=1}^{n-2}\left(\frac1{\sigma}\right)^{n-k-1}k=n-3+{\sigma}^{-(n-2)}\;$
또한, 시프트 된 비트의 전체 범위가 0과 1이 번갈아 가며 구성된 경우 삽입과 삭제를 교체하면 동일한 효과가 발생하므로이 경우에는 이중 계산을 수행하고 빼야합니다.
$\sum_{k=3}^n\left(\frac12\right)^{k-1}(n+1-k)\;$
안으로 스와핑 $\sigma$ 최종 시간은 다음과 같습니다.
$\sum_{k=3}^n\left(\frac1{\sigma}\right)^{k-1}(n+1-k)\;$
이 두 오버 카운트 (심볼이 이진일 때처럼 명확하게 결합 할 수 없음)는 삭제 / 삽입 작업의 초기 카운트에서 빼서이 경우에 의해 생성 된 전체 결과를 산출하지만 위의 경우 3에서는 그렇지 않습니다.
$\frac{(n-1)(n-2)}{\sigma}\ - \left(n-3+{\sigma}^{-(n-2)}\right) - \sum_{k=3}^n\left(\frac1{\sigma}\right)^{k-1}(n+1-k)\;$
- 하나의 삭제, 하나의 삽입, 하나의 대체
동일한 계산이 최종 케이스로 이어집니다. 그러나 여기서는 하나의 삭제와 하나의 삽입의 각 조합 (위의 사례 4에서 이미 집계 된 삼중 치환을 이중 계산하지 않도록 할인 됨)에는 세 번째 편집이 수반됩니다.$n-1$삭제 후 남아있는 원래 기호. 이들 각각 이후$(n-1)$ 상징은 인정한다 $(\sigma-1)$ 새로운 대체, 여섯 번째 및 최종 케이스의 총 개수는 다음과 같습니다.
$\left(\frac{(n-1)(n-2)}{\sigma}\ - \left(n-3+{\sigma}^{-(n-2)}\right) - \sum_{k=3}^n\left(\frac1{\sigma}\right)^{k-1}(n+1-k)\right)(n-1)(\sigma-1);$
이 6 가지 경우 각각에서 생성 된 (이전에 계산되지 않은) 결과를 합산하면 문자열 길이가 변경되지 않은 상태로 유지 될 때 예상되는 개수가 산출됩니다. 못 생겼지 만 (아마도 불필요하게) 정확하길 바랍니다.