megahal.c

megahal is the conversation simulators conversing with a user in natural language. The program will

    /*
     *		Return the best answer we generated
     */
    return(output);
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Dissimilar
 *
 *		Purpose:		Return TRUE or FALSE depending on whether the dictionaries
 *						are the same or not.
 */
bool dissimilar(DICTIONARY *words1, DICTIONARY *words2)
{
    register unsigned int i;

    if(words1->size!=words2->size) return(TRUE);
    for(i=0; i<words1->size; ++i)
	if(wordcmp(words1->entry[i], words2->entry[i])!=0) return(TRUE);
    return(FALSE);
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Make_Keywords
 *
 *		Purpose:		Put all the interesting words from the user's input into
 *						a keywords dictionary, which will be used when generating
 *						a reply.
 */
DICTIONARY *make_keywords(MODEL *model, DICTIONARY *words)
{
    static DICTIONARY *keys=NULL;
    register unsigned int i;
    register unsigned int j;
    int c;

    if(keys==NULL) keys=new_dictionary();
    for(i=0; i<keys->size; ++i) free(keys->entry[i].word);
    free_dictionary(keys);

    for(i=0; i<words->size; ++i) {
	/*
	 *		Find the symbol ID of the word.  If it doesn't exist in
	 *		the model, or if it begins with a non-alphanumeric
	 *		character, or if it is in the exclusion array, then
	 *		skip over it.
	 */
	c=0;
	for(j=0; j<swp->size; ++j)
	    if(wordcmp(swp->from[j], words->entry[i])==0) {
		add_key(model, keys, swp->to[j]);
		++c;
	    }
	if(c==0) add_key(model, keys, words->entry[i]);
    }

    if(keys->size>0) for(i=0; i<words->size; ++i) {

	c=0;
	for(j=0; j<swp->size; ++j)
	    if(wordcmp(swp->from[j], words->entry[i])==0) {
		add_aux(model, keys, swp->to[j]);
		++c;
	    }
	if(c==0) add_aux(model, keys, words->entry[i]);
    }

    return(keys);
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Add_Key
 *
 *		Purpose:		Add a word to the keyword dictionary.
 */
void add_key(MODEL *model, DICTIONARY *keys, STRING word)
{
    int symbol;

    symbol=find_word(model->dictionary, word);
    if(symbol==0) return;
    if(isalnum(word.word[0])==0) return;
    symbol=find_word(ban, word);
    if(symbol!=0) return;
    symbol=find_word(aux, word);
    if(symbol!=0) return;

    add_word(keys, word);
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Add_Aux
 *
 *		Purpose:		Add an auxilliary keyword to the keyword dictionary.
 */
void add_aux(MODEL *model, DICTIONARY *keys, STRING word)
{
    int symbol;

    symbol=find_word(model->dictionary, word);
    if(symbol==0) return;
    if(isalnum(word.word[0])==0) return;
    symbol=find_word(aux, word);
    if(symbol==0) return;

    add_word(keys, word);
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Reply
 *
 *		Purpose:		Generate a dictionary of reply words appropriate to the
 *						given dictionary of keywords.
 */
DICTIONARY *reply(MODEL *model, DICTIONARY *keys)
{
    static DICTIONARY *replies=NULL;
    register int i;
    int symbol;
    bool start=TRUE;

    if(replies==NULL) replies=new_dictionary();
    free_dictionary(replies);

    /*
     *		Start off by making sure that the model's context is empty.
     */
    initialize_context(model);
    model->context[0]=model->forward;
    used_key=FALSE;

    /*
     *		Generate the reply in the forward direction.
     */
    while(TRUE) {
	/*
	 *		Get a random symbol from the current context.
	 */
	if(start==TRUE) symbol=seed(model, keys);
	else symbol=babble(model, keys, replies);
	if((symbol==0)||(symbol==1)) break;
	start=FALSE;

	/*
	 *		Append the symbol to the reply dictionary.
	 */
	if(replies->entry==NULL)
	    replies->entry=(STRING *)malloc((replies->size+1)*sizeof(STRING));
	else
	    replies->entry=(STRING *)realloc(replies->entry, (replies->size+1)*sizeof(STRING));
	if(replies->entry==NULL) {
	    error("reply", "Unable to reallocate dictionary");
	    return(NULL);
	}

	replies->entry[replies->size].length=
	    model->dictionary->entry[symbol].length;
	replies->entry[replies->size].word=
	    model->dictionary->entry[symbol].word;
	replies->size+=1;

	/*
	 *		Extend the current context of the model with the current symbol.
	 */
	update_context(model, symbol);
    }

    /*
     *		Start off by making sure that the model's context is empty.
     */
    initialize_context(model);
    model->context[0]=model->backward;

    /*
     *		Re-create the context of the model from the current reply
     *		dictionary so that we can generate backwards to reach the
     *		beginning of the string.
     */
    if(replies->size>0) for(i=MIN(replies->size-1, model->order); i>=0; --i) {
	symbol=find_word(model->dictionary, replies->entry[i]);
	update_context(model, symbol);
    }

    /*
     *		Generate the reply in the backward direction.
     */
    while(TRUE) {
	/*
	 *		Get a random symbol from the current context.
	 */
	symbol=babble(model, keys, replies);
	if((symbol==0)||(symbol==1)) break;

	/*
	 *		Prepend the symbol to the reply dictionary.
	 */
	if(replies->entry==NULL)
	    replies->entry=(STRING *)malloc((replies->size+1)*sizeof(STRING));
	else
	    replies->entry=(STRING *)realloc(replies->entry, (replies->size+1)*sizeof(STRING));
	if(replies->entry==NULL) {
	    error("reply", "Unable to reallocate dictionary");
	    return(NULL);
	}

	/*
	 *		Shuffle everything up for the prepend.
	 */
	for(i=replies->size; i>0; --i) {
	    replies->entry[i].length=replies->entry[i-1].length;
	    replies->entry[i].word=replies->entry[i-1].word;
	}

	replies->entry[0].length=model->dictionary->entry[symbol].length;
	replies->entry[0].word=model->dictionary->entry[symbol].word;
	replies->size+=1;

	/*
	 *		Extend the current context of the model with the current symbol.
	 */
	update_context(model, symbol);
    }

    return(replies);
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Evaluate_Reply
 *
 *		Purpose:		Measure the average surprise of keywords relative to the
 *						language model.
 */
float evaluate_reply(MODEL *model, DICTIONARY *keys, DICTIONARY *words)
{
    register unsigned int i;
    register int j;
    register int k;
    int symbol;
    float probability;
    int count;
    float entropy=(float)0.0;
    TREE *node;
    int num=0;

    if(words->size<=0) return((float)0.0);
    initialize_context(model);
    model->context[0]=model->forward;
    for(i=0; i<words->size; ++i) {
	symbol=find_word(model->dictionary, words->entry[i]);

	if(find_word(keys, words->entry[i])!=0) {
	    probability=(float)0.0;
	    count=0;
	    ++num;
	    for(j=0; j<model->order; ++j) if(model->context[j]!=NULL) {

		node=find_symbol(model->context[j], symbol);
		probability+=(float)(node->count)/
		    (float)(model->context[j]->usage);
		++count;

	    }

	    if(count>0.0) entropy-=(float)log(probability/(float)count);
	}

	update_context(model, symbol);
    }

    initialize_context(model);
    model->context[0]=model->backward;
    for(k=words->size-1; k>=0; --k) {
	symbol=find_word(model->dictionary, words->entry[k]);

	if(find_word(keys, words->entry[k])!=0) {
	    probability=(float)0.0;
	    count=0;
	    ++num;
	    for(j=0; j<model->order; ++j) if(model->context[j]!=NULL) {

		node=find_symbol(model->context[j], symbol);
		probability+=(float)(node->count)/
		    (float)(model->context[j]->usage);
		++count;

	    }

	    if(count>0.0) entropy-=(float)log(probability/(float)count);
	}

	update_context(model, symbol);
    }

    if(num>=8) entropy/=(float)sqrt(num-1);
    if(num>=16) entropy/=(float)num;

    return(entropy);
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Make_Output
 *
 *		Purpose:		Generate a string from the dictionary of reply words.
 */
char *make_output(DICTIONARY *words)
{
    static char *output=NULL;
    register unsigned int i;
    register int j;
    int length;
    static char *output_none=NULL;

    if(output_none==NULL) output_none=malloc(40);

    if(output==NULL) {
	output=(char *)malloc(sizeof(char));
	if(output==NULL) {
	    error("make_output", "Unable to allocate output");
	    return(output_none);
	}
    }

    if(words->size==0) {
	if(output_none!=NULL)
	    strcpy(output_none, "I am utterly speechless!");
	return(output_none);
    }

    length=1;
    for(i=0; i<words->size; ++i) length+=words->entry[i].length;

    output=(char *)realloc(output, sizeof(char)*length);
    if(output==NULL) {
	error("make_output", "Unable to reallocate output.");
	if(output_none!=NULL)
	    strcpy(output_none, "I forgot what I was going to say!");
	return(output_none);
    }

    length=0;
    for(i=0; i<words->size; ++i)
	for(j=0; j<words->entry[i].length; ++j)
	    output[length++]=words->entry[i].word[j];

    output[length]='\0';

    return(output);
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Babble
 *
 *		Purpose:		Return a random symbol from the current context, or a
 *						zero symbol identifier if we've reached either the
 *						start or end of the sentence.  Select the symbol based
 *						on probabilities, favouring keywords.  In all cases,
 *						use the longest available context to choose the symbol.
 */
int babble(MODEL *model, DICTIONARY *keys, DICTIONARY *words)
{
    TREE *node;
    register int i;
    int count;
    int symbol = 0;

    node = NULL;

    /*
     *		Select the longest available context.
     */
    for(i=0; i<=model->order; ++i)
	if(model->context[i]!=NULL)
	    node=model->context[i];

    if(node->branch==0) return(0);

    /*
     *		Choose a symbol at random from this context.
     */
    i=rnd(node->branch);
    count=rnd(node->usage);
    while(count>=0) {
	/*
	 *		If the symbol occurs as a keyword, then use it.  Only use an
	 *		auxilliary keyword if a normal keyword has already been used.
	 */
	symbol=node->tree[i]->symbol;

	if(
	    (find_word(keys, model->dictionary->entry[symbol])!=0)&&
	    ((used_key==TRUE)||
	     (find_word(aux, model->dictionary->entry[symbol])==0))&&
	    (word_exists(words, model->dictionary->entry[symbol])==FALSE)
	    ) {
	    used_key=TRUE;
	    break;
	}
	count-=node->tree[i]->count;
	i=(i>=(node->branch-1))?0:i+1;
    }

    return(symbol);
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Word_Exists
 *
 *		Purpose:		A silly brute-force searcher for the reply string.
 */
bool word_exists(DICTIONARY *dictionary, STRING word)
{
    register unsigned int i;

    for(i=0; i<dictionary->size; ++i)
	if(wordcmp(dictionary->entry[i], word)==0)
	    return(TRUE);
    return(FALSE);
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Seed
 *
 *		Purpose:		Seed the reply by guaranteeing that it contains a
 *						keyword, if one exists.
 */
int seed(MODEL *model, DICTIONARY *keys)
{
    register unsigned int i;
    int symbol;
    unsigned int stop;

    /*
     *		Fix, thanks to Mark Tarrabain
     */
    if(model->context[0]->branch==0) symbol=0;
    else symbol=model->context[0]->tree[rnd(model->context[0]->branch)]->symbol;

    if(keys->size>0) {
	i=rnd(keys->size);
	stop=i;
	while(TRUE) {
	    if(
		(find_word(model->dictionary, keys->entry[i])!=0)&&
		(find_word(aux, keys->entry[i])==0)
		) {
		symbol=find_word(model->dictionary, keys->entry[i]);
		return(symbol);
	    }
	    ++i;
	    if(i==keys->size) i=0;
	    if(i==stop) return(symbol);
	}
    }

    return(symbol);
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	New_Swap
 *
 *		Purpose:		Allocate a new swap structure.
 */
SWAP *new_swap(void)
{
    SWAP *list;

    list=(SWAP *)malloc(sizeof(SWAP));
    if(list==NULL) {
	error("new_swap", "Unable to allocate swap");
	return(NULL);
    }
    list->size=0;
    list->from=NULL;
    list->to=NULL;

    return(list);
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Add_Swap
 *
 *		Purpose:		Add a new entry to the swap structure.
 */
void add_swap(SWAP *list, char *s, char *d)
{
    list->size+=1;

    if(list->from==NULL) {
	list->from=(STRING *)malloc(sizeof(STRING));
	if(list->from==NULL) {
	    error("add_swap", "Unable to allocate list->from");
	    return;
	}
    }

    if(list->to==NULL) {
	list->to=(STRING *)malloc(sizeof(STRING));
	if(list->to==NULL) {
	    error("add_swap", "Unable to allocate list->to");
	    return;
	}
    }

    list->from=(STRING *)realloc(list->from, sizeof(STRING)*(list->size));
    if(list->from==NULL) {
	error("add_swap", "Unable to reallocate from");
	return;
    }

    list->to=(STRING *)realloc(list->to, sizeof(STRING)*(list->size));
    if(list->to==NULL) {
	error("add_swap", "Unable to reallocate to");
	return;
    }

    list->from[list->size-1].length=strlen(s);
    list->from[list->size-1].word=strdup(s);
    list->to[list->size-1].length=strlen(d);
    list->to[list->size-1].word=strdup(d);
}

/*---------------------------------------------------------------------------*/

/*
 *		Function:	Initialize_Swap
 *
 *		Purpose:		Read a swap