gitignore: add gmqcc, gmqpak, qmcvm, testsuite, pak.

[xonotic/gmqcc.git] / correct.c

diff --git a/correct.c b/correct.c
index fe07902544512a4259f39ab68050e170a101b5c9..7e16608a0084c260810a1f9240e757f6d00f0673 100644 (file)
--- a/correct.c
+++ b/correct.c
@@ -2,7 +2,7 @@
  * 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
@@ -51,11 +51,11 @@
  *  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)
@@ -72,7 +72,7 @@
  *  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
@@ -85,8 +85,8 @@
  *  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.
@@ -117,8 +117,8 @@
  *   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
@@ -128,11 +128,7 @@
  *   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.
  */
 
 
@@ -318,7 +314,7 @@ void correct_del(correct_trie_t* dictonary, size_t **data) {
  * 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;
@@ -419,15 +415,14 @@ static GMQCC_INLINE char **correct_edit(const char *ident, size_t **lens) {
     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;
     }
 
@@ -471,7 +466,7 @@ static char **correct_known(correction_t *corr, correct_trie_t* table, char **ar
         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];
             }
@@ -507,11 +502,13 @@ void correct_init(correction_t *c)
 {
     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();
 }