Comment générer des lignes de texte aléatoires d'une longueur donnée à partir d'un dictionnaire de mots (problème bin-packing)?

Question

J'ai besoin de générer trois lignes de texte (essentiellement du jibberish) qui ont chacune 60 caractères, y compris un retour à la fin de chaque ligne. Les lignes sont générées à partir d'un dictionnaire de mots de différentes longueurs (typiquement 1-8 caractères). Aucun mot ne peut être utilisé plus d'une fois, et les mots doivent être séparés par des espaces. Je pense que c'est essentiellement un problème de bin-emballage.

L'approche que j'ai prise jusqu'ici est de créer un hashMap des mots, groupés par leurs longueurs. Je choisis ensuite une longueur aléatoire, tire un mot de cette longueur de la carte et l'ajoute à la fin de la ligne que je suis en train de générer, en tenant compte des espaces ou d'un retour dur. Cela fonctionne environ la moitié du temps, mais l'autre moitié du temps je suis coincé dans une boucle infinie et mon programme se bloque. Un problème que je rencontre est celui-ci: comme j'ajoute des mots aléatoires aux lignes, les groupes de mots d'une longueur donnée peuvent devenir épuisés. C'est parce qu'il n'y a pas nécessairement le même nombre de mots de chaque longueur dans le dictionnaire, par exemple, il peut y avoir seulement un mot avec une longueur de 1. Donc, je pourrais avoir besoin d'un mot d'une longueur donnée, mais il n'y a plus tous les mots de cette longueur disponibles.

Voici un résumé de ce que j'ai jusqu'à présent. Je travaille en ActionScript, mais j'aimerais avoir un aperçu de ce problème dans n'importe quelle langue. Merci d'avance.

dictionary // map of words with word lengths as keys and arrays of corresponding words as values 
lengths // array of word lengths, sorted numerically 
min = lengths[0] // minimum word length 
max = lengths[lengths.length - 1] // maximum word length 
line = "" 
while (line.length < 60) { 
    len = lengths[round(rand() * (lengths.length - 1))] 
    if (dictionary[len] != null && dictionary[len].length > 0) { 
     diff = 60 - line.length // number of characters needed to complete the line 

     if (line.length + len + 1 == 60) { 
      // this word will complete the line exactly 
      line += dictionary[len].splice(0, 1) + "\n" 
     } 
     else if (min + max + 2 >= diff) { 
      // find the two word lengths that will complete the line 
      // ==> this is where I'm having trouble 
     } 
     else if (line.length + len + 1 < 60 - max) { 
      // this word will fit safely, so just add it 
      line += dictionary[len].splice(0, 1) + " " 
     } 

     if (dictionary[len].length == 0) { 
      // delete any empty arrays and update min and max lengths accordingly 
      dictionary[len] = null 
      delete dictionary[len] 

      i = lengths.indexOf(len) 
      if (i >= 0) { 
       // words of this length have been depleted, so 
       // update lengths array to ensure that next random 
       // length is valid 
       lengths.splice(i, 1) 
      } 
      if (lengths.indexOf(min) == -1) { 
       // update the min 
       min = lengths[0] 
      } 
      if (lengths.indexOf(max) == -1) { 
       // update the max 
       max = lengths[lengths.length - 1] 
      } 
     } 
    } 
} 

Answer 1

1. Vous devriez penser à un mot n-lettre comme étant n + 1 lettres, parce que chaque mot a un espace ou revenir après.
2. Étant donné que tous vos mots contiennent au moins 2 caractères, vous ne souhaitez pas que 59 caractères soient remplis. Si vous obtenez 57 caractères, vous devez sélectionner un nombre de 2 lettres plus revenir. Si vous obtenez à 58, vous avez besoin d'un mot de 1 lettre plus le retour.
3. Essayez-vous d'optimiser pour le temps? Pouvez-vous avoir le même mot plusieurs fois? Plusieurs fois dans une ligne? Est-ce important si vos mots ne sont pas distribués uniformément, par ex. beaucoup de lignes contiennent "a" ou "je" parce que ce sont les seuls mots d'une lettre en anglais?

Voici l'idée de base. Pour chaque ligne, commencez à choisir des longueurs de mots, et gardez trace des longueurs de mots et du nombre total de caractères jusqu'à présent. Lorsque vous arrivez en fin de ligne, choisissez des longueurs de mots inférieures au nombre de caractères restant. (par exemple, s'il vous reste 5 caractères, choisissez des mots de l'ordre de 2 à 5 caractères, en comptant l'espace.) Si vous obtenez 57 caractères, choisissez un mot de 3 lettres (en comptant le retour). Si vous obtenez 58 caractères, choisissez un mot de 2 lettres (en comptant le retour.)

Si vous voulez, vous pouvez mélanger les longueurs de mots à ce stade, de sorte que toutes vos lignes ne se terminent pas avec des mots courts. Ensuite, pour chaque longueur de mot, choisissez un mot de cette longueur et branchez-le.

Answer 2

dictionnary = Group your words by lengths (like you already do) 
total_length = 0 
phrase = "" 

while (total_length < 60){ 

random_length = generate_random_number(1,8) 

if (total_length + random_length > 60) 
{ 
    random_length = 60 - total_length // possibly - 1 if you cound \n and -2 if you 
            // append a blank anyway at the end 
} 

phrase += dictionnary.get_random_word_of_length(random_length) + " " 
total_length += random_length + 1 

}