Generator słów (bardzo duża iość)

Jak najłatwiej napisać program/algorytm umożliwiający utworzenie np 50 milionów słów których długość będzie z przedziału 2 do 10 znaków. Słowa mogą składać się wyłącznie z dużych liter z zakresu A-Z (ASCII bez polskich znaków), java JDK 8 bez dodatkowych bibliotek, środowisko uruchomieniowe pozwala zaalokować maksymalnie 20MB pamięci czyli sporo mniej niż rozmiar pliku z danymi do wygenerowania. Jak najłatwiej można to zrealizować?

http://stackoverflow.com/questions/1062113/fastest-way-to-write-huge-data-in-text-file-java

Spine napisał(a):

http://stackoverflow.com/questions/1062113/fastest-way-to-write-huge-data-in-text-file-java

Dzięki za linka. Przydatna rzecz jeśli chodzi o zapis danych do pliku. Natomiast jak stworzyć algorytm do generowania losowo słów mających sens jak w treści? Czy może po prostu zaciągnąć jakiś słownik z danymi i z niego Randomem wyciągać poszczególne wyrazy? Wydaje mi się że stworzenie takiego algorytmu do generowania słów z sensem jest dość skomplikowane...

Możesz zrobić cos na zasadzie poczciwego bluzgatora - posiadasz kilka grup słów np. podmiot, dopełenienie, orzeczenie i losujesz sobie po 1 ze słow z danej grupy tworząc zdanie.

Generalnie to nie muszą być zdania tylko po prostu lista wyrazów. Kwestia tworzenia listy tych wyrazów, mając słownik z wyrazami w pliku mogę go zaczytać i wybierać losowo istniejące w nim słowa. Jednak zastanawiam się nad stopniem trudności napisania generatora słów z listy liter (A-Z) ale tak by słowa miały sens, czy jest to w ogóle wykonalne (chodź na pewno nie trywialne), bo napisanie generatora słó jako zlepku liter to żaden problem.

możesz zrobić jak pisał kolega wyżej, albo przeskanować książkę, i wyszukać często powtarzających się wzrotów, z tym ze poplsku nie jest to proste bo jest cała masa pre/post fixsów

A czy istnieje w języku polskim 50 milionów słów, na dodatek bez liter ze znakami diakrytycznymi?

A czy napisałem gdzieś że słowa mają się NIEpowtarzać? Nie napisałem!
Oczywiście słowa mogą się powtarzać, kwestia tylko czy można by jakoś samemu napisac algorytm do iche generowania aby miały sens.

Skoro mogą się powtarzać, to napisz 50 milionów razy słowo "mistrz".

bogdans napisał(a):

Skoro mogą się powtarzać, to napisz 50 milionów razy słowo "mistrz".

Jak masz pisać takie bzdury to proszę nie udzielaj się w temacie!
poza tym polecam naukę czytania ze zrozumieniem: SŁOWA (liczba mnoga) to nie SŁOWO.

Anyway jeśli ktoś miałby jakiś pomysł na rozwiązanie będę wdzięczny.

Zamiast pisać wulgaryzmy sprecyzuj wymagania: słowa mogą się powtarzać, ale ile różnych słów musi być, ile razy jedno słowo może się powtórzyć.

I nie, nie napiszesz "generatora" słów. Nie da się generować słów danego języka (ozywiście mówię o języku Polskim). Jedyne wyjście to użycie słownika i losowanie z niego.

Słowa mogą się powtarzać wiele razy, nie może to być jedno i to samo słowo
Długość słów z przedziału 2-10
Tylko duże litery bez polskich znaków (A-Z) w ASCII 65-90
Słów ma być dużo bo 50 mln

Lukigostek napisał(a):

I nie, nie napiszesz "generatora" słów. Nie da się generować słów danego języka (ozywiście mówię o języku Polskim). Jedyne wyjście to użycie słownika i losowanie z niego.

Właśnie o takie coś mi chodziło, bo sam pomysł ze słownikiem to jak najbardziej mam i znam. Chciałem aby ktoś bardziej doświadczony się wypowiedział czy dałoby się rade napisać własny generator słó z sensem :)

Do podanych wymagań pasuje wypisywanie dwóch różnych słów na zmianę, pasuje też losowanie z 5-elementowego słownika.

Dobra. Zrobiłem to tak że znalazłem jakiś słownik w sieci z 2,7 mln haseł, przefiltrowałem go tak aby wybrać z niego wyrazy długości 2-10 znaków z ASCII A-Z. Następnie wrzucam wszystko do Listy i losobo wybieram z niego 50 mln wyrazów a następnie zapisuję do pliku. Plik ten ma około 400 MB. Wszystko fajnie działa i wcale nie tak wolno jak myślałem że będzie działać. Kwestia tylko wymagania że mam do dyspozycji tylko 20 MB pamięci zaalokowanej przez środowisko. Jak można sprawdzić ile paięci zajmuje mój generator?

No jeśli plik ma 400MB a ty go wczytałeś w javie do programu to pewnie zajmujesz przynajmniej z 1GB heapu na sam slownik ;]

Wracając do twojego pytania: wbrew pozorom DA SIĘ generować słowa z dużym prawdopodobieństwem że będą to słowa poprawne dla danego języka. Można do tego wykorzystać łańcuchy Markowa / n-gramy. Taki model do generacji będzie zajmował stosunkowo mało pamięci (wszystko zależy od tego jak długie słowa chcesz generować). Sama generacja modelu oczywiście będzie wymagać dużo więcej pamięci, ale jak to bywa, samo "używanie" modelu już nie wymaga wiele.

Dzięki @Shalom. Generalnie słownik z polskimi wyrazami zajmuje około 4,6 MB - Jego wczytuję do pamięci a następnie z niego losuję Random 50 mln słów i te 50 mln słów mają ok 400 MB.
W takim razie jak najprościej wygenerować 50 mln słów aby zmieścić się w 20 MB pamięci? na bieŻąco (Boże, widzisz takie błędy i nie grzmisz) zapisując je do pliku? Obecnie dodaję je do Listy i na koniec zapisuję z użyciem BufferedWriter...

Czytałem conieco o podejściu Markowa do tego tematu.

No to generuj i zapisuj do pliku słowo po słowie po prostu. Po co je zbierasz do listy? ;]

No tak, tylko że teraz program mi działa dużo wolniej (10 krotnie dłużej) jak zapisuje na bieżąco każdy string...

Ponadto takie coś się pojawia w Java VisualVM:

To jest akurat dość oczywiste że jak pamięci mało to czas wykonania dłuższy. A wykres to pewnie jakieś buforowanie.

@Shalom a czy można gdzieś w Eclipsie (lub gdziekolwiek podejrzeć) ile Heapu zajmuje mój program po jego uruchomieniu? Można to jakoś sprawdzić w ogóle? Albo jak najlepiej obsłużyć aby nie używał więcej niż 20 MB?

To jest raczej słabe ograniczenie dla javy bo java to nie c++ i nie masz specjalnej kontroli nad tym ile pamięci dokładnie zostanie zaalkowane.

Opcja -Xmx polecenia java pozwala ograniczyć rozmiar "heapu".
Ty potrzebujesz pewnie java -Xmx20m Generator.
W Eclipse Run => Run Configurations => zakładka Arguments.

java -Xmx20m Generator w argumentach programu? Generator to nazwa klasy obsługującej generator czy projektu?

W argumentach VM (maszyny wirtualnej), Tylko -Xmx20m.
java -Xmx20m Generator dotyczy uruchamiania w konsoli, Generator jest wtedy nazwą klasy startowej (z metodą main).

Jeśli jednak Wymagana była by unikalność to bym użył bazy danych do przechowywania, silniki baz danych mają mechanizmy żeby efektywnie sprawdzać czy właśnie dodawane słowo jest już na liście nawet jeśli ta lista ma 50 milionów pozycji.

do generowania bym wyszedł od czegoś takiego:

        String[] alfabet= {"a","b", "c"};                        
        for (int i1=0; i1<alfabet.length; i1++){
            for (int i2=0; i2<alfabet.length; i2++){
                for (int i3=0; i3<alfabet.length; i3++){
                    String słowo=alfabet[i1]+alfabet[i2]+alfabet[i3];

                    // Tu zapis słowa do bazy
                }
            }
        }
 

Jeśli dodam -Xmx20m to dostaję taki błąd:

Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded
	at java.util.Arrays.copyOfRange(Arrays.java:3664)
	at java.lang.String.<init>(String.java:207)
	at java.io.BufferedReader.readLine(BufferedReader.java:356)
	at java.io.BufferedReader.readLine(BufferedReader.java:389)
	at java.io.BufferedReader$1.hasNext(BufferedReader.java:571)
	at java.util.Iterator.forEachRemaining(Iterator.java:115)
	at java.util.Spliterators$IteratorSpliterator.forEachRemaining(Spliterators.java:1801)
	at java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:481)
	at java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:471)
	at java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:708)
	at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
	at java.util.stream.ReferencePipeline.collect(ReferencePipeline.java:499)
	at com.Dictionary.read(Dictionary.java:46)
	at com.Dictionary.readBuffered(Dictionary.java:29)
	at com.Dictionary.getDictionary(Dictionary.java:21)
	at com.Words.main(Words.java:23)
 

Kod metody do odczytu:

37 private static List<String> read(BufferedReader reader) throws IOException {
38		
39		List<String> lines = new ArrayList<String>();
49		long start = System.currentTimeMillis();
41
42		lines = reader.lines()/*.filter(line -> line.length() >= 2)
43				.filter(line -> line.length() <= 10)
44				.map(String::toUpperCase)
45				.filter(line -> line.matches("^([A-Z]+)$"))
46				*/.collect(Collectors.toList());
47
48		System.out.println("Reading buffered (initial size: " + reader.lines().collect(Collectors.toList()).size() + ")... ");
49		reader.close();
50		long end = System.currentTimeMillis();
51		System.out.println((end - start) / 1000f + " seconds");
52		return lines;
53	}

Jak można by przerobić tą metodę aby zajmowała mniej pamięci. Plik ze słownikiem (wczytywany jako reader) zawiera około 0,5 mln haseł i waży niecałe 5 MB. Wczytuję go do listy aby potem z niej losowo pobierać słowa. Czy może losowo pobierać słowa bezpośrednio z pliku słownika, odnosząc się do numeru lini?