Iniciar sesiónCerrar
Correo:
Contraseña:
Entrar
Recordar sesión en este navegador
Iniciar sesiónIniciar sesiónCrear cuentaCrear cuenta
LWP » Código Fuente » Dev - C++ » Código de Dev - C++ - Distancia de Levenshtein en C++

Código de Dev - C++ - Distancia de Levenshtein en C++

Volver
Agregar Código Fuente
<<>>
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.234 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 2020gráfica de visualizaciones de la versión: 1
2.235 visualizaciones desde el 10 de Octubre del 2020
estrellaestrellaestrellaestrellaestrella
estrellaestrellaestrellaestrella
estrellaestrellaestrella
estrellaestrella
estrella


Forma parte de Distancia de Levenshtein
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
 
int minimo(int a, int b){
    return a<b ? a:b;
}
 
int main()
{
    string h1;
    string h2;
    string continuar = "si";
    int tamH1 = 0, tamH2 = 0;
 
    cout << "DISTANCIA DE LEVENSHTEIN" << endl << endl;
 
    while(continuar == "Si" || continuar == "SI" || continuar == "si"){
        cout << "Digite la hilera 1: ";
        cin >> h1;
        cout << "Digite la hilera 2: ";
        cin >> h2;
 
        tamH1 = h1.length();
        tamH2 = h2.length();
 
        int matriz[tamH2][tamH1];
 
		//Se inicializa la primer fila de la matriz con la secuencia 0,1,2,...,x
        for(int i = 0;i < tamH1; i++){
            matriz[0][i] = i;
        }
 
		//Se inicializa la primer columna de la matriz con la secuencia 0,1,2,...,Y
        for(int j = 0;j < tamH2; j++){
            matriz[j][0] = j;
        }
 
		//Si h1(j) es igual a h2(i) el costo de la celda es 0.
		//Si h1(j) es diferente a h2(i) el costo de la celda es 1.
        for(int i = 1;i < tamH2; i++){
            for(int j = 1;j < tamH1; j++){
                if(h1.substr(j,1) == h2.substr(i,1)){
                    matriz[i][j] = 0;
                }
                else{
                    matriz[i][j] = 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 la celda (i,j). (substitución)
		 */
        int min=0;
        for(int i = 1;i < tamH2; i++){
            for(int j = 1;j < tamH1; j++){
                min = minimo(matriz[i-1][j] + 1, matriz[i][j-1] + 1);
                matriz[i][j] = minimo(matriz[i-1][j-1] + matriz[i][j], min);
            }
        }
 
        cout << endl;
        for(int i = 0;i < tamH2; i++){
            for(int j = 0;j < tamH1; j++){
                cout << matriz[i][j] << " ";
            }
            cout << endl;
        }
 
		cout << endl << "Hilera 1: " << h1 << "\nHilera 2: " << h2 << endl;
		cout << "Distancia de Levenshtein: " << matriz[tamH2-1][tamH1-1] << endl;
 
        cout << endl << "Desea calcular la distancia de Levenshtein de otras hileras? (Si/No): ";
        cin >> continuar;
    }
    return 0;
}



Comentarios sobre la versión: 1 (0)


No hay comentarios
 

Comentar la versión: 1

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad
Acepto las políticas de privacidad

http://lwp-l.com/s6530