Programmieren lernen

  package ch.programmieraufgaben.arrays.levenshtein;

/**
 * Berechne die Levenshtein-Distanz zweier Zeichenketten.
 * 
 * @author Philipp Gressly (phi AT gressly DOT ch)
 */
public class Levenshtein {

    public static void main(String[] args) {
        new Levenshtein().top();
    }

    void top() {
        test("MUELLER"      , "MEYER"           ,  3);
        test("PHILIP GRESLI", "PHILIPP GRESSLY" ,  3);
        test("TIER"         , "TOR"             ,  2);
        test("HUGENTOBLER"  , "HUNGERBUEHLER"   ,  6);
        test("HALLO WELT"   , "TSCHAU UNIVERSUM", 13);
    }

    void test(String a, String b, int sollDistanz) {
        System.out.println("Teste | '" + a + "' - '" + b + "' |:");
        int ist = levenshtein(a, b);
        System.out.println("Abstand: " + ist);
        if (sollDistanz != ist) {
            System.out.println("Fehler in der Rechnung:");
            System.out.println("Abstand ist : " + ist);
            System.out.println("Abstand soll: " + sollDistanz);
        }
        System.out.println();
    }

    int levenshtein(String a, String b) {
        int[][] feld = new int[a.length() + 1][b.length() + 1];

        initFeld(feld);
        int indexB = 1;
        while (indexB <= b.length()) {
            int indexA = 1;
            while (indexA <= a.length()) {
                berechneFeld(feld, indexA, indexB, a, b);
                indexA = indexA + 1;
            }
            indexB = indexB + 1;
        }
        //debugFeldAusgeben(a, b, feld);
        return feld[a.length()][b.length()];
    }

    void debugFeldAusgeben(String a, String b, int[][] feld) {
       System.out.println("##" + a);
       System.out.print("#");
       for(int i = 0; i <= a.length(); i++) {
           System.out.print(i);
       }
       System.out.println();
       for(int zeile = 1; zeile <= b.length(); zeile++) {
           System.out.print(b.charAt(zeile - 1));
           for(int spalte = 0; spalte <= a.length(); spalte ++) {
               System.out.print(feld[spalte][zeile]);
           }
           System.out.println();
       }
    }
    
    void berechneFeld(int[][] feld, int spaltenNummer, int zeilenNummer, String a, String b) {
        int links     = feld[spaltenNummer - 1][zeilenNummer    ];
        int oben      = feld[spaltenNummer    ][zeilenNummer - 1];
        int linksoben = feld[spaltenNummer - 1][zeilenNummer - 1];

        if (a.charAt(spaltenNummer - 1) == b.charAt(zeilenNummer - 1)) {
            linksoben = linksoben - 1;
        }
        int min;
        min = Math.min(links, oben);
        min = Math.min(min, linksoben);
        feld[spaltenNummer][zeilenNummer] = min + 1;
    }

    void initFeld(int[][] feld) {
        int j = 0;
        while (j < feld[0].length) {
            feld[0][j] = j;
            j = j + 1;
        }

        int i = 0;
        while (i < feld.length) {
            feld[i][0] = i;
            i = i + 1;
        }
    }

} // end of class Levenshtein
                

Lösung von: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

#include <iostream>
#include <string>
using namespace std;

/* Die erste Zeile und erste Spalte des Feldes je nach Länge
 * des Wortes Initializieren
 * 0 1 2 3 4 5 usw.
 * 1
 * 2
 * 3
 * usw
 */
void initializeField(int ** field, int sizeA, int sizeB)
{
	for(int i = 0; i < sizeA; i++)
	{
		field[i][0] = i;
	}
	for(int i = 0; i < sizeB; i++)
	{
		field[0][i] = i;
	}
}

// Levenshtein-Distanz berrechen
int levenshtein(const string a, const string b)
{
	int distance = 0;
	// Dynamisch ein zweidimensionales Array erzeugen
	int** field = new int*[a.size()+1];
	for(int i = 0; i<a.size()+1; i++)
	{
		field[i] = new int[b.size()+1];
	}

	// Innerhalb der Funktion wird der a String wird auf die X-Achse gemappt,
	// und der b String auf die Y-Achse
	initializeField(field, a.size()+1, b.size()+1);

	/* Buchstaben vergleichen und das freie Feld entsprechend mit einem Wert belegen
	* X-Achse = j (-->)
	* Y-Achse = i
	* |
	* V
	*/
	for(int i = 1; i < b.size()+1; i++)
	{
		for(int j = 1; j < a.size()+1; j++)
		{
			if(a.at(j-1) == b.at(i-1))
			{
				field[j][i] = min(min((field[j-1][i-1]-1), field[j-1][i]), min((field[j-1][i-1]-1), field[j][i-1]))+1;
			}
			else
			{
				field[j][i] = min(min((field[j-1][i-1]), field[j-1][i]), min((field[j-1][i-1]), field[j][i-1]))+1;
			}
			distance = field[j][i];
		}
	}

	// Das Feld ausgeben lassen
	/*for(int i = 0; i <b.size()+1; i++)
	{
		for(int j = 0; j< a.size()+1; j++)
		{
			cout << field[j][i] << " ";
		}
		cout << endl;
	}*/

	// Dynamisch allozierten Speicher freigeben
	for(int i = 0; i < a.size()+1 ; i++)
	{
        delete[] field[i];
	}
	delete[] field;
	return distance;
}


int main()
{
	string a, b;
	cout << "Erster String: ";
	cin >> a;
	cout << "Zweiter String: ";
	cin >> b;
	cout << endl;
	cout << "Die Levenshtein-Distanz der beiden Woerter ist : " << levenshtein(a, b);
	cin.ignore();
	cin.get();
}
                

Lösung von: R. Z. (FH-Dortmund)

((autor m. s.))
  ''' Calculates the Levenshtein distance of 2 strings'''


  def printMatrix(m):
      print ' '
      for line in m:
          spTupel = ()
          breite = len(line)
          for column in line:
              spTupel = spTupel + (column, )
          print "%3i"*breite % spTupel

  s1 = raw_input('first word: ')
  s2 = raw_input('second word: ')

  def levenshtein(s1, s2):
    l1 = len(s1)
    l2 = len(s2)

    matrix = [range(l1 + 1)] * (l2 + 1)
    for zz in range(l2 + 1):
      matrix[zz] = range(zz,zz + l1 + 1)
    for zz in range(0,l2):
      for sz in range(0,l1):
        if s1[sz] == s2[zz]:
          matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz])
        else:
          matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz] + 1)
    print "That's the Levenshtein-Matrix:"
    printMatrix(matrix)
    return matrix[l2][l1]
      
  distance = levenshtein(s1, s2)		
  print 'The Levenshtein-Distance of ',s1, ' and ', s2, ' is ', distance
                

Lösung von: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

string strausgabe;
            int ioben;
            int ilinks;
            int iobenlinks;

            Console.Write("1. Wort: ");
            string strwort1 = Console.ReadLine().ToUpper();

            Console.Write("2. Wort: ");
            string strwort2 = Console.ReadLine().ToUpper();

            strausgabe = "##" + strwort2 + "\n#01234567\n";

            // Zeilenweise
            for (int a = 0; a < strwort1.Length; a++)
            {
                strausgabe += strwort1[a] + (a + 1).ToString();
                // Spaltenweise
                for (int b = 0; b < strwort2.Length; b++)
                {
                    ioben = Convert.ToInt32(strausgabe[strausgabe.Length- 10].ToString());
                    iobenlinks = Convert.ToInt32(strausgabe[strausgabe.Length- 11].ToString());
                    ilinks = Convert.ToInt32(strausgabe[strausgabe.Length - 1].ToString());

                    if (strwort2[b] == strwort1[a])
                    {
                        iobenlinks--;
                        // Minimum (l,o,o/l)
                        if (ioben <= iobenlinks && ioben <= ilinks)
                            strausgabe += (ioben+1).ToString();
                        else if (iobenlinks <= ioben && iobenlinks <= ilinks)
                            strausgabe += (iobenlinks+1).ToString();
                        else if (ilinks <=ioben && ilinks <= iobenlinks)
                            strausgabe += (ilinks+1).ToString();
                    }
                    else
                    {
                        if (ioben <= iobenlinks && ioben <= ilinks)
                            strausgabe += (ioben + 1).ToString();
                        else if (iobenlinks <= ioben && iobenlinks <= ilinks)
                            strausgabe += (iobenlinks + 1).ToString();
                        else if (ilinks <= ioben && ilinks <= iobenlinks)
                            strausgabe += (ilinks + 1).ToString();
                    }
                }
                strausgabe += '\n';
            }

            for (int a = 0; a < strausgabe.Length; a++)
            {
                if (a == strausgabe.Length - 2)
                    Console.ForegroundColor = ConsoleColor.Yellow;
                Console.Write(strausgabe[a]);
            }

            Console.WriteLine("Die Levenshtein-Distanz liegt bei '{0}'.", strausgabe[strausgabe.Length - 2]);
            Console.ReadKey();
                

Lösung von: Dennis Müller ()

#Python 3
def levenshtein(string1, string2):
    matrix = [[i+1]+[None]*len(string1)for i in range(len(string2))]
    matrix.insert(0, list(range(len(string1)+1)))
    for i, row in enumerate(matrix[1:], 1):
        for j, col in enumerate(row[1:], 1):
            l, u, lu = matrix[i][j-1], matrix[i-1][j], matrix[i-1][j-1]
            if string1[j-1] == string2[i-1]: lu -= 1
            matrix[i][j] = min(l, u, lu)+1
    return matrix[-1][-1]

print("Levenshtein-Distanz:")
string1 = input("Erstes Wort:  ")
string2 = input("Zweites Wort: ")

ls = levenshtein(string1, string2)

print("Die Levenshtein-Distanz von {} und {} ist {}".format(string1, string2, ls))

                

Lösung von: Karl Welzel ()

function levenshteinDistance(str1, str2) {
  str1 = str1.toUpperCase();
  str2 = str2.toUpperCase();
  let x, y;

  // natrix initialisieren
  let matrix = [];
  for (y = 0; y < str2.length; y++) matrix[y] = new Array(str1.length);
  for (x = 0; x < str2.length; x++) matrix[x][0] = x;
  for (y = 0; y < str1.length; y++) matrix[0][y] = y;

  // matrix füllen
  for (x = 1; x < str2.length; x++)
    for (y = 1; y < str1.length; y++) {
      if (str2[x] == str1[y]) {  // gleicher buchstabe?
        matrix[x][y] = Math.min(
          matrix[x-1][y-1],
          matrix[x][y-1] + 1,
          matrix[x-1][y] + 1
        );
      }
      else {
        matrix[x][y] = Math.min(
          matrix[x-1][y-1] + 1,
          matrix[x][y-1] + 1,
          matrix[x-1][y] + 1
        );
      }
    }
  console.table(matrix);
  return(matrix[x-1][y-1]);
}

// ausgabe
console.log( levenshteinDistance('Meier', 'Mueller') );
console.log( levenshteinDistance('Philip Gresli', 'Phillip Gressly') );
console.log( levenshteinDistance('Tier', 'Tor') );
console.log( levenshteinDistance('Hugentobler', 'Hungerbuehler') );

                                                             // lisalanda@gmx.at
                

Lösung von: Lisa Salander (Heidi-Klum-Gymnasium Bottrop)