4
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Are the any changes in this code from the original question? \$\endgroup\$ – pacmaninbw Sep 1 '19 at 16:00
  • 1
    \$\begingroup\$ I applied the suggested modification (English only, consistent syntax), but the difference is its only 3 (very small) parts and not the whole program \$\endgroup\$ – sayanel Sep 1 '19 at 16:40
  • \$\begingroup\$ Do you have a GitHub or GitLab account or some other repository that you could provide a link to. I didn't see one on the other question either. It might be good as hiring employers might like to view your code. \$\endgroup\$ – pacmaninbw Sep 1 '19 at 17:39
  • 1
    \$\begingroup\$ I'm not really sure I wantpotential employer to see that, first I would like to know about its quality... Anyway I would set up one, it will allow to test it \$\endgroup\$ – sayanel Sep 2 '19 at 6:51
  • \$\begingroup\$ it's done, full project can be found here on Github \$\endgroup\$ – sayanel Sep 9 '19 at 17:09
1
\$\begingroup\$

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)) ...
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for for review! I learnt some there. What would be a suitable name for charmap (it is, after all, a map in which characters are the keys)? Also the double in the pair is a probability (of seeing this key occur), it is handled in the second block of code in the post. \$\endgroup\$ – sayanel Sep 7 '19 at 14:20
  • \$\begingroup\$ "What would be a suitable name for charmap (it is, after all, a map in which characters are the keys)" — Right, I can see that it's a map of char to double just based on the type. But what does it represent? From your comment it sounds like maybe it's a frequency or probability histogram, such that charmap[k] represents the probability of character k? In that case, probability_of_character[k] would be a pretty self-descriptive name. \$\endgroup\$ – Quuxplusone Sep 7 '19 at 17:15

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.