Minimalen Hammingabstand berechnen

[Tina87]

Hallo ihr lieben,
hab mal wieder ein problem beim programmieren.
ich soll eine methode verfassen, die den minimalen hammingabstand von zwei unterschiedlichen langen wörtern (bzw. strings) berechnet.
um die aufgabe etwas näher zu erklären, habe ich mir schon mal überlegt wie sie funktionieren soll:
wenn man die zwei wörter "anatolien" und "toll" hat, dann soll die methode das kürzere wort immer so lange eine position weiter verschieben, bis der minimale abstand gefunden wurde, also so:
anatolien
toll abstand:4
toll abstand:4
toll abstand:3
toll abstand:1
toll abstand:4
toll abstand:4

leider weiß ich nicht so wirklich wie ich das programmieren soll. Vielleicht bringt es was, wenn man sog. substrings verwendet, aber komme da irgendwie nicht weiter.

Um überhaupt einen lösungsansatz zu bieten, habe ich mir eine methode überlegt, wie man gleich lange strings vergleichen kann.

public class HammingDistance {
    static int hamming_distance (String a, String b) {
        
        int countSubstitutions = 0;
        for (int i=0; i<a.length(); i++)
        {
            if(a.charAt(i) != b.charAt(i))
            countSubstitutions++;
        }
        return countSubstitutions;
    }
    
    public static void main (String[ ] args) {
        String a = "till";
        String b = "tall";
        System.out.println(hamming_distance(a,b));
    }
}

hoffe ihr könnt mir sagen, wie ich das jetzt auf unterschiedlich lange strings übertragen kann.
lg

 

[faetzminator]

Du machst etwa folgendes (ungetestet):

String longStr = // hier der längere String
String shortStr = // kürzere
int distance = Integer.MAX_VALUE;
for (int i = 0; i < longStr.length - shortStr.length; i++) {
    distance = Math.min(distance, hammingDistance(longStr.substring(i, i + shortStr.length), shortStr));
}
return distance;

 

[Tina87]

also hab deinen tip mal auf mein prorgamm umgewandelt, das sieht dann so aus:

class test {
    static int hammingDistance (String a, String b) {


int distance = Integer.MAX_VALUE;
for (int i = 0; i < a.length() - b.length(); i++) {
    distance = Math.min(distance, hammingDistance(a.substring(i, i + b.length()), b));
}
return distance;
}

public static void main (String [ ] args) {
String a = "anatolien";
String b = "toll";
System.out.println(hammingDistance(a,b));
}
}

aber das funktioniert dann nicht. er gibt ne wilde zahlenfolge aus.
mein zweites problem ist, dass ich das programm nicht mal verstehe. Ich weiß nicht was Integer.max_value sein soll, oder was der befehl math.min macht. kann mir schon vorstellen, dass er wenn die einzelnen stellen durchläuft nachher die kleinste ausgeben soll, aber so etwas hatten wir noch gar nicht. stehe noch in den anfängen von java.
aber vielleicht kann man das auch noch länger, aber dafür simpler ausdrücken.
also wenn er nen abstand gefunden, soll er den mit dem vorherigen vergleichen und falls er kleiner ist, ihn in den alten abstand reinschreiben oder so.

 

[Thief]

Mir war grad langweilig. Ist sicher nicht die beste Lösung, aber funktioniert

public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        int hamming = getHammingDistance("hallo", "hallolo");
        System.out.println(hamming);
    }

    static int getHammingDistance(String a, String b){
        String longerString;
        String shorterString;

        if(a.length() > b.length()){
            longerString = a;
            shorterString = b;
        }else{
            longerString = b;
            shorterString = a;
        }
        
        int dist = longerString.length() - shorterString.length()+1;

        int cnt = 0;
        int best = longerString.length();
        for(int i=0; i<dist; i++){
            for(int j=0; j<shorterString.length(); j++){
                if(longerString.charAt(i+j) != shorterString.charAt(j))
                    cnt ++;
            }
            if(cnt == 0) return dist-1; // besser geht nicht
            
            if(cnt < best)
                best = cnt;
            cnt = 0;
        }
        return best + dist-1;
    }
}

 

[faetzminator]

Eigentlich sollte meine Methode deine aufrufen (hammingDistance(...)):

public class Foo {

    public static void main(String[] args) {
        String a = "anatolien";
        String b = "toll";
        System.out.println(hammingDistance(a, b));

    }

    public static int hammingDistance(String a, String b) {
        String longStr = a.length() > b.length() ? a : b;
        String shortStr = a.length() > b.length() ? b : a;
        int distance = Integer.MAX_VALUE; // da distance sicher im 1. Schleifendurchgang gesetzt werden soll,
                                          // wird hier distance auf denn grösstmöglichen Wert gesetzt
        for (int i = 0; i < longStr.length() - shortStr.length(); i++) {
            int actDist = hammingDistanceSameLength(longStr.substring(i, i + shortStr.length()), shortStr);
            distance = Math.min(actDist, distance); // gibt die kleinere von beiden Zahlen zurück
        }
        return distance;
    }

    public static int hammingDistanceSameLength(String a, String b) {
        int countSubstitutions = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                countSubstitutions++;
            }
        }
        return countSubstitutions;
    }
}

 

[Sonecc]

void hamming(String a, String b, int pos) {
		if (pos == (a.length()-b.length()+1)) {
			return;
		}
		int n = 0;
		int j = 0;
		for (int i = 0; i < b.length(); i++) {
			if (a.charAt(i+pos) != b.charAt(j)) {
				n++;
			}
			j++;
		}
		System.out.println(b + " abstand:" + n);
		hamming(a, b, (pos+1));
	}

aufruf erfolgt über :

hamming("anatolien", "toll", 0);

Ausgabe ist:

toll abstand:4
toll abstand:4
toll abstand:3
toll abstand:1
toll abstand:4
toll abstand:4

 

[Gast2]

public class Main
{

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args)
    {
        String a = "anatolien";
        String b = "toll";

        System.out.println("String1: " + a);
        System.out.println("String2: " + b);
        System.out.println("MinHammingabstand: " + minimumHamming(a, b));
    }

    private static int minimumHamming(String a, String b)
    {
        int lenA = a.length();
        int lenB = b.length();
        int diff = lenA - lenB;

        int minimum = Integer.MAX_VALUE;
        for (int i = 0; i <= Math.abs(diff); i++) {
            String subA = a.substring((diff >= 0) ? i : 0, (diff >= 0) ? (i + lenB) : lenA);
            String subB = b.substring((diff <= 0) ? i : 0, (diff <= 0) ? (i + lenA) : lenB);

            minimum = Math.min(minimum, hammingDistance(subA, subB));
        }

        return minimum;
    }

    private static int hammingDistance(String a, String b) throws IllegalArgumentException
    {
        if (a.length() != b.length()) throw new IllegalArgumentException("String a und b sind nicht gleich lang");

        int counter = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) counter++;
        }

        return counter;
    }

}

 

[Tina87]

Danke für eure lösungsvorschläge.
hab mich jetzt für die von "faetzminator" entschieden.
ein kleines problem hab ich da noch. wie du schon gesagt hast, greift deine methode auf meine alte zu. lieber wäre es mir aber, wenn alles nur eine methode wäre.
hat mir das dann so überlegt:

public class test {
 
    public static void main(String[] args) {
        String a = "anatolien";
        String b = "toll";
        System.out.println(hammingDistance(a, b));
 
    }
 
    static int hammingDistance(String a, String b) {
        
        int distance = Integer.MAX_VALUE; //distance auf denn grösstmöglichen Wert gesetzt
        int latestDistance = 0;
        int countSubstitutions = 0;
        for (int i = 0; i < a.length() - b.length(); i++) 
        {
            String c = String a.substring(j,j+ b.length());
            for (int j=0; j<c.length();j++)
            {
                if ( c.charAt(j) != b.charAt(j))
                {
                    countSubstitutions++;
                }
                latestDistance=countSubstitutions;
                distance = Math.min(latestDistance, distance); // gibt die kleinere von beiden Zahlen zurück
            }
        }
        return distance;
    }
}

funktioniert natürlich so nicht, aber geht das so etwa in die richtung, um die methoden zusammenzufügen?

 

[Thief]

Tina, das wäre exakt meine Lösung, was du da versuchst (also mit zwei for-Schleifen ineinander)... ?!

edit: der Rest war Quatsch. Hab zwei Benutzer verwechselt *g*

edit2: ach, kann sein dass das Return falsch ist. Für mich unterscheiden sich z.B. "Hallo" und "lo" an mind. 3 Stellen, da ja "lo" kürzer ist als "Hallo". Falls das egal ist, muss natürlich nur best zurück gegeben werden, und nicht best + dist-1.

 

[faetzminator]

In einer Methode würde das folgendermassen aussehen:

public class Foo {

    public static void main(String[] args) {
        String a = "anatolien";
        String b = "toll";
        System.out.println(hammingDistance(a, b));

    }

    public static int hammingDistance(String a, String b) {
        String longStr = a.length() > b.length() ? a : b;
        String shortStr = a.length() > b.length() ? b : a;
        int distance = Integer.MAX_VALUE; // da distance sicher im 1. Schleifendurchgang gesetzt werden soll,
                                          // wird hier distance auf denn grösstmöglichen Wert gesetzt
        for (int i = 0; i <= longStr.length() - shortStr.length(); i++) {
            String secondStr = longStr.substring(i, i + shortStr.length());
            int countSubstitutions = 0;
            for (int j = 0; j < shortStr.length(); j++) {
                if (shortStr.charAt(j) != secondStr.charAt(j)) {
                    countSubstitutions++;
                }
            }
            distance = Math.min(countSubstitutions, distance); // gibt die kleinere von beiden Zahlen zurück
        }
        return distance;
    }
}

Ich finde diese Methode allerdings etwas überladen... Aber ist Geschmackssache

 

[Tina87]

Wollt mich nochmal für eure schnelle Hilfe bedanken!
Klappt jetzt alles super!
Danke!