Rikki Mongoose

Kiyoaki project is 0.2 now. There’re some bugfixes in it, but the main thing is adding the “fixation” procedure. And it’s time to take some notes about the ideas I’ve used.

The main idea was not to try to make the generated surnames perfect. They can’t be perfect, because different dialects produce different rules for surnames. Some surnames from Chevengur (like Dvanov or Chepurnoy) look very unusual for me, but I’ve meet people who had the same.

Like the most of name generator, it’s build on the idea of Markov Chain. If we have such a graph build, it’s easy to reach a next one:

    #code from kiyoaki/morphgen.py

    @staticmethod
    def get_markov_node(nodes_array):
        """ Get the next node in Markov chain according to its value.
        """
        markov_sum = 0
        for node in nodes_array:
            markov_sum += node.get_count()

        rand_sum_elem = random.randint(1, markov_sum)

        for node in nodes_array:
            markov_sum -= node.get_count()
            if markov_sum < rand_sum_elem:
                return node
        return None

I didn’t check for a better algorithm yet, but even this version looks fast enough with complecity o(2n). And of course it can be redefined for any realisation of Markov Chain.

But how to build it, if we have just a lot of example of real-existing surnames in this language?

We can build them automating the method of Alice Kober’s: split every word to all possible pieces and check, are any of these pieces used more then others. So, the most used pieces will give as the main morphemes, like suffixes, prefixes. etc.

Alas! Bruteforce works bad here. There’re p(n) partitions for every n-letter words, but every part of partition can be permutated too. Put-in and Pu-tin are the same partition (7 letters = 3 + 2), but we have different morphemes for it. So, the difficulty of such an algorithm is ~ o(p(n)!). p(x) doesn’t grow fast for n < 10 (the most of surnames are shorter then 10 letters), but factorial makes counting difficult even for n = 7.

The salvation is based on 2 main prepositions. Firstly, a surname is built of 2 parts – “root” and “postfix” (that can be zero). Secondly, we need them not to play Chinese Room, but to be fixed then to “native-looking” surname.

That’s how it works now (morphgen.py again, check the project source too see its architecture):

    def _compile_item(self, text):
        index = len(text) - self.start_index
        was_parsed_head, was_parsed_tail = False, False

        # Prefix is built from the end
        while not was_parsed_tail and index > self.start_index:
            text_head = text[:index]
            text_tail = text[index:]
            index -= ITERATOR

            ready_morphem = self._get_morphem(self.postfixes, text_tail)
            if ready_morphem is not None:
                ready_morphem.inc()
                was_parsed_tail = True

            ready_morphem = self._get_morphem(self.prefixes, text_head)
            if ready_morphem is not None:
                ready_morphem.inc()
                was_parsed_head = True

            for source_item_text in self.sources:
                if not was_parsed_head:
                    if source_item_text == text_head:
                        self._append_morphem(self.prefixes, text_head, True)
                        was_parsed_head = True
                    elif source_item_text.find(text_head) == 0:
                        self._append_morphem(self.prefixes, text_head)
                        was_parsed_head = True

        # Postfix is built from the beginning
        index = self.start_index
        while not was_parsed_tail and index < len(text):
            text_tail = text[index:]
            index += ITERATOR

            ready_morphem = self._get_morphem(self.postfixes, text_tail)
            if ready_morphem is not None:
                ready_morphem.inc()
                was_parsed_tail = True

            for source_item_text in self.sources:
                if not was_parsed_tail:
                    tail_pos = source_item_text.find(text_tail)
                    if tail_pos > -1 and tail_pos == len(source_item_text) - len(text_tail):
                        self._append_morphem(self.postfixes, text_tail)
                        was_parsed_tail = True

        if not was_parsed_head and not was_parsed_tail:
            self._append_morphem(self.prefixes, text, True)

As you can see, it’s much better to generate “not so good” surnames and then fix “wrong” parts with replacing them like common speech do.