March 13, 2009 

Bruteforcowy generator wyrazów w PHP :)

Nudziłem się i machnąłem sobie taki skrypt co to za pomocą łopatologicznej metody generuje sobie wszelkie możliwe kombinacje z zakresu [a-zA-Z0-9]. Jakie efekty? Po pół godziny pracy (każde słowo wrzucałem do bazy danych) otrzymałem jakieś 30 mln rekordów. Całość zajmuje mi na dysku ponad 500Mb, a średni czas wykonania jakiegokolwiek zapytania 15 sekund wzwyż :)

Co ciekawe wszystkie wyrazy zaczynają się tylko od literki ‘a’, czyli przez ten czas nie wygenerowano ani jednej kombinacji typu ‘bxxxxx‘, gdzie x jest dowolnym znakiem alfanumerycznym.

Czy warto? Raczej nie, chociaż kiedyś dobry słownik był podstawą :D . Ogólnie gdybym chciał wygenerować całość (o ile się nie mylę to liczba kombinacji to 62! * n, gdzie n to maksymalna długość) w jakiś sensowny sposób to musiałbym posiadać armię komputerów zombie i jakoś dane między nimi synchronizować.

Ogólnie całość traktuję jako ciekawostkę, kod wrzucam poniżej.

PS. proszę na to nie patrzeć pod kątem jakości kodu. Gdybym chciał mógłbym to jakoś ładniej zrobić.

{geshi lang=”php”}
set_time_limit(0);

mysql_connect('localhost', 'root', '') or die('brak polaczenia');
mysql_select_db('words');
mysql_query('TRUNCATE words');

$znaki = "abcdefghijklmnoprstuwxyzq";
$znaki .= "ABCDEFGHIJKLMNOPRSTUWZYXQ";
$znaki .= "1234567890";

function InsertWord($pWord) {
$sql = "
INSERT INTO
words
SET
word = '{$pWord}'
";

mysql_query($sql);
}

function MkWord($pMaxDepth, $pCurrentDepth = 1, $pText = '') {
global $znaki;
$count = strlen($znaki);

for($i = 0; $i < $count; $i++) {

$str = $pText.$znaki[$i];
InsertWord($str);

if($pMaxDepth != $pCurrentDepth) {
MkWord($pMaxDepth,($pCurrentDepth+1), $str);
}

}

}

echo "Start: ".date(DATE_RFC822)."\n";
// no to lecimy z koksem - generujemy wszelkie mozliwe wyrazy - maks. dlugosc - 6 znakow
MkWord(6);
echo "End: ".date(DATE_RFC822)."\n";

?>
[/sourcecode]

More from this category

9 Responses to “Bruteforcowy generator wyrazów w PHP :)”

  1. radmen March 13, 2009 at 11:54 pm #

    Kolejny PS. W ramach moich ‘testów’ generowałem wyrazy o długości 6 znaków. Oczywiście można tą długość skrócić, chociaż i tak pewnie nie ma to jako takiego znaczenia :)

    Reply
  2. hcz March 13, 2009 at 11:54 pm #

    Mylisz się (a propos liczby „kombinacji”).

    Reply
  3. groszek March 13, 2009 at 11:54 pm #

    Ugh, warto by to przerobić :P – primo, przy każdym generowaniu masz zapytanie do mysql – zuo – secundo, algorytm brzydki – [tertio?] po co za każdym razem generować $count = strlen($znaki); ? Zapisz sobie gdzieś! Tego typu optymalizacje to podstawa :) – http://dl-client.getdropbox.com/u/28596/Stuff/pinky.7z – może się przyda ;) tam jest wygodniejszy algorytm – Można się pokusić o „loop unrolling” tutaj, czyli zamiast pętli po długości znaków zrobić wielkiego switcha – choć nie wiem czy to przyspieszy.

    Reply
  4. radmen March 13, 2009 at 11:54 pm #

    hcz: to popraw mnie
    groszek: wiem, że te zapytania są głupie. W sumie potem mnie olśniło, że o wiele lepszy byłby zapis do pliku :)
    A co jest złęgo w algorytmie? Szczerze mówiąc, to było robione ciut na pałę (metodą prób i błędów). Najlepszym rozwiązaniem zdawała się właśnie rekursja.

    PS, wiem że to można zoptymalizować (i wiem jak :P ). Zdaje się, że nawet napisałem, aby nie patrzeć na „jakość” kodu :)

    Reply
  5. Pyetras March 13, 2009 at 11:54 pm #

    62^n. Wariacja z powtórzeniami

    Reply
  6. kosa March 13, 2009 at 11:54 pm #

    Co do ilości słów to Pyetras ma rację.
    A powiedz mi jeszcze, po co to gdziekolwiek zapisywać? Gdyby to był słownik (czyli coś co zawiera poprawne słowa kodowe) to ok, ale tak? Szybciej na bieżąco generować wszystkie potrzebne w danym momencie kombinacje.

    Reply
  7. hcz March 13, 2009 at 11:54 pm #

    @kosa: liczba słów, nie ilość

    @radmen: Jeśli chcesz policzyć liczbę słów o długości nie większej niż n to będzie:

    62^1 + 62^2 + 62^3 + … + 62^n

    BTW: w twoich znakach brakuje „v”

    Reply
  8. kosa March 13, 2009 at 11:54 pm #

    Oczywiście, liczba.

    Reply
  9. radmen March 13, 2009 at 11:54 pm #

    Pyetrek, hcz:dziękuję za wyjaśnienia :) Faktycznie brakuje ‘v’. Kosa: masz rację. Ja to bardziej robiłem jako taki eksperyment. Z resztą teoretycznie raz wygenerowany słownik, mógłby być dalej używany (choć pewnie w tej sytuacji niewiele przyspieszy).

    Reply

Leave a Reply