10 Fingersystem-Lernprogramm

[Wildcard]

Wenn du es weiterhin 'korrekt'(also mit minimal möglichen Veränderungen) machen willst, viel Glück!
Poste es doch bitte wenn du's fertig hast, dann zeig ich dir gerne einen Fall bei dem's nicht funktioniert :wink:

 

[mic_checker]

Also ich hab heute den Prof in unserer Datenstrukturen+Algorithmen Übungsstunde diesbezüglich mal "angehauen"

Der wollte mir noch nen Link schicken, bzgl. einer Diplomarbeit die sich wohl teilweise damit beschäftigt.
Wenn er geantwortet hat werd ich dir den Link mal schicken...

 

[The_S]

Ach verdammt, konnte das zwar noch nicht durchprogrammieren (ja ich hab auch andere Hobbys und Verpflichtungen :wink: ), aber hab das mal theoretisch auf nem Blatt durchgespielt. Das würde dann so Enden, dass aus Fler gleich im 1. Durchlauf das Wort Fehler gebastelt wird. Nur nicht so wie es eigentlich gedacht war. Weil es dann insgemsamt 4 Fehler gibt. :autsch: Das funzt allso auch nicht. Noch ne möglichkeit wäre, dass Wort so lange durchzugehen, bis die Methode mit den wenigsten Fehlern gefunden wird. Wäre aber sehr Rechenaufwendig.

Ja, poste den Link sobald du ihn hast.

 

[Wildcard]

Ich hab langsam das Gefühl das du mir gar nicht glauben willst!
Wofür muss das ganze denn so exakt sein? Wenn jemand so dämlich ist den ganze Wörter zu vergessen,
dann wird er wohl kaum über dein Prog merkern dürfen...

 

[The_S]

Will ich auch nicht :wink: . Das Problem hat jetzt meinen Ehrgeiz geweckt. Mittlerweile ist die implementierung dieses "Projekts" in mein 10-Fingersystem-Übungsprogramm zweitrangig geworden. Will das jetzt umbedingt lösen! Koste es was es wolle :wink: .

Aber net bös verstehen. Muss ich jetzt einfach ne Lösung für finden. Ich komm (wenn ich zulange keine Erfolgserlebnisse hab) von meinem Trip auch wieder runter, aber solange ich noch drauf bin :bae: , bin ich für jeden Tip dankbar.

 

[mic_checker]

Hab leider noch keine Antwort bekommen, aber anhand des Gesprächs konnte ich v.a. eins extrahieren:
Das Problem ist nicht gerade trivial, ums mal vorsichtig auszudrücken

Zu deiner Idee :
Wer sagt denn das die Variante mit den wenigsten Fehlern die richtige ist? In manchen Fällen ist ja vielleicht die mit den meisten Fehlern korrekt, dann mal wieder die mit den wenigsten etc.
Soll heissen: Nicht nur das es zu rechenintensiv ist, es ist auch praktisch nicht brauchbar.

Würde empfehlen ein paar Regeln aufzustellen nachdenen Fehler berechnet werden, in manchen Fällen muss der User halt in den sauren Apfel beissen und kriegt evtl. mehr Fehler angezeigt als er eigentlich gemacht hat.

Btw. kann deinen Ehrgeiz durchaus verstehen, hab heute ein paar meiner Kumpels damit konfrontiert und die waren nach ein paar Minuten Überlegungen auch überrascht ..... *g*

 

[The_S]

Zu deiner Idee :
Wer sagt denn das die Variante mit den wenigsten Fehlern die richtige ist? In manchen Fällen ist ja vielleicht die mit den meisten Fehlern korrekt, dann mal wieder die mit den wenigsten etc.
Soll heissen: Nicht nur das es zu rechenintensiv ist, es ist auch praktisch nicht brauchbar.

Nach irgendwas muss ich ja gehen :bae: . Denk mal, dass es wahrscheinlicher ist, dass weniger Fehler gemacht wurden als mehr.

Würde empfehlen ein paar Regeln aufzustellen nachdenen Fehler berechnet werden, in manchen Fällen muss der User halt in den sauren Apfel beissen und kriegt evtl. mehr Fehler angezeigt als er eigentlich gemacht hat.

Beispiel? Kann mir da nämlich nichts drunter vorstellen :bahnhof: ???:L

 

[mic_checker]

Also hab heute morgen eine Antwort bekommen, da er momentan nicht auf den zuständigen Server zugreifen konnte hat er mir die Diplomarbeit so zugeschickt.

Viellleicht helfen dir auch noch die Stichworte:
- Levensthein Distanz
(- edit Distanz )


Hab mal kurz gesucht und bin darauf gestossen:
http://www.levenshtein.de/

Viel Spaß

 

[mic_checker]

Hab gerad etwas weiter gesucht.

Vielleicht solltest du dir auch mal die "Damerau-Levenshtein-Metrix" anschauen, da dieser Metrix im Gegensatz zur Levenshtein Metrix ein weiterer Operator zur Verfügung steht (Transposition), die kann benachbarte Elemente/Symbole vertauschen, eignet sich also für dein Beispiel bei "Buchstabendrehern".

Ich kann dir die Arbeit gerne per EMail zuschicken, allerdings befasst sie sich wirklich nur an einigen Stellen damit, da es eigentlich um "Sprachunterstützung" und "eLearning" geht...

 

[The_S]

Kann mir das alles grad net so anschauen, weil ich Berufsschule hab. Kannst mir aber gerne mal per Mail schicken.

 

[The_S]

Hab da noch was gefunden!!! Was als "Longest common Subsequence" bekannt ist. Kennt dazu jemand interessante Links? Bzw. wie realisiere ich sowas in Java?

 

[mic_checker]

Sie haben Post

Btw. hab noch ne andere Seite zum Levenshtein Algo gefunden :

http://www.merriampark.com/ld.htm

Dort ist auch ne Implementierung in Java etc.

Longest-Common-Subsequence (LCS)

Dieses gilt als eine vereinfachte Variante des Levenshtein-Algorithmuses. Dieser Ansatz findet in der Diskussion um approximative Suchtechnologien Bedeutung, da hier direkt zusammenliegende Buchstaben-Sequenzen die gleiche Bedeutung zugewiesen bekommenen, wie Buschstaben-Sequenzen, die innerhalb des Wortes verteilt sind. In Fällen, in denen ein direktes Verhältnis zwischen der Länge der Suchanfrage und der Länge der Wörterbucheinträge nicht gegeben werden kann, ist es ein geeigneter Algorithmus für approximative Suchanfragen. Aber genauso wie beim Bipartiten Matching, gelang bisher nur der Firma Exorbyte eine performante Implementierung kaum möglich.

http://www.levenshtein.de/levenshtein_search.htm

 

[The_S]

Hey das Ding ist geil! Jetzt müsst ichs nur noch verstehen :wink: .

@Wildcard ein vorläufiges :bae: :wink:

 

[mic_checker]

Meinst du den Levi Algorithmus oder Longest-Common-Subsequence oder die ganze Diplomarbeit ?

Da hast du wenigstens was zu tun in den Pausen *g*

 

[The_S]

Alles insgesamt, habs aber auch nur überflogen. Werd mich jetzt mal dran machen da ein wenig durchzusteigen :wink: . Nochmal Danke. :toll:

 

[The_S]

Versuche zZ das hier umzusetzen. Bekomm dass aber nicht so hin, wie ich es möchte. Bin gerade dabei das 2 Dimensionale Array mit Zahlen zu bestücken, damit die Ausgabe so ausschaut, wie bei dem Beispiel auf der Seite. Das klappt auch, solange ich keine Buchstaben zu viel oder zu wenig hab. Wie müsste ich meinen Code erweitern, dass soetwas auch geht (oder geh ich das mit meinem aktuellen Code total falsch an?)?

public class diffTest {
	
	public static void main(String[] args) {
		
		String str1 = "Fehlt";
		String str2 = "Fehlt";
		int fehler = 0;
		int stelle = 1;
		int[][] check = new int[str1.length() + 1][str2.length() + 1];
		for (int a = 0; a < str1.length() + 1; a++) {
			check[a][0] = 0;
		}
		for (int a = 0; a < str2.length() + 1; a++) {
			check[0][a] = 0;
		}
		for (int a = 1; a < str1.length() + 1; a++) {
			for (int b = a; b < str2.length() + 1; b++) {
				if (str1.charAt(a - 1) == str2.charAt(b - 1)) {
					for (int c = b; c < str2.length() + 1; c++) {
						check[a][c] = b - (stelle - 1);
					}
					for (int c = a; c < str1.length() + 1; c++) {
						check[c][a] = b - (stelle - 1);
					}
				}
				else {
					for (int c = b; c < str2.length() + 1; c++) {
						check[a][c] = b - stelle;
					}
					for (int c = a; c < str1.length() + 1; c++) {
						check[c][a] = b - stelle;
					}
					stelle++;
				}
				b = str2.length() + 1;
			}
		}
		for (int a = str1.length(); a >= 0; a--) {
			for (int b = 0; b < str2.length() + 1; b++) {
				System.out.print(check[a][b]);
			}
			System.out.println();
		}
	}
}

 

[mic_checker]

Kamst du eigentlich nochmal weiter? Hatte leider noch keine Zeit mir LCS näher anzuschauen....

Hilft dir der Source vom Applet nicht weiter?

 

[The_S]

Nö bis jetzt noch nicht. Und aus dem Applet-Code werde ich auch nicht wirklich schlau ... Ich post ihn mal ganz *g*:

import java.applet.Applet;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.EventObject;

public class LCSApplet extends Applet
    implements ActionListener, Runnable
{

    public LCSApplet()
    {
        pos_i = 1;
        pos_j = 1;
        backcount = 0;
        calc_length_done = false;
        status = 1;
    }

    public void run()
    {
        setButtons();
        while(status == 0) 
        {
            lcs_next();
            waitDelay(100);
        }
        setButtons();
    }

    public synchronized void stop()
    {
        if(runner != null && runner.isAlive())
        {
            status = 1;
            notify();
            runner = null;
        }
        setButtons();
    }

    public void init()
    {
        y_label = getImage(getDocumentBase(), "label_y.gif");
        x_label = getImage(getDocumentBase(), "label_x.gif");
        setBackground(Color.lightGray);
        Panel panel = new Panel();
        Panel panel1 = new Panel();
        Panel panel2 = new Panel();
        outputPanel = new OutputPanel();
        panel.setLayout(new GridBagLayout());
        GridBagConstraints gridbagconstraints = new GridBagConstraints();
        y_input = new String("ABCBDAB");
        x_input = new String("BDCABA");
        length_output = 0;
        lcs_output = new String("");
        btnPlay = new Button("Play");
        btnStop = new Button("Stop");
        btnPrev = new Button("Prev");
        btnNext = new Button("Next");
        btnReset = new Button("Init / Reset");
        yField = new TextField("ABCBDAB", 14);
        xField = new TextField("BDCABA", 14);
        btnHelp = new Button("Help");
        canvas = new LCSCanvas(y_input, x_input, y_label, x_label);
        label1 = new Label("String 1:", 2);
        label2 = new Label("String 2:", 2);
        btnPlay.addActionListener(this);
        btnStop.addActionListener(this);
        btnPrev.addActionListener(this);
        btnNext.addActionListener(this);
        btnReset.addActionListener(this);
        xField.addActionListener(this);
        yField.addActionListener(this);
        btnHelp.addActionListener(this);
        btnPlay.setFont(new Font("SansSerif", 0, 12));
        btnStop.setFont(new Font("SansSerif", 0, 12));
        btnPrev.setFont(new Font("SansSerif", 0, 12));
        btnNext.setFont(new Font("SansSerif", 0, 12));
        btnReset.setFont(new Font("SansSerif", 0, 12));
        xField.setFont(new Font("SansSerif", 0, 12));
        yField.setFont(new Font("SansSerif", 0, 12));
        label1.setFont(new Font("SansSerif", 0, 12));
        label2.setFont(new Font("SansSerif", 0, 12));
        gridbagconstraints.insets = new Insets(2, 0, 4, 1);
        panel.add(btnPlay, gridbagconstraints);
        gridbagconstraints.insets = new Insets(2, 0, 4, 1);
        panel.add(btnStop, gridbagconstraints);
        gridbagconstraints.insets = new Insets(2, 0, 4, 1);
        panel.add(btnPrev, gridbagconstraints);
        gridbagconstraints.insets = new Insets(2, 0, 4, 1);
        panel.add(btnNext, gridbagconstraints);
        gridbagconstraints.insets = new Insets(2, 0, 4, 2);
        panel.add(btnReset, gridbagconstraints);
        gridbagconstraints.insets = new Insets(2, 0, 4, 2);
        panel.add(label1, gridbagconstraints);
        gridbagconstraints.insets = new Insets(2, 0, 4, 2);
        panel.add(yField, gridbagconstraints);
        gridbagconstraints.insets = new Insets(2, 0, 4, 2);
        panel.add(label2, gridbagconstraints);
        panel.add(xField, gridbagconstraints);
        panel1.add(btnHelp);
        panel2.add(canvas);
        BorderLayout borderlayout = new BorderLayout();
        setLayout(borderlayout);
        add("North", panel);
        add("Center", canvas);
        add("South", outputPanel);
        setButtons();
        canvas.setPos(pos_i, pos_j);
        outputPanel.SetContent(Integer.toString(canvas.getLength(pos_i, pos_j)), "");
    }

    public void start()
    {
    }

    public Insets getInsets()
    {
        return new Insets(3, 3, 3, 3);
    }

    public void actionPerformed(ActionEvent actionevent)
    {
        Object obj = actionevent.getSource();
        if(obj instanceof TextField)
            lcs_reset();
        if(actionevent.getActionCommand() == "Play")
        {
            if(inputHasChanged())
                lcs_reset();
            lcs_play();
        }
        if(actionevent.getActionCommand() == "Stop")
            lcs_stop();
        if(actionevent.getActionCommand() == "Prev")
            lcs_prev();
        if(actionevent.getActionCommand() == "Next")
        {
            if(inputHasChanged())
                lcs_reset();
            lcs_next();
        }
        if(actionevent.getActionCommand() == "Init / Reset")
            lcs_reset();
    }

    public boolean inputHasChanged()
    {
        return !x_input.equals(xField.getText()) || !y_input.equals(yField.getText());
    }

    public synchronized void lcs_play()
    {
        runner = new Thread(this);
        status = 0;
        runner.start();
        setButtons();
    }

    public synchronized void lcs_stop()
    {
        stop();
        setButtons();
        setButtons();
    }

    public synchronized void lcs_prev()
    {
        int i = y_input.length();
        int j = x_input.length();
        if(calc_length_done)
        {
            if(backcount == 1)
                calc_length_done = false;
            backcount--;
            canvas.setPos(calc_length_done, backcount);
            if(canvas.isDone_LCS())
                canvas.isDone_LCS(false);
        } else
        {
            if(pos_j > 1)
                pos_j--;
            else
            if(pos_i > 1)
            {
                pos_i--;
                pos_j = j;
            }
            canvas.setPos(pos_i, pos_j);
        }
        canvas.setStatus(status);
        canvas.setPos(calc_length_done, backcount);
        canvas.repaint();
        int k = canvas.getLength(pos_i, pos_j);
        outputPanel.SetContent(Integer.toString(k), canvas.getLCS(k, backcount));
        setButtons();
    }

    public synchronized void lcs_next()
    {
        int i = y_input.length();
        int j = x_input.length();
        if(pos_j < j)
            pos_j++;
        else
        if(pos_i < i)
        {
            pos_i++;
            pos_j = 1;
        } else
        {
            calc_length_done = true;
        }
        if(calc_length_done)
        {
            if(!canvas.isDone_LCS())
                backcount++;
            canvas.setPos(calc_length_done, backcount);
        } else
        {
            canvas.setPos(pos_i, pos_j);
        }
        if(canvas.isDone_LCS())
            status = 1;
        canvas.setStatus(status);
        canvas.setPos(calc_length_done, backcount);
        canvas.repaint();
        int k = canvas.getLength(pos_i, pos_j);
        outputPanel.SetContent(Integer.toString(k), canvas.getLCS(k, backcount));
        setButtonsPre();
    }

    public synchronized void lcs_reset()
    {
        x_input = xField.getText();
        y_input = yField.getText();
        if(x_input.length() > 14)
        {
            x_input = x_input.substring(0, 14);
            xField.setText(x_input);
        }
        if(y_input.length() > 14)
        {
            y_input = y_input.substring(0, 14);
            yField.setText(y_input);
        }
        pos_j = 1;
        pos_i = 1;
        calc_length_done = false;
        backcount = 0;
        canvas.isDone_LCS(false);
        canvas.setPos(pos_i, pos_j);
        canvas.setPos(calc_length_done, backcount);
        canvas.LCSReset(y_input, x_input);
        outputPanel.SetContent(Integer.toString(canvas.getLength(pos_i, pos_j)), "");
        setButtons();
    }

    public synchronized void setButtons()
    {
        if(status == 0)
        {
            btnPlay.setEnabled(false);
            btnStop.setEnabled(true);
            btnPrev.setEnabled(false);
            btnNext.setEnabled(false);
            btnReset.setEnabled(false);
        } else
        if(canvas.isDone_LCS())
        {
            btnPlay.setEnabled(false);
            btnStop.setEnabled(false);
            btnPrev.setEnabled(true);
            btnNext.setEnabled(false);
            btnReset.setEnabled(true);
        } else
        if(pos_i == 1 && pos_j == 1)
        {
            btnPlay.setEnabled(true);
            btnStop.setEnabled(false);
            btnPrev.setEnabled(false);
            btnNext.setEnabled(true);
            btnReset.setEnabled(true);
        } else
        {
            btnPlay.setEnabled(true);
            btnStop.setEnabled(false);
            btnPrev.setEnabled(true);
            btnNext.setEnabled(true);
            btnReset.setEnabled(true);
        }
    }

    public synchronized void setButtonsPre()
    {
        if(status == 0)
        {
            btnPlay.setEnabled(false);
            btnStop.setEnabled(true);
            btnPrev.setEnabled(false);
            btnNext.setEnabled(false);
            btnReset.setEnabled(false);
        } else
        if(canvas.isPreDone_LCS())
        {
            btnPlay.setEnabled(false);
            btnStop.setEnabled(false);
            btnPrev.setEnabled(true);
            btnNext.setEnabled(false);
            btnReset.setEnabled(true);
        } else
        if(pos_i == 1 && pos_j == 1)
        {
            btnPlay.setEnabled(true);
            btnStop.setEnabled(false);
            btnPrev.setEnabled(false);
            btnNext.setEnabled(true);
            btnReset.setEnabled(true);
        } else
        {
            btnPlay.setEnabled(true);
            btnStop.setEnabled(false);
            btnPrev.setEnabled(true);
            btnNext.setEnabled(true);
            btnReset.setEnabled(true);
        }
    }

    public synchronized void waitDelay(int i)
    {
        try
        {
            wait(i);
        }
        catch(InterruptedException interruptedexception) { }
    }

    public static final int UP = 1;
    public static final int LEFT = 2;
    public static final int DIAGONAL = 3;
    public static final String Y_DEFAULT = "ABCBDAB";
    public static final String X_DEFAULT = "BDCABA";
    public static final int MAX_INPUT_SIZE = 14;
    public static final int STEP_SPEED = 100;
    public volatile int pos_i;
    public volatile int pos_j;
    public volatile int backcount;
    public volatile boolean calc_length_done;
    private static final int GO = 0;
    private static final int TERMINATE = 1;
    private volatile int status;
    Thread runner;
    String y_input;
    String x_input;
    int length_output;
    String lcs_output;
    TextField yField;
    TextField xField;
    Button btnPlay;
    Button btnStop;
    Button btnPrev;
    Button btnNext;
    Button btnReset;
    Button btnHelp;
    Label label1;
    Label label2;
    LCSCanvas canvas;
    OutputPanel outputPanel;
    Image y_label;
    Image x_label;
}

Tu mir im Moment ein bisschen schwer damit, fremden Code zu verstehen.

 

[The_S]

Hab jetzt eine Denk ich verwertbare Ausgabe, nur weiß ich nicht wie ich sie auswerte :autsch: :bae: . Mein aktueller Code:

public class diffTest { 
    
	public static void main(String[] args) { 
       
		String str1 = "Fehler"; 
		String str2 = "Fehler"; 
		int fehler = 0;
		int[][] check = new int[str1.length()][str2.length()]; 
		for (int a = 0; a < str1.length(); a++) { 
			for (int b = 0; b < str2.length(); b++) { 
				if (str1.charAt(a) == str2.charAt(b)) { 
					check[a][b] = 1;
				}
			} 
		} 
		for (int a = str1.length() - 1; a >= 0; a--) { 
			for (int b = 0; b < str2.length(); b++) { 
				System.out.print(check[a][b]); 
			} 
			System.out.println(); 
		} 	
	} 
}

In diesem Beispiel wird

000001
010010
000100
001000
010010
100000

ausgegeben. D. h. dass alles richtig ist, da von rechts oben diagonal bis links unten alles mit 1ern voll steht. Nur wie werte ich das in anderen Fällen am Besten aus? könne ja auch z. B. so dastehen:

Fehler => Fdhler

000001
000010
000100
001000
000010
100000

oder so:

Fehler => Fler

0001
0010
0100
0000
0010
1000

usw.

 

[mic_checker]

Hab mir jetzt den Algo nicht mehr genau angeschaut, aber warum kontrollierst du dann nicht einfach die Werte in der Hauptdiagonalen (also ob 1) und zählst Unterschiede (wenn das reicht).

Im andern Fall : Die Anzahl der Spalten und Zeilen ist ja schon unterschiedlich....was gibt er denn aus wenn du nicht "Fler" eingibst sondern "Fder" oder sonst was, was nicht genau übereinstimmt (bis auf Länge)?

Kann leider momentan nichts testen und kann deswegen auch nichts konkretes sagen....

 

[The_S]

Hab mir jetzt den Algo nicht mehr genau angeschaut, aber warum kontrollierst du dann nicht einfach die Werte in der Hauptdiagonalen (also ob 1) und zählst Unterschiede (wenn das reicht).

Wie stellst du dir dass vor?

Im andern Fall : Die Anzahl der Spalten und Zeilen ist ja schon unterschiedlich....was gibt er denn aus wenn du nicht "Fler" eingibst sondern "Fder" oder sonst was, was nicht genau übereinstimmt (bis auf Länge)?

Hier noch ein paar Beispiele:

Fder

0001
0010
0000
0000
0010
1000

Feehder

0000001
0110010
0000000
0001000
0110010
1000000

Feeler

000001
011010
000100
000000
011010
100000

Feeeee

000000
011111
000000
000000
011111
100000

...

 

[mic_checker]

Wie stellst du dir dass vor?

Also - wenn in der Hauptdiagonalen von rechts oben nach links unten nur Einsen stehen und die Anzahl der Spalten == Anzahl der Zeilen, dann ist alles korrekt . richtig?

Du musst also sukzessive die Werte in der Hauptdiagonalen überprüfen.

Falls Anzahl Spalten != Anzahl Zeilen müsste man die Zeilen/Spalten vielleicht irgendwie ummodellieren...

Hatte eben "Arbeitsrecht" , also entschuldige bitte wenn das was ich geschrieben hab totaler Schwachsinn ist

 

[The_S]

Hmm ... hab bis jetzt geschafft, dass es erkennt, wenn es richtig ist und wenn ein Buchstabe zuviel ist. Noch fraglich ist es, wie ich es anstelle, damit er den Rest erkennt (also Buchstaben vergessen, Buchstaben vertauscht oder eine Kombination aus beiden). Das hier ist der Code um festzustellen ob es richtig ist, oder ob ein Buchstabe im Eingabetext zuviel ist (einfach an den ursprünglichen Dranhängen):

		for (int a = str1.length() - 1, b = str2.length() - 1; a >= 0 && b >= 0;) {
			if (check[a][b] == 1) {
				a--;
				b--;
			}
			else {
				if (a != str1.length() - 1 && check[a + 1][b] == 1) {
					fehler++;
					a++;
				}
			}
		}

Hab zwar schon einiges für die anderen möglichen Varianten ausprobiert, aber nichts hat wirklich 100%ig funktioniert.

 

[mic_checker]

Hab gerad auch ne andere Lösung dafür gemacht, aber ist ja gehoppt wie gesprungen. Übrigens: Deine Ausgabe oben könnte etwas verwirren: Man könnte meinen die Hauptdiagonalen beginne bei [0][5] und ende bei [5][0], tatsächlich aber fängt sie ja eigentlich bei [0][0] an und endet bei [5][5] (Wenn man Array-Elemente "richtig" ausgeben lässt).

Ist nur ne Idee, aber wenn was zuviel/zuwenig eingegeben wurde, könnte man doch Spalten/Zeilen löschen , bzw. die Matrizen irgendwie in eine symmetrische Matrix transferieren...

 

[mic_checker]

Damit man besser sieht was ich meine:

Ursprung:
Fder

0001
0010
0000
0000
0010
1000


Nachher:
0001
0010
0000
0000

-> Du hast zwei Zeilen gelöscht (Fehler = 2), es fehlen zwei Einsen in der neuen Hauptdiagonalen (Fehler + 2), somit hast du 4 Fehler, was ja stimmen müsste.

Fraglich ist noch ob man dafür ne allgemeine Regel aufstellen kann....

Hoffe ich hab mich nicht unklar ausgedrückt.

 

[The_S]

Ursprung:
Fder

0001
0010
0000
0000
0010
1000


Nachher:
0001
0010
0000
0000

-> Du hast zwei Zeilen gelöscht (Fehler = 2), es fehlen zwei Einsen in der neuen Hauptdiagonalen (Fehler + 2), somit hast du 4 Fehler, was ja stimmen müsste.

Aber hier wurden keine 4 Fehler gemacht :bae: . Die letzten beiden Buchstaben sind Richtig

0001
0010

er

zwei Buchstaben wurden ausgelassen und einer vertauscht. Der 1. Buchstabe ist wieder richtig

1000

F

Macht nach Adam Riese 3 Fehler. Hat ich auch schon so versucht. Hab es auch mal versucht, die Matrix einmal falsch und einmal komplett richtig zu erzeugen und dann zu vergleichen. Das hat aber auch nicht wirklich hingehauen, sobald in nem Wort ein Buchstabe zweimal vorkommt ???:L . Wie wäre denn deine Lösung für Buchstaben zuviel und richtig? Vielleicht inspiriert sie mich ja :wink: . Vielleicht könnte man aber die drei falschen Zeilen

0000
0000
0010

rauslöschen. Wäre nur die Frage nach welchem Schema man das macht ...

Stimmt, könnte echt ein wenig verwirren meine Aussage. An alle (sofern dass hier jemand liest außer dir mic_checker :wink: ) ich hab das so wie mic_checker gesagt hat gemeint. Von [0][0] zu [5][5].

 

[mic_checker]

Aber hier wurden keine 4 Fehler gemacht :bae:

arg, wer zählen kann ist klar im vorteil

Hab leider heute und morgen nicht viel zeit mir was zu überlegen, bzw. was konkretes an code zu posten, aber es müsste eigentlich irgendwie möglich sein , nur wie ...

 

[The_S]

Schade, dass du keine Zeit hast. Kann mir auch nicht vorstellen, dass das so schwer ist. Ich versuchs auf jeden Fall weiter. Wenn ichs bis morgen noch net hab, kannst ja mal schauen, ob dir noch was einfällt.

 

[mic_checker]

Hab mal ne Frage zu deiner Implementierung des LCS:

In dem Beispiel auf der Seite entsteht eine Matrix auch mit Zahlen > 1, also 2, 3 und 4. Es wird auch jeweils auf andere Array Elemente zugegriffen (siehe Pseudocode und "Zeichnung").
In deiner Variante vergleichst du nur jeweils die Strings an den jeweiligen Stellen und setzt je nachdem den Wert auf 1 oder lässt ihn auf 0.

Warum hast du dich für diese Implementierung entschieden und nicht für die auf der Seite? Versuche gerade das von der Seite zu machen, allerdings gefällt mir der Pseudocode nicht besonders ....

Hoffe du weisst was ich meine....

 

[mic_checker]

Also ich hab mich nochmal dran gesetzt und hab folgenden Code entwickelt:

   public static void lcs() {
   	String orig = "Fehler";
	   String in = "Fder";
	   int[][] l = new int[orig.length()+1][in.length()+1];
	   
	   int laenge = 0;
	   for(int i = 0,c = orig.length()-1;i < orig.length() && c >= 0;i++,c--) {
	   	for(int j = 0,k = 1;j < in.length() && k <= in.length();j++,k++) {
		   	if(orig.charAt(i) == in.charAt(j)) {
			   	l[c][k] = l[c+1][k-1] + 1; 
			   } else {
			   	if(l[c+1][k] > l[c][k-1])
				   	l[c][k] = l[c+1][k];
					else
						l[c][k] = l[c][k-1];
			   }	
			   laenge = l[c][k];   
		   }
		}
		
		System.out.println("Aktuelle Länge = "+laenge);
		
		for (int a = 0; a < l.length; a++) {
         for (int b = 0; b < l[0].length; b++) {
            System.out.print(l[a][b]);
         }
         System.out.println();
      } 
   
   }

Bisherige Tests gaben mir die gleiche "Matrix" aus wie die Seite die du gepostet hast, es wurde bisher auch immer die LCS korrekt ausgegeben.

Allerdings will ich mich nicht zu früh freuen, hab ich schon zu oft zuvor gemacht in dem Thread

Bitte darum das ganze zu testen !

 

[The_S]

Jo, wird morgen gemacht. Hab jetzt aber keine Zeit mehr. Ich hab mich gegen die Seite entschieden, weil ich aus dem Pseudo-Code nicht schlau wurde und es auch so nicht hinbekommen hab :wink: .

 

[mic_checker]

Der Pseudocode hat mich anfangs auch verwirrt, man muss sich die Matrix ganz genau angucken und darf es nicht eins zu eins vom Pseudocode übertragen, wie man oben sieht.

Wichtig ist, dass man links unten im Array anfängt und dann Reihe für Reihe weiter nach oben geht, außerdem ist wichtig das man die zwei Zählvariablen für die zwei Strings und extra Zählvariablen für Zeile/Spalte holt (zumindest ist es so einfacher).

Und wehe du findest ein Beispiel wo es nicht klappt !

Btw. Wildcard: Du wolltest doch ein Beispiel posten *g*

 

[Wildcard]

Ist das das Endergebnis? Will mir das jetzt nicht alles durchlesen, was soll die Matrix am Ende bedeuten?

 

[mic_checker]

Das ist noch nicht direkt das Endergebnis, da du mit dem Code von oben nur die sog. "Longest Common Subsequence" kriegst, aber wenn ich das bisher richtig beobachtet habe kannst du anhand dessen die Anzahl der Fehler ermitteln.

Beispiel:
Du ermittelst mit die LCS für den eingegebenen Text (verglichen mit Original Text) - kommt dabei die Länge des Original Textes raus ist alles fehlerfrei, kommt z.B. 0 raus, sind nur Fehler aufgetreten. Entsprechend kannst du die Anzahl der Fehler bestimmen. (Falls ich nichts falsch verstanden hab).

 

[Wildcard]

Also ist die Anzahl der Fehler die originallänge - das länge ergebnis?

 

[mic_checker]

Es ist nicht immer die Originallänge, es kommt darauf an ob man zuviel/zuwenig Buchstaben eingetippt hat.
Es gilt also den längeren Text zu ermitteln und danach das Ergebnis der Methode lcs() davon abzuziehen.

Das ist zumindest aktueller Stand der Dinge

Falls jemand ein Beispiel findet bei dem es nicht funktioniert bitte Original String und eingegebenen String posten.

 

[Wildcard]

Es gilt also den längeren Text zu ermitteln und danach das Ergebnis der Methode lcs() davon abzuziehen.


Falls jemand ein Beispiel findet bei dem es nicht funktioniert bitte Original String und eingegebenen String posten.

        String orig = "aaabbbb"; 
        String in = "bbbaaa";

Laut Ergebnis 4 Fehler. Wie soll das gehen? :wink:

 

[mic_checker]

Ach du mit deinen utopischen Beispielen

Mal schauen wie man das ganze noch weiterentwickeln kann. Der Algorithmus ermittelt ja eigentlich "nur" in dem Fall : "aaa" als LCS.

Für die richtigen Ergebnisse in (fast allen) Fällen müsste man wohl die komplexeren Algorithmen zu Rate ziehen , zumindest funzt es so schon besser als vorher

Gilt noch zu klären ob es einen weiterbringt die Position der LCS zu ermitteln, ob man darauf aufbauend also noch weiter schlussfolgern kann: IN dem und dem Fall muss man noch weitere schritte einleiten......mal gucken....

edit:
Hab gerad nochmal das ganze auf der einen Seite mit dem Applet getestet, auch da kommt man zum selben Ergebnis, liegt also nicht am Code (scheinbar), sondern am Algorithmus.....weiss nicht ob das gut oder schlecht sein soll

 

[Wildcard]

Ach du mit deinen utopischen Beispielen

:lol:

Womit wir aber wieder bei dem sind was ich weiter vorne schon gesagt hab: Einschränkungen. Exakt wird das IMHO sehr sehr schwierig. Von der Rechenzeit abgesehen würds mich interessieren ob dafür überhaupt schonmal jemand einen exakten Algo geschrieben hat.

 

[mic_checker]

Ich weiss jetzt nicht genau ob der Levenshtein Fälle wie oben erkennen würde, afaik ist der LCS ja "nur" eine vereinfachte Version des Levenshtein.

Allerdings erkennt man so schon mal in einigen Fällen Fehler die man sonst nicht erkannt hätte.

Denke also das dieser Ansatz vorerst als "eingeschränkte Version" akzeptabel ist.....

 

[Wildcard]

Ich weiss jetzt nicht genau ob der Levenshtein Fälle wie oben erkennen würde, afaik ist der LCS ja "nur" eine vereinfachte Version des Levenshtein.

Womöglich schon, mich interessiert eher das algemeinere Problem von minimal möglich Transformationen, und ob's
da einen Algo gibt der nachweislich exakt ist.

Denke also das dieser Ansatz vorerst als "eingeschränkte Version" akzeptabel ist.....

Ich denke er ist mehr als ausreichend! Klar entwickelt man für DAU's, aber mal eben 20 Buchstaben vergessen und dann 4 vertauschen geht IMHO über einen DAU hinaus und würde mich nicht weiter interessieren.
Wenn das tatsächlich real vorkommt ist der entsprechende DAU vermutlich auch ausserstande das Ergebnis zu überprüfen :wink:

 

[mic_checker]

Womöglich schon, mich interessiert eher das algemeinere Problem von minimal möglich Transformationen, und ob's
da einen Algo gibt der nachweislich exakt ist.

Das Themengebiet ist schon sehr interessant, wir werden wohl leider nur sehr entfernt und ansatzweise in Datenstrukturen und Algorithmen drauf eingehen ..... allerdings ist es - wie du ja auch schon mehrfach gesagt hast - eine recht komplexe Thematik.

Ich denke er ist mehr als ausreichend! Klar entwickelt man für DAU's, aber mal eben 20 Buchstaben vergessen und dann 4 vertauschen geht IMHO über einen DAU hinaus und würde mich nicht weiter interessieren.
Wenn das tatsächlich real vorkommt ist der entsprechende DAU vermutlich auch ausserstande das Ergebnis zu überprüfen :wink:

Idealfall ist eh: Der Benutzer macht keine Fehler, kriegt nur bestätigt : 0 Fehler und gut is Müsst jetzt noch überlegen wie das Programm das gemacht hat das ich damals mal benutzt habe zum 10 Fingersystem lernen.....

Oder benutzt einer von euch noch so ein Programm und kann mal posten wie das da gehandhabt wird?

 

[The_S]

Bleiben wir doch bei meiner Matrix, die hat nämlich mit "aaabbb" und "bbbaaa" keine Probleme. Aber wie werte ich sie aus :cry: :x :cry:

[edit] wenn die Strings gleich lang sind ist dass kein Problem,

if (str1.length() == str2.length()) {
	for (int a = str1.length() - 1; a >= 0; a--) {
		if (check[a][a] != 1) {
			fehler++;
		}
	}
}

´

aber bei unterschiedlicher länge ... vielleicht wenn man den String irgendwie ergänzt, nur wie

 

[The_S]

OK, jetzt hab was gebastelt, dass scheinbar funktioniert!!! Wer findet ein Beispiel, dass falsch ist!?

import java.io.*;

public class diffTest { 
    
    void diff(String str1, String str2) {
    	
    	str1 = " " + str1 + " ";
    	str2 = " " + str2 + " ";
    	int fehler = 0; 
		int[][] check = new int[str1.length()][str2.length()]; 
		for (int a = 0; a < str1.length(); a++) { 
			for (int b = 0; b < str2.length(); b++) { 
				if (str1.charAt(a) == str2.charAt(b)) { 
					check[a][b] = 1; 
				} 
			} 
		} 
		if (str1.length() == str2.length()) {
			for (int a = str1.length() - 1; a >= 0; a--) {
				if (check[a][a] != 1) {
					fehler++;
				}
			}
		}
		else {
			if (str1.length() < str2.length()) {
				fehler = str2.length() - str1.length();
			}
			for (int a = str1.length() - 1, b = str2.length() - 1; a >= 0 && b >= 0;) {
				if (check[a][b] == 1) {
					a--;
					b--;
				}
				else {
					for (int c = 0; c <= a; c++) {
						fehler++;
						for (int d = 0; d <= b; d++) {
							if (check[a - c][b - d] == 1) {
								a = a - c;
								b = b - d;
								d = b + 1;
								c = a + 1;
								fehler--;
							}
						}
					}
				}
			}
		}
		System.out.println("Fehler: " + fehler);
    }
    
	public static void main(String[] args) { 

		String str1 = null;
		String str2 = null;
		diffTest test = new diffTest();
		while(true) {
			try {
				str1 = new BufferedReader(new InputStreamReader(System.in)).readLine();
				str2 = new BufferedReader(new InputStreamReader(System.in)).readLine();
			}
			catch (Exception e) {
				System.out.println(e.toString());
			}
			test.diff(str1, str2);
		} 
	}
}

[edit] Code angepasst

Hab festgestellt, dass es zu Problemen kommen kann, wenn der 1. und der letzte Buchstabe falsch ist ....

[edit2] Code angepasst

1. und letzter Buchstabe falsch => Problem behoben

 

[mic_checker]

Hast du das ganze mal mit den Beispielen getestet die im Thread vorkamen?

Muss gleich wieder zur Vorlesung, kann erst heute Mittag testen.

Wenn ich das richtig seh hast du deinen umgewandelten LCS benutzt oder?
Mal schauen ob es zu den andern Verfahren auch verständlichen Pseudocode gibt - der vom LCS war ja etwas verwirrend.
Hab mir jetzt z.B. die Damerau Levenshtein Metrik etc. nicht mehr angeschaut, aber viel. findet man da auch was passendes.

Also werd heute mittag erste Testergebnisse posten

 

[The_S]

Hab gerade festgestellt, dass das teilweise ganz gewaltig hackt ...

Fehler bis jetzt:

Original    Eingabe    Fehler    Berechnet    Bemerkung

Fehler      Fehla        2           4        Wenn ich als Original Fehla nehme und als Eingabe Fehler stimmts
Microsoft   Microshrot   3           2
Kruzifix    Kreuzfix     2           3
Hirsch      Hier         4           3

Weiß jemand woran das liegen könnte, und was ich ändern kann?

@mic_checker, lass dir ruhig Zeit :wink:

 

[mic_checker]

Ich denke mal wir müssen gar nicht erst großartig weiter testen wenn klar ist das manchmal was falsches raus kommt (was ja eigentlich klar war).

Du könntest dich jetzt für deine Variante entscheiden, die LCS holen oder dir noch weitere Verfahren anschauen.

Ohne die von Wildcard mehrfach erwähnten "Einschränkungen" wirst du aber wohl nicht leben können (vorerst *g*)

Hab noch was anderes, was vielleicht helfen könnte:

Die Damerau-Levenshtein-Metrik gibt nichts Anderes als die Zahl der Unterschiede von 2 Wörtern an. Sie ist also ein Maß für die Ähnlichkeit zweier Wörter.

http://www.doublefind.de/technology.html

Hört sich doch net schlecht an oder? Mal gucken wie sich das implementierungstechnisch umsetzen lässt.

 

[The_S]

Hey!!! Google macht mir Konkurenz!!! Manchmal wird hier auf meinem Thread rechts oben ein Link zu einem 10-Fingersystem-Lernprogramm angezeigt http://www.neuber.com/schreibtrainer/index.html?ref=google.

Zurück zum Thema:

Ich denke mal, dass Algorithmus nur bestimmte Fehler nicht beachtet. Wenn ich allerdings weiß, wo der Fehler liegt, könnte ich das noch einbauen und ihn vielleicht (nahezu :wink: ) Perfekt machen.

Den Link schau ich mir jetzt gleich mal an.

[edit] Leider findet man im www nicht sonderlich viel zur Damerau-Levenshtein-Metrik. Kennt jemand ne gute seite?

 

[mic_checker]

Hab auch nicht viel gefunden.

Aber ich hab mich noch mal an den Levenshtein gemacht:

   public static int levenshtein() {
   	/* Schritt 1 */
   	String s = "HIRSCH";
	   String t = "HIER";
   	int n = s.length();
	   int m = t.length();
	   int cost,minimum;
	   char chs,cht;
	   
	   if(n == 0 || m == 0)
	   	return 0;
		
		int hoehe = n + 1;
		int breite = m + 1;
		
		int[][] matrix = new int[hoehe][breite];
		
		/* Schritt 2 */
		for(int i = 0;i < hoehe;i++)
			matrix[i][0] = i;
	
		for(int j = 0;j < breite;j++)
			matrix[0][j] = j;
			
		/* Schritte 3 - 6 */
		for(int i = 1;i < hoehe;i++) {
			chs = s.charAt(i-1);
			
			for(int j = 1;j < breite;j++) {
				cht = t.charAt(j-1);
				
				if(chs == cht)
					cost = 0;
				else
					cost = 1;
				
				/* Berechnung des Minimums */	
				minimum = matrix[i-1][j]+1;
				
				if((matrix[i][j-1]+1) < minimum)
					minimum = matrix[i][j-1]+1;
				
				if((matrix[i-1][j-1] + cost) < minimum)
					minimum = matrix[i-1][j-1] + cost;

				matrix[i][j] = minimum;
			}
		}
		
		
		/*
		* Ausgabe der Matrix
		*/
		for (int a = 0; a < matrix.length; a++) {
         for (int b = 0; b < matrix[0].length; b++) {
            System.out.print(matrix[a][b]);
         }
         System.out.println();
      } 
		
		return matrix[n][m];	
   }

Hab nachher gesehen das ne Implementierung einige Zeilen drunter stand, meine müsste aber auch stimmen, da es nach der Algorithmus Beschreibung der selben Seite gemacht wurde (und nur hier und da etwas abweicht).

Die Ausgabe der Matrix kannst du natürlich raus nehmen, hab ich nur testweise reingemacht.

Vielleicht klappt es damit besser als mit LCS.

 

[The_S]

Levenshtein bin ich irgendwie nie richtig durchgestiegen ... Deswegen, was gibt er mir zurück? Was soll ich damit anfangen?