Skip to content

levenshtein ​

Devuelve el número mínimo de inserciones, eliminaciones y sustituciones para transformar una cadena en otra. La distancia se mide sobre bytes UTF-8.

tyrus
import { levenshtein } from "tyrus:algorithm";

const distance: usize = levenshtein("kitten", "sitting");
print(distance); // 3

Resultado de estudio ​

tyrus
interface EditDistanceInfo {
    left: string;
    right: string;
    distance: usize;
    rowCount: usize;
    columnCount: usize;
    evaluatedCellCount: usize;
}
tyrus
import { EditDistanceInfo, levenshteinInfo } from "tyrus:algorithm";

const info: EditDistanceInfo = levenshteinInfo("kitten", "sitting");
print(info.left); // kitten
print(info.right); // sitting
print(info.distance); // 3
print(info.rowCount); // 7
print(info.columnCount); // 8
print(info.evaluatedCellCount); // 42

El resultado de estudio conserva la fila incremental utilizada por el cálculo e informa sus dimensiones y celdas evaluadas sin devolver una matriz cuadrática.

El algoritmo se ejecuta en O(nm) y usa espacio auxiliar O(m).