Número médio de strings com distância de edição no máximo 3 (alfabeto maior)

Dec 21 2020

Considere uma string de comprimento $n \geq 3$ sobre um alfabeto $\{1,\dots, \sigma\}$. Uma operação de edição é a inserção, exclusão ou substituição de um único símbolo. A distância de edição entre duas strings é o número mínimo de operações de edição necessárias para transformar uma string em outra. Dado um string$S$ de comprimento $n$ com $S_i \in \{1,\dots, \sigma\}$, minha pergunta se refere ao número de strings distintas que são editadas no máximo $3$ a partir de $S$.

Vamos escrever $g_{k, \sigma}(S)$ para o número de strings distintas no alfabeto $\{1,\dots, \sigma\}$ quais são editar distância no máximo $k$ a partir de $S$, ie $g_{k,\sigma}(S) = |\{S' : d(S', S) \leq k\}|$ Onde $d(-,-)$ é a distância de edição.

Deixei $X_n$ ser uma variável aleatória representando uma string aleatória sobre o alfabeto $\{1,\dots, \sigma\}$ de comprimento $n$, com os símbolos escolhidos de maneira uniforme e independente.

Isso leva diretamente à minha pergunta:

Deixei $X_n$ ser uma variável aleatória que representa uma sequência aleatória de comprimento $n$, com os símbolos escolhidos de maneira uniforme e independente. O que é:

$$\mathbb{E}(g_{3, \sigma}(X_n))\;?$$

Para $\sigma=2$podemos obter uma fórmula explícita $(40+6n-4n^2)/2^n-83/2+(331/12)n-6n^2+(2/3)n^3$. Minha pergunta é: qual a dependência do tamanho do alfabeto$\sigma$ parece?

Respostas

1 BillVanderLugt Dec 30 2020 at 03:15

Variando v. Comprimento de String Inalterado

Se, como você indicou inicialmente em resposta ao meu comentário, o comprimento da string transformada pode ser diferente do comprimento do original, então este problema se torna muito mais difícil porque o conjunto de operações de edição distintas (operações que podem potencialmente produzir um resultado distinto ) inclui todos os 18 dos seguintes:

  • comprimento +3 = 3 inserções
  • comprimento +2 = 2 inserções e 0 ou 1 substituições
  • comprimento +1 = 1 inserção e 0, 1 ou 2 substituições
  • comprimento inalterado = 0, 1, 2 ou 3 substituições; 1 exclusão, 1 inserção e 0 ou 1 substituições
  • comprimento -1 = 1 exclusão e 0, 1 ou 2 substituições
  • comprimento -2 = 2 exclusões e 0 ou 1 substituições
  • comprimento -3 = 3 exclusões

Além disso, sempre que múltiplas inserções ou múltiplas eliminações são realizadas, a contagem torna-se extremamente difícil. Se, por outro lado, exigirmos que o comprimento permaneça inalterado, temos apenas 6 combinações de edição a considerar e o problema se torna mais tratável porque nenhuma dessas 6 combinações envolve múltiplas inserções ou múltiplas exclusões. Na verdade, a contagem para cada um dos seis casos torna-se relativamente simples; a parte mais complicada é descontar para evitar ocorrências de contagem dupla, quando duas operações de edição diferentes produzirão a mesma string - um problema resolvido em uma resposta a outra pergunta .

Os Seis Casos e o Perigo de Contagem Excessiva
Para nos orientar inicialmente, podemos generalizar esta lógica :

  • A corda deve manter $n$ símbolos.
  • O número esperado de grupos de símbolos idênticos é $\frac{n+1}{\sigma}$
  • O número esperado de pares de símbolos idênticos adjacentes é $\frac{n-1}{\sigma}$
  • O número de extremidades é 2.

Uma consideração detalhada dos cinco tipos possíveis de edições únicas resulta, portanto:

  • O número de substituições possíveis é $n(\sigma-1)$
  • O número esperado de reduções de um grupo de símbolos idênticos é $\frac{n+1}{\sigma}$
  • O número esperado de expansões de um grupo de símbolos idênticos com o mesmo símbolo é $\frac{n+1}{\sigma}$
  • O número esperado de inserções em um grupo de símbolos idênticos com o mesmo símbolo é $\frac{n-1}{\sigma}$
  • O número de inserções possíveis de um caractere diferente no início ou no final é $2(\sigma-1)$

Agora podemos aplicar essa lógica básica a cada um dos nossos seis casos:

  1. sem edições A
    execução de nenhuma edição produz apenas a string original, portanto, 1 resultado para este caso.

  2. uma substituição
    $n$ símbolos diferentes e $\sigma-1$ maneiras que cada um pode ser substituído por um símbolo diferente, então $n(\sigma-1)$ resultados.

  3. duas substituições
    existem$\binom{n}{2}$ pares diferentes e $(\sigma-1)^2$ maneiras de modificar cada um: $\binom{n}{2}(\sigma-1)^2$ resultados.

  4. três substituições
    existem$\binom{n}{3}$ trios diferentes e $(\sigma-1)^3$ maneiras de modificar cada um: $\binom{n}{3}(\sigma-1)^3$.

  5. uma exclusão, uma inserção, nenhuma substituição
    Para este caso, podemos generalizar esta solução para$\sigma=2$ para qualquer $\sigma$, usando a mesma lógica para evitar a contagem dupla das instâncias em que duas substituições produziriam o mesmo resultado como uma exclusão e uma inserção.

Vamos contar os casos em que a inserção está à esquerda da exclusão e depois multiplicar por 2. O efeito combinado da inserção e da exclusão é deslocar todos os 𝑘 bits entre eles para a direita enquanto substitui o primeiro e remove o último . Este resultado também pode ser obtido por no máximo 𝑘 substituições, então precisamos de 𝑘> 2. Inserir 𝑥 dentro de uma série de 𝑥s tem o mesmo efeito que inserir no final da execução. Assim, podemos contar todas as inserções com efeitos diferentes uma vez, inserindo sempre o bit complementar ao que está à direita da inserção. Da mesma forma, uma exclusão dentro de uma execução tem o mesmo efeito que uma exclusão no início da execução, portanto, devemos apenas contar as exclusões que seguem uma mudança entre 0 e 1. Isso nos dá uma contagem inicial de:

$2\cdot\frac12\sum_{k=3}^n(n+1-k)=\sum_{k=1}^{n-2}k=\frac{(n-1)(n-2)}2\;$

Como a lógica complicada para evitar a contagem dupla é transportada diretamente, a única modificação necessária é substituir uma variável $\sigma$ para o fixo $\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}\;$

A contagem excessiva de resultados que já foram contabilizados como duas substituições pode ser calculada da seguinte forma quando $\sigma=2$:

Se não houver mais mudanças nos 𝑘 bits deslocados além do anterior à exclusão, então apenas os bits próximos à inserção e exclusão mudam, e podemos conseguir isso com 2 substituições, então temos que subtrair

$\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)}\;$

Novamente, nossa única modificação é substituir $\sigma$ para 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)}\;$

Além disso, se todo o intervalo de bits deslocados consiste em zeros e uns alternados, a troca da inserção e da exclusão produz o mesmo efeito, portanto, neste caso, contamos duas vezes e precisamos subtrair

$\sum_{k=3}^n\left(\frac12\right)^{k-1}(n+1-k)\;$

Trocando em $\sigma$ um tempo final produz:

$\sum_{k=3}^n\left(\frac1{\sigma}\right)^{k-1}(n+1-k)\;$

Essas duas contagens excessivas (que, infelizmente, não podem ser combinadas de forma tão clara como quando os símbolos são binários) são então subtraídas da contagem inicial de operações de exclusão / inserção para produzir os resultados gerais produzidos por este caso, mas não pelo caso 3 acima:

$\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)\;$

  1. uma exclusão, uma inserção, uma substituição
    Esse mesmo cálculo é transportado para o caso final. Aqui, no entanto, cada combinação de uma exclusão e uma inserção - da mesma forma descontada para evitar a contagem dupla das substituições triplas já contadas no caso 4 acima - é acompanhada por uma terceira edição: uma substituição envolvendo um dos$n-1$símbolos originais restantes após a exclusão. Já que cada um desses$(n-1)$ símbolos admitem $(\sigma-1)$ novas substituições, a contagem total para o sexto e último caso torna-se:

$\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);$

A soma dos resultados (não contados anteriormente) produzidos por cada um desses seis casos deve produzir a contagem esperada quando o comprimento da corda permanecer inalterado. É feio (talvez desnecessariamente), mas espero que esteja correto.