View Full Version : Distanza di editing
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
28-08-2017, 16:14
Operazioni di modifica su quale stringa?
In quel codice io non vedo nessuna operazione di modifica di stringhe!
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
29-08-2017, 09:48
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.
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
29-08-2017, 10:34
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.
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 ?
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
29-08-2017, 15:04
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.
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
30-08-2017, 07:52
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??? :confused:
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... :rolleyes:
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
31-08-2017, 16:25
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.
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
02-10-2017, 17:08
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.
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
04-10-2017, 11:39
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.
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 ?
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.