Distanza di editing

[stev809]

Ciao a tutti ho aperto un nuovo tread per chiedere se c'è la possibilità che da questo codice

	public static int distanzaEditing (CharSequence lhs, CharSequence rhs) {                          
		    int len0 = lhs.length() + 1;                                                     
		    int len1 = rhs.length() + 1;                                                     
		    int cost_replace =0;
		    int cost_insert =0;
            int cost_delete =0;
		    // the array of distances                                                       
		    int[] cost = new int[len0];                                                     
		    int[] newcost = new int[len0];                                                  
		                                                                                    
		    // initial cost of skipping prefix in String s0                                 
		    for (int i = 0; i < len0; i++) cost[i] = i;                                     
		                                                                                    
		    // dynamically computing the array of distances                                  
		                                                                                    
		    // transformation cost for each letter in s1                                    
		    for (int j = 1; j < len1; j++) {                                                
		        // initial cost of skipping prefix in String s1                             
		        newcost[0] = j;                                                             
		                                                                                    
		        // transformation cost for each letter in s0                                
		        for(int i = 1; i < len0; i++) {                                             
		            // matching current letters in both strings                             
		            int match = (lhs.charAt(i - 1) == rhs.charAt(j - 1)) ? 0 : 1;             
		                                                                                    
		            // computing cost for each transformation                               
		             cost_replace = cost[i - 1] + match;                                 
		             cost_insert  = cost[i] + 1;                                         
		             cost_delete  = newcost[i - 1] + 1;                                  
		                                                                                    
		            // keep minimum cost                                                    
		            newcost[i] = Math.min(Math.min(cost_insert, cost_delete), cost_replace);
		        }                                                                           
		                                                                                    
		        // swap cost/newcost arrays                                                 
		        int[] swap = cost; 
		        cost = newcost; 
		        newcost = swap;                          
		    }
		    
		                                                                                    
		    // the distance is the cost for transforming all letters in both strings        
		    return cost[len0 - 1] ;                                                          
		}

io possa estrapolare gli indici e le lettere per stampare quali operazioni di modifica siano state fatte e in che parte della stringa

Grazie a tutti

[tomminno]

Operazioni di modifica su quale stringa?
In quel codice io non vedo nessuna operazione di modifica di stringhe!

[stev809]

Si perchè quello è il codice per calcolare la distanza di editing ....
A me serve dopo aver trovato tale distanza stampare quali procedimenti sono stati eseguti per cambiare la prima stringa nella seconda,
ad esempio :
"carota" e "cartone" hanno distanza di editing 3 , eseguendo un operazione di scambio tra 'o' e 't' ,un operazione di sotituzione di 'n' con 'a' e una operazione di aggiunta della lettera 'e'
Quello che devo fare io non è implementare queste operazioni ma stampare che sono state eseguite

Spero di essermi spiegato meglio ora

[tomminno]

Originariamente inviato da stev809

Si perchè quello è il codice per calcolare la distanza di editing ....
A me serve dopo aver trovato tale distanza stampare quali procedimenti sono stati eseguti per cambiare la prima stringa nella seconda,
ad esempio :
"carota" e "cartone" hanno distanza di editing 3 , eseguendo un operazione di scambio tra 'o' e 't' ,un operazione di sotituzione di 'n' con 'a' e una operazione di aggiunta della lettera 'e'
Quello che devo fare io non è implementare queste operazioni ma stampare che sono state eseguite

Spero di essermi spiegato meglio ora

Da quello che vedo la metrica riconosce lo swap solo di caratteri immediatamente adiacenti, quindi per sostituzione, aggiunta o cancellazione ti basta confrontare qual è il minimo valore di costo quando i==j, invece dovresti avere uno swap di caratteri quando le lettere sono uguali ma cost_replace non è 0.

[stev809]

Non mi sono spiegato ancora.
L'algoritmo in se funziona benissimo mi stampa il numero di operazioni che sono state effettuate.
Quello di cui ho bisogno invece è stampare QUALI OPERAZIONI sono state effettuate comprese di indice e carattere(se viene modificato o aggiunto), cioè
se c'è stata una sostituzine nella lettara in posizione 3 , la stampa deve essere
"sost(3,c) con 'c' il carattere che viene immesso .
Io pensavo di usare questi metodi :

	public String ins(char c, int index){
		for (int i = 0 ,j =0; i < parola.length();i++ ,j++){
			if(index <parola.length()){
				if(index != i){
			arrayParola[j]= parola.charAt(i);
				}else if(index == i){
				arrayParola[i]= c ;
				j++;
			}
		  }
		}
		String nuovaParola = new String(new StringBuilder().append(arrayParola));
		return nuovaParola;
	}
	
	/** Metodo per la cancellazione di un carattere di una stringa in una precisa posizione.
	 * Il metodo prende in input un intero index e restituisce la stringa modificata*/
	
	public String can(int index ){
		int j =0;
		char[] arrayParola1 = new char[parola.length()-1];
		for(int i =0;i< arrayParola.length;i++){
			if(index != i){
				arrayParola1[j] = arrayParola[i]; 
			j++;
			}
		}
		String nuovaParola = new String(new StringBuilder().append(arrayParola1));
		return nuovaParola;
	}
	
	public String sos(char c, int index){	
		arrayParola[index] =c ;
		String nuovaParola = new String(new StringBuilder().append(arrayParola));
		return nuovaParola;
	}

attraverso questi scrivo dei metodi booleani che mi verificano se la stringa è stata modificata con uno di questi metodi ed estraggo il carattere che è stato modificato .... ma per farlo devo riuscire a tirar fuori gli indici dal metodo sopra.....cioè la posizione della lettera in cui è stato verificato l edit .
Forse ci sarà un modo più semplice ma al momento non mi viene in mente niente

Spero di essermi spiegato meglio ora perchè sono in alto mare

[tomminno]

Scusa ma perchè allora chiedere:

c'è la possibilità che da questo codice io possa estrapolare gli indici e le lettere per stampare quali operazioni di modifica siano state fatte e in che parte della stringa

da quel codice, ovvero da distanzaEditing, si può fare e ti ho anche indicato come.

Se poi cambi le carte in tavola non so che dirti. Il tuo problema adesso è diventato come faccio a trovare in maniera generica le modifiche da apportare ad una stringa per trasformarla in un'altra, che è una domanda a cui si può dare risposta senza sapere niente di distanzaEditing. Chiarisciti prima le idee su quello che devi fare, perchè così è impossibile aiutarti.

[stev809]

Scusa ma non so spiegarmi bene purtroppo.
Hai detto che mi hai spiegato , ma non ho capito come dovrei fare, quello che ho postato ora è solo un idea,ma non mi sembra molto efficiente come soluzione anche se dei confronti dovrò farli lo stesso
Forse dovrei scrivere degli algoritmi simili al primo dove al posto della distanza di editing mi dice se c'è stato uno scambio ,una sostituzione o un aggiunta o una cancellazione.

Dici che si puo fare? Ed è piu efficente ?

[Mursey]

Originariamente inviato da stev809

Forse dovrei scrivere degli algoritmi simili al primo dove al posto della distanza di editing mi dice se c'è stato uno scambio ,una sostituzione o un aggiunta o una cancellazione.

Dici che si puo fare? Ed è piu efficente ?

Io avevo capito che più che algoritmi bastavano delle semplici tracciate di log...

[tomminno]

Originariamente inviato da stev809

Scusa ma non so spiegarmi bene purtroppo.
Hai detto che mi hai spiegato , ma non ho capito come dovrei fare, quello che ho postato ora è solo un idea,ma non mi sembra molto efficiente come soluzione anche se dei confronti dovrò farli lo stesso
Forse dovrei scrivere degli algoritmi simili al primo dove al posto della distanza di editing mi dice se c'è stato uno scambio ,una sostituzione o un aggiunta o una cancellazione.

Dici che si puo fare? Ed è piu efficente ?

Cosa non ti è chiaro di questa frase:

per sostituzione, aggiunta o cancellazione ti basta confrontare qual è il minimo valore di costo quando i==j, invece dovresti avere uno swap di caratteri quando le lettere sono uguali ma cost_replace non è 0.

?

Ovviamente tutto riferito al codice di distanzaEditing.

Se vuoi usare queste informazioni al di fuori di distanzaEditing devi cambiare il tipo di ritorno e cambiarlo da intero ad una classe che contenga non solo la distanza ma anche tutte le informazioni sulle modifiche necessarie a trasformare lhs in rhs.

[stev809]

Sinceramente non mi è chiara questa parte:

dovresti avere uno swap di caratteri quando le lettere sono uguali ma cost_replace non è 0.

cioè dovrei aggiungere uno swap ? è questo che non capisco e poi sul fatto di implementare una classe che esegue queste operazioni poi io come la uso all interno dell algoritmo ?

[tomminno]

Originariamente inviato da stev809

Sinceramente non mi è chiara questa parte:

Scusa ma te il codice del metodo distanzaEditing l'hai studiato?
Hai provato a vedere come traccia le informazioni che ti servono?
Non è difficile, basta prendere un compilatore (anche online) aggiungere un po' di print o armarsi di debug e vedere passo passo cosa fa nelle varie casistiche.

Quella frase vuole dire esattamente quello che c'è scritto, ovvero che distanzaEditing identifica lo swap di caratteri quando cost_replace != 0 e i caratteri delle 2 stringhe a parità di indice sono uguali.

cioè dovrei aggiungere uno swap ? è questo che non capisco e poi sul fatto di implementare una classe che esegue queste operazioni poi io come la uso all interno dell algoritmo ?

Come aggiungere uno swap???
Se devi tracciare che c'è uno swap ti serve l'informazione che c'è uno swap tra caratteri!

All'interno di quale algoritmo?
Non è che qui siamo indovini e sappiamo tutto! Sei partito con una domanda su un metodo ben preciso e continui a divagare con domande di cui non abbiamo il contesto...

[stev809]

Cerco di essere più preciso ...
Partiamo da zero il testo del problema è questo:
stampare quali operazioni sono state effettuate per modificare la prima stringa nella seconda.
esempio :
tra "carota" e "cartone " la distanza di editing è 3 e le operazioni che la determinano sono;
scambio(4) dove 4 è la posizione della lettera 'o' che viene scambiata con la lettera successiva 't'.
sostituzine(6, n) 6 è la posizione in cui viene sostituita 'a' con 'n'
aggiunta(7,e) aggiunta del carattere 'e' in posizione 7

non implementare i metodi per eseguire queste operazioni ma stampare la loro avvenuta esecuzione

[tomminno]

Originariamente inviato da stev809

Cerco di essere più preciso ...
Partiamo da zero il testo del problema è questo:
stampare quali operazioni sono state effettuate per modificare la prima stringa nella seconda.
esempio :
tra "carota" e "cartone " la distanza di editing è 3 e le operazioni che la determinano sono;
scambio(4) dove 4 è la posizione della lettera 'o' che viene scambiata con la lettera successiva 't'.
sostituzine(6, n) 6 è la posizione in cui viene sostituita 'a' con 'n'
aggiunta(7,e) aggiunta del carattere 'e' in posizione 7

non implementare i metodi per eseguire queste operazioni ma stampare la loro avvenuta esecuzione

Quindi vedi che devi identificare se c'è uno swap di caratteri?
Come fai ad indentificare che c'è uno swap di caratteri a partire da distanzaEditing? Come ti ho detto io: quando i caratteri a parità di indice sono uguali ma cost_replace non è 0.
Le altre informazioni che ti servono le recuperi in base a qual è il minimo tra cost_replace, cost_insert e cost_delete.

[stev809]

cmq ancora non ho capito come devo fare ...... letto e riletto riflettuto fatto prove su prove con la stampa ma nada
Potresti essere piu chiaro ?

[wingman87]

L'algoritmo del primo post calcola la distanza di Levenshtein che non tiene conto dello swap tra lettere. Tiene conto dell'inserimento, cancellazione e sostituzione di caratteri (la sostituzione non è uno swap tra caratteri vicini, è la sostituzione di un carattere con un altro).

Detto questo, può esserci più di un modo ottimo (costo minimo) per passare da una parola all'altra. Uno di questi dovrebbe essere ripercorrere la matrice risultante dall'algoritmo (l'algoritmo che stai usando tu è un'ottimizzazione che salva solo le ultime due righe della matrice, a te servirebbe tutta la matrice) al contrario, partendo dall'angolo "in basso a destra" e seguendo la discesa dei valori fino allo 0.

Vedi la spiegazione dell'algoritmo e le matrici di esempio qui per comprendere meglio ciò che ho tentato di spiegare brevemente:
https://en.wikipedia.org/wiki/Levenshtein_distance

Ad ogni modo non risolveresti il problema dello swap. Forse esiste un altro algoritmo che ne tiene conto ma non lo conosco.

[stev809]

Ho letto e riletto la spiegazione dell algoritmo ma non trovo sbocchi per quello che devo fare io.
Ho cercato anche su google ma niente...Inizio a pensare che una cosa del genere non si possa fare
Qualche altro suggerimento da qualcuno?

[wingman87]

Guarda come è evidenziata la matrice in questo link:

http://www.levenshtein.net/

La scia evidenziata non è altro che i possibili percorsi ottimali dall'angolo in basso a destra allo zero in alto a sinistra.
Subito sotto alla matrice ci sono anche le due possibili operazioni effettuate sulla prima stringa per passare alla seconda.

Tutto ciò però è valido per la distanza di Levenshtein (l'algoritmo del tuo primo post) che non tiene conto degli swap.

Se cerchi su google "Levenshtein distance with swap" (come ho appena fatto anch'io), troverai la distanza di Damerau–Levenshtein.
In questo caso però non puoi semplicemente ripercorrere la matrice al contrario seguendo la discesa fino allo zero perché non avresti modo di identificare uno swap. La soluzione sarebbe, oltre a costruirti la matrice numerica, costruire un'altra matrice con l'operazione effettuata ad ogni passaggio.

[stev809]

Allora dopo varie peripezie son giunto a questo punto

package soluzione;

import java.util.ArrayList;
import java.util.Arrays;

public class DistanzaDiEditing {
	
	
	private static int[][] matriceDiAdiacenza ;
	
	
	public static String distanza(String str1,String str2){
	
		String operazioni=" op: ";
		int lunghezza1 = str1.length();
		int lunghezza2 = str2.length();
		 matriceDiAdiacenza = new int[lunghezza1+1][lunghezza2+1];
		int match; 
		
		/*riempimento della riga 0 della matrice di adiacenza*/
		for(int i = 0 ; i <= lunghezza1 ; i++){
			matriceDiAdiacenza[i][0]=i;
		}
		/*riempimento della colonna 0 della matrice di adiacenza*/
		for(int j = 0 ; j <= lunghezza2 ;j++){
			matriceDiAdiacenza[0][j]=j;
		}
		/*Calcolo della distanza tra tutte le sottosringhe delineate nella matrice*/
	
		for(int i = 1 ; i <= lunghezza1 ;i++){
			for( int j=1 ;j <= lunghezza2 ; j++){
				//valuto se i caratteri son uguali 
				if(str1.charAt(i-1)==str2.charAt(j-1)){
					match = 0;
				}else{
					match = 1;
					}
					matriceDiAdiacenza[i][j]=Math.min(matriceDiAdiacenza[i-1][j]+1// costo cancellazione
							,Math.min(matriceDiAdiacenza[i][j-1]+1,//costo inserzione
									matriceDiAdiacenza[i-1][j-1]+match));// costo sostituzione
				if(i>1 && j>1 && str1.charAt(i-1)==str2.charAt(j-2)&&str1.charAt(i-2)==str2.charAt(j-1)){
					matriceDiAdiacenza[i][j]= Math.min(matriceDiAdiacenza[i][j],matriceDiAdiacenza[i-2][j-2]+match);//costo scambio
				}
				 
				// System.out.print(matriceDiAdiacenza[i-1][j-1]+"\t");
			}
			
			
		}
		for(int i = 0 ; i < matriceDiAdiacenza.length ;i++){
			for(int j=0 ;j <matriceDiAdiacenza[i].length ; j++){
				 System.out.print(matriceDiAdiacenza[i][j]+"\t");
			}
			// System.out.print(matriceDiAdiacenza[i][0]+"\n");
			 System.out.print("\n");
			}
	/	   int k = 0;
		   int h = 0;
		 for( k=1,h=1 ; k < matriceDiAdiacenza.length ;k++,h++){
				//if(k>1 && h>1 && str1.charAt(k-1)==str2.charAt(h-2)&&str1.charAt(k-2)==str2.charAt(h-1))
		
			 if(matriceDiAdiacenza[k][h]== (matriceDiAdiacenza[k][h-1])){
	  			 operazioni += "canc("+ k + ") ";
	  			 if(k < matriceDiAdiacenza.length-1)
	    	     k++;
	    	   }
	  		  
	  		   
		  }  
	  		   
		
		return matriceDiAdiacenza[lunghezza1][lunghezza2] +"\n" +operazioni;
		
	}
	
}

ma ho dei problemi con la stampe delle operazioni

	   int k = 0;
		   int h = 0;
		 for( k=1,h=1 ; k < matriceDiAdiacenza.length ;k++,h++){
				//if(k>1 && h>1 && str1.charAt(k-1)==str2.charAt(h-2)&&str1.charAt(k-2)==str2.charAt(h-1))
		
			 if(matriceDiAdiacenza[k][h]== (matriceDiAdiacenza[k][h-1])){
	  			 operazioni += "canc("+ k + ") ";
	  			 if(k < matriceDiAdiacenza.length-1)
	    	     k++;
	    	   }
	  		  
	  		   
		  }

se per caso ci son più di 2 lettere in meno alla fine della seconda stringa mi lancia un eccezione e mi sa che non è il modo giusto per stampare le operazioni
come faccio a percorrere tutta la matrice senza cascare in eccezioni e trovando quali operazioni son state effettuate ?