A recurring problem is to generate an infinite number of names / surnames random *.
To do this you need an algorithm that mimics the language, words that imitate the process of creating a name.
There are a lot of ways, but almost all are complicated, with poor results. The method according
me more effective and easy is what provides for the use of Markov chains.
A Markov process is a process that determines the N th execution in the light only from its N-1 th realization. A word can be seen in this light, that is N th letter depends only on N-1 th letter. The
word "John" for example can be seen as a chain of two Markov processes with a structure of type u-> g-> o, where u-> g is the first trial and g-> or the second. Thus, given any letter you can use a Markov process to find the next letter and so on to form a whole word.
But the operator (->) how do you build? * Simple, with a list of existing words, or by calculating the probability that any state (ie a letter) is passed to the next.
In the example where your vocabulary is composed of the word "John", the probability of moving from "u" to "g" is 100% as the probability of moving from "g" to "or". But even if I introduce the word "scream",
things change, that is, the probability of moving from "u" to "g" has fallen to 50%,
because now there is also a transition u-> r. If we introduce a fairly large number of items can I build a matrix of transition probabilities. Suppose that words are formed only by abcdefghijklmnopqrstuvwxyz (let's pretend that they are 29, I have not counted for laziness *). I have a 29x29 matrix that gives me the transition probability between a letter and the next.
The simplest example, perhaps you can do with DNA, whose bases (letters) are just four: ATGC (even those I have not counted out of laziness). In this case, the array is a 4x4. Suppose you have a string of DNA g ATTTTCGGATTTGTA. Count the number of times you switch from one base to another. eg A-> T occurs two times, G-> G only once, so ... If you can find the normalized probability that X is close to Y. If multiplied by 100 to find the percentage of probability. In Fig.1 see just that for the string of DNA sample (the numbers are the percentages of transition, the transitions with probability nothing has been omitted eg C-> T).
extend this thing to a list of names and instead of the 4 bases used 29 letters. Now, given a letter by chance know what is the probability of a given letter after the selection. Given a letter and then rolling a die ("cheating" with the odds) I get the next letter.
Repeating the process I get a word.
If you want to be more precise, we can also introduce a "letter word beginning" $ type and a "letter of word order" type #. We will therefore ugo # $ $ and the five processes -> u-> g-> o-> #. In this way I have the probability that a word beginning with a given letter and ending with a certain letter.
The practical example you here, where a few names from a list ( this ) can be determined based on those potentially infinite number of names on the list. It starts with "$" and randomly assigned to find the sequence of letters. Note that names are discarded too long, too short or long sequences of consecutive consonants. In addition, you can create family with the scent of different nationalities. Finally, note that the names are chosen at random from a list, while the names are generated with a Markov process.
More. If you do not already have an outlet for boredom * you can use this method for a lot of useful things. For example, (i) control spam by verifying whether a message has a probability lower than that usually arrive, or (ii) simulate the style of write the words instead of letters in the example above, or (iii) to predict weather based on those found in your area in recent years ... etc.
enough!
sj
* Note that the phrase does not hide any irony.
0 comments:
Post a Comment