* Copyright (C) 2012, 2013
* Dale Weiler
* Wolfgang Bumiller
- *
+ *
* Permission is hereby granted, free of charge, to any person obtaining a copy of
* this software and associated documentation files (the "Software"), to deal in
* the Software without restriction, including without limitation the rights to
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*/
+#include <string.h>
#include "gmqcc.h"
/*
* 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 ..)
- *
+ * 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)
* 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
* 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.
- *
+ * I had concieved of checking everything.
+ *
* A little information on additional algorithms used:
*
* Initially when I implemented this corrector, it was very slow.
* 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
* 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.
- *
- * Our control mechanisim could use a limit, i.e limit the number of
- * sets of edits for distance X. This would also increase execution
- * speed considerably.
+ * this could become a problem when lots of identifiers are involved.
*/
* not in the mood to figure out that logic. This is a reminder to
* do it, or for someone else to :-) correct_edit however would also
* need to take a size_t ** to carry it along (would all the argument
- * overhead be worth it?)
+ * overhead be worth it?)
*/
static GMQCC_INLINE size_t correct_deletion(const char *ident, char **array) {
size_t itr = 0;
return find;
}
-/*
- * We could use a hashtable but the space complexity isn't worth it
- * since we're only going to determine the "did you mean?" identifier
- * on error.
- */
-static GMQCC_INLINE int correct_exist(char **array, size_t rows, char *ident, size_t len) {
+static GMQCC_INLINE int correct_exist(char **array, register size_t *sizes, size_t rows, char *ident, register size_t len) {
size_t itr;
for (itr = 0; itr < rows; itr++) {
- if (!memcmp(array[itr], ident, len))
+ /*
+ * We can save tons of calls to memcmp if we simply ignore comparisions
+ * that we know cannot contain the same length.
+ */
+ if (sizes[itr] == len && !memcmp(array[itr], ident, len))
return 1;
}
row = correct_size(array[itr]);
for (jtr = 0; jtr < row; jtr++) {
- if (correct_find(table, end[jtr]) && !correct_exist(res, len, end[jtr], bit[jtr])) {
+ if (correct_find(table, end[jtr]) && !correct_exist(res, bit, len, end[jtr], bit[jtr])) {
res = correct_known_resize(res, &nxt, len+1);
res[len++] = end[jtr];
}
{
correct_pool_new();
c->edits = NULL;
+ c->lens = NULL;
}
void correct_free(correction_t *c)
{
vec_free(c->edits);
+ vec_free(c->lens);
correct_pool_delete();
}