3
\$\begingroup\$

I play a lot of old-school western CRPGs, and most of them (if not all) require the player to generate an avatar at the start of a new game, including naming the character (with names that will never be pronounced).

I want my character to have the most unique and beautiful name, with as few namesakes as possible and make her have absolutely meaningless name, so that she can define the meaning of her name herself, without being overshadowed by the meaning of the name in any way.

Naturally the name has to be random, though of course random.sample(ascii_lowercase, 7) isn't a valid solution, the result must be pronounceable.

I always have huge trouble making up the names, I can't make up anything devoid of meaning by myself, because humans are fundamentally incapable of choosing randomly, choice is a conscious act therefore the outcome is inherently deterministic. Therefore the use of computers is required.

Thankfully most these games have built-in random name generator's, for those without RNG I use online RNG. The results of the RNGs most of the time sadly seemed way too common, they seemed to be just choosing two random strings from two predefined lists instead of actually generating them...

I always spent dozens of minutes hitting the generate button hundreds of times just trying to find the right name, and I am very not impressed...

So I am inspired to write a program to actually generate pronounceable gibberish...

I have chosen the Markov chain process, though maybe I will throw in Markov Chain Monte Carlo, Neural Network, Minimax and whatnot along the way just for the best result. I am still learning though I understand their basics.

In simple terms, Markov Chain involves choosing an initial state randomly from a list of states with weights, then choose a state that can come after the first state with weights, and repeat...

Anyway this is the script that analyzes the corpus to generate the statistical data necessary for the generation and store the data...

It is supposed to take an inputted corpus and output the data in a database, but for now it is non-interactive and uses the default corpus, and doesn't output to a database... But it is working properly, although performance isn't very impressive.

I have pulled 105230 words from GCIDE and I have done quite a lot analyses.

I have identified valid chunks (common letter groups that can appear in a syllable rather than must be in two separate syllables) between lengths 1 and 3 (inclusive), the chunks are generated using another script and that script is not for review, the chunks are required by this script.

I have counted the lengths of the words (how many words are n letters long, n must be an integer greater than 3 and the count must be greater than or equal to 50).

I have counted the starting letters of the words.

I have counted how many times letter b is the second letter if letter a is the first letter.

I have counted how many times letter b follows letter a in all positions.

I have counted the starting chunks of the words (using re, the pattern is constructed in such a way so that the longer parts come before shorter parts).

I have counted how many times chunk b is the second chunk if chunk a is first.

I have counted how many times chunk b follows chunk a in all positions.

And I have counted the occurrences of states; in this usage, state means a sequence of three groups (letter or chunk) immediately following each other, I have counted letter and chunk states occurring at first, second and any positions (6 groups of data).

And I did more than just the above. I filtered the data using a number of conditions, each producing more than one set of new data.

The conditions include:

  • alternate: letter condition, in this condition a vowel can only be adjacent to a consonant and vice versa, y is a semi-vowel and can be adjacent to any letter except itself.

  • singlecon: letter condition, a vowel and y can be adjacent to any letter, but consonant letters can't be adjacent to each other.

  • safe: chunk condition, similar to above, chunks consisting only of consonant letters can't be adjacent to each other.

I used the above to create 9 new sets of data.

I intend to make my program support 4 modes, including each of the above conditions plus no condition.

The intended execution flow is: choose randomly with weights from the dataset that contains the first parts valid for the condition, then the second part, then any part, using the states as basis for scoring... (sorry it is really hard for me to explain this process in English, but I can write the code).

I did also sort nested dict and eliminate infrequent entries and a few other things...

Here is the code:

import json
import re
import time
from ast import literal_eval
from collections import Counter, defaultdict
from pathlib import Path

start = time.time()

DIRECTORY = Path(__file__).parent
INCLUDIR = DIRECTORY / 'include'
DATADIR = DIRECTORY / 'data'
DATADIR.mkdir(exist_ok=True)

def read_list(path):
    return path.read_text().splitlines()

def read_dict(path):
    return json.loads(path.read_text())

def export(var, path):
    (DATADIR / path).write_text(json.dumps(var, indent=4))

def represent(dic):
    ls = [' ' * 4 + repr(k) + ': ' + repr(v) for k, v in sorted(dic.items())]
    return '{\n' + ',\n'.join(ls) + '\n}'

CONSONANT = '[b-df-hj-np-tv-xz]'
CORPUS = read_list(INCLUDIR / 'gcide_dict.txt')
CHUNKS = read_list(INCLUDIR / 'chunks.txt')
IS_CONSONANT = read_dict(INCLUDIR / 'is_consonant.json')
IS_VOWEL = read_dict(INCLUDIR / 'is_vowel.json')
CONSONANT_CHUNKS = {k: bool(re.match('^'+CONSONANT+'+$', k)) for k in sorted(CHUNKS)}
UNITS = re.compile('(' + '|'.join(i[::-1] for i in sorted(CHUNKS, key=lambda x: -len(x))) + ')')
CONSONANTS = [i for i in sorted(CHUNKS) if re.match('^'+CONSONANT+'+$', i)]

STARTING_CONSONANTS = Counter([m.group() for w in CORPUS if
    (m := re.match('^'+CONSONANT+'+', w))])

STARTING_CONSONANTS = {k: v for k, v in sorted(STARTING_CONSONANTS.items()) if v >= 20}

export(STARTING_CONSONANTS, 'starting_consonants.json')
export(CONSONANT_CHUNKS, 'consonant_chunks.json')
(DATADIR / 'consonants.txt').write_text('\n'.join(CONSONANTS))

def alternate(x, y): return IS_VOWEL[x] != IS_VOWEL[y]
def singlecon(x, y): return IS_CONSONANT[x] + IS_CONSONANT[y] < 2
def safe(x, y): return CONSONANT_CHUNKS[x] + CONSONANT_CHUNKS[y] < 2

alternate_triplets = {
    (0, 0.5, 0), (0, 0.5, 1),
    (0, 1, 0), (0, 1, 0.5),
    (0.5, 0, 0.5), (0.5, 0, 1),
    (0.5, 1, 0), (0.5, 1, 0.5),
    (1, 0, 0.5), (1, 0, 1),
    (1, 0.5, 0), (1, 0.5, 1)
}

singlecon_triplets = {(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (1, 0, 1)}

def alternate_triplet(tri):
    return tuple(IS_VOWEL[i] for i in tri) in alternate_triplets

def singlecon_triplet(tri):
    return tuple(IS_CONSONANT[i] for i in tri) in singlecon_triplets

def safe_triplet(tri):
    return tuple(CONSONANT_CHUNKS[i] for i in tri) in singlecon_triplets

def regularize(dic, lim):
    last = False
    while True:
        want_loop = False
        for k, v in list(dic.items()):
            if isinstance(v, dict):
                regularize(v, lim)
            if isinstance(v, int):
                if v < lim:
                    length = len(k)
                    if length == 1 and last:
                        dic.pop(k)
                    if length > 1:
                        want_loop = True
                        dic.setdefault(k[:-1], 0)
                        dic[k[:-1]] += v
                        dic.pop(k)
        if last:
            break
        if not want_loop:
            last = True
    for k, v in list(dic.items()):
        if not v:
            dic.pop(k)

def sort_dict(dic):
    d = dict()
    for k, v in sorted(dic.items()):
        if isinstance(v, dict):
            d[k] = dict(sorted(v.items(), key=lambda x: (-x[1], x[0])))
        else:
            d[k] = v
    return d

chunk_first = Counter()
letter_first = Counter()
chunk_triplet_first = Counter()
chunk_triplet_second = Counter()
chunk_triplet_sequence = Counter()
chunk_triplet_terminal = Counter()
letter_triplet_first = Counter()
letter_triplet_second = Counter()
letter_triplet_sequence = Counter()
letter_triplet_terminal = Counter()
chunk_second = defaultdict(Counter)
chunk_sequence = defaultdict(Counter)
letter_second = defaultdict(Counter)
letter_sequence = defaultdict(Counter)
chunk_terminal = defaultdict(Counter)
letter_terminal = defaultdict(Counter)
word_length = Counter()

for word in CORPUS:
    letter_first[word[0]] += 1
    len1 = len(word)
    word_length[len1] += 1
    parts = [i[::-1] for i in UNITS.findall(word[::-1])][::-1]
    chunk_first[parts[0]] += 1
    len2 = len(parts)
    if len1 >= 2:
        a, b = word[:2]
        letter_second[a][b] += 1
        a, b = word[-2:]
        letter_terminal[a][b] += 1
        for a, b in zip(word, word[1:]):
            letter_sequence[a][b] += 1
    
    if len1 >= 3:
        key = word[:3]
        letter_triplet_first[key] += 1
        key = word[-3:]
        letter_triplet_terminal[key] += 1
    
    if len1 >= 4:
        key = word[1:4]
        letter_triplet_second[key] += 1
        for key in [word[i:i+3] for i in range(len1-2)]:
            letter_triplet_sequence[key] += 1
    
    if len2 >= 2:
        a, b = parts[:2]
        chunk_second[a][b] += 1
        a, b = parts[-2:]
        chunk_terminal[a][b] += 1
        for a, b in zip(parts, parts[1:]):
            chunk_sequence[a][b] += 1
    
    if len2 >= 3:
        key = tuple(parts[:3])
        chunk_triplet_first[key] += 1
        key = tuple(parts[-3:])
        chunk_triplet_terminal[key] += 1
    
    if len2 >= 4:
        key = tuple(parts[1:4])
        chunk_triplet_second[key] += 1
        for key in [parts[i:i+3] for i in range(len2-2)]:
            key = tuple(key)
            chunk_triplet_sequence[key] += 1

for i in (chunk_first, chunk_second, chunk_sequence):
    regularize(i, 10)

for k1, v1 in chunk_terminal.items():
    for k2, v2 in list(v1.items()):
        if v2 < 10:
            chunk_terminal[k1].pop(k2)

chunk_terminal = {k: v for k, v in chunk_terminal.items() if v}

for i in (letter_second, letter_sequence, letter_terminal):
    regularize(i, 20)

chunk_second = {k: chunk_second[k]
                for k in sorted(set(chunk_first) & set(chunk_second))}

chunk_first = {k: sum(chunk_second[k].values())
                for k in chunk_first if k in chunk_second}

assert not set(j for i in chunk_second.values()
                for j in i.keys()) - set(chunk_sequence)
assert not set(j for i in chunk_second.values() for j in i.keys()) - \
    set(j for i in chunk_sequence.values() for j in i.keys())
assert not set(chunk_first) ^ set(chunk_second)
assert not set(chunk_second) - set(chunk_sequence)

terminal = set(j for i in chunk_sequence.values()
                for j in i.keys()) - set(chunk_sequence)
terminal = sorted(terminal)
(DATADIR / 'terminal.txt').write_text('\n'.join(terminal))

word_length = {k: v for k, v in sorted(
    word_length.items()) if k > 3 and v >= 50}
(DATADIR / 'word_length.repr').write_text(represent(word_length))

def sort_and_export(var, file):
    var = sort_dict(var)
    export(var, file)

batch1 = [
    (chunk_first, 'chunk_first.json'),
    (chunk_second, 'chunk_second.json'),
    (chunk_sequence, 'chunk_sequence.json'),
    (chunk_terminal, 'chunk_terminal.json'),
    (letter_first, 'letter_first.json'),
    (letter_second, 'letter_second.json'),
    (letter_sequence, 'letter_sequence.json'),
    (letter_terminal, 'letter_terminal.json')
]

for a, b in batch1:
    sort_and_export(a, b)

def filter_sort_export(var, file, lim):
    var = {k: v for k, v in var.items() if v >= lim}
    var = sort_dict(var)
    if file.endswith('.json'):
        export(var, file)
    elif file.endswith('.repr'):
        (DATADIR / file).write_text(represent(var))

batch2 = [
    (chunk_triplet_first, 'chunk_triplet_first.repr', 10),
    (chunk_triplet_second, 'chunk_triplet_second.repr', 10),
    (chunk_triplet_sequence, 'chunk_triplet_sequence.repr', 10),
    (chunk_triplet_terminal, 'chunk_triplet_terminal.repr', 10),
    (letter_triplet_first, 'letter_triplet_first.json', 20),
    (letter_triplet_second, 'letter_triplet_second.json', 20),
    (letter_triplet_sequence, 'letter_triplet_sequence.json', 20),
    (letter_triplet_terminal, 'letter_triplet_terminal.json', 20),
]

for a, b, c in batch2:
    filter_sort_export(a, b, c)

def postprocess(infile, outfile, condition, lim):
    var = read_dict(DATADIR / infile)
    result = defaultdict(dict)
    for k1, v1 in var.items():
        for k2, v2 in v1.items():
            if condition(k1, k2):
                result[k1][k2] = v2
    regularize(result, lim)
    result = sort_dict(result)
    export(result, outfile)

batch3 = [
    ('letter_second.json', 'alternate_second.json', alternate, 20),
    ('letter_sequence.json', 'alternate_sequence.json', alternate, 20),
    ('letter_terminal.json', 'alternate_terminal.json', alternate, 20),
    ('letter_second.json', 'singlecon_second.json', singlecon, 20),
    ('letter_sequence.json', 'singlecon_sequence.json', singlecon, 20),
    ('letter_terminal.json', 'singlecon_terminal.json', singlecon, 20),
    ('chunk_second.json', 'safe_chunk_second.json', safe, 10),
    ('chunk_sequence.json', 'safe_chunk_sequence.json', safe, 10),
    ('chunk_terminal.json', 'safe_chunk_terminal.json', safe, 10)
]

for a, b, c, d in batch3:
    postprocess(a, b, c, d)

def postprocess_triplet(infile, condition, outfile):
    var = read_dict(DATADIR / infile)
    var = {k: v for k, v in var.items() if condition(k)}
    export(var, outfile)

batch4 = [
    ('letter_triplet_first.json', alternate_triplet, 'alternate_triplet_first.json'),
    ('letter_triplet_first.json', singlecon_triplet, 'singlecon_triplet_first.json'),
    ('letter_triplet_second.json', alternate_triplet, 'alternate_triplet_second.json'),
    ('letter_triplet_second.json', singlecon_triplet, 'singlecon_triplet_second.json'),
    ('letter_triplet_sequence.json', alternate_triplet, 'alternate_triplet_sequence.json'),
    ('letter_triplet_sequence.json', singlecon_triplet, 'singlecon_triplet_sequence.json'),
    ('letter_triplet_terminal.json', alternate_triplet, 'alternate_triplet_terminal.json'),
    ('letter_triplet_terminal.json', singlecon_triplet, 'singlecon_triplet_terminal.json')
]

for a, b, c in batch4:
    postprocess_triplet(a, b, c)

def postprocess_chunk_triplet(infile):
    var = literal_eval((DATADIR / infile).read_text())
    var = {k: v for k, v in var.items() if safe_triplet(k)}
    (DATADIR / ('safe_' + infile)).write_text(represent(var))

for i in ['chunk_triplet_first.repr', 'chunk_triplet_second.repr', 'chunk_triplet_sequence.repr', 'chunk_triplet_terminal.repr']:
    postprocess_chunk_triplet(i)

end = time.time()
print(end-start)

I have packed all the necessary files and the outputs and uploaded to Google Drive.

I want to know how the performance can be improved. Currently it takes around 8 seconds to complete, and I want it to come down to around 3 seconds.

I want to to how to eliminate code duplication and repetition. Due to the nature of the script a lot of things are repeated, but I have done my best to reuse the functions, but I think more things can be enclosed in functions and reused.

I want to know whether my coding style and code format can be improved.

Lastly and most importantly, I want to know how I should store all these data; my data are mostly nested dicts but they are in fact dicts of Counters (though I used defaultdict for convenience), and the dictionary keys in my data can be ints and tuples, and I would like to store the data while keeping their data types, HUMAN READABLY (I need to read the output), so pickle and dill and the like are out of the question.

I mostly use json as you can see. I am OK with Counter becoming dict (thus losing advantage of being a Counter), int becoming str is absolutely not OK and there is no way to store tuple keys in json files, so I have written my own serialization function based on repr, because I don't know how to do repr with indentation yet, and the data is de-serialized using ast.literal_eval...

I want my data be stored more structurally and organized, retaining its datatypes and humanreadableness; what are my options? I don't like CSV and it doesn't keep data types, I have used MySQL and datatypes are changed on retrieval, I don't know about sqlite3...

What tools can store these data in a more organized way while retaining the identity and readability?


Update

I have managed to update thirteen variables in a gigantic nested for loop, and now the code takes around 3.5 seconds to complete, and I have renamed the output files so that files of the same mode are sorted next to each other, I have also reorganized the folder structure of the module, I still don't know how to store all these data more structurally though...


Update1

I have re-implemented the pattern matching algorithm using this:

# sort parts by length with longer parts coming first to ensure longer parts are matched first
parts = sorted(CHUNKS, key=lambda x: -len(x)))
# reverse the individual parts
parts = [i[::-1] for i in parts]
# compile regex pattern
UNITS = re.compile('(' + '|'.join(parts) + ')')
# reverse the word, find reversed parts and reverse each part back, and reverse the order of parts
[i[::-1] for i in UNITS.findall(word[::-1])][::-1]

This significantly improves the accuracy of the algorithm.

I have also expanded the definition of the chunks, and counted last letter, last chunk, last letter states and last chunk states and variants.

Google Drive link updated

\$\endgroup\$
3
  • \$\begingroup\$ I've just chosen the path of least resistance and use a single character for the names, like 'I', 'Z' etc. :) \$\endgroup\$
    – hjpotter92
    Oct 18, 2021 at 4:45
  • \$\begingroup\$ The first problem I see is that you've probably written two pages to explain your code, yet your code itself contains NO comments or documentation. If you think it needs explanation, add the explanation. \$\endgroup\$ Oct 18, 2021 at 22:31
  • \$\begingroup\$ The second problem I see is that you are still working on this code, based on the two updates since you posted it yesterday. Stop, please. If you post code, we can review it. If you post a series of thoughts, updates, and patches, it no longer fits the format of the site (and, no one will want to review it either--at some point you'll be told to delete the question and re-post the latest version). Don't worry about having done it so far, since I'm sure you didn't know--just letting you know it makes it very hard to review. \$\endgroup\$ Oct 18, 2021 at 23:11

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.