Neue Wörter bilden

J

JavaAnda

Gast
Hallo,

ich verfolge folgendes Ziel:
Ich soll ein Programm erstellen, dass aus einem kurzen Eingabewort eine überschaubare Menge von Anagramen generiert.
Dazu habe ich mir gedacht, ein Wörterbuch in Textform als Grundlage zu nehmen. Jedoch fehlt mir momentan der Ansatz, wie ich die Wörter generieren lassen soll. Klar ist das ich zunächst das Eingabewort in verschiedene chars aufteile und erstmal nach der Länger gucke. Aber wie gehe ich dann voran? Hat jemand da eine Idee? Über jede Antwort freue ich mich sehr. Viele Grüße
 
J

JavaAndaa

Gast
Als Wörterbuch könnte ich z.B. von Firefox das deutsche Wörterbuch nehmen und die dic Datei einfach als Textdokument abspeichern, oder welches Format wäre da besser geeignet? Die Wörter stehen zweilenweise in dieser Liste.
 

Marco13

Top Contributor
Wenn man eine Datei hat, wo Zeilenweise Wörter drinstehen, kann man die auch Zeilenweise einlesen und in ein Set packen. Für die Permutationen gäbe es vielleicht speziellere (und dann auch elegantere) Ansätze, weil es ja nur um Strings geht. Groß/Kleinschreibung muss man halt noch beachten. (D.h. man muss beachten, dass man sie ignorieren muss :D)


Hm... is das 'ne Hausaufgabe? Ach, egal, ich wollt's mal ausprobieren. Das ist nur gehackt. Solltest du so nicht abgeben, falls es eine Hausaufgabe ist...
Java:
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;
import java.io.*;
import java.net.*;

class AnagramSearch extends JFrame
{

    public static void main(String args[])
    {
        SwingUtilities.invokeLater(new Runnable()
        {
            public void run()
            {
                new AnagramSearch().setVisible(true);
            }
        });
    }


    private Set<String> words = null;
    private JTextField input = null;
    private JTextArea output = null;

    public AnagramSearch()
    {
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        getContentPane().setLayout(new BorderLayout());


        JPanel p = new JPanel(new GridLayout(1,3));
        getContentPane().add(p, BorderLayout.NORTH);

        JButton b = new JButton("Read and block GUI :-)");
        b.addActionListener(new ActionListener()
        {
            public void actionPerformed(ActionEvent e)
            {
                read("http://wortschatz.uni-leipzig.de/Papers/top10000de.txt");
            }
        });
        p.add(b);

        input = new JTextField("Angel");
        p.add(input);

        b = new JButton("Generate");
        b.addActionListener(new ActionListener()
        {
            public void actionPerformed(ActionEvent e)
            {
                generate();
            }
        });
        p.add(b);


        output = new JTextArea();
        getContentPane().add(new JScrollPane(output));
        setSize(600, 600);
    }



    private void read(String urlString)
    {
        words = new HashSet<String>();
        try
        {
            URL url = new URL(urlString);
            InputStream is = url.openStream();
            BufferedReader br = new BufferedReader(new InputStreamReader(is));

            while (true)
            {
                String s = br.readLine();
                if (s == null)
                {
                    break;
                }
                words.add(s.trim().toLowerCase());
            }
        }
        catch (Exception e)
        {
            e.printStackTrace();
        }
        output.append("Read "+words.size()+" words\n");
    }

    private void generate()
    {


        String inputString = input.getText();
        output.append("Anagrams of "+inputString+":\n");

        inputString = inputString.trim().toLowerCase();

        String inputArray[] = new String[inputString.length()];
        for (int i=0; i<inputArray.length; i++)
        {
            inputArray[i] = ""+inputString.charAt(i);
        }
        PermutationIterable<String> pi = new PermutationIterable<String>(inputArray);
        for (String s[] : pi)
        {
            String ss = "";
            for (int i=0; i<s.length; i++)
            {
                ss += s[i];
            }
            if (words.contains(ss))
            {
                output.append(ss+"\n");
            }
        }
    }



}



/**
 * A class providing an iterator over all permutations of a set of
 * elements. For a set S with n=|S|, there are m=n! different
 * permutations. Example: <br />
 * <pre>
 * S = { A,B,C }, n = |S| = 3
 * m = n! = 6
 *
 * Permutations:
 * [A, B, C]
 * [A, C, B]
 * [B, A, C]
 * [B, C, A]
 * [C, A, B]
 * [C, B, A]
 * </pre>
 *
 * @author [url]http://www.java-forum.org/members/Marco13.html[/url]
 */
class PermutationIterable<T> implements Iterable<T[]>
{
    private T input[];
    private int numPermutations = 0;

    public PermutationIterable(T... input)
    {
        this.input = input.clone();
        numPermutations = factorial(input.length);
    }

    public Iterator<T[]> iterator()
    {
        return new Iterator<T[]>()
        {
            int current = 0;

            public boolean hasNext()
            {
                return current < numPermutations;
            }

            // Adapted from [url=http://en.wikipedia.org/wiki/Permutation]Permutation - Wikipedia, the free encyclopedia[/url]
            public T[] next()
            {
                T result[] = input.clone();
                int factorial = numPermutations / input.length;
                for (int i = 0; i < result.length - 1; i++)
                {
                    int tempIndex = (current / factorial) %
                        (result.length - i);
                    T temp = result[i + tempIndex];
                    for (int j = i + tempIndex; j > i; j--)
                    {
                        result[j] = result[j - 1];
                    }
                    result[i] = temp;
                    factorial /= (result.length - (i + 1));
                }
                current++;
                return result;
            }

            public void remove()
            {
                throw new UnsupportedOperationException(
                    "May not remove elements from a permutation");
            }
        };
    }



    /**
     * Utility method for computing the factorial n! of a number n.
     * The factorial of a number n is n*(n-1)*(n-2)*...*1, or more
     * formally:<br />
     * 0! = 1 <br />
     * 1! = 1 <br />
     * n! = n*(n-1)!<br />
     *
     * @param n The number of which the factorial should be computed
     * @return The factorial, i.e. n!
     */
    public static int factorial(int n)
    {
        int f = 1;
        for (int i = 2; i <= n; i++)
        {
            f *= i;
        }
        return f;
    }

}
 
K

KYL3R

Gast
Im Prinzip, musst du nur die Eingabe Splitten, nehmen wir an es sei ein zusammenhängendes Wort, und die einzelnen Buchstaben per random() vermischen, dann hast du ein Anagramm. Wenn du Sinnvolle Wörter haben willst, musst du natürlich iwie ne Datenbank, oder ein Wörterbuch haben, vllt auf eines zugreifen, wörter mit gleicher Länge und Buchstaben suchen und vergleichen, das wär ziemlich komplex, verglichen mit dem ersten Schritt
 

0x7F800000

Top Contributor
nur so als tipp, um schneller sinnvolle wörter zu erstellen:
scanne paar gigabyte von text, berechne die wahrscheinlichkeit für "nach buchstabe X kommt Y", und probiere immer zuerst di kombinationen aus, die mit höchst möglichen wahrscheinlichkeit nach einem korrekten wort klingen. Schließlich gibt es ja sowas wie Silben, die öfters auftreten, als sowas wie "gzr" oder "plj" oder "hcs"...
 

guni

Bekanntes Mitglied
ich würde mir wahrscheinlich das wörterbuch nicht vollständig in ein set laden.
stattdessen denke ich, dass es mehr sinn macht, wenn du pro anfangsbuchstabe ein eigenes set machst.

wenn du dann zum beispiel ein wort mit 8 buchstaben hast, dann musst du für deine Anagramme im worst case (kein buchstabe kommt in deinem wort mehrfach vor) 8 sets durchsuchen.
vielleicht gibt es noch weitere kriterien, so dass du die sets noch feiner aufteilen kannst (nicht nur nach anfangsbuchstaben) ...

mfg, guni
 

faetzminator

Gesperrter Benutzer
Man kann das Problem ganz einfach und schnell lösen:
Alle Wörter müssen in irgendeiner Form zur Verfügung stehen, dazu ein "Fingerprint", bei welchem alle Buchstaben/Zeichen alphabetisch geordnet sind. So würde man für HAUS noch "AHSU" speichern. Mit dem eingegebenen Wort macht man das selbe und holt alle Wörter, welche den gleichen "Fingerprint" haben.
Gespeichert in einer SQL DB mit Indexing auf den Fingerprint würde eine Transformation und eine Query bedeuten.
 

0x7F800000

Top Contributor
ich würde mir wahrscheinlich das wörterbuch nicht vollständig in ein set laden.
stattdessen denke ich, dass es mehr sinn macht, wenn du pro anfangsbuchstabe ein eigenes set machst.

wenn du dann zum beispiel ein wort mit 8 buchstaben hast, dann musst du für deine Anagramme im worst case (kein buchstabe kommt in deinem wort mehrfach vor) 8 sets durchsuchen.
vielleicht gibt es noch weitere kriterien, so dass du die sets noch feiner aufteilen kannst (nicht nur nach anfangsbuchstaben) ...
Und das soll wozu gut sein? Mehr codezeilen & langsamerer code?

Man kann das Problem ganz einfach und schnell lösen:
Alle Wörter müssen in irgendeiner Form zur Verfügung stehen, dazu ein "Fingerprint", bei welchem alle Buchstaben/Zeichen alphabetisch geordnet sind. So würde man für HAUS noch "AHSU" speichern. Mit dem eingegebenen Wort macht man das selbe und holt alle Wörter, welche den gleichen "Fingerprint" haben.
Gespeichert in einer SQL DB mit Indexing auf den Fingerprint würde eine Transformation und eine Query bedeuten.
Das macht performancemäßig zumindest Sinn. Funktioniert allerding nur, wenn man an der Datenbank rumfummeln darf. Ich habe soeben mal versucht, minimal speziellere Begriffe in einer Datenbank mit (angeblich) 700 Mio Wörtern zu finden, und habe festgestellt, dass 700 Mio Wörter wohl ein ziemlich platter Wortschatz ist: kaum etwas wurde gefunden. Daher halte ich das für nicht wirklich praktikabel, eine noch wesentlich größere Datenbank sich auf die festplatte zu holen... Wenn man nur die alltäglichen Wörter nimmt, die jedem ein Begriff sind, dann schafft man das wahrscheinlich schon. Wenn man aber auch griechische Mythologie, medizinisches Fachjargon, wirtschaftsmathematische Grundbegriffe, hinduistische Gottheiten und polnische Namen (in je 3 Schreibweisen) haben will, dann dürfte es imho schwierig werden. Da ist es schon einfacher, bei google nachzufragen, ob es das eine oder das andere Wort gibt.
 
Q

Quurks

Gast
Kannst du mir mal den Link zu dieser Datenbank geben? Würde mich stark für ein anderes Projekt interessieren.
Wobei ich stark bezweifle, dass die soviel hat da 700.000.000 Wörter * 5 Bytes pro wort = 3,5 GB allein für die Daten, ohne die Datenbank.

Zum Thema: ich würde da das Eingabewort kurz ist sämtliche Kombinationen der Buchstaben bilden und diese in einer Datenbank bzw Textdatei suchen
Bsp:
2 Zeichen=>2 Suchen
3 Seichen=>6 Suchen
4 Zeichen=>24 Suchen
5 Zeichen=>120 Suchen
6 Zeichen=>720 Suchen
Alles darüber hinaus wird als lang definiert
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
N neue Objektnamen durchlaufen Allgemeine Java-Themen 12
C Java11+ JavaFX HtmlEditor ContextMenu neue MenuItems hinzufügen Allgemeine Java-Themen 5
N Apache POI/ neue Reihe in Excel mit einem Button Allgemeine Java-Themen 2
B Java Mail: Prüfung auf neue Emails Allgemeine Java-Themen 1
ralfb1105 Blöcke aus Datei filtern/suchen und in neue Datei schreiben Allgemeine Java-Themen 10
G Excel Tabelle lesen und in neue Excel Tabelle einfügen Allgemeine Java-Themen 11
E neue Lizenzpflicht Java Allgemeine Java-Themen 10
T ändern neue Java Versionen was an der Programmiersprache? Allgemeine Java-Themen 15
K Mit Button neue Klasse öffnen Allgemeine Java-Themen 9
C Classpath Neue Klasse über einen Button ausführen Allgemeine Java-Themen 3
KeVoZ_ Nacheinander folgende Strings in Textdokument auf neue Zeile schreiben Allgemeine Java-Themen 6
J Java Software Compare Files und Neue File erstellen Allgemeine Java-Themen 0
K Einfaches Array in 2 neue aufteilen. Allgemeine Java-Themen 2
N Neue Software in Java 7 oder 8? Allgemeine Java-Themen 3
K Neue Elemente in JList einfügen Allgemeine Java-Themen 2
K Methode soll neue Buttons erstellen Allgemeine Java-Themen 5
S Best Practice verschiedene Exceptions fangen und neue Exception erzeugen Allgemeine Java-Themen 11
W Vergleich eines Datenträgers auf neue Dateien Allgemeine Java-Themen 14
N Datenstrukturen an neue Klasse übergeben Allgemeine Java-Themen 16
M Neue Instanz/Kopie einer unbekannten Klasse Allgemeine Java-Themen 7
F Wie zur Laufzeit ganz neue Objekte erzeugen? Allgemeine Java-Themen 5
S Neue Instanz eines Objekts erzeugen - Konstruktor erhaelt Parameter. Allgemeine Java-Themen 5
J Was ist schneller? Neue Variable oder neuer Wert speziell int Allgemeine Java-Themen 3
T Log4J: Bei Programmstart immer eine neue LogDatei erzeugen Allgemeine Java-Themen 9
J Text einer .csv Datei einlesen und Zeile in NEUE Zeile hänge Allgemeine Java-Themen 1
B Logs - txt-Datei neue Zeile anfuegen, neue Datei erstellen Allgemeine Java-Themen 6
S Zweidimensionales Array neue Zeile erzeugen Allgemeine Java-Themen 3
P Neue Zeile Plattformunabhängig Allgemeine Java-Themen 3
W Programm prüft auf webserver ob neue version vorhanden? Allgemeine Java-Themen 3
I Neue Klassenbibliothek in Klassenpfad einbinden Allgemeine Java-Themen 3
B Ausgabe auf stdout "löschen" und dafür neue Ausgab Allgemeine Java-Themen 10
M neue Thread in neuem Fenster Allgemeine Java-Themen 3
M neue Textdatei DOS/Unix-Format Allgemeine Java-Themen 11
WMaerz Der neue JDK 6 enthält keine javac.exe, tool.jar usw. Allgemeine Java-Themen 6
J Neue Objekte werden nciht angezeigt Allgemeine Java-Themen 2
T iText + neue Seite Allgemeine Java-Themen 14
A Kann keine neue Klasse erstellen. Allgemeine Java-Themen 3
G Programm erzeugt ständig neue Strings . Allgemeine Java-Themen 2
G Neue Warenwirtschaft aber sehr langsam! Allgemeine Java-Themen 3
M in jar eine neue datei per JarOutputStream hinzufügen Allgemeine Java-Themen 2
B Braucht man die neue VM 1.5 Allgemeine Java-Themen 3
F neue klassen einbinden Allgemeine Java-Themen 3
F Neue Bibliothek dem JDK hinzufügen Allgemeine Java-Themen 5
AGW in Java-Code plötzlich ein paar Wörter in Rot Allgemeine Java-Themen 2
C Kürzeste Wörter bestimmen Allgemeine Java-Themen 8
K Java Standardbib/reservierte Wörter erweitern Allgemeine Java-Themen 1
B Java Audio in Wörter/Phonems aufteilen Allgemeine Java-Themen 0
OlafHD Prozentualer Abgleich von zweit Sätzen/Wörter Allgemeine Java-Themen 5
J Mehrere Wörter getrennt in eine Array einlesen, wie ? Allgemeine Java-Themen 7
B Per Buttonklicks einer Liste Wörter hinzufügen - Wie umsetzen? Allgemeine Java-Themen 11
D Wörter aus Datei einlesen Allgemeine Java-Themen 9
K Wörter in Strings zählen Allgemeine Java-Themen 7
S Speichern/Laden/Hinzufügen/Löschen der Array-Wörter; unerwartete Ausgabe Allgemeine Java-Themen 6
T Wörter Vergleichen Allgemeine Java-Themen 3
G Regulärer Ausdruck für 2 Wörter Allgemeine Java-Themen 3
D Wort in Text mit >100.000 Wörter finden Allgemeine Java-Themen 7
S Wörter ohne Leerzeichen erkennen Allgemeine Java-Themen 5
L Textdatei nach Wörter durchsuchen Allgemeine Java-Themen 3
J String Wörter zählen Allgemeine Java-Themen 4
M Wörter Algorithmus Allgemeine Java-Themen 7
M JTextPane Mausklick auf bestimmte Wörter startet Aktion Allgemeine Java-Themen 8
S Wörter ersetzen mit regex Allgemeine Java-Themen 11
J Konstrukt um alle Paare und Tripel einer Punkte-Menge bilden Allgemeine Java-Themen 12
A MD5 Summe von einer CDROM Bilden Allgemeine Java-Themen 3

Ähnliche Java Themen

Neue Themen


Oben