T9 // Wörterkorrektur

Hallo =)

Wieder stellt sich mir ein Problem :/ Ich versuche ein Programm zu schreiben, dass falsch geschriebene Wörter automatisch korrigiert bzw. das nächst wahrscheinlichste Wort aus einer txt. Datei findet...

Ich habe schon ein wenig angefangen und suche noch Anregungen/Ideen wie man an das Problem rangeht...


Main-Programm sollte iwie so anfangen

Java:
public class ForumName {

         public static void main(String[] args) {
  
        
        
         String Entryname = "eter";
         ArrayList<Name> names  = ReadTxt.ReadTxt();
        
         int Counter[] = new int[names.size()];
        
        
        boolean Test = TestName.TestName(Entryname, names);
        
        if(Test){
            
            System.out.println("Entryname true");
            
        }
        
        else {
            System.out.println("Entryname false");
            
/*         for (int j = 0; j< names.size() ; j++){

             Counter[j] = 0;
            for (int i = 0; i <  Entryname.length() ;i++ ){
                if (names.get(j).getName().length() == Entryname.length() ) {
                    if (Entryname.charAt(i) ==  names.get(j).getName().charAt(i)) {
                        System.out.println("Buchstabe " + i + " stimmt " + names.get(j).getName());
                        Counter[j]++;
                        System.out.println(names.get(j).getName() + " hat " + Counter[j] + " Übereinstimmungen.");
                    }
                
                  else{}
                    }
                else{}
                }
              }
*/
       }
   }
}


Java:
public class Name {
    
    private String name;


    public Name(String name){
        this.name = name;

    }


    public String getName() {
        return name;
    }


    public void setName(String name) {
        this.name = name;
    }
  
}

Java:
public class ReadTxt {
    
    
    public static ArrayList<Name> ReadTxt() {

        File file = new File("C:\\Temp\\Namen.txt");

        BufferedReader br = null; 
        ArrayList<Name> names = new ArrayList<Name>();
        try {
            br = new BufferedReader(new FileReader(file));
            String line;
            while ((line = br.readLine()) != null) {

                String[] parts = line.split("\t");         //Freiheiten für spätere Nachträge in der
                Name name = new Name(parts[0]);   // .txt Datei offen zu halten
                names.add(name);
               

            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (br != null) {
                try {
                    br.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
        return names;
    }
}

Java:
public class TestName {
    
    public static boolean TestName (String Entryname, ArrayList<Name> names){
         
         boolean test = false;
         
                 for (int i= 0 ; i < names.size();i++){
                     
            if (Entryname.equalsIgnoreCase(names.get(i).getName()) ) {
               
                         test = true;
                     }
            
            else { 

            }

            
         }
                 
         return test;
     }
}


Wäre dankbar für jede Idee :)

Best Grüße
Der Problematiker :)
 
Oh ja, sehr schöne Wahrscheinlichkeitsberechnung nur brauch ich es sogar noch ein wenig spezieller z.B. wenn der User einen Tippfehler begeht mit Sonderzeichen -> "#" "%" etc sollten umgewandelt werden und/oder gelöscht werden.

Aber schon einmal Danke für den Link :)
 

timbeau

Gesperrter Benutzer
Ich denke ein Preprocessing braucht man in jedem Fall. Also alle nicht Buchstaben und Zahlen raus. Aber den User auch nicht ZU sehr an die Kandare nehmen. Wenn ich "fr34K*#" suchen will, will ich "fr34K*#" suchen und nicht "meinten sie "frk"?
 
Um Dein Beispiel aufzufassen:

Ja doch es sollte "frk" oder "freak" rauskommen, da ich keine Namen kenne, in denen Zahlen/Sonderzeichen vorkommen :)

Aber ja ich denke ich müsste als erstes schauen ob der Name der eingegeben wurde nicht schon richtig ist (siehe oben Code, das funktioniert bereits) und danach eine Auswahl an Sonderzeichen entfernen und alle Stellen dahinter um eins nach vorne verschieben (?).

Bzw ist es ein Problem vorher Sonderzeichen zu entfernen weil die Zeichenkettenlänge verändert wird und man nicht weiß ob es ein Tippfehler statt Buchstabe oder ein zusätzliches Zeichen ist ...???

Wäre ein Ansatz.
 
Zuletzt bearbeitet:

timbeau

Gesperrter Benutzer
Ein Ansatz aber was ist wenn es "freak" und "fr34k" gibt? Von Real-Namen war ja bisher nicht die Rede. Ansonsten halt ein ReplaceAll im Preprocessing mit Regex. Du wirst bei guten Tests feststellen, dass grade bei Namen das System seine Schwächen haben wird, die man aber fast nie beseitigen kann. Wörter aus dem Duden sind da schon einfacher.

Schreib dir auf jeden Fall mal nen Test mit 10 Wörtern die umgewandelt werden sollen. Dann kannst du diese Liste jedes Mal durchlaufen und automatisch testen ob sie korrekt umgewandelt wurden.

Eingabe ebenfalls so gut wie möglich automatisieren, z.B. von jedem Namen erst 1 Buchstaben weglassen, dann 1 Buchstaben tauschen usw. Nicht anfangen manuell erst "eter", dann "petr" usw zu testen.

Edit: Der Hammingabstand dürfte zwischen "eter" und "Oeter" keinen Unterschied machen.
 

timbeau

Gesperrter Benutzer
Das kann sein, ich hatte auch mal was von einem anderen Abstand gehört, finde den aber gerade nicht. Lief aber ähnlich ab, wieviele Operationen braucht man um das Wort in das korrekte Wort zu transformieren. Die Probleme sehe ich da ähnlich wie du, woher weiß ich ob aus "eter" mit 5 Schritten "Peter" wird indem

e -> P = "Pter"
t -> e = "Peer"
e -> t = "Petr"
r -> e = "Pete"
" " -> r = "Peter"

oder einfach ein P vorne dran gestellt wird. Da gibts aber bestimmt was zu
 
Ich glaube es wird viele Verzweigungen/Bedingungen in dem Programm geben müssen.
Aber vielleicht hat ja auch jemand so etwas schon einmal geschrieben :)

Man muss das Rad nicht zweimal erfinden :)

Oder mehr Ideen zur Lösung des Problems :)


Java:
        if(Test){
            
            System.out.println("Name true");
            
        }
        
        else {
            System.out.println("Name false");
            Hamming.getHammingDistance(Entryname, names);
}

getHammingDistance funktioniert auch aber ich muss als erstes testen ob die 2 Wörter gleichlang sind...


Java:
public static int getHammingDistance(String Entryname,ArrayList<Name> names)
    {
        int counter = 0;
        for(int i = 0; i<names.size(); i++){
 
        if (Entryname.length() != names.get(i).getName().length())
        {
            counter = 9999;
        }
        else{
            counter = 0;
            for(int j = 0 ; j < Entryname.length(); j ++)
            {
            if (Entryname.charAt(j) != names.get(i).getName().charAt(j)) {
                 counter++;
            }
            else{}
             } 
            
            }    
            System.out.println(names.get(i).getName() +" mit Hamming Abstand " + counter);
                                            }
        return counter;
    }
 
Zuletzt bearbeitet:

MiMa

Top Contributor
Hallo,

ja das Problem wollte ich auch demnächst angehen, wenn ich mit den Büchern über Tika und Lucene fertig bin. Bei mir sind die Texte, die untersucht werden sollen nicht von Menschen geschrieben, sondern kommen aus einer OCR Texterkennung. Und da kommt es auch vor, das die Wörter nicht richtig erkannt werden.

Meine Lösungsidee ist, das man die Texte mit einem digitalen Wörterbuch in der jeweiligen Sprache abgleicht, oder eine Semantische Applikation schreibt.

Mi
 

MiMa

Top Contributor
Das weis ich noch nicht so genau, der Inhalt der Bücher haben mir aber gezeigt das ich jetzt einiges anders mache als ich gedacht hatte. Lucene, Tika und UIMA sind da schon sehr hilfreiche Tools.

Apache UIMA
UIMA ? Wikipedia

wäre wohl das richtige Projekt.
Es steht bei mir nach Lucene an.

Mi
 
Das Problem liegt nicht darin zu schauen, wie viele gleiche Stelle zwei verglichene Wörter zusammen haben und dann abzuschätzen (wenn es 2 gleich große Wahrscheinlichkeiten gibt, welches nehmen, da meine Liste begrenzt ist und die Wahrscheinlichkeit einer solchen Situation sehr gering ist) sondern darin, was man mit Tippfehler wie "#" macht. Löschen ? Ersetzen ? Löschen und Ersetzen ? Stelle im Wort verschieben ?

Da ich mit Hamming angefangen habe kommen weiter Probleme dazu. Es können nur gleichlange Zeichenketten vergleichen werden ->
wie können 2 nicht gleichlange Zeichenketten verglichen werden ? d.h. ein Zeichen dazu erstellen aber an welcher Stelle ? etc etc etc
 
Java:
     public static Name characterComparison(String Entryname, ArrayList<Name> names) {
         
         
         for(int j = 0; j < names.size(); j++){
             StringBuffer a = new StringBuffer (names.get(j).getName());
             int counter =0;
             names.get(j).setcharComHamming(0);
             int i = 0;
             while(i < Entryname.length()){
                 for(int k = 0 ; k < a.length(); k++){
                 if(Entryname.charAt(i) == a.charAt(k)){
                     counter++;
                     names.get(j).setcharComHamming(counter);
                     a.delete(k, k+1);
                     a.replace(k, k, "^");
                     break;
                 }
                }
               i++;
             }
             
         }
         
        return null;     
  }

Ich habe nur nachgeschaut welche buchstaben drin sind und wie oft und mit den buchstaben der einzelnen namen aus der liste verglichen. Dadurch kann man die Länge des Wortes, Sonderzeichen, Buchstabendreher etc umgehen.

EDIT:

Man musste nur beachten..

eter != Peter

1. man muss darauf achten, dass das erste "e" nicht doppelte gezählt wird weil Peter 2 "e" enthält
-> schleifenabbruch nach detektion
2. man muss darauf achten das das 2 "e" bei "eter" nicht das erste "e" bei Peter zwei mal zählt
-> StringBuffer


sry timbeau =)
 
Zuletzt bearbeitet:

timbeau

Gesperrter Benutzer
Hast du auch sowas wie

"Oeter"

"ePter"

"Pter"?

Kommt da immer "Peter" raus?

Bzw was passiert wenn du das gleiche mit

"Martina"

und "Nartina" etc machst? Passen deine Tests auf alle Worte bzw wie groß ist die Fehlerrate?
 
Die Folge der Zeichenkette ist völlig egal. Auch wenn ein Sonderzeichen mit "reingerutscht" ist, ein buchstabe vergessen wurde (d.h. Die Zeichenkettelänge nicht korrekt ist) oder sonstiges.

Natürlich wird er bei z.b.

Richtige Namen: Sven, Svenja

und eingetippten Namen: vSen, #Sven, Sv en , etc

Dir eine Auswahl zwischen den beiden oben genannten geben.
 
Meine weitere Überlegung..

Mit dem Algo den ich jetzt geschrieben habe, bekommt man eine Auswahl an möglichen Worten vorgegeben.
Hat jemand eine Idee die (nur noch wenige Möglichkeiten) noch vorgegebenen Wörter zu filtern?
z.b. man hat vSen eingegeben. der Algo spuckt 2 Möglichkeiten heraus wie Sven und Svenja da beide Wörter gleichviele Übereinstimmungen haben.

Wie könnte ich nun das richtige Wort gerausfiltern ? (Wobei das Problem ein schlechtes Beispiel ist da nun die Frage ist, ist das "ja" von Svenja vergessen worden/Tippfehler oder wollte man Sven schreiben)
 

MiMa

Top Contributor
Da es sich um Namen Handelt, die weder in der Rechtschreibung noch in Wörterbücher zu finden sind, kommt mir da die Idee eine Namensdatenbank an zu legen, mit der abgeglichen wird.
Denn das wird man niemals über einen Algorithmus allein lösen können.

Mi
 

MiMa

Top Contributor
OK, dann hast du schon eine Quelle mit der die Namen abgeglichen werden kann.
Ich setze das ein ähnliches Verfahren ein um in Dokumente bestimmte Wörter zu finden.

Mi.
 

MiMa

Top Contributor
Ja das wünsche ich mir auch manchmal, aber leider läßt sich das in bestimmten Situationen auch nicht vermeiden. Der Unterschied zwischen Sven und Svenja ist ja teilweise identisch und woher soll der Algorithmus wissen, um welches Geschlecht es geht.

Der Gedanke liegt nahe zu erkennen ob der Inhalt an eine männliche oder weibliche Person gerichtet ist.
Das wäre eine Option, die mir so spontan einfällt.

Ich kämpfe auch zur Zeit mit dem Problem, dass ich verschiedene Datumsangaben habe und dann das richtige heraus ermitteln muss, was eine echt knifflige Angelegenheit ist.

mi
 

MiMa

Top Contributor
Du siehst das falsch, das Gehirn ist da, was dem PC fehlt ist die Ausbildung. :D
Klasse 1 bis 13 und dann noch das Studium. :rtfm:
Das musst du übernehmen ;( weil der ist doof wie Bohnenstroh.
Am besten verknüpfe all das ganze wissen was Du bekommen kannst in die Applikation, dann wird es schon werden. :toll:

mi
 

MiMa

Top Contributor
Ich selbst versuche demnächst Apache Lucene und UIMA zusammen mit Semantik zu verwenden, damit die Texte auch der Inhaltlich Sinn erkannt und Strukturiert wird.

mi
 

Oben