Datentypen Verdrehte Wörter wieder herstellen

[CptK]

Servus, ich habe einen Text bestehen aus verdrehten Wörtern z.B.: "Blad feil ihr Auge auf eine klenie Gaslbüchse, die unter dem Tcsihe lag". Der erste und der letzte Buchstabe sind im Wort jeweils richtig, was heißt mich interessieren nur die Wörter mit mehr als 3 Zeichen. Zudem habe ich eine Wörterliste (pro Zeile ein Wort). Jetzt möchte ich ein Programm haben, dass mit Hilfe der Liste die verdrehten Wörter erschließt.
Ich weiß leider nicht genau wie ich da rangehen soll, bin also für jede Hilfe dankbar.

Ich habe das jetzt folgendermaßen versucht:

private ArrayList<String> words = new ArrayList<String>();
    private ArrayList<String> untwistedWords = new ArrayList<String>();
    private ArrayList<String> wörterbuch = new ArrayList<String>();

private void untwist(int wordNr) {
        char n[] = words.get(wordNr).toCharArray();
        if(n.length > 3) {
        
            for(int i = 0; i < wörterbuch.size(); i++) {
                char w[] = wörterbuch.get(i).toCharArray();
                if(n.length == w.length) {
                    if(n[0] == w[0]) {
                        if(n[n.length-1] == w[w.length-1]) {
                        
                        }
                    }
                }
            }
        
        } else {
            untwistedWords.add(words.get(wordNr));
        }
    }

Ich wandel mir die Wörter in Chararrays um und gehe dann die Wörterliste durch, ob die Wörter dort gleich lang sind und der erste und der letzte Buchstabe gleich sind. Das grenzt das Ganze zwar schon etwas ein, ist aber nicht genau genug. Jetzt würde ich einfach hingehen und überprüfen, ob alle Buchstaben von n[] enthalten sind.
Ich weiß jetzt aber leider nicht, wie ich das ganze am besten umsetzen soll.

 

[max40]

eine Möglichkeit die aber optimiert werden sollte, damit das sortieren nicht so oft gemacht werden muss:

 ...
if(n[n.length-1] == w[w.length-1]) {

    Arrays.sort(w, 1, w.length-1);
    Arrays.sort(n, 1, n.length-1);
    if (Arrays.equals(w,  n)){
        untwistedWords.add(wörterbuch.get(i));
        return;
    }
  
}
...

 

[Robat]

Wie schon in deinem anderen Thread geschrieben, kannst du hierzu die Levenshtein-Distanz benutzen.

public class Untangler {
    private List<String> dictionary;

    public Untangler(List<String> dictionary) {
        this.dictionary = dictionary;
    }

    public String untangleAndGet(String twistedSentence) {
        StringBuilder builder = new StringBuilder(twistedSentence.length());

        for (String word : twistedSentence.split(" ")) {
            if (word.length() > 3) {
                Optional<String> actualWord = dictionary.stream().min(Comparator.comparingInt(o -> computeLevenshteinDistance(word, o)));
                actualWord.ifPresent(builder::append);
            } else {
                builder.append(word);
            }
            builder.append(" ");
        }
        return builder.toString();
    }

    private int minimum(int a, int b, int c) {
        return Math.min(Math.min(a, b), c);
    }

    private int computeLevenshteinDistance(String first, String second) {
        int[][] distance = new int[first.length() + 1][second.length() + 1];

        for (int i = 0; i <= first.length(); i++) {
            distance[i][0] = i;
        }

        for (int j = 1; j <= second.length(); j++) {
            distance[0][j] = j;
        }

        for (int i = 1; i <= first.length(); i++) {
            for (int j = 1; j <= second.length(); j++) {
                int match = (first.charAt(i - 1) == second.charAt(j - 1)) ? 0 : 1;
                distance[i][j] = minimum(
                        distance[i - 1][j] + 1,
                        distance[i][j - 1] + 1,
                        distance[i - 1][j - 1] + match);
            }
        }

        return distance[first.length()][second.length()];
    }
}

An einem einfachen Beispiel getestet:

String sentence = "Java ist eine komplexe Programmiersprache die zur Entwicklung von Anwendungen geeignet ist.";
List<String> dictionary = Arrays.asList(sentence.split(" "));

Untangler entwister = new Untangler(dictionary);
String twistedSentence = "Jvaa ist eine kpomlxee Prorgmmaeirpsarhce die zur Enwtikclnug von Anwendungen geeignet ist.";

System.out.println("Original : " + sentence);
System.out.println("Twisted  : " + twistedSentence);
System.out.println("Entwisted: " + entwister.untangleAndGet(twistedSentence));

liefert folgende Ausgabe:

Original : Java ist eine komplexe Programmiersprache die zur Entwicklung von Anwendungen geeignet ist.
Twisted  : Jvaa ist eine kpomlxee Prorgmmaeirpsarhce die zur Enwtikclnug von Anwendungen geeignet ist.
Entwisted: Java ist eine komplexe Programmiersprache die zur Entwicklung von Anwendungen geeignet ist.

 

[Xyz1]

Sind die Buchstaben der Wörter eigentlich vermischt oder gedreht? Weil ich bin von gemischt ausgegangen....
Das ändert natürlich alles!

 

[Meniskusschaden]

Wie schon in deinem anderen Thread geschrieben, kannst du hierzu die Levenshtein-Distanz benutzen.

Das funktioniert noch nicht ganz richtig. Beispiel:

public static void main(String[] args) {
    String sentence = "Haftung Haltung Sichtung Dichtung";
    List<String> dictionary = Arrays.asList(sentence.split(" "));

    Untangler entwister = new Untangler(dictionary);
    String twistedSentence = "Hatlung Sxchtung Dichtugn";

    System.out.println("Original : " + sentence);
    System.out.println("Twisted  : " + twistedSentence);
    System.out.println("Entwisted: " + entwister.untangleAndGet(twistedSentence));
}

Ausgabe:

Original : Haftung Haltung Sichtung Dichtung
Twisted  : Hatlung Sxchtung Dichtugn
Entwisted: Haftung Sichtung Dichtung

Aus "Hatlung" hätte "Haltung" und nicht "Haftung" werden müssen, "Sxchtung" (x ist falsch) und "Dichtugn" (Endbuchtstabe nicht gleich) hätten gar nicht übersetzt werden dürfen.

Sind die Buchstaben der Wörter eigentlich vermischt oder gedreht? Weil ich bin von gemischt ausgegangen....

Ich bin von (auch mehrfachen) Verdrehungen ausgegangen, so dass die inneren Buchstaben letztendlich beliebig vertauscht sein können, aber in der jeweils korrekten Anzahl vorhanden sein müssen.

 

[CptK]

Also es soll so sein, dass die Wörter so geändert werden, dass der erste und der letzte Buchstabe gleich bleiben und die Wörter in der Mitte werden untereinander getauscht, jedoch nicht mit anderen Wörtern.
Das Wort "Hallo" zum Beispiel ist getwistet also "Hlalo" oder "Hllao".

 

[Robat]

Das mit den Endbuchstaben hab ich ganz überlesen. Jetzt sollten eigentlich alle Fälle abgedeckt sein, oder?

public class Untangler {

    private List<String> dictionary;

    public Untangler(List<String> dictionary) {
        this.dictionary = dictionary;
    }

    public String untangleAndGet(String twistedSentence) {
        StringBuilder builder = new StringBuilder(twistedSentence.length());

        for (String word : twistedSentence.split(" ")) {
            Optional<String> actualWord = dictionary.stream()
                    .filter(otherWord -> hasMinimumLength(otherWord) &&
                            haveSameLetters(word, otherWord) &&
                            areSurroundedWithSameLetters(word, otherWord))
                    .min(Comparator.comparingInt(o -> computeLevenshteinDistance(word, o)));
            actualWord.ifPresentOrElse(builder::append, () -> builder.append(word));
            builder.append(" ");
        }
        return builder.toString();
    }

    private boolean hasMinimumLength(String word) {
        return word.length() > 3;
    }

    private boolean areSurroundedWithSameLetters(String firstWord, String secondWord) {
        return firstWord.charAt(0) == secondWord.charAt(0) &&
                firstWord.charAt(firstWord.length() - 1) == secondWord.charAt(secondWord.length() - 1);
    }

    private boolean haveSameLetters(String firstWord, String secondWord) {
        char[] lettersFirstWord = firstWord.toCharArray();
        char[] lettersSecondWord = secondWord.toCharArray();
        Arrays.sort(lettersFirstWord);
        Arrays.sort(lettersSecondWord);

        return Arrays.equals(lettersFirstWord, lettersSecondWord);
    }

    private int min(int a, int b, int c) {
        return Math.min(Math.min(a, b), c);
    }

    private int computeLevenshteinDistance(String first, String second) {
        int[][] distance = new int[first.length() + 1][second.length() + 1];

        for (int i = 0; i <= first.length(); i++) {
            distance[i][0] = i;
        }

        for (int j = 1; j <= second.length(); j++) {
            distance[0][j] = j;
        }

        for (int i = 1; i <= first.length(); i++) {
            for (int j = 1; j <= second.length(); j++) {
                int match = (first.charAt(i - 1) == second.charAt(j - 1)) ? 0 : 1;
                distance[i][j] = min(
                        distance[i - 1][j] + 1,
                        distance[i][j - 1] + 1,
                        distance[i - 1][j - 1] + match);
            }
        }

        return distance[first.length()][second.length()];
    }
}

 

[Meniskusschaden]

Jetzt sollten eigentlich alle Fälle abgedeckt sein, oder?

Glaube schon. Ich sehe jedenfalls keine Fehler mehr.

 

[Robat]

Das einzige wo es sehr wahrscheinlich nicht klappen würde, wäre bei Anagrammen die mit dem gleichen Buchstaben anfangen / aufhören. Zum Beispiel bei ["Asche", "Achse"] .. nur fällt mir da auch spontan nichts ein um das zu prüfen.

Original : Asche Achse
Twisted  : Acshe Ahcse
Entwisted: Asche Asche

 

[mihe7]

@Robat @Meniskusschaden was mir gerade nicht ganz klar ist: wenn ich davon ausgehe, dass die inneren Buchstaben zufällig vertauscht sind, was bringt dann die an

Optional<String> actualWord = dictionary.stream()
                    .filter(otherWord -> hasMinimumLength(otherWord) &&
                            haveSameLetters(word, otherWord) &&
                            areSurroundedWithSameLetters(word, otherWord))

anschließende Ähnlichkeitssuche?

 

[Meniskusschaden]

@Robat @Meniskusschaden was mir gerade nicht ganz klar ist: wenn ich davon ausgehe, dass die inneren Buchstaben zufällig vertauscht sind, was bringt dann die an
...
anschließende Ähnlichkeitssuche?

Ich weiß nicht, ob es hier wirklich etwas bringt. Kommt eben darauf an, ob in dem Anwendungsfall die Intensität der Unordnung umgekehrt proportional zur Treffer-Wahrscheinlichkeit ist. Als Anwender würde ich bei Mehrdeutigkeiten wahrscheinlich lieber die Alternativen sehen und selbst entscheiden.

 

[mihe7]

die Intensität der Unordnung umgekehrt proportional zur Treffer-Wahrscheinlichkeit ist.

ROFL - die Intensität der Unordnung werde ich mal untersuchen 🙂

 

[Robat]

@mihe7 das kommt drauf an wie das Wörterbuch aussieht denke ich. Sind denn nur Wörter im Wörterbuch, die auch im Satz vorhanden sind

 

[mihe7]

Ich seh das so: ich habe ein verdrehtes Wort, dann gibt es im Wörterbuch entweder

1. nur eine Permutation des Worts, dann ist die Sache eindeutig und ich kann mir die Ähnlichkeitssuche sparen,
2. oder mehrere Permutationen des verdrehten Wortes. Da aber alle Permutationen gleich wahrscheinlich sind, kann ich eine beliebige wählen und mir die Ähnlichkeitssuche sparen.

 

[Robat]

Jetzt merk ich erst worauf du (und wahrscheinlich auch der TE) hinaus willst.
Bin irgendwie davon ausgegangen, dass neben verdrehten Buchstaben auch falsche Buchstaben vorkommen können.. dem ist ja aber nicht so.

Indem Fall würde die Ähnlichkeitssuche tatsächlich überflüssig sein.

Bleibt die Frage wie man mit Anagrammen umzugehen hat. (Asche, Achse)

 

[mihe7]

Ja, jetzt reden wir vom gleichen.

Bleibt die Frage wie man mit Anagrammen umzugehen hat. (Asche, Achse)

Das ist doch genau der Punkt: ohne Kontext ist es nicht bestimmbar, ob Ahsce nun zu Asche oder Achse werden muss.
Daher:

Da aber alle Permutationen gleich wahrscheinlich sind, kann ich eine beliebige wählen

😀

 

[Xyz1]

Ich seh das so: ich habe ein verdrehtes Wort, dann gibt es im Wörterbuch entweder

Dann habe ich in diesem Video

ja schon die beste Lösung 😀 🙄

 

[max40]

Warum machst du erst ein Substring um dann das array zu sortieren?
Hast du dir überhaupt mein Lösungsvorschlag von gestern angeschaut?
Beim sort kannst du den Bereich mitgeben, welchen er sortieren soll.

 

[Xyz1]

Beim sort kannst du den Bereich mitgeben

Werde das heute Abend ca 21 Uhr berichtigen. 🙄

 

[mihe7]

Werde das heute Abend ca 21 Uhr berichtigen

😱 Im Video? 😛

 

[Xyz1]

Im Video?

Ja, Livestream möchtest Du doch nicht wirklich - oder? 🙄

 

[Xyz1]

Etwas eher 🙂

Beim sort kannst du den Bereich mitgeben, welchen er sortieren soll.

Ja ist besser....

    String sortB(String s) {
        char[] a = s.toCharArray();
        Arrays.sort(a, 1, a.length-1);
        return String.valueOf(a);
    }

Habe eine Benchmark hier erstellt.

Benchmark                 Mode  Cnt     Score   Error   Units
MyBenchmark.testMethodA  thrpt       1460.738          ops/ms
MyBenchmark.testMethodB  thrpt       1784.005          ops/ms

1/6 ungefähr....