--- title: "Edit Distance (Distância de Edição) em Zig — Implementação e Explicação" url: "https://ziglang.com.br/algoritmos/edit-distance-dist%C3%A2ncia-de-edi%C3%A7%C3%A3o-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/" markdown_url: "https://ziglang.com.br/algoritmos/edit-distance-dist%C3%A2ncia-de-edi%C3%A7%C3%A3o-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD" description: "Aprenda o algoritmo Edit Distance (Levenshtein) implementado em Zig. Programação dinâmica para distância de edição com código funcional." date: "2026-02-21" author: "Zig Brasil" --- # Edit Distance (Distância de Edição) em Zig — Implementação e Explicação Aprenda o algoritmo Edit Distance (Levenshtein) implementado em Zig. Programação dinâmica para distância de edição com código funcional. # Edit Distance (Distância de Edição) em Zig — Implementação e Explicação A **distância de edição** (ou distância de Levenshtein) mede o número mínimo de operações necessárias para transformar uma string em outra. As operações permitidas são: **inserção**, **remoção** e **substituição** de um caractere. ## Como Funciona Construímos uma tabela dp[i][j] que representa a distância de edição entre os primeiros i caracteres de X e os primeiros j caracteres de Y. ``` Se X[i-1] == Y[j-1]: dp[i][j] = dp[i-1][j-1] Senão: dp[i][j] = 1 + min( dp[i-1][j], // remoção dp[i][j-1], // inserção dp[i-1][j-1] // substituição ) ``` ### Visualização ``` X = "kitten" Y = "sitting" Tabela dp: "" 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 Distância = 3 (substituir k→s, substituir e→i, inserir g) Operações: kitten → sitten (substituir k por s) sitten → sittin (substituir e por i) sittin → sitting (inserir g no final) ``` ## Implementação em Zig ```zig const std = @import("std"); const Allocator = std.mem.Allocator; const Operacao = enum { nenhuma, inserir, remover, substituir, }; const PassoEdicao = struct { op: Operacao, pos: usize, char_de: ?u8, char_para: ?u8, }; /// Calcula a distância de edição entre duas strings. pub fn editDistance(allocator: Allocator, x: []const u8, y: []const u8) !u32 { const m = x.len; const n = y.len; // Otimização de espaço: usa apenas duas linhas var anterior = try allocator.alloc(u32, n + 1); defer allocator.free(anterior); var atual = try allocator.alloc(u32, n + 1); defer allocator.free(atual); for (0..n + 1) |j| { anterior[j] = @intCast(j); } for (1..m + 1) |i| { atual[0] = @intCast(i); for (1..n + 1) |j| { if (x[i - 1] == y[j - 1]) { atual[j] = anterior[j - 1]; } else { atual[j] = 1 + @min(@min(anterior[j], atual[j - 1]), anterior[j - 1]); } } const temp = anterior; anterior = atual; atual = temp; } return anterior[n]; } /// Versão com reconstrução das operações. pub fn editDistanceDetalhado( allocator: Allocator, x: []const u8, y: []const u8, ) !struct { distancia: u32, operacoes: []PassoEdicao } { const m = x.len; const n = y.len; // Tabela completa para rastreamento const dp = try allocator.alloc([]u32, m + 1); defer { for (dp) |row| allocator.free(row); allocator.free(dp); } for (0..m + 1) |i| { dp[i] = try allocator.alloc(u32, n + 1); dp[i][0] = @intCast(i); } for (0..n + 1) |j| { dp[0][j] = @intCast(j); } for (1..m + 1) |i| { for (1..n + 1) |j| { if (x[i - 1] == y[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = 1 + @min(@min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]); } } } // Reconstrói operações var ops = std.ArrayList(PassoEdicao).init(allocator); var i: usize = m; var j: usize = n; while (i > 0 or j > 0) { if (i > 0 and j > 0 and x[i - 1] == y[j - 1]) { i -= 1; j -= 1; } else if (i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + 1) { try ops.append(.{ .op = .substituir, .pos = i - 1, .char_de = x[i - 1], .char_para = y[j - 1] }); i -= 1; j -= 1; } else if (j > 0 and dp[i][j] == dp[i][j - 1] + 1) { try ops.append(.{ .op = .inserir, .pos = i, .char_de = null, .char_para = y[j - 1] }); j -= 1; } else { try ops.append(.{ .op = .remover, .pos = i - 1, .char_de = x[i - 1], .char_para = null }); i -= 1; } } return .{ .distancia = dp[m][n], .operacoes = try ops.toOwnedSlice(), }; } pub fn main() !void { const stdout = std.io.getStdOut().writer(); var gpa = std.heap.GeneralPurposeAllocator(.{}){}; defer _ = gpa.deinit(); const allocator = gpa.allocator(); const pares = [_][2][]const u8{ .{ "kitten", "sitting" }, .{ "algoritmo", "logaritmo" }, .{ "zig", "zag" }, .{ "", "abc" }, }; for (pares) |par| { const dist = try editDistance(allocator, par[0], par[1]); try stdout.print("\"{s}\" → \"{s}\" = {d} operações\n", .{ par[0], par[1], dist }); } // Exemplo detalhado try stdout.print("\nDetalhamento \"kitten\" → \"sitting\":\n", .{}); const detalhe = try editDistanceDetalhado(allocator, "kitten", "sitting"); defer allocator.free(detalhe.operacoes); for (detalhe.operacoes) |op| { switch (op.op) { .inserir => try stdout.print(" Inserir '{c}' na posição {d}\n", .{ op.char_para.?, op.pos }), .remover => try stdout.print(" Remover '{c}' da posição {d}\n", .{ op.char_de.?, op.pos }), .substituir => try stdout.print(" Substituir '{c}' por '{c}' na posição {d}\n", .{ op.char_de.?, op.char_para.?, op.pos }), .nenhuma => {}, } } } ``` ## Análise de Complexidade | Caso | Tempo | Espaço | |------|-------|--------| | **Com rastreamento** | O(m * n) | O(m * n) | | **Apenas distância** | O(m * n) | O(min(m, n)) | ## Aplicações - **Correção ortográfica**: sugerir palavras próximas ao que o usuário digitou - **Bioinformática**: alinhar sequências de DNA - **Detecção de duplicatas**: encontrar registros semelhantes em bancos de dados - **Busca fuzzy**: encontrar matches aproximados ## Recursos Relacionados - [Levenshtein Distance](/algoritmos/levenshtein-distance/) — Métrica completa de similaridade - [LCS — Subsequência Comum](/algoritmos/lcs-subsequencia-comum/) — Problema relacionado - [KMP Pattern Matching](/algoritmos/kmp-pattern-matching/) — Busca exata em strings - [Fibonacci (DP)](/algoritmos/fibonacci-dp/) — Introdução à programação dinâmica