PHP-Kombinatorik-Schlüsselwörter: Best-Practise gesucht

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • PHP-Kombinatorik-Schlüsselwörter: Best-Practise gesucht

    Hallo liebes Forum,

    seit mehreren Tagen überlege ich nun schon an einem guten Lösungsweg und komme auf keinen grünen Zweig.
    Mein Problem liegt darin, systematisch Schlüsselwörter aus einem gegebenen Zeichenset und Zeichenlänge mit PHP zu generieren.
    Bisher läuft das nach einem Zufallsverfahren und einer Überprüfung, ob das Schlüsselwort vergeben ist oder nicht. Da es aber relativ ineffizient ist und ein weiteres Problem mit sich zieht, möchte ich die Schlüsselwörter mit einem System vergeben.

    Immer, wenn ein Datensatz hinzugefügt werden soll, wird ein neues (einzigartiges) Schlüsselwort benötigt. Ist keines übergeben worden, muss sich ein Algorithmus ein Schlüsselwort ausdenken. Gegeben wird dann aber das Zeichenset, das für alle User gleich ist. Aber die Schlüsselwortlänge variiert von Benutzer zu Benutzer.

    Angenommen, das Charset ist {A,B,C} und die Länge ist zwei, so sähe eine systematische Vergabe so aus:
    AA √
    AB √
    AC (jetzt diese Kombination zurückgeben)
    BA
    BB
    BC
    CA
    CB
    CC

    Damit ich aber nicht jedes Mal beim Hinzufügen erst ein Array dieser Kombinationen erstellen muss (da uU. sehr lahm), möchte ich eine Art Cache einführen.
    Ich würde also dann dieses Array abspeichern und die letzte benutze Kombination, um direkt auf die nächste Kombination zugreifen zu können.

    Probleme kommen jetzt dabei auf, dass dieser Cache sich natürlich unterscheiden kann, je nach Länge der Schlüsselwörter für den aktuellen Benutzer. Sprich, es wird immer mehrere Caches geben, da sich die Längen unterscheiden. Die Caches müssen neu angelegt werden, wenn sich Länge/Charset ändern.
    Eigentlich gar kein Problem, soweit. Umgesetzt habe ich davon aber noch nichts, weil ich eben noch nicht weiß, wie final eine solche Lösung ist. Und um Eure Ratschläge bitte ich hiermit, wenn man die folgenden Probleme betrachtet:

    Schlüsselwörter können auch manuell mitgegeben werden. Gebe ich also als Schlüsselwort 'webutterthebreadwithbutter' mit, beträgt die Länge schon 26. Da es das erste Schlüsselwort mit dieser Länge ist, müsste ich beim Hinzufügen den Cache dafür erstellen. Man stelle sich nun vor: Das Charset beinhaltet alle Buchstaben (case-senetive) und Ziffern, hätten wir 62 mögliche 'chars'.
    Dass das Erstellen dieses Caches nun 62^26 Kombinationen ergibt, ist dabei natürlich ein Hindernis, was garantiert den RAM auslastet und das Script abbricht. Das passiert leider aber auch schon bei sehr viel kleineren Kombinationen, dass der Arbeitsspeicher schlicht nicht ausreicht.

    So kann ich zwar eine Zeichenkette problemlos mit den Kombinationen erzeugen, diese Zeichenkette jedoch in ein Array umwandeln wird nichts. Oder gar in JSON umwandeln.

    Warum will ich das nicht mehr nach dem Zufallsprinzip machen? Ganz klar: Schnelleres Hinzufügen ermöglichen, die Länge automatisch inkrementieren, wenn eine freie Kombination mit der Länge verfügbar ist.
    Ich glaube kaum, dass die Informationen hier genügen, aber wenn ich noch mehr schreibe wird es nur verwirrender. Wenn Fragen auftauchen, einfach stellen und ich liefere die Infos nach!
    Was sollte ich machen? Wie umgeht man diese Probleme?


    Liebe Grüße
    Jan







    (√ soll ein Haken darstellen)

  • Nein, es ist eben nicht (mehr) egal.

    Ich möchte aus gegebener Menge an 'Chars' und der gegebenen Länge systematisch Schlüsselwörter erzeugen, um das nächste unbenutzte Schlüsselwort 'einfach' zu 'berechnen'.


    PHP Code dazu sieht zB. so aus:

    PHP-Quellcode

    1. <?php
    3. $c = "1234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; // charset
    4. $l = 4; // string length
    6. $startTime = time();
    7. $array = array();
    9. for($t='',$cl=strlen($c),$s=array_fill(0,$l,0),$i=pow($cl,$l);$a=0,$i--;){
    10. for($t&&$t.=', ';$a<$l;$t.=$c[$s[$a++]]);
    11. for(;$a--&&++$s[$a]==$cl;$s[$a]=0);
    12. };
    14. echo time()-$startTime;
    16. echo $t;
    17. ?>
    Alles anzeigen

    Dafür braucht mein Mac zB. schon 14 Sekunden (also ausgenommen der Ausgabe).

  • Also wenn du annimmst, dass Du z.B. 25 Zeichen hast, dann hast du einfach ein 25 Zeichen-Zahlensystem. Genau wie wenn du 16 Zeichen hast, du ein Hex-System hast. Damit kann man doch genauso gut rechnen. Also alle 25 Zeichen kommt die nächste Stelle. Ob Du die dann (wie bei Zahlen) vorne anfügst oder hinten ist doch wurst.

    Wenn du also einfach einen Index mitzählst der quasi den letzten Wert enthält, dann kannst du zu jedem Index sehr einfach deinen Schlüssel erstellen indem du den Index immer durch 25 Teilst und den Rest als Zeichen nimmst.

    Beispiel:

    5676

    5676 / 25 = 227 Rest 1 Also ist dein erstes Zeichen ein B (mal angenommen dein erstes Zeichen wäre A=0)
    227 / 25 = 9 Rest 2 Also ist dein zweites Zeichen ein C
    und dein drittes Zeichen ein J

    Deine Schlüssel wäre also

    BCJ

    Gruß

    Claus
    2 Stunden Try & Error erspart 10 Minuten Handbuchlesen.

    Pre-Kaffee-Posts sind mit Vorsicht zu geniessen :)

  • Nun, ich habe mal angefangen zu implementieren, hier einmal der Algorithmus, der alle Kombinationen erzeugt. Mit dem Memory-Limit muss ich noch schauen, aber das fällt jetzt eh weg, da der Anwendungsfall ja jetzt nur noch den Index speichert und die Kalkulation _immens_ schnell ist.

    PHP-Quellcode

    1. <?php
    2. ini_set('memory_limit', '-1');
    5. $string = "1234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; // charset
    6. $length = 4; // string length
    9. $char_array = preg_split('//', $string, -1, PREG_SPLIT_NO_EMPTY);
    10. $char_count = count($char_array);
    12. $index = 0;
    13. $max = pow($char_count, $length);
    15. $keywords = array();
    16. $startTime = time();
    18. while ($index<$max)
    19. {
    20. $keywords[] = calculate_keyword($index,$length,$char_count,$char_array);
    22. $index++;
    23. }
    25. echo time()-$startTime;
    27. file_put_contents("/Users/q/Desktop/test.json",json_encode($keywords));
    29. function calculate_keyword($index,$length,$char_count,$char_array)
    30. {
    31. $position = 0;
    32. $current_keyword = "";
    33. $index_divider = $index;
    35. while ($position < $length)
    36. {
    37. $mod = $index_divider % $char_count;
    38. $index_divider = $index_divider / $char_count;
    40. $current_keyword = get_char($mod,$char_array) . $current_keyword;
    42. $position++;
    43. }
    45. return $current_keyword;
    46. }
    48. function get_char($index,$char_array)
    49. {
    50. return $char_array[$index];
    51. }
    53. ?>
    Alles anzeigen


    Randnotiz: Das Ausführen dauert bei mir 47,8 Sekunden, 42 Sekunden davon berechnet er alle Kombinationen. Die restliche Zeit verbringt er mit dem Umwandeln von array zu json und dem Speichern der Datei (103MB). Insgesamt ist das also langsamer als die drei geschachtelten For-Schleifen (siehe oben), dafür aber gezielt berechenbar.


    Danke!

  • klar ist es langsamer wiel ja berechnet wird.

    wozu aber solche funktionen wie get_char()? hier kopierst du ja unnötigerweise immer das komplette array. wenn du dafür schon eine funktion haben willst (warum eigentlich, es machts doch nur länger und unübersichtlicher) dann übergib das array doch by refernce und nicht by value.