/* ** 2012 April 10 ** ** The author disclaims copyright to this source code. In place of ** a legal notice, here is a blessing: ** ** May you do good and not evil. ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* ** ** This module implements a VIRTUAL TABLE that can be used to search ** a large vocabulary for close matches. For example, this virtual ** table can be used to suggest corrections to misspelled words. Or, ** it could be used with FTS4 to do full-text search using potentially ** misspelled words. ** ** Create an instance of the virtual table this way: ** ** CREATE VIRTUAL TABLE demo USING spellfix1; ** ** The "spellfix1" term is the name of this module. The "demo" is the ** name of the virtual table you will be creating. The table is initially ** empty. You have to populate it with your vocabulary. Suppose you ** have a list of words in a table named "big_vocabulary". Then do this: ** ** INSERT INTO demo(word) SELECT word FROM big_vocabulary; ** ** If you intend to use this virtual table in cooperation with an FTS4 ** table (for spelling correctly of search terms) then you can extract ** the vocabulary using an fts3aux table: ** ** INSERT INTO demo(word) SELECT term FROM search_aux WHERE col='*'; ** ** You can also provide the virtual table with a "rank" for each word. ** The "rank" is an estimate of how common the word is. Larger numbers ** mean the word is more common. If you omit the rank when populating ** the table, then a rank of 1 is assumed. But if you have rank ** information, you can supply it and the virtual table will show a ** slight preference for selecting more commonly used terms. To ** populate the rank from an fts4aux table "search_aux" do something ** like this: ** ** INSERT INTO demo(word,rank) ** SELECT term, documents FROM search_aux WHERE col='*'; ** ** To query the virtual table, include a MATCH operator in the WHERE ** clause. For example: ** ** SELECT word FROM demo WHERE word MATCH 'kennasaw'; ** ** Using a dataset of American place names (derived from ** http://geonames.usgs.gov/domestic/download_data.htm) the query above ** returns 20 results beginning with: ** ** kennesaw ** kenosha ** kenesaw ** kenaga ** keanak ** ** If you append the character '*' to the end of the pattern, then ** a prefix search is performed. For example: ** ** SELECT word FROM demo WHERE word MATCH 'kennes*'; ** ** Yields 20 results beginning with: ** ** kennesaw ** kennestone ** kenneson ** kenneys ** keanes ** keenes ** ** The virtual table actually has a unique rowid with five columns plus three ** extra hidden columns. The columns are as follows: ** ** rowid A unique integer number associated with each ** vocabulary item in the table. This can be used ** as a foreign key on other tables in the database. ** ** word The text of the word that matches the pattern. ** Both word and pattern can contains unicode characters ** and can be mixed case. ** ** rank This is the rank of the word, as specified in the ** original INSERT statement. ** ** distance This is an edit distance or Levensthein distance going ** from the pattern to the word. ** ** langid This is the language-id of the word. All queries are ** against a single language-id, which defaults to 0. ** For any given query this value is the same on all rows. ** ** score The score is a combination of rank and distance. The ** idea is that a lower score is better. The virtual table ** attempts to find words with the lowest score and ** by default (unless overridden by ORDER BY) returns ** results in order of increasing score. ** ** top (HIDDEN) For any query, this value is the same on all ** rows. It is an integer which is the maximum number of ** rows that will be output. The actually number of rows ** output might be less than this number, but it will never ** be greater. The default value for top is 20, but that ** can be changed for each query by including a term of ** the form "top=N" in the WHERE clause of the query. ** ** scope (HIDDEN) For any query, this value is the same on all ** rows. The scope is a measure of how widely the virtual ** table looks for matching words. Smaller values of ** scope cause a broader search. The scope is normally ** choosen automatically and is capped at 4. Applications ** can change the scope by including a term of the form ** "scope=N" in the WHERE clause of the query. Increasing ** the scope will make the query run faster, but will reduce ** the possible corrections. ** ** srchcnt (HIDDEN) For any query, this value is the same on all ** rows. This value is an integer which is the number of ** of words examined using the edit-distance algorithm to ** find the top matches that are ultimately displayed. This ** value is for diagnostic use only. ** ** soundslike (HIDDEN) When inserting vocabulary entries, this field ** can be set to an spelling that matches what the word ** sounds like. See the DEALING WITH UNUSUAL AND DIFFICULT ** SPELLINGS section below for details. ** ** When inserting into or updating the virtual table, only the rowid, word, ** rank, and langid may be changes. Any attempt to set or modify the values ** of distance, score, top, scope, or srchcnt is silently ignored. ** ** ALGORITHM ** ** A shadow table named "%_vocab" (where the % is replaced by the name of ** the virtual table; Ex: "demo_vocab" for the "demo" virtual table) is ** constructed with these columns: ** ** id The unique id (INTEGER PRIMARY KEY) ** ** rank The rank of word. ** ** langid The language id for this entry. ** ** word The original UTF8 text of the vocabulary word ** ** k1 The word transliterated into lower-case ASCII. ** There is a standard table of mappings from non-ASCII ** characters into ASCII. Examples: "æ" -> "ae", ** "þ" -> "th", "ß" -> "ss", "á" -> "a", ... The ** accessory function spellfix1_translit(X) will do ** the non-ASCII to ASCII mapping. The built-in lower(X) ** function will convert to lower-case. Thus: ** k1 = lower(spellfix1_translit(word)). ** ** k2 This field holds a phonetic code derived from k1. Letters ** that have similar sounds are mapped into the same symbol. ** For example, all vowels and vowel clusters become the ** single symbol "A". And the letters "p", "b", "f", and ** "v" all become "B". All nasal sounds are represented ** as "N". And so forth. The mapping is base on ** ideas found in Soundex, Metaphone, and other ** long-standing phonetic matching systems. This key can ** be generated by the function spellfix1_charclass(X). ** Hence: k2 = spellfix1_charclass(k1) ** ** There is also a function for computing the Wagner edit distance or the ** Levenshtein distance between a pattern and a word. This function ** is exposed as spellfix1_editdist(X,Y). The edit distance function ** returns the "cost" of converting X into Y. Some transformations ** cost more than others. Changing one vowel into a different vowel, ** for example is relatively cheap, as is doubling a constant, or ** omitting the second character of a double-constant. Other transformations ** or more expensive. The idea is that the edit distance function returns ** a low cost of words that are similar and a higher cost for words ** that are futher apart. In this implementation, the maximum cost ** of any single-character edit (delete, insert, or substitute) is 100, ** with lower costs for some edits (such as transforming vowels). ** ** The "score" for a comparison is the edit distance between the pattern ** and the word, adjusted down by the base-2 logorithm of the word rank. ** For example, a match with distance 100 but rank 1000 would have a ** score of 122 (= 100 - log2(1000) + 32) where as a match with distance ** 100 with a rank of 1 would have a score of 131 (100 - log2(1) + 32). ** (NB: The constant 32 is added to each score to keep it from going ** negative in case the edit distance is zero.) In this way, frequently ** used words get a slightly lower cost which tends to move them toward ** the top of the list of alternative spellings. ** ** A straightforward implementation of a spelling corrector would be ** to compare the search term against every word in the vocabulary ** and select the 20 with the lowest scores. However, there will ** typically be hundreds of thousands or millions of words in the ** vocabulary, and so this approach is not fast enough. ** ** Suppose the term that is being spell-corrected is X. To limit ** the search space, X is converted to a k2-like key using the ** equivalent of: ** ** key = spellfix1_charclass(lower(spellfix1_translit(X))) ** ** This key is then limited to "scope" characters. The default scope ** value is 4, but an alternative scope can be specified using the ** "scope=N" term in the WHERE clause. After the key has been truncated, ** the edit distance is run against every term in the vocabulary that ** has a k2 value that begins with the abbreviated key. ** ** For example, suppose the input word is "Paskagula". The phonetic ** key is "BACACALA" which is then truncated to 4 characters "BACA". ** The edit distance is then run on the 4980 entries (out of ** 272,597 entries total) of the vocabulary whose k2 values begin with ** BACA, yielding "Pascagoula" as the best match. ** ** Only terms of the vocabulary with a matching langid are searched. ** Hence, the same table can contain entries from multiple languages ** and only the requested language will be used. The default langid ** is 0. ** ** DEALING WITH UNUSUAL AND DIFFICULT SPELLINGS ** ** The algorithm above works quite well for most cases, but there are ** exceptions. These exceptions can be dealt with by making additional ** entries in the virtual table using the "soundslike" column. ** ** For example, many words of Greek origin begin with letters "ps" where ** the "p" is silent. Ex: psalm, pseudonym, psoriasis, psyche. In ** another example, many Scottish surnames can be spelled with an ** initial "Mac" or "Mc". Thus, "MacKay" and "McKay" are both pronounced ** the same. ** ** Accommodation can be made for words that are not spelled as they ** sound by making additional entries into the virtual table for the ** same word, but adding an alternative spelling in the "soundslike" ** column. For example, the canonical entry for "psalm" would be this: ** ** INSERT INTO demo(word) VALUES('psalm'); ** ** To enhance the ability to correct the spelling of "salm" into ** "psalm", make an addition entry like this: ** ** INSERT INTO demo(word,soundslike) VALUES('psalm','salm'); ** ** It is ok to make multiple entries for the same word as long as ** each entry has a different soundslike value. Note that if no ** soundslike value is specified, the soundslike defaults to the word ** itself. ** ** Listed below are some cases where it might make sense to add additional ** soundslike entries. The specific entries will depend on the application ** and the target language. ** ** * Silent "p" in words beginning with "ps": psalm, psyche ** ** * Silent "p" in words beginning with "pn": pneumonia, pneumatic ** ** * Silent "p" in words beginning with "pt": pterodactyl, ptolemaic ** ** * Silent "d" in words beginning with "dj": djinn, Djikarta ** ** * Silent "k" in words beginning with "kn": knight, Knuthson ** ** * Silent "g" in words beginning with "gn": gnarly, gnome, gnat ** ** * "Mac" versus "Mc" beginning Scottish surnames ** ** * "Tch" sounds in Slavic words: Tchaikovsky vs. Chaykovsky ** ** * The letter "j" pronounced like "h" in Spanish: LaJolla ** ** * Words beginning with "wr" versus "r": write vs. rite ** ** * Miscellanous problem words such as "debt", "tsetse", ** "Nguyen", "Van Nuyes". */ #if SQLITE_CORE # include "sqliteInt.h" #else # include # include # include # include "sqlite3ext.h" SQLITE_EXTENSION_INIT1 #endif /* !SQLITE_CORE */ /* ** Character classes for ASCII characters: ** ** 0 '' Silent letters: H W ** 1 'A' Any vowel: A E I O U (Y) ** 2 'B' A bilabeal stop or fricative: B F P V ** 3 'C' Other fricatives or back stops: C G J K Q S X Z ** 4 'D' Alveolar stops: D T ** 5 'H' Letter H at the beginning of a word ** 6 'L' Glides: L R ** 7 'M' Nasals: M N ** 8 'W' Letter W at the beginning of a word ** 9 'Y' Letter Y at the beginning of a word. ** 10 '9' A digit: 0 1 2 3 4 5 6 7 8 9 ** 11 ' ' White space ** 12 '?' Other. */ #define CCLASS_SILENT 0 #define CCLASS_VOWEL 1 #define CCLASS_B 2 #define CCLASS_C 3 #define CCLASS_D 4 #define CCLASS_H 5 #define CCLASS_L 6 #define CCLASS_M 7 #define CCLASS_W 8 #define CCLASS_Y 9 #define CCLASS_DIGIT 10 #define CCLASS_SPACE 11 #define CCLASS_OTHER 12 /* ** The following table gives the character class for non-initial ASCII ** characters. */ static const unsigned char midClass[] = { /* x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xa xb xc xd xe xf */ /* 0x */ 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 11, 12, 11, 12, 12, 12, /* 1x */ 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, /* 2x */ 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, /* 3x */ 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 12, 12, 12, 12, 12, 12, /* 4x */ 12, 1, 2, 3, 4, 1, 2, 3, 0, 1, 3, 3, 6, 7, 7, 1, /* 5x */ 2, 3, 6, 3, 4, 1, 2, 0, 3, 1, 3, 12, 12, 12, 12, 12, /* 6x */ 12, 1, 2, 3, 4, 1, 2, 3, 0, 1, 3, 3, 6, 7, 7, 1, /* 7x */ 2, 3, 6, 3, 4, 1, 2, 0, 3, 1, 3, 12, 12, 12, 12, 12, }; /* ** This tables gives the character class for ASCII characters that form the ** initial character of a word. The only difference from midClass is with ** the letters H, W, and Y. */ static const unsigned char initClass[] = { /* x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xa xb xc xd xe xf */ /* 0x */ 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 11, 12, 11, 12, 12, 12, /* 1x */ 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, /* 2x */ 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, /* 3x */ 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 12, 12, 12, 12, 12, 12, /* 4x */ 12, 1, 2, 3, 4, 1, 2, 3, 5, 1, 3, 3, 6, 7, 7, 1, /* 5x */ 2, 3, 6, 3, 4, 1, 2, 8, 3, 9, 3, 12, 12, 12, 12, 12, /* 6x */ 12, 1, 2, 3, 4, 1, 2, 3, 5, 1, 3, 3, 6, 7, 7, 1, /* 7x */ 2, 3, 6, 3, 4, 1, 2, 8, 3, 9, 3, 12, 12, 12, 12, 12, }; /* ** Mapping from the character class number (0-12) to a symbol for each ** character class. Note that initClass[] can be used to map the class ** symbol back into the class number. */ static const unsigned char className[] = ".ABCDHLMWY9 ?"; /* ** Generate a string of character classes corresponding to the ** ASCII characters in the input string zIn. If the input is not ** ASCII then the behavior is undefined. ** ** Space to hold the result is obtained from sqlite3_malloc() ** ** Return NULL if memory allocation fails. */ static unsigned char *characterClassString(const unsigned char *zIn, int nIn){ unsigned char *zOut = sqlite3_malloc( nIn + 1 ); int i; int nOut = 0; char cPrev = 0x77; const unsigned char *aClass = initClass; if( zOut==0 ) return 0; for(i=0; i='A' && cTo<='Z') || (cTo>='a' && cTo<='z')) ){ /* differ only in case */ return 0; } classFrom = characterClass(cPrev, cFrom); classTo = characterClass(cPrev, cTo); if( classFrom==classTo ){ /* Same character class */ return classFrom=='A' ? 25 : 40; } if( classFrom>=CCLASS_B && classFrom<=CCLASS_Y && classTo>=CCLASS_B && classTo<=CCLASS_Y ){ /* Convert from one consonant to another, but in a different class */ return 75; } /* Any other subsitution */ return 100; } /* ** Given two strings zA and zB which are pure ASCII, return the cost ** of transforming zA into zB. If zA ends with '*' assume that it is ** a prefix of zB and give only minimal penalty for extra characters ** on the end of zB. ** ** Smaller numbers mean a closer match. ** ** Negative values indicate an error: ** -1 One of the inputs is NULL ** -2 Non-ASCII characters on input ** -3 Unable to allocate memory */ static int editdist(const char *zA, const char *zB){ int nA, nB; /* Number of characters in zA[] and zB[] */ int xA, xB; /* Loop counters for zA[] and zB[] */ char cA, cB; /* Current character of zA and zB */ char cAprev, cBprev; /* Previous character of zA and zB */ int d; /* North-west cost value */ int dc = 0; /* North-west character value */ int res; /* Final result */ int *m; /* The cost matrix */ char *cx; /* Corresponding character values */ int *toFree = 0; /* Malloced space */ int mStack[60+15]; /* Stack space to use if not too much is needed */ /* Early out if either input is NULL */ if( zA==0 || zB==0 ) return -1; /* Skip any common prefix */ while( zA[0] && zA[0]==zB[0] ){ dc = zA[0]; zA++; zB++; } if( zA[0]==0 && zB[0]==0 ) return 0; #if 0 printf("A=\"%s\" B=\"%s\" dc=%c\n", zA, zB, dc?dc:' '); #endif /* Verify input strings and measure their lengths */ for(nA=0; zA[nA]; nA++){ if( zA[nA]>127 ) return -2; } for(nB=0; zB[nB]; nB++){ if( zB[nB]>127 ) return -2; } /* Special processing if either string is empty */ if( nA==0 ){ cBprev = dc; for(xB=res=0; (cB = zB[xB])!=0; xB++){ res += insertOrDeleteCost(cBprev, cB)/FINAL_INS_COST_DIV; cBprev = cB; } return res; } if( nB==0 ){ cAprev = dc; for(xA=res=0; (cA = zA[xA])!=0; xA++){ res += insertOrDeleteCost(cAprev, cA); cAprev = cA; } return res; } /* A is a prefix of B */ if( zA[0]=='*' && zA[1]==0 ) return 0; /* Allocate and initialize the Wagner matrix */ if( nB<(sizeof(mStack)*4)/(sizeof(mStack[0])*5) ){ m = mStack; }else{ m = toFree = sqlite3_malloc( (nB+1)*5*sizeof(m[0])/4 ); if( m==0 ) return -3; } cx = (char*)&m[nB+1]; /* Compute the Wagner edit distance */ m[0] = 0; cx[0] = dc; cBprev = dc; for(xB=1; xB<=nB; xB++){ cB = zB[xB-1]; cx[xB] = cB; m[xB] = m[xB-1] + insertOrDeleteCost(cBprev, cB); cBprev = cB; } cAprev = dc; for(xA=1; xA<=nA; xA++){ int lastA = (xA==nA); cA = zA[xA-1]; if( cA=='*' && lastA ) break; d = m[0]; dc = cx[0]; m[0] = d + insertOrDeleteCost(cAprev, cA); cBprev = 0; for(xB=1; xB<=nB; xB++){ int totalCost, insCost, delCost, subCost, ncx; cB = zB[xB-1]; /* Cost to insert cB */ insCost = insertOrDeleteCost(cx[xB-1], cB); if( lastA ) insCost /= FINAL_INS_COST_DIV; /* Cost to delete cA */ delCost = insertOrDeleteCost(cx[xB], cA); /* Cost to substitute cA->cB */ subCost = substituteCost(cx[xB-1], cA, cB); /* Best cost */ totalCost = insCost + m[xB-1]; ncx = cB; if( (delCost + m[xB])nA ){ res = m[nA]; for(xB=nA+1; xB<=nB; xB++){ if( m[xB]=0xc0 ){ c = sqlite3Utf8Trans1[c-0xc0]; while( i=xBtm ){ x = (xTop + xBtm)/2; if( translit[x].cFrom==c ){ zOut[nOut++] = translit[x].cTo0; if( translit[x].cTo1 ){ zOut[nOut++] = translit[x].cTo1; /* Add an extra "ch" after the "sh" for Щ and щ */ if( c==0x0429 || c== 0x0449 ){ zOut[nOut++] = 'c'; zOut[nOut++] = 'h'; } } c = 0; break; }else if( translit[x].cFrom>c ){ xTop = x-1; }else{ xBtm = x+1; } } if( c ) zOut[nOut++] = '?'; } } zOut[nOut] = 0; return zOut; } /* ** spellfix1_translit(X) ** ** Convert a string that contains non-ASCII Roman characters into ** pure ASCII. */ static void transliterateSqlFunc( sqlite3_context *context, int argc, sqlite3_value **argv ){ const unsigned char *zIn = sqlite3_value_text(argv[0]); int nIn = sqlite3_value_bytes(argv[0]); unsigned char *zOut = transliterate(zIn, nIn); if( zOut==0 ){ sqlite3_result_error_nomem(context); }else{ sqlite3_result_text(context, (char*)zOut, -1, sqlite3_free); } } /* ** spellfix1_scriptcode(X) ** ** Try to determine the dominant script used by the word X and return ** its ISO 15924 numeric code. ** ** The current implementation only understands the following scripts: ** ** 215 (Latin) ** 220 (Cyrillic) ** 200 (Greek) ** ** This routine will return 998 if the input X contains characters from ** two or more of the above scripts or 999 if X contains no characters ** from any of the above scripts. */ static void scriptCodeSqlFunc( sqlite3_context *context, int argc, sqlite3_value **argv ){ const unsigned char *zIn = sqlite3_value_text(argv[0]); int nIn = sqlite3_value_bytes(argv[0]); int c, sz; int scriptMask = 0; int res; # define SCRIPT_LATIN 0x0001 # define SCRIPT_CYRILLIC 0x0002 # define SCRIPT_GREEK 0x0004 while( nIn>0 ){ c = utf8Read(zIn, nIn, &sz); zIn += sz; nIn -= sz; if( c<0x02af ){ scriptMask |= SCRIPT_LATIN; }else if( c>=0x0400 && c<=0x04ff ){ scriptMask |= SCRIPT_CYRILLIC; }else if( c>=0x0386 && c<=0x03ce ){ scriptMask |= SCRIPT_GREEK; } } switch( scriptMask ){ case 0: res = 999; break; case SCRIPT_LATIN: res = 215; break; case SCRIPT_CYRILLIC: res = 220; break; case SCRIPT_GREEK: res = 200; break; default: res = 998; break; } sqlite3_result_int(context, res); } /***************************************************************************** ** Fuzzy-search virtual table *****************************************************************************/ typedef struct spellfix1_vtab spellfix1_vtab; typedef struct spellfix1_cursor spellfix1_cursor; /* Fuzzy-search virtual table object */ struct spellfix1_vtab { sqlite3_vtab base; /* Base class - must be first */ sqlite3 *db; /* Database connection */ char *zDbName; /* Name of database holding this table */ char *zTableName; /* Name of the virtual table */ }; /* Fuzzy-search cursor object */ struct spellfix1_cursor { sqlite3_vtab_cursor base; /* Base class - must be first */ spellfix1_vtab *pVTab; /* The table to which this cursor belongs */ int nRow; /* Number of rows of content */ int nAlloc; /* Number of allocated rows */ int iRow; /* Current row of content */ int iLang; /* Value of the lang= constraint */ int iTop; /* Value of the top= constraint */ int iScope; /* Value of the scope= constraint */ int nSearch; /* Number of vocabulary items checked */ struct spellfix1_row { /* For each row of content */ sqlite3_int64 iRowid; /* Rowid for this row */ char *zWord; /* Text for this row */ int iRank; /* Rank for this row */ int iDistance; /* Distance from pattern for this row */ int iScore; /* Score for sorting */ } *a; }; /* ** Construct one or more SQL statements from the format string given ** and then evaluate those statements. The success code is written ** into *pRc. ** ** If *pRc is initially non-zero then this routine is a no-op. */ static void spellfix1DbExec( int *pRc, /* Success code */ sqlite3 *db, /* Database in which to run SQL */ const char *zFormat, /* Format string for SQL */ ... /* Arguments to the format string */ ){ va_list ap; char *zSql; if( *pRc ) return; va_start(ap, zFormat); zSql = sqlite3_vmprintf(zFormat, ap); va_end(ap); if( zSql==0 ){ *pRc = SQLITE_NOMEM; }else{ *pRc = sqlite3_exec(db, zSql, 0, 0, 0); sqlite3_free(zSql); } } /* ** xDisconnect/xDestroy method for the fuzzy-search module. */ static int spellfix1Uninit(int isDestroy, sqlite3_vtab *pVTab){ spellfix1_vtab *p = (spellfix1_vtab*)pVTab; int rc = SQLITE_OK; if( isDestroy ){ sqlite3 *db = p->db; spellfix1DbExec(&rc, db, "DROP TABLE IF EXISTS \"%w\".\"%w_vocab\"", p->zDbName, p->zTableName); } if( rc==SQLITE_OK ){ sqlite3_free(p->zTableName); sqlite3_free(p); } return rc; } static int spellfix1Disconnect(sqlite3_vtab *pVTab){ return spellfix1Uninit(0, pVTab); } static int spellfix1Destroy(sqlite3_vtab *pVTab){ return spellfix1Uninit(1, pVTab); } /* ** xConnect/xCreate method for the spellfix1 module. Arguments are: ** ** argv[0] -> module name ("spellfix1") ** argv[1] -> database name ** argv[2] -> table name ** argv[3].. -> optional arguments (currently ignored) */ static int spellfix1Init( int isCreate, sqlite3 *db, void *pAux, int argc, const char *const*argv, sqlite3_vtab **ppVTab, char **pzErr ){ spellfix1_vtab *pNew = 0; const char *zModule = argv[0]; const char *zDbName = argv[1]; const char *zTableName = argv[2]; int nDbName; int rc = SQLITE_OK; if( argc<3 ){ *pzErr = sqlite3_mprintf( "%s: wrong number of CREATE VIRTUAL TABLE arguments", argv[0] ); rc = SQLITE_ERROR; }else{ nDbName = strlen(zDbName); pNew = sqlite3_malloc( sizeof(*pNew) + nDbName + 1); if( pNew==0 ){ rc = SQLITE_NOMEM; }else{ memset(pNew, 0, sizeof(*pNew)); pNew->zDbName = (char*)&pNew[1]; memcpy(pNew->zDbName, zDbName, nDbName+1); pNew->zTableName = sqlite3_mprintf("%s", zTableName); pNew->db = db; if( pNew->zTableName==0 ){ rc = SQLITE_NOMEM; }else{ rc = sqlite3_declare_vtab(db, "CREATE TABLE x(word,rank,distance,langid," "score,top HIDDEN,scope HIDDEN,srchcnt HIDDEN," "soundslike HIDDEN)" ); } if( rc==SQLITE_OK && isCreate ){ sqlite3_uint64 r; spellfix1DbExec(&rc, db, "CREATE TABLE IF NOT EXISTS \"%w\".\"%w_vocab\"(\n" " id INTEGER PRIMARY KEY,\n" " rank INT,\n" " langid INT,\n" " word TEXT,\n" " k1 TEXT,\n" " k2 TEXT\n" ");\n", zDbName, zTableName ); sqlite3_randomness(sizeof(r), &r); spellfix1DbExec(&rc, db, "CREATE INDEX IF NOT EXISTS \"%w\".\"%w_index_%llx\" " "ON \"%w_vocab\"(langid,k2);", zDbName, zModule, r, zTableName ); } } } *ppVTab = (sqlite3_vtab *)pNew; return rc; } /* ** The xConnect and xCreate methods */ static int spellfix1Connect( sqlite3 *db, void *pAux, int argc, const char *const*argv, sqlite3_vtab **ppVTab, char **pzErr ){ return spellfix1Init(0, db, pAux, argc, argv, ppVTab, pzErr); } static int spellfix1Create( sqlite3 *db, void *pAux, int argc, const char *const*argv, sqlite3_vtab **ppVTab, char **pzErr ){ return spellfix1Init(1, db, pAux, argc, argv, ppVTab, pzErr); } /* ** Reset a cursor so that it contains zero rows of content but holds ** space for N rows. */ static void spellfix1ResetCursor(spellfix1_cursor *pCur, int N){ int i; for(i=0; inRow; i++){ sqlite3_free(pCur->a[i].zWord); } pCur->a = sqlite3_realloc(pCur->a, sizeof(pCur->a[0])*N); pCur->nAlloc = N; pCur->nRow = 0; pCur->iRow = 0; pCur->nSearch = 0; } /* ** Close a fuzzy-search cursor. */ static int spellfix1Close(sqlite3_vtab_cursor *cur){ spellfix1_cursor *pCur = (spellfix1_cursor *)cur; spellfix1ResetCursor(pCur, 0); sqlite3_free(pCur); return SQLITE_OK; } /* ** Search for terms of these forms: ** ** (A) word MATCH $str ** (B) langid == $langid ** (C) top = $top ** (D) scope = $scope ** ** The plan number is a bit mask formed with these bits: ** ** 0x01 (A) is found ** 0x02 (B) is found ** 0x04 (C) is found ** 0x08 (D) is found ** ** filter.argv[*] values contains $str, $langid, $top, and $scope, ** if specified and in that order. */ static int spellfix1BestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){ int iPlan = 0; int iLangTerm = -1; int iTopTerm = -1; int iScopeTerm = -1; int i; const struct sqlite3_index_constraint *pConstraint; pConstraint = pIdxInfo->aConstraint; for(i=0; inConstraint; i++, pConstraint++){ if( pConstraint->usable==0 ) continue; /* Terms of the form: word MATCH $str */ if( (iPlan & 1)==0 && pConstraint->iColumn==0 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_MATCH ){ iPlan |= 1; pIdxInfo->aConstraintUsage[i].argvIndex = 1; pIdxInfo->aConstraintUsage[i].omit = 1; } /* Terms of the form: langid = $langid */ if( (iPlan & 2)==0 && pConstraint->iColumn==3 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ ){ iPlan |= 2; iLangTerm = i; } /* Terms of the form: top = $top */ if( (iPlan & 4)==0 && pConstraint->iColumn==5 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ ){ iPlan |= 4; iTopTerm = i; } /* Terms of the form: scope = $scope */ if( (iPlan & 8)==0 && pConstraint->iColumn==6 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ ){ iPlan |= 8; iScopeTerm = i; } } if( iPlan&1 ){ int idx = 2; pIdxInfo->idxNum = iPlan; if( pIdxInfo->nOrderBy==1 && pIdxInfo->aOrderBy[0].iColumn==4 && pIdxInfo->aOrderBy[0].desc==0 ){ pIdxInfo->orderByConsumed = 1; /* Default order by iScore */ } if( iPlan&2 ){ pIdxInfo->aConstraintUsage[iLangTerm].argvIndex = idx++; pIdxInfo->aConstraintUsage[iLangTerm].omit = 1; } if( iPlan&4 ){ pIdxInfo->aConstraintUsage[iTopTerm].argvIndex = idx++; pIdxInfo->aConstraintUsage[iTopTerm].omit = 1; } if( iPlan&8 ){ pIdxInfo->aConstraintUsage[iScopeTerm].argvIndex = idx++; pIdxInfo->aConstraintUsage[iScopeTerm].omit = 1; } pIdxInfo->estimatedCost = (double)10000; }else{ pIdxInfo->idxNum = 0; pIdxInfo->estimatedCost = (double)10000000; } return SQLITE_OK; } /* ** Open a new fuzzy-search cursor. */ static int spellfix1Open(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){ spellfix1_vtab *p = (spellfix1_vtab*)pVTab; spellfix1_cursor *pCur; pCur = sqlite3_malloc( sizeof(*pCur) ); if( pCur==0 ) return SQLITE_NOMEM; memset(pCur, 0, sizeof(*pCur)); pCur->pVTab = p; *ppCursor = &pCur->base; return SQLITE_OK; } /* ** Adjust a distance measurement by the words rank in order to show ** preference to common words. */ static int spellfix1Score(int iDistance, int iRank){ int iLog2; for(iLog2=0; iRank>0; iLog2++, iRank>>=1){} return iDistance + 32 - iLog2; } /* ** Compare two spellfix1_row objects for sorting purposes in qsort() such ** that they sort in order of increasing distance. */ static int spellfix1RowCompare(const void *A, const void *B){ const struct spellfix1_row *a = (const struct spellfix1_row*)A; const struct spellfix1_row *b = (const struct spellfix1_row*)B; return a->iScore - b->iScore; } /* ** This version of the xFilter method work if the MATCH term is present ** and we are doing a scan. */ static int spellfix1FilterForMatch( spellfix1_cursor *pCur, int idxNum, int argc, sqlite3_value **argv ){ const unsigned char *zPatternIn; char *zPattern; int nPattern; char *zClass; int nClass; int iLimit = 20; int iScope = 4; int iLang = 0; char *zSql; int rc; sqlite3_stmt *pStmt; int idx = 1; spellfix1_vtab *p = pCur->pVTab; if( idxNum&2 ){ iLang = sqlite3_value_int(argv[idx++]); } if( idxNum&4 ){ iLimit = sqlite3_value_int(argv[idx++]); if( iLimit<1 ) iLimit = 1; } if( idxNum&8 ){ iScope = sqlite3_value_int(argv[idx++]); if( iScope<1 ) iScope = 1; } spellfix1ResetCursor(pCur, iLimit); zPatternIn = sqlite3_value_text(argv[0]); if( zPatternIn==0 ) return SQLITE_OK; zPattern = (char*)transliterate(zPatternIn, sqlite3_value_bytes(argv[0])); if( zPattern==0 ) return SQLITE_NOMEM; nPattern = strlen(zPattern); if( zPattern[nPattern-1]=='*' ) nPattern--; if( nPatterniScope ){ zClass[iScope] = 0; nClass = iScope; } zSql = sqlite3_mprintf( "SELECT id, word, rank, k1" " FROM \"%w\".\"%w_vocab\"" " WHERE langid=%d AND k2 GLOB '%q*'", p->zDbName, p->zTableName, iLang, zClass ); rc = sqlite3_prepare_v2(p->db, zSql, -1, &pStmt, 0); sqlite3_free(zSql); if( rc==SQLITE_OK ){ const char *zK1; int iDist; int iRank; int iScore; int iWorst = 999999999; int idx; int idxWorst; int i; while( sqlite3_step(pStmt)==SQLITE_ROW ){ zK1 = (const char*)sqlite3_column_text(pStmt, 3); if( zK1==0 ) continue; pCur->nSearch++; iRank = sqlite3_column_int(pStmt, 2); iDist = editdist(zPattern, zK1); iScore = spellfix1Score(iDist,iRank); if( pCur->nRownAlloc ){ idx = pCur->nRow; }else if( iScorea[idx].zWord); }else{ continue; } pCur->a[idx].zWord = sqlite3_mprintf("%s", sqlite3_column_text(pStmt, 1)); pCur->a[idx].iRowid = sqlite3_column_int64(pStmt, 0); pCur->a[idx].iRank = iRank; pCur->a[idx].iDistance = iDist; pCur->a[idx].iScore = iScore; if( pCur->nRownAlloc ) pCur->nRow++; if( pCur->nRow==pCur->nAlloc ){ iWorst = pCur->a[0].iScore; idxWorst = 0; for(i=1; inRow; i++){ iScore = pCur->a[i].iScore; if( iWorsta, pCur->nRow, sizeof(pCur->a[0]), spellfix1RowCompare); pCur->iTop = iLimit; pCur->iScope = iScope; sqlite3_finalize(pStmt); sqlite3_free(zPattern); sqlite3_free(zClass); return SQLITE_OK; } /* ** This version of xFilter handles a full-table scan case */ static int spellfix1FilterForFullScan( spellfix1_cursor *pCur, int idxNum, int argc, sqlite3_value **argv ){ spellfix1ResetCursor(pCur, 0); return SQLITE_OK; } /* ** Called to "rewind" a cursor back to the beginning so that ** it starts its output over again. Always called at least once ** prior to any spellfix1Column, spellfix1Rowid, or spellfix1Eof call. */ static int spellfix1Filter( sqlite3_vtab_cursor *cur, int idxNum, const char *idxStr, int argc, sqlite3_value **argv ){ spellfix1_cursor *pCur = (spellfix1_cursor *)cur; int rc; if( idxNum & 1 ){ rc = spellfix1FilterForMatch(pCur, idxNum, argc, argv); }else{ rc = spellfix1FilterForFullScan(pCur, idxNum, argc, argv); } return rc; } /* ** Advance a cursor to its next row of output */ static int spellfix1Next(sqlite3_vtab_cursor *cur){ spellfix1_cursor *pCur = (spellfix1_cursor *)cur; if( pCur->iRow < pCur->nRow ) pCur->iRow++; return SQLITE_OK; } /* ** Return TRUE if we are at the end-of-file */ static int spellfix1Eof(sqlite3_vtab_cursor *cur){ spellfix1_cursor *pCur = (spellfix1_cursor *)cur; return pCur->iRow>=pCur->nRow; } /* ** Return columns from the current row. */ static int spellfix1Column(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){ spellfix1_cursor *pCur = (spellfix1_cursor*)cur; switch( i ){ case 0: { sqlite3_result_text(ctx, pCur->a[pCur->iRow].zWord, -1, SQLITE_STATIC); break; } case 1: { sqlite3_result_int(ctx, pCur->a[pCur->iRow].iRank); break; } case 2: { sqlite3_result_int(ctx, pCur->a[pCur->iRow].iDistance); break; } case 3: { sqlite3_result_int(ctx, pCur->iLang); break; } case 4: { sqlite3_result_int(ctx, pCur->a[pCur->iRow].iScore); break; } case 5: { sqlite3_result_int(ctx, pCur->iTop); break; } case 6: { sqlite3_result_int(ctx, pCur->iScope); break; } case 7: { sqlite3_result_int(ctx, pCur->nSearch); break; } default: { sqlite3_result_null(ctx); break; } } return SQLITE_OK; } /* ** The rowid. */ static int spellfix1Rowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){ spellfix1_cursor *pCur = (spellfix1_cursor*)cur; *pRowid = pCur->a[pCur->iRow].iRowid; return SQLITE_OK; } /* ** The xUpdate() method. */ static int spellfix1Update( sqlite3_vtab *pVTab, int argc, sqlite3_value **argv, sqlite_int64 *pRowid ){ int rc = SQLITE_OK; sqlite3_int64 rowid, newRowid; spellfix1_vtab *p = (spellfix1_vtab*)pVTab; sqlite3 *db = p->db; if( argc==1 ){ /* A delete operation on the rowid given by argv[0] */ rowid = *pRowid = sqlite3_value_int64(argv[0]); spellfix1DbExec(&rc, db, "DELETE FROM \"%w\".\"%w_vocab\" " " WHERE id=%lld", p->zDbName, p->zTableName, rowid); }else{ const unsigned char *zWord = sqlite3_value_text(argv[2]); int nWord = sqlite3_value_bytes(argv[2]); int iLang = sqlite3_value_int(argv[5]); int iRank = sqlite3_value_int(argv[3]); const unsigned char *zSoundslike = sqlite3_value_text(argv[10]); int nSoundslike = sqlite3_value_bytes(argv[10]); char *zK1, *zK2; int i; char c; if( zWord==0 ){ pVTab->zErrMsg = sqlite3_mprintf("%w.word may not be NULL", p->zTableName); return SQLITE_CONSTRAINT; } if( iRank<1 ) iRank = 1; if( zSoundslike ){ zK1 = (char*)transliterate(zSoundslike, nSoundslike); }else{ zK1 = (char*)transliterate(zWord, nWord); } if( zK1==0 ) return SQLITE_NOMEM; for(i=0; (c = zK1[i])!=0; i++){ if( c>='A' && c<='Z' ) zK1[i] += 'a' - 'A'; } zK2 = (char*)characterClassString((const unsigned char*)zK1, i); if( zK2==0 ){ sqlite3_free(zK1); return SQLITE_NOMEM; } if( sqlite3_value_type(argv[0])==SQLITE_NULL ){ spellfix1DbExec(&rc, db, "INSERT INTO \"%w\".\"%w_vocab\"(rank,langid,word,k1,k2) " "VALUES(%d,%d,%Q,%Q,%Q)", p->zDbName, p->zTableName, iRank, iLang, zWord, zK1, zK2 ); *pRowid = sqlite3_last_insert_rowid(db); }else{ rowid = sqlite3_value_int64(argv[0]); newRowid = *pRowid = sqlite3_value_int64(argv[1]); spellfix1DbExec(&rc, db, "UPDATE \"%w\".\"%w_vocab\" SET id=%lld, rank=%d, lang=%d," " word=%Q, rank=%d, k1=%Q, k2=%Q WHERE id=%lld", p->zDbName, p->zTableName, newRowid, iRank, iLang, zWord, zK1, zK2, rowid ); } sqlite3_free(zK1); sqlite3_free(zK2); } return rc; } /* ** Rename the spellfix1 table. */ static int spellfix1Rename(sqlite3_vtab *pVTab, const char *zNew){ spellfix1_vtab *p = (spellfix1_vtab*)pVTab; sqlite3 *db = p->db; int rc = SQLITE_OK; char *zNewName = sqlite3_mprintf("%s", zNew); if( zNewName==0 ){ return SQLITE_NOMEM; } spellfix1DbExec(&rc, db, "ALTER TABLE \"%w\".\"%w_vocab\" RENAME TO \"%w_vocab\"", p->zDbName, p->zTableName, zNewName ); if( rc==SQLITE_OK ){ sqlite3_free(p->zTableName); p->zTableName = zNewName; } return rc; } /* ** A virtual table module that provides fuzzy search. */ static sqlite3_module spellfix1Module = { 0, /* iVersion */ spellfix1Create, /* xCreate - handle CREATE VIRTUAL TABLE */ spellfix1Connect, /* xConnect - reconnected to an existing table */ spellfix1BestIndex, /* xBestIndex - figure out how to do a query */ spellfix1Disconnect, /* xDisconnect - close a connection */ spellfix1Destroy, /* xDestroy - handle DROP TABLE */ spellfix1Open, /* xOpen - open a cursor */ spellfix1Close, /* xClose - close a cursor */ spellfix1Filter, /* xFilter - configure scan constraints */ spellfix1Next, /* xNext - advance a cursor */ spellfix1Eof, /* xEof - check for end of scan */ spellfix1Column, /* xColumn - read data */ spellfix1Rowid, /* xRowid - read data */ spellfix1Update, /* xUpdate */ 0, /* xBegin */ 0, /* xSync */ 0, /* xCommit */ 0, /* xRollback */ 0, /* xFindMethod */ spellfix1Rename, /* xRename */ }; /* ** Register the various functions and the virtual table. */ static int spellfix1Register(sqlite3 *db){ int nErr = 0; int i; nErr += sqlite3_create_function(db, "spellfix1_translit", 1, SQLITE_UTF8, 0, transliterateSqlFunc, 0, 0); nErr += sqlite3_create_function(db, "spellfix1_editdist", 2, SQLITE_UTF8, 0, editdistSqlFunc, 0, 0); nErr += sqlite3_create_function(db, "spellfix1_charclass", 1, SQLITE_UTF8, 0, characterClassSqlFunc, 0, 0); nErr += sqlite3_create_function(db, "spellfix1_scriptcode", 1, SQLITE_UTF8, 0, scriptCodeSqlFunc, 0, 0); nErr += sqlite3_create_module(db, "spellfix1", &spellfix1Module, 0); /* Verify sanity of the translit[] table */ for(i=0; i