# Neue Wörter bilden



## JavaAnda (29. Mrz 2010)

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


----------



## AlexSpritze (29. Mrz 2010)

Also hier hast du zumindest eine Möglichkeit Permutationen zu erzeugen: http://www.java-forum.org/codeschnipsel-u-projekte/81973-combinatorics.html

Dein Wörterbuch müsstest du dann als Set aufbauen und dann jede Permutation testen, ob sie in dem Set enthalten ist und dann ausgeben. Ist natürlich nur die Fragen, wie du an das Wörterbuch kommst


----------



## JavaAndaa (29. Mrz 2010)

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 (29. Mrz 2010)

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 )


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...

```
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;
    }

}
```


----------



## KYL3R (31. Mrz 2010)

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 (31. Mrz 2010)

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 (31. Mrz 2010)

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 (31. Mrz 2010)

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 (31. Mrz 2010)

guni hat gesagt.:


> 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?



faetzminator hat gesagt.:


> 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.


----------



## Quurks (4. Apr 2010)

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


----------



## 0x7F800000 (4. Apr 2010)

Quurks hat gesagt.:


> Kannst du mir mal den Link zu dieser Datenbank geben? Würde mich stark für ein anderes Projekt interessieren.


weiß nicht mehr wie die hieß, bin da auch nur durch planloses googlen draufgekommen, wirst du nach einigen Minuten auch schaffen...


----------

