Wednesday, May 9, 2012

Random Name Generator

In the spirit of the (almost) pure random demon name generator, I wanted to show a random name generator in Factor.

Some time ago, I implemented a vocabulary for creating fake data which could generate "fake names". The way it worked was to make a name by picking randomly from a list of valid first and last names. The drawback with that approach is that you can only create names that already exist in your list. It would be more interesting if you can use a list of valid names to "seed" a random name generator which uses that to create names that are similar to your list but do not appear in it.

Transition Tables

To do this, we will create a table of "transitions". A transition is a pair of characters that appear next to each other in a name. In pseudo-code, it will be something like this:

  1. For each name from a list of valid names,
  2. For every character in the name,
  3. Update the table by adding the "transition" at the characters index.

We can create a sequence of transitions for a given string by clumping each pair of characters together (as well as showing the last character transitions to f, meaning the end of the word):

: transitions ( string -- enum )
    { f } { } append-as 2 clump <enum> ;

Given a string and a transition table, we can update it with those transitions:

: (transition-table) ( string assoc -- )
    [ transitions ] dip '[ swap _ push-at ] assoc-each ;

So, given a sequence of strings, we can create the transition table easily:

: transition-table ( seq -- assoc )
    H{ } clone [ [ (transition-table) ] curry each ] keep ;

You can try it out and it will look something like this:

IN: scratchpad { "hello" } transition-table .
    { 0 V{ { CHAR: h CHAR: e } } }
    { 1 V{ { CHAR: e CHAR: l } } }
    { 2 V{ { CHAR: l CHAR: l } } }
    { 3 V{ { CHAR: l CHAR: o } } }
    { 4 V{ { CHAR: o f } } }

Generating Names

We can use the make vocabulary to randomly choose the next transition from our table given a previous character, an index, and a transition table:

: next-char, ( prev index assoc -- next )
    at swap [ [ nip = ] curry assoc-filter ] when*
    random [ first , ] [ second ] bi ;

Generating the names is as easy as starting from zero and adding each character until we hit an f indicating the end of a word.

: generate-name ( seq -- name )
    transition-table [
        f 0 [
            [ pick next-char, ] [ 1 + ] bi over
        ] loop 3drop
    ] "" make ;

Generating a number of names is just:

: generate-names ( n seq -- names )
    [ generate-name ] curry replicate ;

Try It

So, does it work? Well, if we load a list of Star Trek races, we can generate some new names that sound pretty good!

IN: scratchpad 10 star-trek-races generate-names .

The code for this is on my Github.

No comments: