Equipe Rust Brasil 11 min de leitura

Distancia de Levenshtein em Rust

Distancia de Levenshtein em Rust: distancia de edicao para busca fuzzy, correcao ortografica e analise de DNA com variante Damerau-Levenshtein.

strings distancia-de-edicao levenshtein programacao-dinamica

A Distancia de Levenshtein (ou distancia de edicao) mede o numero minimo de operacoes de edicao necessarias para transformar uma string em outra. As operacoes permitidas sao: insercao, remocao e substituicao de um unico caractere. Esse conceito, proposto por Vladimir Levenshtein em 1965, e a base de inumeras aplicacoes praticas: correcao ortografica, busca fuzzy (aproximada), alinhamento de sequencias de DNA, deteccao de plagio e sistemas de autocompletar.

Embora o problema possa ser resolvido recursivamente, a solucao eficiente usa programacao dinamica, preenchendo uma tabela que armazena as distancias entre todos os prefixos das duas strings. A variante Damerau-Levenshtein adiciona uma quarta operacao – transposicao de caracteres adjacentes – que modela melhor os erros de digitacao humanos.

Como Funciona

A Tabela de Programacao Dinamica

Para calcular a distancia entre “gato” e “pato”, construimos uma tabela onde dp[i][j] e a distancia entre os primeiros i caracteres da string de origem e os primeiros j caracteres da string de destino:

      ""  p  a  t  o
  ""   0  1  2  3  4
  g    1  1  2  3  4
  a    2  2  1  2  3
  t    3  3  2  1  2
  o    4  4  3  2  1

Resposta: dp[4][4] = 1 (apenas trocar 'g' por 'p')

Regras de Preenchimento

Para cada celula dp[i][j]:

Se s1[i-1] == s2[j-1]:
  dp[i][j] = dp[i-1][j-1]        (caracteres iguais, sem custo)

Senao:
  dp[i][j] = 1 + min(
    dp[i-1][j],     // remocao    (remove s1[i-1])
    dp[i][j-1],     // insercao   (insere s2[j-1])
    dp[i-1][j-1]    // substituicao (troca s1[i-1] por s2[j-1])
  )

Trace Detalhado: “kitten” -> “sitting”

         ""  s  i  t  t  i  n  g
  ""      0  1  2  3  4  5  6  7
  k       1  1  2  3  4  5  6  7
  i       2  2  1  2  3  4  5  6
  t       3  3  2  1  2  3  4  5
  t       4  4  3  2  1  2  3  4
  e       5  5  4  3  2  2  3  4
  n       6  6  5  4  3  3  2  3

Distancia = dp[6][7] = 3

Operacoes:
  1. Substituir 'k' por 's': "kitten" -> "sitten"
  2. Substituir 'e' por 'i': "sitten" -> "sittin"
  3. Inserir 'g' no final:   "sittin" -> "sitting"

Caminho na tabela (traceback):
  dp[6][7]=3 <- dp[5][6]=3 (insercao de 'g')
  dp[5][6]=3 <- dp[4][5]=2 (substituicao 'e'->'i')
  dp[4][5]=2 <- dp[3][4]=1 (diagonal, 't'=='t')
  dp[3][4]=1 <- dp[2][3]=2? Nao, dp[3][4]=1 <- dp[2][3]=2 nao funciona.
  Melhor: dp[3][4]=1 <- dp[2][3]=2... (substituicao? nao, t==t)
  dp[3][3]=1 <- dp[2][2]=1 (diagonal, 't'=='t')
  dp[2][2]=1 <- dp[1][1]=1 (diagonal, 'i'=='i')
  dp[1][1]=1 <- dp[0][0]=0 (substituicao 'k'->'s')

Complexidade

VarianteTempoEspaco
Tabela completaO(n*m)O(n*m)
Espaco otimizadoO(n*m)O(min(n,m))
Damerau-LevenshteinO(n*m)O(n*m)
Com limiar (threshold)O(n*k)O(k)

Onde n e m sao os comprimentos das strings e k e o limiar maximo de distancia.

Implementacao em Rust

/// Calcula a distancia de Levenshtein entre duas strings.
/// Usa espaco otimizado O(min(n,m)) mantendo apenas duas linhas da tabela.
fn levenshtein(s1: &str, s2: &str) -> usize {
    let s1: Vec<char> = s1.chars().collect();
    let s2: Vec<char> = s2.chars().collect();
    let n = s1.len();
    let m = s2.len();

    // Otimizacao: usa a string menor como coluna
    if n < m {
        return levenshtein_chars(&s2, &s1);
    }
    levenshtein_chars(&s1, &s2)
}

fn levenshtein_chars(s1: &[char], s2: &[char]) -> usize {
    let m = s2.len();

    // Apenas duas linhas da tabela DP
    let mut anterior: Vec<usize> = (0..=m).collect();
    let mut atual = vec![0usize; m + 1];

    for i in 1..=s1.len() {
        atual[0] = i;

        for j in 1..=m {
            let custo_substituicao = if s1[i - 1] == s2[j - 1] { 0 } else { 1 };

            atual[j] = (anterior[j] + 1) // remocao
                .min(atual[j - 1] + 1) // insercao
                .min(anterior[j - 1] + custo_substituicao); // substituicao
        }

        std::mem::swap(&mut anterior, &mut atual);
    }

    anterior[m]
}

/// Calcula a distancia e tambem recupera as operacoes de edicao.
fn levenshtein_com_operacoes(s1: &str, s2: &str) -> (usize, Vec<String>) {
    let s1: Vec<char> = s1.chars().collect();
    let s2: Vec<char> = s2.chars().collect();
    let n = s1.len();
    let m = s2.len();

    // Tabela completa para traceback
    let mut dp = vec![vec![0usize; m + 1]; n + 1];

    // Inicializacao
    for i in 0..=n {
        dp[i][0] = i;
    }
    for j in 0..=m {
        dp[0][j] = j;
    }

    // Preenchimento
    for i in 1..=n {
        for j in 1..=m {
            let custo = if s1[i - 1] == s2[j - 1] { 0 } else { 1 };
            dp[i][j] = (dp[i - 1][j] + 1)
                .min(dp[i][j - 1] + 1)
                .min(dp[i - 1][j - 1] + custo);
        }
    }

    // Traceback: recupera as operacoes
    let mut operacoes = Vec::new();
    let mut i = n;
    let mut j = m;

    while i > 0 || j > 0 {
        if i > 0 && j > 0 && s1[i - 1] == s2[j - 1] {
            // Caracteres iguais, sem operacao
            i -= 1;
            j -= 1;
        } else if i > 0 && j > 0 && dp[i][j] == dp[i - 1][j - 1] + 1 {
            operacoes.push(format!(
                "Substituir '{}' por '{}' na posicao {}",
                s1[i - 1],
                s2[j - 1],
                i - 1
            ));
            i -= 1;
            j -= 1;
        } else if j > 0 && dp[i][j] == dp[i][j - 1] + 1 {
            operacoes.push(format!(
                "Inserir '{}' na posicao {}",
                s2[j - 1],
                i
            ));
            j -= 1;
        } else if i > 0 && dp[i][j] == dp[i - 1][j] + 1 {
            operacoes.push(format!(
                "Remover '{}' da posicao {}",
                s1[i - 1],
                i - 1
            ));
            i -= 1;
        } else {
            break;
        }
    }

    operacoes.reverse();
    (dp[n][m], operacoes)
}

fn main() {
    // Exemplo basico
    let s1 = "kitten";
    let s2 = "sitting";

    let distancia = levenshtein(s1, s2);
    println!("Distancia entre \"{}\" e \"{}\": {}", s1, s2, distancia);
    println!();

    // Com operacoes detalhadas
    let (dist, ops) = levenshtein_com_operacoes(s1, s2);
    println!("Operacoes ({} edicoes):", dist);
    for op in &ops {
        println!("  {}", op);
    }
    println!();

    // Mais exemplos
    let pares = vec![
        ("gato", "pato"),
        ("rust", "trust"),
        ("algoritmo", "logaritmo"),
        ("", "abc"),
        ("abc", "abc"),
    ];

    println!("Tabela de distancias:");
    for (a, b) in &pares {
        println!("  \"{}\" -> \"{}\" = {}", a, b, levenshtein(a, b));
    }
}

Exemplo de Execucao

Distancia entre "kitten" e "sitting": 3

Operacoes (3 edicoes):
  Substituir 'k' por 's' na posicao 0
  Substituir 'e' por 'i' na posicao 4
  Inserir 'g' na posicao 6

Tabela de distancias:
  "gato" -> "pato" = 1
  "rust" -> "trust" = 1
  "algoritmo" -> "logaritmo" = 3
  "" -> "abc" = 3
  "abc" -> "abc" = 0

Variacoes e Otimizacoes

1. Damerau-Levenshtein (com Transposicoes)

A variante Damerau-Levenshtein adiciona transposicao de caracteres adjacentes, modelando melhor erros de digitacao:

/// Distancia de Damerau-Levenshtein: permite insercao, remocao,
/// substituicao e transposicao de caracteres adjacentes.
fn damerau_levenshtein(s1: &str, s2: &str) -> usize {
    let s1: Vec<char> = s1.chars().collect();
    let s2: Vec<char> = s2.chars().collect();
    let n = s1.len();
    let m = s2.len();

    if n == 0 {
        return m;
    }
    if m == 0 {
        return n;
    }

    let mut dp = vec![vec![0usize; m + 1]; n + 1];

    for i in 0..=n {
        dp[i][0] = i;
    }
    for j in 0..=m {
        dp[0][j] = j;
    }

    for i in 1..=n {
        for j in 1..=m {
            let custo = if s1[i - 1] == s2[j - 1] { 0 } else { 1 };

            dp[i][j] = (dp[i - 1][j] + 1) // remocao
                .min(dp[i][j - 1] + 1) // insercao
                .min(dp[i - 1][j - 1] + custo); // substituicao

            // Transposicao de caracteres adjacentes
            if i > 1
                && j > 1
                && s1[i - 1] == s2[j - 2]
                && s1[i - 2] == s2[j - 1]
            {
                dp[i][j] = dp[i][j].min(dp[i - 2][j - 2] + 1);
            }
        }
    }

    dp[n][m]
}

fn main() {
    // Transposicao: "ab" -> "ba" = 1 (em vez de 2 no Levenshtein puro)
    println!(
        "Levenshtein(\"ab\", \"ba\") = {}",
        levenshtein("ab", "ba")
    ); // 2
    println!(
        "Damerau-Levenshtein(\"ab\", \"ba\") = {}",
        damerau_levenshtein("ab", "ba")
    ); // 1

    // Erro de digitacao tipico
    println!(
        "Damerau(\"teh\", \"the\") = {}",
        damerau_levenshtein("teh", "the")
    ); // 1
}

2. Distancia com Limiar (Threshold)

Quando voce so precisa saber se a distancia e menor que um limite, pode cortar cedo:

/// Calcula a distancia de Levenshtein, mas retorna None se exceder o limiar.
/// Mais eficiente quando o limiar e pequeno.
fn levenshtein_com_limiar(s1: &str, s2: &str, limiar: usize) -> Option<usize> {
    let s1: Vec<char> = s1.chars().collect();
    let s2: Vec<char> = s2.chars().collect();
    let n = s1.len();
    let m = s2.len();

    // Se a diferenca de comprimento ja excede o limiar
    if n.abs_diff(m) > limiar {
        return None;
    }

    let mut anterior: Vec<usize> = (0..=m).collect();
    let mut atual = vec![0usize; m + 1];

    for i in 1..=n {
        atual[0] = i;
        let mut min_na_linha = i;

        for j in 1..=m {
            let custo = if s1[i - 1] == s2[j - 1] { 0 } else { 1 };
            atual[j] = (anterior[j] + 1)
                .min(atual[j - 1] + 1)
                .min(anterior[j - 1] + custo);

            min_na_linha = min_na_linha.min(atual[j]);
        }

        // Se o minimo na linha inteira excede o limiar, impossivel obter resultado
        if min_na_linha > limiar {
            return None;
        }

        std::mem::swap(&mut anterior, &mut atual);
    }

    if anterior[m] <= limiar {
        Some(anterior[m])
    } else {
        None
    }
}

3. Operacoes com Pesos Customizados

/// Distancia de edicao com pesos customizados para cada operacao.
struct PesosEdicao {
    insercao: usize,
    remocao: usize,
    substituicao: usize,
}

fn levenshtein_ponderado(s1: &str, s2: &str, pesos: &PesosEdicao) -> usize {
    let s1: Vec<char> = s1.chars().collect();
    let s2: Vec<char> = s2.chars().collect();
    let n = s1.len();
    let m = s2.len();

    let mut dp = vec![vec![0usize; m + 1]; n + 1];

    for i in 1..=n {
        dp[i][0] = dp[i - 1][0] + pesos.remocao;
    }
    for j in 1..=m {
        dp[0][j] = dp[0][j - 1] + pesos.insercao;
    }

    for i in 1..=n {
        for j in 1..=m {
            if s1[i - 1] == s2[j - 1] {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = (dp[i - 1][j] + pesos.remocao)
                    .min(dp[i][j - 1] + pesos.insercao)
                    .min(dp[i - 1][j - 1] + pesos.substituicao);
            }
        }
    }

    dp[n][m]
}

Aplicacoes Praticas

Corretor Ortografico Simples

/// Corretor ortografico que sugere as palavras mais proximas do dicionario.
fn sugerir_correcoes(palavra: &str, dicionario: &[&str], max_distancia: usize) -> Vec<(String, usize)> {
    let mut sugestoes: Vec<(String, usize)> = Vec::new();

    for &palavra_dict in dicionario {
        if let Some(dist) = levenshtein_com_limiar(palavra, palavra_dict, max_distancia) {
            sugestoes.push((palavra_dict.to_string(), dist));
        }
    }

    // Ordena por distancia (menor primeiro)
    sugestoes.sort_by_key(|s| s.1);
    sugestoes
}

fn main() {
    let dicionario = vec![
        "rust", "ruby", "python", "java", "javascript",
        "rust", "rosto", "rusto", "justo", "custo",
        "lista", "pista", "vista", "mista", "fusta",
    ];

    let palavra = "rustp";
    let sugestoes = sugerir_correcoes(palavra, &dicionario, 2);

    println!("Correcoes para \"{}\":", palavra);
    for (sugestao, dist) in &sugestoes {
        println!("  \"{}\" (distancia: {})", sugestao, dist);
    }
}

Busca Fuzzy em Lista de Nomes

/// Busca fuzzy: encontra os itens mais similares a consulta.
fn busca_fuzzy<'a>(consulta: &str, itens: &[&'a str], max_resultados: usize) -> Vec<(&'a str, usize)> {
    let mut resultados: Vec<(&str, usize)> = itens
        .iter()
        .map(|&item| {
            let dist = levenshtein(
                &consulta.to_lowercase(),
                &item.to_lowercase(),
            );
            (item, dist)
        })
        .collect();

    resultados.sort_by_key(|r| r.1);
    resultados.truncate(max_resultados);
    resultados
}

fn main() {
    let cidades = vec![
        "Sao Paulo", "Rio de Janeiro", "Belo Horizonte",
        "Salvador", "Brasilia", "Curitiba", "Porto Alegre",
        "Fortaleza", "Recife", "Manaus",
    ];

    let consulta = "Sao Polo";
    let resultados = busca_fuzzy(consulta, &cidades, 3);

    println!("Busca fuzzy por \"{}\":", consulta);
    for (cidade, dist) in &resultados {
        println!("  \"{}\" (distancia: {})", cidade, dist);
    }
}

Similaridade de Sequencias (DNA)

/// Calcula a similaridade entre duas sequencias como porcentagem.
fn similaridade(s1: &str, s2: &str) -> f64 {
    let dist = levenshtein(s1, s2);
    let max_len = s1.len().max(s2.len());

    if max_len == 0 {
        return 100.0;
    }

    (1.0 - dist as f64 / max_len as f64) * 100.0
}

fn main() {
    let seq1 = "ATCGATCG";
    let seq2 = "ATCAATCG";

    let dist = levenshtein(seq1, seq2);
    let sim = similaridade(seq1, seq2);

    println!("Sequencia 1: {}", seq1);
    println!("Sequencia 2: {}", seq2);
    println!("Distancia de edicao: {}", dist);
    println!("Similaridade: {:.1}%", sim);

    // Visualizacao do alinhamento
    println!();
    println!("Alinhamento:");
    println!("  {}", seq1);
    print!("  ");
    for (c1, c2) in seq1.chars().zip(seq2.chars()) {
        if c1 == c2 {
            print!("|");
        } else {
            print!("x");
        }
    }
    println!();
    println!("  {}", seq2);
}

Comparacao com Outros Algoritmos

MetricaOperacoesTempoUso Tipico
LevenshteinIns, Rem, SubO(n*m)Correcao ortografica
Damerau-LevenshteinIns, Rem, Sub, TransO(n*m)Erros de digitacao
HammingApenas substituicaoO(n)Strings mesmo tamanho
LCS (subseq. comum)Ins, Rem (sem sub)O(n*m)Diff de arquivos
Jaro-WinklerTransposicoesO(n*m)Nomes proprios
Needleman-WunschIns, Rem, Sub (ponderado)O(n*m)Alinhamento de DNA

A Distancia de Levenshtein e a metrica de edicao mais utilizada e serve como base para variantes mais especializadas. Para strings curtas (nomes, palavras), Jaro-Winkler pode ser mais adequado. Para alinhamento biologico, Needleman-Wunsch com matrizes de substituicao (BLOSUM, PAM) e preferido.

Exercicios Praticos

  1. Autocompletar fuzzy: Combine a Distancia de Levenshtein com uma Trie para implementar autocompletar que tolera erros de digitacao. Para cada no da Trie, calcule a distancia ate a consulta e pode os ramos que excedem o limiar.

  2. Diff de linhas: Implemente um diff simplificado (similar ao diff do Unix) que mostra insercoes e remocoes entre duas versoes de um arquivo. Use a LCS (Longest Common Subsequence) derivada da tabela de Levenshtein.

  3. Agrupamento por similaridade: Dado um conjunto de palavras, agrupe-as por similaridade (distancia <= k). Implemente usando uma matriz de distancias e um algoritmo de agrupamento simples.

  4. Teclado QWERTY ponderado: Modifique a funcao de substituicao para considerar a distancia entre teclas no teclado QWERTY. Teclas adjacentes (como ‘r’ e ’t’) devem ter custo de substituicao menor que teclas distantes (como ‘r’ e ‘p’).

Veja Tambem