Estadísticas de la versión: 1 - Distancia de Levenshtein en C++ - Dev - C++

Imágen de perfil

Distancia de Levenshtein en C++gráfica de visualizaciones


Dev - C++

Publicado el 10 de Octubre del 2020 por Administrador (718 códigos)
2.213 visualizaciones desde el 10 de Octubre del 2020
Este algortimo también es conocido como distancia de edición. La similaridad entre dos cadenas de texto A y B se basa en el conjunto mínimo de operaciones de edición necesarias para transformar A en B, o viceversa. Hay tres operaciones de edición, las cuales son destrucción, inserción y substitución. Entre más cerca de cero es la distancia de Levenshtein más parecidas son las hileras.


El algoritmo es el siguiente:

- El tamaño de la hilera A es x, y el tamaño de la hilera B es y. Si x = 0, retornar y; si y = 0 retornar x.
- Construir una matriz con y + 1 filas y x + 1 columnas. Inicializar la primer fila de la matriz con la secuencia 0, 1, 2, ..., x; y la primer columna de la matriz con la secuencia 0, 1, 2, ..., y.
- Colocar cada carácter de la hilera A en su correspondiente celda i (i va de 1 a x).
- Colocar cada carácter de la hilera B en su correspondiente celda j (j va de 1 a y).
- Si A(i) es igual a B(j) el costo de la celda es 0.
- Si A(i) es diferente de B(j) el costo de la celda es 1.
- El valor de la celda d(i,j) es el mínimo de:
- Valor de la celda (i-1,j) + 1 (ELIMINACIÓN)
- Valor de la celda (i,j-1) + 1 (INSERCIÓN)
- Valor de la celda (i-1,j-1) + costo de celda (SUBSTITUCIÓN)
- La distancia es la celda d(x,y)

1

Publicado el 10 de Octubre del 2020
2.213 visualizaciones desde el 10 de Octubre del 2020

80 visualizaciones durante los últimos 90 días


18
0