16
\$\begingroup\$

Since I posted my first version of the spelling corrector here, I've been working on improving it a little in my free time. I've also gone ahead and put the project up on Github so that others can now make contributions to the project if they wish to do so.

checkmate.c:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <search.h>
#include <fcntl.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>

#define TABLE_SIZE 5013
#define ALPHABET_SIZE (sizeof(alphabet) - 1)

char *dictionary = "5k.txt";
const char alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                        "abcdefghijklmnopqrstuvwxyz"
                        " '";

void *checkedMalloc(size_t len)
{
    void *ret = malloc(len);
    if (!ret)
    {
        fputs("Out of memory!", stderr);
        exit(0);
    }
    return ret;
}

int arrayExist(char **array, int rows, char *word)
{
    for (int i = 0; i < rows; ++i)
    {
        if (!strcmp(array[i], word)) return 1;
    }
    return 0;
}

void arrayCleanup(char **array, int rows)
{
    for (int i = 0; i < rows; i++)
    {
        free(array[i]);
    }
}

ENTRY *find(char *word)
{
    return hsearch((ENTRY){.key = word}, FIND);
}

/**
 * Takes in a file name to open and read into the hast table dict
 *
 * @param fileName Name of file to open
 * @param dict Empty ENTRY that is at least the size of the number of lines in
 the file opened by fileName
 */
int readDictionary(const char* fileName, ENTRY dict)
{
    int fd = open(fileName, O_RDONLY);
    if (fd < 0) return 0;

    struct stat sb;
    if (stat(dictionary, &sb)) return 0;
    char *result = strdup(mmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE, fd, 0));
    if (result != MAP_FAILED)
    {
        char *w = NULL;
        char *delimiter = "\n";
        char *word = strtok(result, delimiter);
        for (size_t i = 0; word; ++i)
        {
            if ((w = strdup(word)))
            {
                dict.key  = w;
                // this next line assumes that the dictinary is a frequency
                // list ordered with the most frequent words first
                dict.data = (void*) i;
                if(!hsearch(dict, ENTER))
                {
                    puts("Error adding entry to table");
                    close(fd);
                    exit(-1);
                }
            }
            word = strtok(NULL, delimiter);
        }
        close(fd);
        return 1;
    }
    return -1;
}

/**
 * Takes a part of the source string and appends it to the destination string.
 *
 * @param dst       Destination string to append to.
 * @param dstLen    Current length of the destination string.  This will
 *                  be updated with the new length after appending.
 * @param src       Source string.
 * @param srcBegin  Starting index in the source string to copy from.
 * @param len       Length of portion to copy.
 */
void append(char *dst, int *dstLen, const char *src, int srcBegin, size_t length)
{
    if (length > 0)
    {
        memcpy(&dst[*dstLen], &src[srcBegin], length);
        *dstLen += length;
    }
    dst[*dstLen] = 0;
}

int deletion(char *word, char **array, int start)
{
    int i = 0;
    size_t length = strlen(word);

    for (; i < length; i++)
    {
        int pos = 0;
        array[i + start] = checkedMalloc(length);
        append(array[i + start], &pos, word, 0, i);
        append(array[i + start], &pos, word, i + 1, length - (i + 1));
    }
    return i;
}

int transposition(char *word, char **array, int start)
{
    int i = 0;
    size_t length = strlen(word);

    for (; i < length-1; i++)
    {
        int pos = 0;
        array[i + start] = checkedMalloc(length + 1);
        append(array[i + start], &pos, word, 0, i);
        append(array[i + start], &pos, word, i + 1, 1);
        append(array[i + start], &pos, word, i, 1);
        append(array[i + start], &pos, word, i + 2, length - (i + 2));
    }
    return i;
}

// bottle-neck #1
int alteration(char *word, char **array, int start)
{
    int k = 0;
    size_t length = strlen(word);
    char c[2] = {};

    for (int i = 0; i < length; ++i)
    {
        for (int j = 0; j < ALPHABET_SIZE; ++j, ++k)
        {
            int pos = 0;
            c[0] = alphabet[j];
            array[k + start] = checkedMalloc(length + 1);
            append(array[k + start], &pos, word, 0, i);
            append(array[k + start], &pos, c, 0, 1);
            append(array[k + start], &pos, word, i + 1, length - (i + 1));
        }
    }
    return k;
}

// bottle-neck #2
int insertion(char *word, char **array, int start)
{
    int k = 0;
    size_t length = strlen(word);
    char c[2] = {};

    for (int i = 0; i <= length; ++i)
    {
        for (int j = 0; j < ALPHABET_SIZE; ++j, ++k)
        {
            int pos = 0;
            c[0] = alphabet[j];
            array[k + start] = checkedMalloc(length + 2);
            append(array[k + start], &pos, word, 0, i);
            append(array[k + start], &pos, c, 0, 1);
            append(array[k + start], &pos, word, i, length - i);
        }
    }
    return k;
}

size_t totalEdits(char *word)
{
    size_t length = strlen(word);

    return (length)                + // deletion
    (length - 1)                   + // transposition
    (length * ALPHABET_SIZE)       + // alteration
    (length + 1) * ALPHABET_SIZE;    // insertion
}

char **edits(char *word)
{
    int index;
    char **array = malloc(totalEdits(word) * sizeof(char*));

    if (!array) return NULL;

    index  = deletion(word, array, 0);
    index += transposition(word, array, index);
    index += alteration(word, array, index);
    insertion(word, array, index);

    return array;
}

char **knownEdits(char **array, int rows, int *e2_rows)
{
    int resSize = 0;
    int resMax  = 0;
    char **res = NULL;

    for (int i = 0; i < rows; i++)
    {
        char **e1 = edits(array[i]);
        size_t e1_rows = totalEdits(array[i]);

        for (int j = 0; j < e1_rows; j++)
        {
            if (find(e1[j]) && !arrayExist(res, resSize, e1[j]))
            {
                if (resSize >= resMax)
                {
                    // initially allocate 50 entries, after double the size
                    if (resMax == 0) resMax = 50;
                    else resMax *= 2;
                }
                res = realloc(res, sizeof(char*) * resMax);
                res[resSize++] = e1[j];
            }
        }
    }

    *e2_rows = resSize;

    return res;
}

char *bestMatch(char **array, int rows)
{
    char *maxWord = NULL;
    int maxSize = TABLE_SIZE;
    ENTRY *e;
    for (int i = 0; i < rows; i++)
    {
        e = find(array[i]);
        if (e && ((int) e->data < maxSize))
        {
            maxSize = (int) e->data;
            maxWord = e->key;
        }
    }
    return maxWord;
}

char *correct(char *word)
{
    char **e1 = NULL;
    char **e2 = NULL;
    char *e1_word = NULL;
    char *e2_word = NULL;
    char *resWord = word;
    int e1_rows = 0;
    char e2_rows = 0;

    if (find(word)) return word;

    e1_rows = (unsigned) totalEdits(word);
    if (e1_rows)
    {
        e1 = edits(word);
        e1_word = bestMatch(e1, e1_rows);

        if (e1_word)
        {
            arrayCleanup(e1, e1_rows);
            free(e1);
            return e1_word;
        }
    }

    e2 = knownEdits(e1, e1_rows, (int*)&e2_rows);
    if (e2_rows)
    {
        e2_word = bestMatch(e2, e2_rows);
        if (e2_word) resWord = e2_word;
    }

    arrayCleanup(e1, e1_rows);
    arrayCleanup(e2, e2_rows);

    free(e1);
    free(e2);
    return resWord;
}

int main(int argc, char **argv)
{
    //    if (argc != 2)
    //    {
    //        puts("Usage: ./check <word>");
    //        return 1;
    //    }

    ENTRY dict = {};
    hcreate(TABLE_SIZE);

    if (!readDictionary(dictionary, dict)) return -1;

    //    char *corrected_word = correct(argv[argc - 1]);
    //    puts(corrected_word);
    char* correctArray[] = {"baccalaureate", "basketball", "beautiful",
        "course", "desire", "discotheque","engineering",
        "English", "examination","example", "favorite",
        "family", "follow", "finish", "friend", "finally",
        "gas", "graduate", "have", "holiday", "ideal",
        "important", "interested", "language", "leisure",
        "like", "libraries", "masters", "matches",
        "mechanicals", "prepare", "pretty", "Russian",
        "second", "secondary", "situated", "sixty", "spent",
        "snooker", "study", "succeed", "teaching",
        "university", "week", "with"};
    char* checkArray[] =   {"bacalaureat", "baskett ball", "beautifull",
        "cours", "desir", "discotec","engeneering",
        "enlgish", "examinition", "exemple","favrit",
        "familly", "folow", "finisch", "freind", "finaly",
        "gaz", "graduat", "hav", "hollyday", "ideale",
        "importante", "intrested", "langage", "leasure",
        "luke", "libraries", "mastes", "matchs",
        "mechanials", "prepar", "prety", "rusian", "secund",
        "secundry", "situed", "sixthy", "sepent", "snoker",
        "studie", "succed", "theaching", "univercity",
        "wik", "whith"};
    int arraySize = sizeof(checkArray)/sizeof(checkArray[0]);
    int correctSum = 0;
    char* guess = NULL;
    for (int i = 0; i < arraySize; ++i)
    {
        guess = correct(checkArray[i]);
        if (!strcmp(correctArray[i], guess))
        {
            printf("Successful correction: got \"%s\" from \"%s\"\n", guess, checkArray[i]);
            ++correctSum;
        }
        else printf("Erroneous correction: expected \"%s\", got \"%s\" from \"%s\"\n", correctArray[i], guess, checkArray[i]);
    }
    printf("Percent correct: %g%%\n", (double) correctSum / arraySize * 100);
}

Output & Analysis:

$ time ./check
Erroneous correction: expected "baccalaureate", got "bacalaureat" from "bacalaureat"
Successful correction: got "basketball" from "baskett ball"
Successful correction: got "beautiful" from "beautifull"
Successful correction: got "course" from "cours"
Successful correction: got "desire" from "desir"
Erroneous correction: expected "discotheque", got "discover" from "discotec"
Successful correction: got "engineering" from "engeneering"
Successful correction: got "English" from "enlgish"
Successful correction: got "examination" from "examinition"
Successful correction: got "example" from "exemple"
Successful correction: got "favorite" from "favrit"
Successful correction: got "family" from "familly"
Successful correction: got "follow" from "folow"
Successful correction: got "finish" from "finisch"
Successful correction: got "friend" from "freind"
Successful correction: got "finally" from "finaly"
Successful correction: got "gas" from "gaz"
Successful correction: got "graduate" from "graduat"
Successful correction: got "have" from "hav"
Successful correction: got "holiday" from "hollyday"
Successful correction: got "ideal" from "ideale"
Successful correction: got "important" from "importante"
Successful correction: got "interested" from "intrested"
Successful correction: got "language" from "langage"
Erroneous correction: expected "leisure", got "measure" from "leasure"
Successful correction: got "like" from "luke"
Successful correction: got "libraries" from "libraries"
Erroneous correction: expected "masters", got "master" from "mastes"
Erroneous correction: expected "matches", got "match" from "matchs"
Erroneous correction: expected "mechanicals", got "mechanical" from "mechanials"
Successful correction: got "prepare" from "prepar"
Successful correction: got "pretty" from "prety"
Successful correction: got "Russian" from "rusian"
Successful correction: got "second" from "secund"
Successful correction: got "secondary" from "secundry"
Erroneous correction: expected "situated", got "site" from "situed"
Erroneous correction: expected "sixty", got "sixth" from "sixthy"
Erroneous correction: expected "spent", got "spend" from "sepent"
Erroneous correction: expected "snooker", got "smoke" from "snoker"
Erroneous correction: expected "study", got "studio" from "studie"
Successful correction: got "succeed" from "succed"
Successful correction: got "teaching" from "theaching"
Successful correction: got "university" from "univercity"
Erroneous correction: expected "week", got "win" from "wik"
Successful correction: got "with" from "whith"
Percent correct: 73.3333%

real  0m1.657s
user  0m1.505s
sys   0m0.112s

So overall, this program is much more accurate. The old spelling corrector had a very low percentage (zero?) rate for accuracy; this program, using a slightly modified version of Roger Mitton's Birkbeck spelling error corpus, is able to achieve 73.3333% accuracy.

The accuracy can be greatly attributed to the frequency list that I got from here. Since I'm a poor college student I could only get the free 5000 lemma formatted word list, which covers ~85% of all words in the English language. I believe if I had a larger list that this spelling corrector would be even more accurate, since words such as "baccalaureate" don't appear in my current list.


Here is what I would like reviewed (mostly the same as last time):

  • Accuracy: What can I do to make the program output a more accurate prediction of what it thinks the correct word should be?

  • Speed: Are there any improvements that could be made to improve runtime speeds?

  • Refinement: In what ways could I shorten my code down a bit? I'm trying to reduce the LOC to create a smaller executable more well suited for possible embedded environments.

  • Resources: Is there a better/more modern spelling error corpus and frequency list that I could use for this program? The ones that I'm using may be fine but I fear are a bit dated (especially the spelling error corpus) or are too small of sample size.

\$\endgroup\$
  • 1
    \$\begingroup\$ For increased accuracy, you might want to check out Soundex et al. \$\endgroup\$ – abligh Jul 25 '15 at 21:55
  • \$\begingroup\$ There is probably an open dictionary out there. I'd be shocked if what Firefox uses is closed behind a paywall. Screw em! \$\endgroup\$ – Alec Teal Jul 26 '15 at 5:52
  • \$\begingroup\$ Download enable1.txt from dotnetperls-controls: "Public domain word list for some of the word programs here". It has more than 170,000 words (including baccalaureate). \$\endgroup\$ – pmg Jul 26 '15 at 17:38
  • \$\begingroup\$ @pmg Only problem with that is that it isn't a frequency list, so I have little to no way of ranking the words in order to generate a best guess for the correction. \$\endgroup\$ – syb0rg Jul 26 '15 at 18:39
11
\$\begingroup\$

Here are some things that may help you improve your code.

Be careful with signed and unsigned

In the deletion routine and various others, the code compares an int i to a size_t length, but size_t is unsigned and int is signed. Instead, declare both variables as size_t types.

Don't use empty braces as initializers

This line is not legal ISO C:

char c[2] = {};

The problem is that there isn't anything in the curly braces. If you want to initialize it, the syntax would be this:

char c[2] = {0};

Prefer const variables to #define

For both TABLE_SIZE and ALPHABET_SIZE, their values should be declared as

const size_t TABLE_SIZE = 5013;
const size_t ALPHABET_SIZE = sizeof alphabet - 1;

The difference is that when they are declared this way, they have a bit of additional type safety.

Be wary of pointer size assumptions

In the bestMatch function, the code includes these lines:

int maxSize = TABLE_SIZE;
ENTRY *e;
// ...
maxSize = (int) e->data;

The problem with this is that it implicitly assumes that the pointer (e->data) is the same size as an int. That is not guaranteed by the language, and in fact, they are different sizes on my machine. There are a few options. One is to leave the logic in place but add a static assert.

_Static_assert(sizeof maxSize == sizeof e->data, 
        "Pointer and integer are not the same size");

The _Static_assert syntax was added to the language specification with C11.

The other, better, option is to make maxWord a void * so that they can't ever be mismatched. That eliminates the casts.

Use const where practical

There are a number of places in the code where variables could be declared const such as in correct:

const size_t e1_rows = totalEdits(word);

Eliminate global variables where possible

The dictionary variable is global but should really be in main. If you move it to main (as a const char * of course), it will reveal an error within readDictionary:

if (stat(dictionary, &sb)) return 0;

Instead of using the global variable, it should instead use the passed parameter:

if (stat(fileName, &sb)) return 0;

Don't leak memory

The code leaks lots of memory. To begin with, the code calls hcreate but there is no corresponding call to hdestroy. A deeper problem, however, is the the allocation of memory within the program. The first is this line:

char *result = strdup(mmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE, fd, 0));

That first maps the dictionary file into memory using mmap and then doubles the memory use by making a copy which is never freed. Instead, just map with the appropriate permissions:

char *result = mmap(NULL, sb.st_size, PROT_READ|PROT_WRITE, MAP_PRIVATE, fd, 0);

When the program terminates, the mmap will be released. Also within that function, each word is additionally being strduped but never freed. Since the memory is already allocated, there's no need to make an additional copy. There is also a memory leak in edit but I have not had the time to track down its exact location yet.

Reduce platform dependencies

For embedded system work, it's often the case that there isn't even a file system. For that reason, if you're intending this for use in embedded systems you should strive to reduce platform dependencies. For example, mmap is not that common. You could accomplish the same effect by using nothing more than fseek, ftell and fread that are all part of stdio.h.

Prefer compile-time to runtime

Embedded systems often have much slower CPUs, so to maximize the efficiency of the code, the entire dictionary structure could be created at compile time and then simply used. This skips the dictionary creation step and reduces dependencies on the platform still further since even file I/O is no longer needed if the dictionary is a static block of memory.

Reduce memory usage

The correct function creates, in memory, all variations of deletions, transpositions, alterations and insertions for each word. This is a huge amount of memory for each individual word! Instead of allocating all of them and then checking each one, a less memory intensive means would be to check each variation as it's created, immediately checking each one and discarding it if it does not seem to be the best match so far.

Consider a better algorithm

The current algorithm assumes that some variation of the word will match a word in the dictionary, and so it exhaustively checks all variations to see if they're dictionary words. An alternative approach would be to calculate the Levenshtein distance between a proposed word and plausible dictionary words. "Plausible" in this case could be as simple as having about the same number of characters.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I'm a little curious (and a little inexperienced with C); how could the dictionary structure be created at compile time? \$\endgroup\$ – SirPython Jul 26 '15 at 17:00
  • \$\begingroup\$ @SirPython: generically, one can write a program to create the dictionary as a C structure. Then use the output of that program (which is compilable C code) and compile it with the code that uses the dictionary. \$\endgroup\$ – Edward Jul 26 '15 at 17:14
  • \$\begingroup\$ That's pretty cool, and I don't think I've ever seen that be done. Do you know any examples I could find (online, preferably)? \$\endgroup\$ – SirPython Jul 26 '15 at 17:16
  • \$\begingroup\$ I don't know of any online examples, but I'll write one and post it as a Code Review question. \$\endgroup\$ – Edward Jul 26 '15 at 17:30
  • 2
    \$\begingroup\$ Done. See codereview.stackexchange.com/questions/98167/… \$\endgroup\$ – Edward Jul 26 '15 at 21:52
11
\$\begingroup\$

Program exit code

The checkedMalloc function does exit(0) in case you run out of memory. Exit code 0 usually means success, so it would be better to use something else.

The main function returns -1 if a problem happens while reading the dictionary.

The readDictionary does exit(-1) if it cannot add a word to the hash table.

It's confusing to have multiple exit points scattered around in the program. It's also hard to keep track of the exit codes that are magic numbers.

As a first step, it would be good to put the exit codes in well-named constants. As a second step, it would be good to centralize the exit points if possible. (For out-of-memory it's probably not practical, but for the others it might be, especially considering that readDictionary sometimes returns on errors instead of exiting.)

Error handling and function return values

readDictionary behaves very confusingly:

  • Return 0 if opening dictionary file failed
  • Return 0 if getting stats on dictionary file failed
  • Return -1 if mmap failed
  • Exit program with -1 if adding entry to hash table failed
  • Return 1 on success

The return value of this function is checked with !readDictionary(...), so the returned -1 will be considered success.

It's also unfortunate that the fileName parameter of the function is exactly the same as the dictionary global variable. Either use the global variable and drop the parameter, or use the parameter instead of the global variable.

Naming

When I see dictionary, I'm thinking some kind of hash table. But in this program it's a char* variable, storing the name of the dictionary file. So I'd call it dictionary_path.

Usability

Instead of hardcoding correctArray and checkArray inside main, it would be easier to play with and test the program if it took filenames as command line arguments.

Writing style

I was a bit surprised by this code at first:

return (length)                + // deletion
(length - 1)                   + // transposition
(length * ALPHABET_SIZE)       + // alteration
(length + 1) * ALPHABET_SIZE;    // insertion

At first I didn't really get what are those expressions lined up vertically. It became clearer as I read the right-end of the lines. This way it would have been more obvious right off the bat:

return (length)                         // deletion
       + (length - 1)                   // transposition
       + (length * ALPHABET_SIZE)       // alteration
       + (length + 1) * ALPHABET_SIZE;  // insertion
| improve this answer | |
\$\endgroup\$
11
\$\begingroup\$

Hash table implementation

Using the normal search.h functions is not safe because only one hash table can be used at a time. This might not be a concern, but keep this in mind if you plan to go multi-threaded or release this as a library. There are _r suffixed versions of these functions, but they are GNU extensions, and are as such not portable across POSIX environments.

Using search.h also restricts what libc implementation you can use (for embedded). uClibc includes search.h, but newlib doesn't. I suggest that you use another hash table implementation. When searching for a replacement I found uthash which seems to fit your needs. It's small and actively developed, but I haven't used it myself so I cannot know for certain if it's good. See this question for more alternatives.

Commented out code

I consider leaving commented out lines in your code without explanation a bad practise. Let me quote @nhgrif in this answer:

Source control should help you keep track of code that used to be there, so there's not a real good excuse to leave it there for any historical reason.

Arguably, you might want to leave it in if it's something you're frequently uncommenting for some sort of testing purposes, but if that's the case, perhaps leave a comment above the line, something to the effect of:

// Uncomment the following line to ... 

One statement per line

if (resMax == 0) resMax = 50;
else resMax *= 2;

Don't do this, put each statement on a line of it's own. This increases readability as one can simply scan the left edge of the code for the beginning of statements, and also allows you to put a breakpoint when the clause is executed.

if (resMax == 0)
    resMax = 50;
else
    resMax *= 2;

Documentation

Document your functions! Your don't have to write an essay on each, but a one line comment helps a great deal in understanding the code. You've done this for some functions, but for others not. I think all functions deserve an explanation.

Executable size

One way to reduce the size of the executable is to look for common patterns and encapsulating them in functions. One such pattern I found skimming through the code is to first call arrayCleanup and then free on the array. This code duplication can be removed by calling free in arrayCleanup instead.

I'm sure there are lots of other small gains that can be found throughout the code in a similar fashion.

Memory leaks

Your program leaks a lot of memory - try running it with valgrind. It's a great tool for finding leaks and other memory related problems.

==4170== LEAK SUMMARY:
==4170==    definitely lost: 99,441,026 bytes in 29,053 blocks
==4170==    indirectly lost: 135,222,187 bytes in 12,405,877 blocks
==4170==      possibly lost: 14 bytes in 1 blocks
==4170==    still reachable: 0 bytes in 0 blocks
==4170==         suppressed: 0 bytes in 0 blocks

I understand that this is a toy project, but for instance your implementation of readDictionary is just sloppy. You never free result (which is 37K).

Memory usage

You use a lot of memory for targeting embedded devices. Something that could reduce memory usage is to rethink your implementation of readDictionary altogether. Right now, you first map the whole file into memory, and then duplicate it! This is terribly inefficient use of memory. Use getline or something similar. This uses memory proportional to the length of words instead of proportional to the length of the entire file.


Some minor points:

  • dictonary is not mutated anywhere - make it const.
  • @janos is right about exit values. I recommend using EXIT_FAILURE as it's standard and explicit.
| improve this answer | |
\$\endgroup\$
11
\$\begingroup\$

The algorithm

I'm going to focus this review on your algorithm and ways to improve it.

Right now, the program is slow because the algorithm has to do a lot of work. It tries to generate all possible word variants with 2 modifications, which ends up being a lot of candidate words. Call the alphabet size \$N\$ and the word length \$M\$. The transposition and deletion modifications are not important because they only generate \$M\$ candidates. On the other hand, the insertion and alteration modifications each generate \$M*N\$ candidates. So for 2 modifications, you need to generate \$4 * M^2 *N^2\$ candidates (the 4 comes from having both insertions and alterations). With M=52 and N=10, you generate roughly 4*52*52*10*10 = 1081600 candidate words. With each word being 10 characters, this involves over 10 million operations just to generate the words, without even trying to rank them.

Reduce alphabet size

So the easiest thing you could do is to only use lowercase letters when generating words. That would speed everything up by about 4x by cutting the alphabet size in half. You could leave the dictionary with uppercase letters as long as you use a case insensitive search.

Alternate algorithm #1: Don't generate words

A more radical change would be to completely change the algorithm. One reason why the current algorithm is so slow is because it generates a lot of words that are not in the dictionary. For example, inserting a 'z' into a word usually isn't going to be useful because that word won't exist. So instead of generating a million word variants, you could iterate over the words in the dictionary (which should be less than the number of word variants). For example, in pseudocode:

for (each word in the dictionary) {
    score = scoreWord(word, dictionaryWord, dictionaryRanking);
    if (score > bestScore)
        Remember best score and best word;
}

Here, the scoring function would compute the Damerau-Levenshtein distance between the two words. That is just a fancy way of saying that it computes the number of edits (inserts/deletes/alterations/transposes) to change one word into the other, which is what your original algorithm is based on. After computing the distance, it should factor in the frequency ranking as a secondary factor. For example:

int scoreWord(const char *word, const char *dictWord, int dictRanking)
{
    return distance(word, dictWord) * 1000000 + dictRanking;
}

Here, lower scores are better, and dictRanking is the frequency ranking that you already use (lower rankings are more frequent).

One advantage of this algorithm is that it will find the closest match even if the misspelled word is more than 2 edits away from the actual word. One disadvantage is that will be slower to find 1 edit words than your current algorithm. It also depends on your dictionary being small. The larger your dictionary, the slower this will work.

Alternate algorithm #2: Using a trie

I think that an even better idea than #1 is to read your dictionary into a trie data structure. Once your dictionary is in a trie, you could do something similar to your current algorithm. But instead of generating words, you would be searching down the trie. The reason this is faster than the current algorithm is twofold:

  1. The trie limits your searching to words that exist. So you won't waste time inserting 'z' characters unless they are actually needed.

  2. You don't need to allocate extra memory and generate a list of words. This saves a bunch of time avoiding needless copying.

Here is some example code that shows what a trie search would look like (untested):

// Sample Trie implementation.  Other variations exist that can reduce
// memory utilization.
typedef struct TrieNode {
    bool  isEndOfWord;
    int   wordRanking;
    char *word;
    struct TrieNode *child[ALPHABET_SIZE];
} TrieNode;

void trieSearch(const char *remainingWord, const TrieNode *node, int numEdits)
{
    char letter      = *remainingWord;
    int  letterIndex = getIndexFromLetter(letter);

    // Handle end of word.
    if (letter == '\0') {
        if (node->isEndOfWord) {
            int ranking = numEdits * 1000000 + node->wordRanking;
            if (ranking > bestRanking) {
                bestRanking = ranking;
                bestEdits   = numEdits;
                bestWord    = node->word;
            }
        }
        return;
    }

    // Try no edits first.
    if (node->child[letterIndex] != NULL)
        trieSearch(remainingWord + 1, node->child[letterIndex], numEdits);

    // If we can't make any more edits, stop.
    if (numEdits >= bestEdits)
        return;

    // Now try each type of edit.

    // Deletion.
    trieSearch(remainingWord + 1, node, numEdits + 1);

    // Transposition.
    char nextLetter = remainingWord[1];
    if (nextLetter != '\0') {
        int nextLetterIndex = getIndexFromLetter(nextLetter);
        if (node->child[nextLetterIndex] != NULL &&
                node->child[nextLetterIndex]->child[letterIndex] != NULL) {
            trieSearch(remainingWord + 2,
                    node->child[nextLetterIndex]->child[letterIndex],
                    numEdits + 1);
        }
    }

    // Alteration.
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (i != letterIndex && node->child[i]) {
            trieSearch(remainingWord + 1, node->child[i], numEdits + 1);
        }
    }

    // Insertion.
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (node->child[i]) {
            trieSearch(remainingWord, node->child[i], numEdits + 1);
        }
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ In reducing alphabet size, I agree with you for the most part except with the fact that some words are always capitalized in order to be correctly spelled ("english" for example is technically incorrect spelling, "English" is how it should be spelt). Though only the first letter in these words are uppercase... using this knowledge would reduce the number of generated words in my original algorithm. \$\endgroup\$ – syb0rg Jul 26 '15 at 2:25
  • \$\begingroup\$ @syb0rg Yes but you can still retain capitalization in your dictionary. Just generate all lowercase words, but then search using case insensitive search in the dictionary. So if your word was "eglish", you can generate "english" and still find "English" in your dictionary. Now, whether that counts as 1 edit or 2 (because of the capitalization) is up to you. \$\endgroup\$ – JS1 Jul 26 '15 at 2:39

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.