Generating words sounding similar to the ones given in a wordlist -- Core program only

Question

This topic is about the same project as this previous one.

I think posting the full project was a bit too much, so here I post again only three functions, which are the core of my program, with a few modification from the comments I already had.

The goal is to generate words that sounds similar to a language. In order to do that, we first analyze a dictionary of this language, then generate the words.
The analysis takes the word, as a Qstring, and notes each occurrence of each possible letter chain. It depends on a 'coherence length', which means the size of the chain. For example, on the word 'test' with a coherence length of 3 we have to note the occurrence of "void, void, t", "void, t, e", "t, e, s", "e, s ,t", "s, t, end".

This is stored in charmap: the key of the map is a vector of Qchar (a.k.a, the character chain, e.g. "t, e, s"), and the value is a pair where first is the number of occurrence and the second is a probability associated to each key (handled outside of the function).

On this function, I construct the charmap word after word:

void QanalyzeWord(const QString &word, map<vector<QChar>, pair<int,double>> &charmap, uint lcoh, int &nb) {
    vector<QChar> letterChain(lcoh,'\0');

    for(int i=0; i<word.size(); i++) {
        letterChain[lcoh-1]=word.at(i);
        charmap[letterChain].first++;
        nb++;
        for(uint j=0; j<lcoh-1; j++) {
            letterChain[j]=letterChain[j+1];
        }
    }

    //Indicates last character is void
    letterChain[lcoh-1]='\0';
    charmap[letterChain].first++;
    return;
}

Once the full dictionary has been analyzed, we still have to give, to each letter chain, a probability of occurrence. This means completing the second of the pair in the charmap.

I didn't manage to explain this part clearly, so the best is with the simplest example:

If the charmap indicates that thi has been encountered 6 times, the 3 times and tho 1 time, and no other letter is possible after th, then we want to gives a probability of 0.6 to thi, 0.3 to the and 0.1 to tho. In addition, we will be doing cumulative probability, so since the comes before thi then tho in the map, we will have charmap["the"].second=0.3 charmap['thi'].second=0.3+0.6 and charmap['tho'].second=0.3+0.6+0.1 (always sums up to one).

std::map<std::vector<QChar>, std::pair<int,double>>::iterator it = charmap.begin() , cePrBegin , cePrEnd;
//cePrBegin and cePrFin are iterators to the beginning and the end of the letter chain currently on the scope

while(it!=charmap.end()) {
    std::vector<QChar> cePr(&it->first[0], &it->first[lcoh-1]);
    cePrBegin = it;
    int nbPosLet = 0; //number of possible letters after 'cePr'

    //We go from cePrBeging to cePrEnd 2 times:
    //1st: counting occurence of each chain

    while( (it!=charmap.end()) && (cePr==std::vector<QChar>(&it->first[0], &it->first[lcoh-1])) ) {
        nbPosLet += it->second.first; //it->second = the pair in the charmap / then .first = the 'int'= nb of occurences
        it++;
    }
    cePrEnd = it;

    //2nd: dividing occurence number / total + add (we are doing cumulative probability)
    for(std::map<std::vector<QChar>, std::pair<int,double>>::iterator secondPass = cePrBegin; secondPass!=cePrEnd && secondPass!=charmap.end(); ++secondPass) {
        secondPass->second.second = double(secondPass->second.first) / nbPosLet;
        if (secondPass != cePrBegin && secondPass!=charmap.begin() )
            secondPass->second.second += prev(secondPass)->second.second; //prev() = previous element
    }
}

We may now generate a word. We want to find, letter after letter, which letter we should append to the word. For this, we get a random number r in [0,1]. From the previous example, if r < 0.3 we append a e to th, if 0.3 < r < 0.9 it's an i and if 0.9 < r < 1 it's an o.

For this, we have two iterators representing th\firsPossibleCharacter and th\lastPossibileCharacter and go from one to the other, comparing r to the second of the pair each time.

Note that end of word if a character like any other, but we can force the size of the word, it if ever it gets to long.

string Qgenerateur(std::map<std::vector<QChar>, pair<int,double>> &charmap, uint lcoh, uint maxsize) {
    QString myword="";

    vector<QChar> cePr(lcoh-1,'\0'); //represents the chain of previous characters
    vector<QChar> cePrMin, cePrMax; //represents the chain of previous character + the first (resp. last) possible character
    cePrMin.reserve(lcoh); cePrMax.reserve(lcoh);
    map<vector<QChar>, pair<int,double>>::iterator it, itLow, itHigh;
    //itLow : iterator to the first element of the map having this chain of previous character (=cePr)
    //itHigh: iterator to the element after the last element of the map having this chain of previous character (=cePr)

    do {
        cePrMin=cePr;   cePrMin.push_back(QChar::Null);
        cePrMax=cePr;   cePrMax.push_back(QChar::LastValidCodePoint);

        itLow = charmap.lower_bound(cePrMin);
        itHigh = charmap.upper_bound(cePrMax);
        it = itLow;

        double r = double(rand())/ RAND_MAX; // 0 < r < 1
        while (r > it->second.second && it != itHigh) { //places iterator to the 1st caracter having a probability less than r
            it++;
        }
        myword += QString(it->first.back()); //append this caracter to the word
        //it.first is the vector of QChar, representing the letter chain. We append its last letter to our word (the previous letters are already in the word)

        for(uint i=0; i<cePr.size()-1; i++) {
            cePr[i] = cePr[i+1];
        }
        cePr[cePr.size()-1] = it->first.back();
    } while ( (it->first.back()!='\0') && uint(myword.size()) <= maxsize);
    return myword.toStdString();
}

Here it is, we have invented a word. It's a bit complicated (for myself at least, I got confused multiple times). I do not especially expect a review from the algorithmic point of view, more for the code itself, for improvement or clarity.

Note the use of Qt Qstring and Qchar. This is the best solution I found to handle accentuated letter (I'm messed up with wchar_t, didn't manage to did it easily), but maybe there is another solution?

I also had one question: I wanted to monitor the progress of the analysis, so I added the nb parameter to QanalyzeWord. Is there a solution to do this debugging without modifying the function prototype (e.g. don't have nb in the prototype), knowing that this is only for debugging, not final release?

And also: should I have used auto instead of these awfully long iterator type?

Answer 1

I find your code very dense and difficult to skim. I think you can help it quite a bit by making sure each statement is on a line by itself; that there's whitespace around your operators; and that you use std:: qualification on standard library types and functions. More controversially, I would say "don't abuse foo++ to mean foo += 1" — the shorthand operator should be used only in idioms such as for.

Also, I'd avoid cryptic abbreviations like uint for unsigned — and in fact, I'd avoid unsigned types in APIs altogether!

You also write word.at(i) where word[i] would suffice; and in fact you don't need i at all if you just use a plain old ranged for loop for (QChar ch : word).

So where you had

void QanalyzeWord(const QString &word, map<vector<QChar>, pair<int,double>> &charmap, uint lcoh, int &nb) {
    vector<QChar> letterChain(lcoh,'\0');

    for(int i=0; i<word.size(); i++) {
        letterChain[lcoh-1]=word.at(i);
        charmap[letterChain].first++;
        nb++;
        for(uint j=0; j<lcoh-1; j++) {
            letterChain[j]=letterChain[j+1];
        }
    }

    //Indicates last character is void
    letterChain[lcoh-1]='\0';
    charmap[letterChain].first++;
    return;
}

I would write

void QanalyzeWord(
    const QString& word,
    std::map<std::vector<QChar>, std::pair<int, double>>& charmap,
    int lcoh,
    int& nb)
{
    std::vector<QChar> letterChain(lcoh, '\0');

    for (QChar ch : word) {
        charmap[letterChain].first += 1;
        nb += 1;
        letterChain[lcoh - 1] = ch;
        for (int j = 0; j < lcoh - 1; ++j) {
            letterChain[j] = letterChain[j+1];
        }
    }

    letterChain[lcoh-1] = '\0';
    charmap[letterChain].first += 1;
}

---

The next thing to look at is that inner loop (for (int j...)). It looks wrong at a glance, because it seems to be "shifting down" every letter in the array... but we've already overwritten one of the letters in the array with a new value! It looks like what we meant to write was

        for (int j = 0; j < lcoh - 1; ++j) {
            letterChain[j] = letterChain[j+1];
        }
        letterChain[lcoh - 1] = ch;

or more concisely,

        std::copy(letterChain.begin() + 1, letterChain.end(), letterChain.begin());
        letterChain.back() = ch;

or more concisely,

        QChar *first = &letterChain[0];
        *first = ch;
        std::rotate(first, first + lcoh, first + 1);

---

The line charmap[letterChain].first += 1; also wants some attention. What is .first? Well, we can look at the function signature and find that charmap[letterChain] is a std::pair<int, double>. But we don't know what the int and the double represent. So it would help the reader understand the code if we created a custom data type:

struct MapEntry {
    int occurrences = 0;
    double not_sure_what_this_is = 0.0;
};

And then we could write

charmap[letterChain].occurrences += 1;

which is a little bit clearer. I suspect that the names charmap and MapEntry both could be improved. Naming is important!

---

I didn't really look at the other snippets in your question, but I did notice this part:

if (cePr==std::vector<QChar>(&it->first[0], &it->first[lcoh-1])) ...

Heap-allocating a vector just to do a comparison seems like overkill. You should look into the std::equal algorithm

if (std::equal(cePr.begin(), cePr.end(), it->first.begin(), it->first.end() - 1)) ...

or just write a helper function that can compare two ranges for you.

if (vector_begins_with(it->first, cePr)) ...