15
\$\begingroup\$

This was the most humerus coding I've ever done. It's for my string library in C. It detects if the user is angry to various degrees, namely str_isHeated().

Why?

Ever play a text-based game and you're swearing at the computer by typing, typing multiple !!!, and the computer responds very dumb? I think it may be useful for AI where NPC's (non-playable characters) can judge your mood and respond appropriately. Maybe even used for customer service online.

It works, but I'm interested to see if anyone has any thoughts on how to improve it. I've been having some fun with it.

/*
Function: str_getHeat()
Software usually gets user information, but it hardly 
detects the user's emotion when entering in the information. 
This may be useful for checking a customer's or player's 
typing behavior, which may generate better responses with AI.
Calculated as follows:
    All Caps 
    One or more words in caps
    Exclamation Point Count
    If 'please' or 'sorry' is found, take off heat points.
    Swearing words
Returns: EHeat_Cold, EHeat_Warm, EHeat_Heated, EHeat_VeryHeated
*/
EHeat str_isHeated(STRING *objString)
{
int i;
int intHeatScore = 0;       /* 0% cold; 100% very heated */
STRINGCOLLECTION tokens; 
STRING temp_a;

/* Count how many exclamations there are */
for (i = 0; i < objString->length; i++)
{
    if (objString->str[i] == '!')
        intHeatScore += 10;
}

/* tokenize user's input */
sc_init(&tokens);
str_tokenize(objString, &tokens); 

    /* Check if all caps. That can be taken as impatient. */
if (str_isUpper(objString))
{
    intHeatScore += 10;
}
else
{
    /* check if one or more words are all in caps. That is 
       demanding behavior, and that is not nice. */
    for (i = 0; i < tokens.count; i++)
    {
        if (str_isUpperCString(tokens.items[i])) 
        { 
            intHeatScore += 10; 

            /* 'I' is excused. */
            if (!strcmp(tokens.items[i], "I"))
                intHeatScore -= 10; 
        } 
    }
}

/* Check if the user said please. That's always nice. 
   Take off a few heat points. */
if (str_findStringIgnoreCaps(objString, "please"))
    intHeatScore -= 6;

/* Check if the user said he's sorry. That's also nice. */
if (str_findStringIgnoreCaps(objString, "sorry"))
    intHeatScore -= 6;

/* Almost forgot... swearing. That is never nice. */   
for (i = 0; i < tokens.count; i++)
{
    str_setText(&temp_a, tokens.items[i]);
    str_toLower(&temp_a);

    /* don't say these words out loud (censored for your innocence*/
    if (str_findString(&temp_a, "$#@#") ||    
        str_findString(&temp_a, "@#$@") ||
        str_findString(&temp_a, "@$$") ||
			str_findString(&temp_a, "@$$#@") ||   
        str_findString(&temp_a, "%#@") ||   
        str_findString(&temp_a, "@#$") 
        )
    {
        /* big no-no */
        intHeatScore += 20;
    } 
}

/* Check the final heat score */
if (intHeatScore >= 50)
    return EHeat_VeryHeated;

else if (intHeatScore >= 30)
    return EHeat_Heated;

else if (intHeatScore > 10)
    return EHeat_Warm;

else if (intHeatScore >= 0)
    return EHeat_Cold; 

return EHeat_Cold;
}
\$\endgroup\$
  • 8
    \$\begingroup\$ My initial thought was "lol" :) \$\endgroup\$ – Mathieu Guindon Dec 11 '13 at 19:18
  • 2
    \$\begingroup\$ If you're interested into the more academic side of this, look into sentiment analysis. What you've done is make a simple sentiment analyzer. \$\endgroup\$ – Corbin Dec 11 '13 at 19:49
  • \$\begingroup\$ How about a dictionary of sorts for the words: char *words[] = {"!#@&", "^#$%", …}; \$\endgroup\$ – Fiddling Bits Dec 11 '13 at 21:57
  • \$\begingroup\$ Good idea! I actually made a string table DS earlier, so I'll try it out. \$\endgroup\$ – Phil Dec 11 '13 at 23:01
  • \$\begingroup\$ Or that works too.. \$\endgroup\$ – Phil Dec 11 '13 at 23:14
8
\$\begingroup\$

Algorithm:

There are a few fallacies that you assume in your approach. Nothing wrong, but things that could be improved:

  • You assume bounds on your "heat score" with this comment

    /* 0% cold; 100% very heated */
    

    But there is no code implementing these bounds. You can go negative, as well as go above 100. I'd recommend observing these bounds, and sentiment should be seen as a probability which can only be between 0 and 1.

    To match this probability, it might be better for you to store your sentiment score as a double rather than an int but that choice is up to you.

  • Right now you are using a bag-of-words model. This is a typical approach when first starting out with sentiment analysis since it is easier, but it usually gives a lower accuracy representing what the actual sentiment of the text is.

    As I was saying, it's a fairly straightforward and practical way to go, but there are a lot of situations where it will get make mistakes.

    1. Ambiguous sentiment words - "This product works terribly" vs. "This product is terribly good"

    2. Missed negations - "I would never in a millions years say that this product is worth buying"

    3. Quoted/Indirect text - "My dad says this product is terrible, but I disagree"

    4. Comparisons - "This product is about as useful as a hole in the head"

    5. Anything subtle - "This product is ugly, slow and uninspiring, but it's the only thing on the market that does the job"

    As far as NLP helping you with any of this, word sense disambiguation (or even just part-of-speech tagging) may help with (1), syntactic parsing might help with the long range dependencies in (2), some kind of chunking might help with (3). It's all research level work though, there's nothing that I know of that you can directly use. Issues (4) and (5) are a lot harder, I throw up my hands and give up at this point.

  • You are going to not score a decent amount of sentences that occur in actual life. Take a look at a lot of sentences in this post, for example. They don't contain swear words, "please" or "sorry", exclamation points or words in caps. You need a more general lexicon of positive, negative, and neutral words and then a system to weigh in the effects of these words into your score.

  • There are some odd score modifications you do. Why is it when I refer to myself with "I", that the score is considered more positive? I don't think it should, and I would say to reconsider the reason you think so.

    Sentences that end with an exclamation point aren't necessary negative (higher heat) either. An exclamation point is often used to indicate strong feelings (such as excitement) or high volume. Most sentiment analysis systems that I've looked at don't consider punctuation in the final score at all.

    "A" should be considered the same as "I". It is very possible that a sentence could start with "A", and be either positive or neutral but your program considers it to have a negative connotation.

For a basic sentiment analysis this is fine, but do note that it does have it's flaws. If you're looking to improve the accuracy of your algorithm, I'd recommend reading this research paper, which achieves a classification accuracy of 90% (higher than any other published results).

Code:

  • Right now you have the method str_findString(). I'm guessing this is an variation of strstr(). I'm also guessing that <string.h>'s implementation of this method will be more efficient and faster, based on it being a standard library.

    if (strstr(temp_a, "$#@#"))
    {
        ...
    }
    
  • Declare i inside of your for loops.(C99)

    for (int i = 0; i < objString->length; i++)
    
  • I would add another tab to the function body.

    EHeat str_isHeated(STRING *objString)
    {
        int intHeatScore = 0;       /* 0% cold; 100% very heated */
        STRINGCOLLECTION tokens; 
    
  • I would combine your last two return conditions into one.

    else if (intHeatScore >= 0)
        return EHeat_Cold; 
    
    return EHeat_Cold;
    

    I find the last else-if comparison useless overall, and would just return EHeat_Cold anyways if it wasn't included.

    return EHeat_Cold;
    
  • I'm not too sure about what I'm assuming are #defines: STRING and STRINGCOLLECTION. I guess it is okay to keep them, but is there a specific reason you don't just put in what they actually are: char* and char* array respectively?

\$\endgroup\$
5
\$\begingroup\$

I would try and approach this more generically.

Define a rules interface, run each section of the string through the Rule and add the result.

The rules can then check individually for all caps, exclamation marks, etc rather than hard coding it into your central method.

(i.e. a rule that returns 1 point for every exclamation mark it finds or something).

Might be worth having two types of rule - "full string rule" and "word rule". the full string rule can process things like total number of exclamation marks and stuff, then you split the string on whitespace and run all the found words through the word rules.

For things like nice/nasty words I would have a configuration file somewhere listing words and a positive or negative score next to them - for example please -10, swearing +10, etc.

Your word rule can then scan your words against that dictionary and apply the result to your score.

\$\endgroup\$
4
\$\begingroup\$

Use a hash table! Something like this would work:

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>
#include <sys/resource.h>
#include <sys/time.h>


// default dictionary (LIST OF BAD WORDS)
#define DICTIONARY "/PATH_TO_BAD_WORDS"

// prototype
double calculate(const struct rusage* b, const struct rusage* a);

int main(int argc, char* argv[])
{
    // check for correct number of args
    if (argc != 2 && argc != 3)
    {
        printf("Usage: speller [dictionary] text\n");
        return 1;
    }

    // structs for timing data
    struct rusage before, after;

    // benchmarks
    double ti_load = 0.0, ti_check = 0.0, ti_size = 0.0, ti_unload = 0.0;

    // determine dictionary to use
    char* dictionary = (argc == 3) ? argv[1] : DICTIONARY;

    // load dictionary
    getrusage(RUSAGE_SELF, &before);
    bool loaded = load(dictionary);
    getrusage(RUSAGE_SELF, &after);

    // abort if dictionary not loaded
    if (!loaded)
    {
        printf("Could not load %s.\n", dictionary);
        return 1;
    }

    // calculate time to load dictionary
    ti_load = calculate(&before, &after);

    // try to open text
    char* text = (argc == 3) ? argv[2] : argv[1];
    FILE* fp = fopen(text, "r");
    if (fp == NULL)
    {
        printf("Could not open %s.\n", text);
        unload();
        return 1;
    }

    // prepare to report misspellings
    printf("\nMISSPELLED WORDS\n\n");

    // prepare to spell-check
    int index = 0, misspellings = 0, words = 0;
    char word[LENGTH+1];

    // spell-check each word in text
    for (int c = fgetc(fp); c != EOF; c = fgetc(fp))
    {
        // allow only alphabetical characters and apostrophes
        if (isalpha(c) || (c == '\'' && index > 0))
        {
            // append character to word
            word[index] = c;
            index++;

            // ignore alphabetical strings too long to be words
            if (index > LENGTH)
            {
                // consume remainder of alphabetical string
                while ((c = fgetc(fp)) != EOF && isalpha(c));

                // prepare for new word
                index = 0;
            }
        }

        // ignore words with numbers (like MS Word can)
        else if (isdigit(c))
        {
            // consume remainder of alphanumeric string
            while ((c = fgetc(fp)) != EOF && isalnum(c));

            // prepare for new word
            index = 0;
        }

        // we must have found a whole word
        else if (index > 0)
        {
            // terminate current word
            word[index] = '\0';

            // update counter
            words++;

            // check word's spelling
            getrusage(RUSAGE_SELF, &before);
            bool misspelled = !check(word);
            getrusage(RUSAGE_SELF, &after);

            // update benchmark
            ti_check += calculate(&before, &after);

            // print word if misspelled
            if (misspelled)
            {
                printf("%s\n", word);
                misspellings++;
            }

            // prepare for next word
            index = 0;
        }
    }

    // check whether there was an error
    if (ferror(fp))
    {
        fclose(fp);
        printf("Error reading %s.\n", text);
        unload();
        return 1;
    }

    // close text
    fclose(fp);

    // determine dictionary's size
    getrusage(RUSAGE_SELF, &before);
    unsigned int n = size();
    getrusage(RUSAGE_SELF, &after);

    // calculate time to determine dictionary's size
    ti_size = calculate(&before, &after);

    // unload dictionary
    getrusage(RUSAGE_SELF, &before);
    bool unloaded = unload();
    getrusage(RUSAGE_SELF, &after);

    // abort if dictionary not unloaded
    if (!unloaded)
    {
        printf("Could not unload %s.\n", dictionary);
        return 1;
    }

    // calculate time to unload dictionary
    ti_unload = calculate(&before, &after);

    // report benchmarks
    printf("\nWORDS MISSPELLED:     %d\n", misspellings);
    printf("WORDS IN DICTIONARY:  %d\n", n);
    printf("WORDS IN TEXT:        %d\n", words);
    printf("TIME IN load:         %.2f\n", ti_load);
    printf("TIME IN check:        %.2f\n", ti_check);
    printf("TIME IN size:         %.2f\n", ti_size);
    printf("TIME IN unload:       %.2f\n", ti_unload);
    printf("TIME IN TOTAL:        %.2f\n\n", 
     ti_load + ti_check + ti_size + ti_unload);

    // that's all folks
    return 0;
}

/**
 * Returns number of seconds between b and a.
 */
double calculate(const struct rusage* b, const struct rusage* a)
{
    if (b == NULL || a == NULL)
    {
        return 0.0;
    }
    else
    {
        return ((((a->ru_utime.tv_sec * 1000000 + a->ru_utime.tv_usec) -
                 (b->ru_utime.tv_sec * 1000000 + b->ru_utime.tv_usec)) +
                ((a->ru_stime.tv_sec * 1000000 + a->ru_stime.tv_usec) -
                 (b->ru_stime.tv_sec * 1000000 + b->ru_stime.tv_usec)))
                / 1000000.0);
    }
}
// maximum length for a word
// (e.g., pneumonoultramicroscopicsilicovolcanoconiosis)
#define LENGTH 45

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word);

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary);

/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void);

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void);


// size of hashtable
#define SIZE 1000000

// create nodes for linked list
typedef struct node
{
    char word[LENGTH+1];
    struct node* next;
}
node;

// create hashtable
node* hashtable[SIZE] = {NULL};

// create hash function
int hash (const char* word)
{
    int hash = 0;
    int n;
    for (int i = 0; word[i] != '\0'; i++)
    {
        // alphabet case
        if(isalpha(word[i]))
            n = word [i] - 'a' + 1;

        // comma case
        else
            n = 27;

        hash = ((hash << 3) + n) % SIZE;
    }
    return hash;    
}

// create global variable to count size
int dictionarySize = 0;

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    // TODO
    // opens dictionary
    FILE* file = fopen(dictionary, "r");
    if (file == NULL)
        return false;

    // create an array for word to be stored in
    char word[LENGTH+1];

    // scan through the file, loading each word into the hash table
    while (fscanf(file, "%s\n", word)!= EOF)
    {
        // increment dictionary size
        dictionarySize++;

        // allocate memory for new word 
        node* newWord = malloc(sizeof(node));

        // put word in the new node
        strcpy(newWord->word, word);

        // find what index of the array the word should go in
        int index = hash(word);

        // if hashtable is empty at index, insert
        if (hashtable[index] == NULL)
        {
            hashtable[index] = newWord;
            newWord->next = NULL;
        }

        // if hashtable is not empty at index, append
        else
        {
            newWord->next = hashtable[index];
            hashtable[index] = newWord;
        }      
    }

    // close file
    fclose(file);

    // return true if successful 
    return true;
}

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    // TODO
    // creates a temp variable that stores a lower-cased version of the word
    char temp[LENGTH + 1];
    int len = strlen(word);
    for(int i = 0; i < len; i++)
        temp[i] = tolower(word[i]);
    temp[len] = '\0';

    // find what index of the array the word should be in
    int index = hash(temp);

    // if hashtable is empty at index, return false
    if (hashtable[index] == NULL)
    {
        return false;
    }

    // create cursor to compare to word
    node* cursor = hashtable[index];

    // if hashtable is not empty at index, iterate through words and compare
    while (cursor != NULL)
    {
        if (strcmp(temp, cursor->word) == 0)
        {
            return true;
        }
        cursor = cursor->next;
    }

    // if you don't find the word, return false
    return false;
}

/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{
    // TODO
    // if dictionary is loaded, return number of words
    if (dictionarySize > 0)
    {
        return dictionarySize;
    }

    // if dictionary hasn't been loaded, return 0
    else
        return 0;
}

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void)
{
    // TODO
    // create a variable to go through index
    int index = 0;

    // iterate through entire hashtable array
    while (index < SIZE)
    {
        // if hashtable is empty at index, go to next index
        if (hashtable[index] == NULL)
        {
            index++;
        }

        // if hashtable is not empty, iterate through nodes and start freeing
        else
        {
            while(hashtable[index] != NULL)
            {
                node* cursor = hashtable[index];
                hashtable[index] = cursor->next;
                free(cursor);
            }

            // once hashtable is empty at index, go to next index
            index++;
        }
    }

    // return true if successful
    return true;
}

#ifndef DICTIONARY_H
\$\endgroup\$

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.