+/*
+ * This is a very clever method for correcting mistakes in QuakeC code
+ * most notably when invalid identifiers are used or inproper assignments;
+ * we can proprly lookup in multiple dictonaries (depening on the rules
+ * of what the task is trying to acomplish) to find the best possible
+ * match.
+ *
+ *
+ * A little about how it works, and probability theory:
+ *
+ * When given an identifier (which we will denote I), we're essentially
+ * just trying to choose the most likely correction for that identifier.
+ * (the actual "correction" can very well be the identifier itself).
+ * There is actually no way to know for sure that certian identifers
+ * such as "lates", need to be corrected to "late" or "latest" or any
+ * other permutations that look lexically the same. This is why we
+ * must advocate the usage of probabilities. This means that instead of
+ * just guessing, instead we're trying to find the correction for C,
+ * out of all possible corrections that maximizes the probability of C
+ * for the original identifer I.
+ *
+ * Thankfully there exists some theroies for probalistic interpretations
+ * of data. Since we're operating on two distictive intepretations, the
+ * transposition from I to C. We need something that can express how much
+ * degree of I should rationally change to become C. this is called the
+ * Bayesian interpretation. You can read more about it from here:
+ * http://www.celiagreen.com/charlesmccreery/statistics/bayestutorial.pdf
+ * (which is probably the only good online documentation for bayes theroy
+ * no lie. Everything else just sucks ..)
+ *
+ * Bayes' Thereom suggests something like the following:
+ * AC P(I|C) P(C) / P(I)
+ *
+ * However since P(I) is the same for every possibility of I, we can
+ * completley ignore it giving just:
+ * AC P(I|C) P(C)
+ *
+ * This greatly helps visualize how the parts of the expression are performed
+ * there is essentially three, from right to left we perform the following:
+ *
+ * 1: P(C), the probability that a proposed correction C will stand on its
+ * own. This is called the language model.
+ *
+ * 2: P(I|C), the probability that I would be used, when the programmer
+ * really meant C. This is the error model.
+ *
+ * 3: AC, the control mechanisim, an enumerator if you will, one that
+ * enumerates all feasible values of C, to determine the one that
+ * gives the greatest probability score.
+ *
+ * In reality the requirement for a more complex expression involving
+ * two seperate models is considerably a waste. But one must recognize
+ * that P(C|I) is already conflating two factors. It's just much simpler
+ * to seperate the two models and deal with them explicitaly. To properly
+ * estimate P(C|I) you have to consider both the probability of C and
+ * probability of the transposition from C to I. It's simply much more
+ * cleaner, and direct to seperate the two factors.
+ *
+ * Research tells us that 80% to 95% of all spelling errors have an edit
+ * distance no greater than one. Knowing this we can optimize for most
+ * cases of mistakes without taking a performance hit. Which is what we
+ * base longer edit distances off of. Opposed to the original method of
+ * I had concieved of checking everything.
+ *
+ * A little information on additional algorithms used:
+ *
+ * Initially when I implemented this corrector, it was very slow.
+ * Need I remind you this is essentially a brute force attack on strings,
+ * and since every transformation requires dynamic memory allocations,
+ * you can easily imagine where most of the runtime conflated. Yes
+ * It went right to malloc. More than THREE MILLION malloc calls are
+ * performed for an identifier about 16 bytes long. This was such a
+ * shock to me. A forward allocator (or as some call it a bump-point
+ * allocator, or just a memory pool) was implemented. To combat this.
+ *
+ * But of course even other factors were making it slow. Initially
+ * this used a hashtable. And hashtables have a good constant lookup
+ * time complexity. But the problem wasn't in the hashtable, it was
+ * in the hashing (despite having one of the fastest hash functions
+ * known). Remember those 3 million mallocs? Well for every malloc
+ * there is also a hash. After 3 million hashes .. you start to get
+ * very slow. To combat this I had suggested burst tries to Blub.
+ * The next day he had implemented them. Sure enough this brought
+ * down the runtime by a factor > 100%
+ *
+ * The trie initially was designed to work on all strings, but later it
+ * became aparent that not only was this not a requirement. It was also
+ * slowing down get/sets' for the trie. To fully understand, only
+ * correct_alpha needs to be understood by the trie system, knowing this
+ * We can combat the slowness using a very clever but evil optimization.
+ * By Setting a fixed sized amount of branches for the trie using a
+ * char-to-index map into the branches. We've complelty made the trie
+ * accesses entierly constant in lookup time. No really, a lookup is
+ * literally trie[str[0]] [str[1]] [2] .... .value.
+ *
+ *
+ * Future Work (If we really need it)
+ *
+ * Currently we can only distinguish one source of error in the
+ * language model we use. This could become an issue for identifiers
+ * that have close colliding rates, e.g colate->coat yields collate.
+ *
+ * Currently the error model has been fairly trivial, the smaller the
+ * edit distance the smaller the error. This usually causes some un-
+ * expected problems. e.g reciet->recite yields recipt. For QuakeC
+ * this could become a problem when lots of identifiers are involved.
+ */
+
+
+#define CORRECT_POOL_SIZE (128*1024*1024)