/* ** 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. ** ** matchlen For prefix queries, the number of characters in the prefix ** of the returned value (word) that matched the query term. ** For non-prefix queries, the number of characters in the ** returned value. ** ** 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_phonehash(X). ** Hence: k2 = spellfix1_phonehash(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_phonehash(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 */ #include /* ** 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' Glide: L ** 7 'R' Semivowel: R ** 8 'M' Nasals: M N ** 9 'W' Letter W at the beginning of a word ** 10 'Y' Letter Y at the beginning of a word. ** 11 '9' A digit: 0 1 2 3 4 5 6 7 8 9 ** 12 ' ' White space ** 13 '?' 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_R 7 #define CCLASS_M 8 #define CCLASS_W 9 #define CCLASS_Y 10 #define CCLASS_DIGIT 11 #define CCLASS_SPACE 12 #define CCLASS_OTHER 13 /* ** The following table gives the character class for non-initial ASCII ** characters. */ static const unsigned char midClass[] = { /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_SPACE, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_SPACE, /* */ CCLASS_SPACE, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_SPACE, /* ! */ CCLASS_OTHER, /* " */ CCLASS_OTHER, /* # */ CCLASS_OTHER, /* $ */ CCLASS_OTHER, /* % */ CCLASS_OTHER, /* & */ CCLASS_OTHER, /* ' */ CCLASS_SILENT, /* ( */ CCLASS_OTHER, /* ) */ CCLASS_OTHER, /* * */ CCLASS_OTHER, /* + */ CCLASS_OTHER, /* , */ CCLASS_OTHER, /* - */ CCLASS_OTHER, /* . */ CCLASS_OTHER, /* / */ CCLASS_OTHER, /* 0 */ CCLASS_DIGIT, /* 1 */ CCLASS_DIGIT, /* 2 */ CCLASS_DIGIT, /* 3 */ CCLASS_DIGIT, /* 4 */ CCLASS_DIGIT, /* 5 */ CCLASS_DIGIT, /* 6 */ CCLASS_DIGIT, /* 7 */ CCLASS_DIGIT, /* 8 */ CCLASS_DIGIT, /* 9 */ CCLASS_DIGIT, /* : */ CCLASS_OTHER, /* ; */ CCLASS_OTHER, /* < */ CCLASS_OTHER, /* = */ CCLASS_OTHER, /* > */ CCLASS_OTHER, /* ? */ CCLASS_OTHER, /* @ */ CCLASS_OTHER, /* A */ CCLASS_VOWEL, /* B */ CCLASS_B, /* C */ CCLASS_C, /* D */ CCLASS_D, /* E */ CCLASS_VOWEL, /* F */ CCLASS_B, /* G */ CCLASS_C, /* H */ CCLASS_SILENT, /* I */ CCLASS_VOWEL, /* J */ CCLASS_C, /* K */ CCLASS_C, /* L */ CCLASS_L, /* M */ CCLASS_M, /* N */ CCLASS_M, /* O */ CCLASS_VOWEL, /* P */ CCLASS_B, /* Q */ CCLASS_C, /* R */ CCLASS_R, /* S */ CCLASS_C, /* T */ CCLASS_D, /* U */ CCLASS_VOWEL, /* V */ CCLASS_B, /* W */ CCLASS_SILENT, /* X */ CCLASS_C, /* Y */ CCLASS_VOWEL, /* Z */ CCLASS_C, /* [ */ CCLASS_OTHER, /* \ */ CCLASS_OTHER, /* ] */ CCLASS_OTHER, /* ^ */ CCLASS_OTHER, /* _ */ CCLASS_OTHER, /* ` */ CCLASS_OTHER, /* a */ CCLASS_VOWEL, /* b */ CCLASS_B, /* c */ CCLASS_C, /* d */ CCLASS_D, /* e */ CCLASS_VOWEL, /* f */ CCLASS_B, /* g */ CCLASS_C, /* h */ CCLASS_SILENT, /* i */ CCLASS_VOWEL, /* j */ CCLASS_C, /* k */ CCLASS_C, /* l */ CCLASS_L, /* m */ CCLASS_M, /* n */ CCLASS_M, /* o */ CCLASS_VOWEL, /* p */ CCLASS_B, /* q */ CCLASS_C, /* r */ CCLASS_R, /* s */ CCLASS_C, /* t */ CCLASS_D, /* u */ CCLASS_VOWEL, /* v */ CCLASS_B, /* w */ CCLASS_SILENT, /* x */ CCLASS_C, /* y */ CCLASS_VOWEL, /* z */ CCLASS_C, /* { */ CCLASS_OTHER, /* | */ CCLASS_OTHER, /* } */ CCLASS_OTHER, /* ~ */ CCLASS_OTHER, /* */ CCLASS_OTHER, }; /* ** 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[] = { /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_SPACE, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_SPACE, /* */ CCLASS_SPACE, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_OTHER, /* */ CCLASS_SPACE, /* ! */ CCLASS_OTHER, /* " */ CCLASS_OTHER, /* # */ CCLASS_OTHER, /* $ */ CCLASS_OTHER, /* % */ CCLASS_OTHER, /* & */ CCLASS_OTHER, /* ' */ CCLASS_OTHER, /* ( */ CCLASS_OTHER, /* ) */ CCLASS_OTHER, /* * */ CCLASS_OTHER, /* + */ CCLASS_OTHER, /* , */ CCLASS_OTHER, /* - */ CCLASS_OTHER, /* . */ CCLASS_OTHER, /* / */ CCLASS_OTHER, /* 0 */ CCLASS_DIGIT, /* 1 */ CCLASS_DIGIT, /* 2 */ CCLASS_DIGIT, /* 3 */ CCLASS_DIGIT, /* 4 */ CCLASS_DIGIT, /* 5 */ CCLASS_DIGIT, /* 6 */ CCLASS_DIGIT, /* 7 */ CCLASS_DIGIT, /* 8 */ CCLASS_DIGIT, /* 9 */ CCLASS_DIGIT, /* : */ CCLASS_OTHER, /* ; */ CCLASS_OTHER, /* < */ CCLASS_OTHER, /* = */ CCLASS_OTHER, /* > */ CCLASS_OTHER, /* ? */ CCLASS_OTHER, /* @ */ CCLASS_OTHER, /* A */ CCLASS_VOWEL, /* B */ CCLASS_B, /* C */ CCLASS_C, /* D */ CCLASS_D, /* E */ CCLASS_VOWEL, /* F */ CCLASS_B, /* G */ CCLASS_C, /* H */ CCLASS_SILENT, /* I */ CCLASS_VOWEL, /* J */ CCLASS_C, /* K */ CCLASS_C, /* L */ CCLASS_L, /* M */ CCLASS_M, /* N */ CCLASS_M, /* O */ CCLASS_VOWEL, /* P */ CCLASS_B, /* Q */ CCLASS_C, /* R */ CCLASS_R, /* S */ CCLASS_C, /* T */ CCLASS_D, /* U */ CCLASS_VOWEL, /* V */ CCLASS_B, /* W */ CCLASS_W, /* X */ CCLASS_C, /* Y */ CCLASS_Y, /* Z */ CCLASS_C, /* [ */ CCLASS_OTHER, /* \ */ CCLASS_OTHER, /* ] */ CCLASS_OTHER, /* ^ */ CCLASS_OTHER, /* _ */ CCLASS_OTHER, /* ` */ CCLASS_OTHER, /* a */ CCLASS_VOWEL, /* b */ CCLASS_B, /* c */ CCLASS_C, /* d */ CCLASS_D, /* e */ CCLASS_VOWEL, /* f */ CCLASS_B, /* g */ CCLASS_C, /* h */ CCLASS_SILENT, /* i */ CCLASS_VOWEL, /* j */ CCLASS_C, /* k */ CCLASS_C, /* l */ CCLASS_L, /* m */ CCLASS_M, /* n */ CCLASS_M, /* o */ CCLASS_VOWEL, /* p */ CCLASS_B, /* q */ CCLASS_C, /* r */ CCLASS_R, /* s */ CCLASS_C, /* t */ CCLASS_D, /* u */ CCLASS_VOWEL, /* v */ CCLASS_B, /* w */ CCLASS_W, /* x */ CCLASS_C, /* y */ CCLASS_Y, /* z */ CCLASS_C, /* { */ CCLASS_OTHER, /* | */ CCLASS_OTHER, /* } */ CCLASS_OTHER, /* ~ */ CCLASS_OTHER, /* */ CCLASS_OTHER, }; /* ** Mapping from the character class number (0-13) 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[] = ".ABCDHLRMWY9 ?"; /* ** Generate a "phonetic hash" from a string of ASCII characters ** in zIn[0..nIn-1]. ** ** * Map characters by character class as defined above. ** * Omit double-letters ** * Omit vowels beside R and L ** * Omit T when followed by CH ** * Omit W when followed by R ** * Omit D when followed by J or G ** * Omit K in KN or G in GN at the beginning of a word ** ** Space to hold the result is obtained from sqlite3_malloc() ** ** Return NULL if memory allocation fails. */ static unsigned char *phoneticHash(const unsigned char *zIn, int nIn){ unsigned char *zOut = sqlite3_malloc( nIn + 1 ); int i; int nOut = 0; char cPrev = 0x77; char cPrevX = 0x77; const unsigned char *aClass = initClass; if( zOut==0 ) return 0; if( nIn>2 ){ switch( zIn[0] ){ case 'g': case 'k': { if( zIn[1]=='n' ){ zIn++; nIn--; } break; } } } if( zIn[0]=='k' && zIn[1]=='n' ){ zIn++, nIn--; } 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 ** ** If pnMatch is not NULL, then *pnMatch is set to the number of bytes ** of zB that matched the pattern in zA. If zA does not end with a '*', ** then this value is always the number of bytes in zB (i.e. strlen(zB)). ** If zA does end in a '*', then it is the number of bytes in the prefix ** of zB that was deemed to match zA. */ static int editdist1(const char *zA, const char *zB, int iLangId, int *pnMatch){ 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 */ char cAnext, cBnext; /* Next character in 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 */ int nMatch = 0; /* 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++; nMatch++; } if( pnMatch ) *pnMatch = nMatch; 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, zB[xB+1])/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, zA[xA+1]); 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++){ cBnext = zB[xB]; cB = zB[xB-1]; cx[xB] = cB; m[xB] = m[xB-1] + insertOrDeleteCost(cBprev, cB, cBnext); cBprev = cB; } cAprev = dc; for(xA=1; xA<=nA; xA++){ int lastA = (xA==nA); cA = zA[xA-1]; cAnext = zA[xA]; if( cA=='*' && lastA ) break; d = m[0]; dc = cx[0]; m[0] = d + insertOrDeleteCost(cAprev, cA, cAnext); cBprev = 0; for(xB=1; xB<=nB; xB++){ int totalCost, insCost, delCost, subCost, ncx; cB = zB[xB-1]; cBnext = zB[xB]; /* Cost to insert cB */ insCost = insertOrDeleteCost(cx[xB-1], cB, cBnext); if( lastA ) insCost /= FINAL_INS_COST_DIV; /* Cost to delete cA */ delCost = insertOrDeleteCost(cx[xB], cA, cBnext); /* 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])nLang; i++){ EditDist3Cost *pCost, *pNext; pCost = p->a[i].pCost; while( pCost ){ pNext = pCost->pNext; sqlite3_free(pCost); pCost = pNext; } } sqlite3_free(p->a); memset(p, 0, sizeof(*p)); } static void editDist3ConfigDelete(void *pIn){ EditDist3Config *p = (EditDist3Config*)pIn; editDist3ConfigClear(p); sqlite3_free(p); } /* ** Load all edit-distance weights from a table. */ static int editDist3ConfigLoad( EditDist3Config *p, /* The edit distance configuration to load */ sqlite3 *db, /* Load from this database */ const char *zTable /* Name of the table from which to load */ ){ sqlite3_stmt *pStmt; int rc; char *zSql; int iLangPrev = -9999; EditDist3Lang *pLang; zSql = sqlite3_mprintf("SELECT iLang, cFrom, cTo, iCost" " FROM \"%w\" WHERE iLang>=0 ORDER BY iLang", zTable); if( zSql==0 ) return SQLITE_NOMEM; rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0); sqlite3_free(zSql); if( rc ) return rc; editDist3ConfigClear(p); while( sqlite3_step(pStmt)==SQLITE_ROW ){ int iLang = sqlite3_column_int(pStmt, 0); const char *zFrom = (const char*)sqlite3_column_text(pStmt, 1); int nFrom = sqlite3_column_bytes(pStmt, 1); const char *zTo = (const char*)sqlite3_column_text(pStmt, 2); int nTo = sqlite3_column_bytes(pStmt, 2); int iCost = sqlite3_column_int(pStmt, 3); if( nFrom>100 || nFrom<0 || nTo>100 || nTo<0 ) continue; if( iCost<0 ) continue; if( iLang!=iLangPrev ){ EditDist3Lang *pNew; p->nLang++; pNew = sqlite3_realloc(p->a, p->nLang*sizeof(p->a[0])); if( pNew==0 ){ rc = SQLITE_NOMEM; break; } p->a = pNew; pLang = &p->a[p->nLang-1]; pLang->iLang = iLang; pLang->iInsCost = 100; pLang->iDelCost = 100; pLang->iSubCost = 200; pLang->pCost = 0; iLangPrev = iLang; } if( nFrom==1 && zFrom[0]=='?' && nTo==0 ){ pLang->iDelCost = iCost; }else if( nFrom==0 && nTo==1 && zTo[0]=='?' ){ pLang->iInsCost = iCost; }else if( nFrom==1 && nTo==1 && zFrom[0]=='?' && zTo[0]=='?' ){ pLang->iSubCost = iCost; }else{ EditDist3Cost *pCost; int nExtra = nFrom + nTo - 4; if( nExtra<0 ) nExtra = 0; pCost = sqlite3_malloc( sizeof(*pCost) + nExtra ); if( pCost==0 ){ rc = SQLITE_NOMEM; break; } pCost->nFrom = nFrom; pCost->nTo = nTo; pCost->iCost = iCost; memcpy(pCost->a, zFrom, nFrom); memcpy(pCost->a + nFrom, zTo, nTo); pCost->pNext = pLang->pCost; pLang->pCost = pCost; } } sqlite3_finalize(pStmt); return rc; } /* ** Return the length (in bytes) of a utf-8 character. Or return a maximum ** of N. */ static int utf8Len(unsigned char c, int N){ int len = 1; if( c>0x7f ){ if( (c&0xe0)==0xc0 ){ len = 2; }else if( (c&0xf0)==0xe0 ){ len = 3; }else{ len = 4; } } if( len>N ) len = N; return len; } /* ** Return TRUE (non-zero) of the To side of the given cost matches ** the given string. */ static int matchTo(EditDist3Cost *p, const char *z, int n){ if( p->nTo>n ) return 0; if( memcmp(p->a+p->nFrom, z, p->nTo)!=0 ) return 0; return 1; } /* ** Return TRUE (non-zero) of the To side of the given cost matches ** the given string. */ static int matchFrom(EditDist3Cost *p, const char *z, int n){ if( p->nFrom>n ) return 0; if( memcmp(p->a, z, p->nFrom)!=0 ) return 0; return 1; } /* ** Return TRUE (non-zero) of the next FROM character and the next TO ** character are the same. */ static int matchFromTo( EditDist3FromString *pStr, /* Left hand string */ int n1, /* Index of comparison character on the left */ const char *z2, /* Right-handl comparison character */ int n2 /* Bytes remaining in z2[] */ ){ int b1 = pStr->a[n1].nByte; if( b1>n2 ) return 0; if( memcmp(pStr->z+n1, z2, b1)!=0 ) return 0; return 1; } /* ** Delete an EditDist3FromString objecct */ static void editDist3FromStringDelete(EditDist3FromString *p){ int i; if( p ){ for(i=0; in; i++){ sqlite3_free(p->a[i].apDel); sqlite3_free(p->a[i].apSubst); } sqlite3_free(p); } } /* ** Create a EditDist3FromString object. */ static EditDist3FromString *editDist3FromStringNew( const EditDist3Lang *pLang, const char *z, int n ){ EditDist3FromString *pStr; EditDist3Cost *p; int i; if( n<0 ) n = (int)strlen(z); pStr = sqlite3_malloc( sizeof(*pStr) + sizeof(pStr->a[0])*n + n + 1 ); if( pStr==0 ) return 0; pStr->a = (EditDist3From*)&pStr[1]; pStr->n = n; pStr->z = (char*)&pStr->a[n]; memcpy(pStr->z, z, n+1); if( n && z[n-1]=='*' ){ pStr->isPrefix = 1; n--; pStr->n--; pStr->z[n] = 0; }else{ pStr->isPrefix = 0; } for(i=0; ia[i]; memset(pFrom, 0, sizeof(*pFrom)); pFrom->nByte = utf8Len((unsigned char)z[i], n-i); for(p=pLang->pCost; p; p=p->pNext){ EditDist3Cost **apNew; if( i+p->nFrom>n ) continue; if( matchFrom(p, z+i, n-i)==0 ) continue; if( p->nTo==0 ){ apNew = sqlite3_realloc(pFrom->apDel, sizeof(*apNew)*(pFrom->nDel+1)); if( apNew==0 ) break; pFrom->apDel = apNew; apNew[pFrom->nDel++] = p; }else{ apNew = sqlite3_realloc(pFrom->apSubst, sizeof(*apNew)*(pFrom->nSubst+1)); if( apNew==0 ) break; pFrom->apSubst = apNew; apNew[pFrom->nSubst++] = p; } } if( p ){ editDist3FromStringDelete(pStr); pStr = 0; break; } } return pStr; } /* ** Return the number of bytes in the common prefix of two UTF8 strings. ** Only complete characters are considered. */ static int editDist3PrefixLen(const char *z1, const char *z2){ int n = 0; while( z1[n] && z1[n]==z2[n] ){ n++; } while( n && (z1[n]&0xc0)==0x80 ){ n--; } return n; } /* ** Return the number of bytes in the common suffix of two UTF8 strings. ** Only complete characters are considered. */ static int editDist3SuffixLen(const char *z1, int n1, const char *z2, int n2){ int origN1 = n1; while( n1>0 && n2>0 && z1[n1-1]==z2[n2-1] ){ n1--; n2--; } while( n1pCost; p; p=p->pNext){ EditDist3Cost **apNew; if( p->nFrom>0 ) continue; if( i2+p->nTo>n2 ) continue; if( matchTo(p, z2+i2, n2-i2)==0 ) continue; a2[i2].nIns++; apNew = sqlite3_realloc(a2[i2].apIns, sizeof(*apNew)*a2[i2].nIns); if( apNew==0 ){ res = -1; /* Out of memory */ goto editDist3Abort; } a2[i2].apIns = apNew; a2[i2].apIns[a2[i2].nIns-1] = p; } } /* Prepare to compute the minimum edit distance */ szRow = f.n+1; memset(m, 0x01, (n2+1)*szRow*sizeof(m[0])); m[0] = 0; /* First fill in the top-row of the matrix with FROM deletion costs */ for(i1=0; i1iDelCost); for(k=0; knFrom, i1, p->iCost); } } /* Fill in all subsequent rows, top-to-bottom, left-to-right */ for(i2=0; i2iInsCost); for(k=0; knTo), rxp, p->iCost); } for(i1=0; i1iDelCost); for(k=0; knFrom, cxp, p->iCost); } updateCost(m, cx, cxu, pLang->iInsCost); if( matchFromTo(&f, i1, z2+i2, n2-i2) ){ updateCost(m, cx, cxd, 0); } updateCost(m, cx, cxd, pLang->iSubCost); for(k=0; knFrom+szRow*p->nTo, cxd, p->iCost); } } } } #if 0 printf(" ^"); for(i1=0; i19999 ) printf(" ****"); else printf(" %4d", v); } printf("\n"); for(i2=0; i29999 ) printf(" ****"); else printf(" %4d", v); } printf("\n"); } #endif /* Free memory allocations and return the result */ res = (int)m[szRow*(n2+1)-1]; if( f.isPrefix ){ *pnMatch = n2; for(i2=1; i2<=n2; i2++){ int b = m[szRow*i2-1]; if( b<=res ){ res = b; if( pnMatch ) *pnMatch = i2-1; } } }else if( pnMatch ){ *pnMatch = n2; } editDist3Abort: for(i2=0; i2nLang; i++){ if( pConfig->a[i].iLang==iLang ) return &pConfig->a[i]; } return &editDist3Lang; } /* ** Function: editdist3(A,B,iLang) ** editdist3(tablename) ** ** Return the cost of transforming string A into string B using edit ** weights for iLang. ** ** The second form loads edit weights into memory from a table. */ static void editDist3SqlFunc( sqlite3_context *context, int argc, sqlite3_value **argv ){ EditDist3Config *pConfig = (EditDist3Config*)sqlite3_user_data(context); sqlite3 *db = sqlite3_context_db_handle(context); int rc; if( argc==1 ){ const char *zTable = (const char*)sqlite3_value_text(argv[0]); rc = editDist3ConfigLoad(pConfig, db, zTable); if( rc ) sqlite3_result_error_code(context, rc); }else{ const char *zA = (const char*)sqlite3_value_text(argv[0]); const char *zB = (const char*)sqlite3_value_text(argv[1]); int nA = sqlite3_value_bytes(argv[0]); int nB = sqlite3_value_bytes(argv[1]); int iLang = argc==3 ? sqlite3_value_int(argv[2]) : 0; const EditDist3Lang *pLang = editDist3FindLang(pConfig, iLang); EditDist3FromString *pFrom; int dist; pFrom = editDist3FromStringNew(pLang, zA, nA); if( pFrom==0 ){ sqlite3_result_error_nomem(context); return; } dist = editDist3Core(pFrom, zB, nB, pLang, 0); editDist3FromStringDelete(pFrom); sqlite3_result_int(context, dist); } } /* ** Register the editDist3 function with SQLite */ static int editDist3Install(sqlite3 *db){ int rc; EditDist3Config *pConfig = sqlite3_malloc( sizeof(*pConfig) ); if( pConfig==0 ) return SQLITE_NOMEM; memset(pConfig, 0, sizeof(*pConfig)); rc = sqlite3_create_function_v2(db, "editdist3", 2, SQLITE_UTF8, pConfig, editDist3SqlFunc, 0, 0, 0); if( rc==SQLITE_OK ){ rc = sqlite3_create_function_v2(db, "editdist3", 3, SQLITE_UTF8, pConfig, editDist3SqlFunc, 0, 0, 0); } if( rc==SQLITE_OK ){ rc = sqlite3_create_function_v2(db, "editdist3", 1, SQLITE_UTF8, pConfig, editDist3SqlFunc, 0, 0, editDist3ConfigDelete); }else{ sqlite3_free(pConfig); } return rc; } /* End configurable cost unicode edit distance routines ****************************************************************************** ****************************************************************************** ** Begin transliterate unicode-to-ascii implementation */ #if !SQLITE_AMALGAMATION /* ** This lookup table is used to help decode the first byte of ** a multi-byte UTF8 character. */ static const unsigned char sqlite3Utf8Trans1[] = { 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x00, 0x01, 0x02, 0x03, 0x00, 0x01, 0x00, 0x00, }; #endif /* ** Return the value of the first UTF-8 character in the string. */ static int utf8Read(const unsigned char *z, int n, int *pSize){ int c, i; if( n==0 ){ c = i = 0; }else{ c = z[0]; i = 1; if( c>=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; } /* ** Return the number of characters in the shortest prefix of the input ** string that transliterates to an ASCII string nTrans bytes or longer. ** Or, if the transliteration of the input string is less than nTrans ** bytes in size, return the number of characters in the input string. */ static int translen_to_charlen(const char *zIn, int nIn, int nTrans){ int i, c, sz, nOut; int nChar; i = nOut = 0; for(nChar=0; i=128 ){ int xTop, xBtm, x; xTop = sizeof(translit)/sizeof(translit[0]) - 1; xBtm = 0; while( xTop>=xBtm ){ x = (xTop + xBtm)/2; if( translit[x].cFrom==c ){ if( translit[x].cTo1 ) nOut++; if( c==0x0429 || c== 0x0449 ) nOut += 2; break; }else if( translit[x].cFrom>c ){ xTop = x-1; }else{ xBtm = x+1; } } } } return nChar; } /* ** 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); } /* End transliterate ****************************************************************************** ****************************************************************************** ** Begin Polloc & Zamora SPEEDCOP style keying functions. */ /* ** The Pollock & Zamora skeleton function. Move all consonants to the ** front and all vowels to the end, removing duplicates. Except if the ** first letter is a vowel then it remains as the first letter. */ static void pollockSkeletonKey(const char *zIn, char *zOut){ int i, j; unsigned char c; char seen[26]; static const unsigned char isVowel[] = { 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 }; memset(seen, 0, sizeof(seen)); for(i=j=0; (c = (unsigned char)zIn[i])!=0; i++){ if( c<'a' || c>'z' ) continue; if( j>0 || isVowel[c-'a'] ) continue; if( seen[c-'a'] ) continue; seen[c-'a'] = 1; zOut[j++] = c; } for(i=0; (c = (unsigned char)zIn[i])!=0; i++){ if( c<'a' || c>'z' ) continue; if( seen[c-'a'] ) continue; if( !isVowel[c-'a'] ) continue; seen[c-'a'] = 1; zOut[j++] = c; } zOut[j] = 0; } /* ** Function: pollock_skeleton(X) ** ** Return the Pollock and Zamora skeleton key for a string X of all ** lower-case letters. */ static void pollockSkeletonSqlFunc( sqlite3_context *context, int argc, sqlite3_value **argv ){ const char *zIn = (const char*)sqlite3_value_text(argv[0]); int nIn = sqlite3_value_bytes(argv[0]); char *zOut; if( zIn ){ zOut = sqlite3_malloc( nIn + 1 ); if( zOut==0 ){ sqlite3_result_error_nomem(context); }else{ pollockSkeletonKey(zIn, zOut); sqlite3_result_text(context, (char*)zOut, -1, sqlite3_free); } } } /* ** The Pollock & Zamora omission key. ** ** The key consists of unique consonants in the following order: ** ** jkqxzvwybfmgpdhclntsr ** ** These are followed by unique vowels in input order. */ static void pollockOmissionKey(const char *zIn, char *zOut){ int i, j; unsigned char c; char seen[26]; static const unsigned char isVowel[] = { 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 }; static const unsigned char constOrder[] = "jkqxzvwybfmgpdhclntsr"; memset(seen, 0, sizeof(seen)); for(i=j=0; (c = (unsigned char)zIn[i])!=0; i++){ if( c<'a' || c>'z' ) continue; if( isVowel[c-'a'] ) continue; if( seen[c-'a'] ) continue; seen[c-'a'] = 1; } for(i=0; (c = constOrder[i])!=0; i++){ if( seen[c-'a'] ) zOut[j++] = c; } for(i=0; (c = (unsigned char)zIn[i])!=0; i++){ if( c<'a' || c>'z' ) continue; if( seen[c-'a'] ) continue; if( !isVowel[c-'a'] ) continue; seen[c-'a'] = 1; zOut[j++] = c; } zOut[j] = 0; } /* ** Function: pollock_omission(X) ** ** Return the Pollock and Zamora omission key for a string X of all ** lower-case letters. */ static void pollockOmissionSqlFunc( sqlite3_context *context, int argc, sqlite3_value **argv ){ const char *zIn = (const char*)sqlite3_value_text(argv[0]); int nIn = sqlite3_value_bytes(argv[0]); char *zOut; if( zIn ){ zOut = sqlite3_malloc( nIn + 1 ); if( zOut==0 ){ sqlite3_result_error_nomem(context); }else{ pollockOmissionKey(zIn, zOut); sqlite3_result_text(context, (char*)zOut, -1, sqlite3_free); } } } /* End SPEEDCOP keying functions ****************************************************************************** ****************************************************************************** ** Begin spellfix1 virtual table. */ /* Maximum length of a phonehash used for querying the shadow table */ #define SPELLFIX_MX_HASH 8 /* Maximum number of hash strings to examine per query */ #define SPELLFIX_MX_RUN 8 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 */ char *zCostTable; /* Table holding edit-distance cost numbers */ EditDist3Config *pConfig3; /* Parsed edit distance costs */ }; /* 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 */ char *zPattern; /* rhs of MATCH clause */ 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 */ int iMatchlen; /* Value of matchlen column (or -1) */ char zHash[SPELLFIX_MX_HASH]; /* the phonehash used for this match */ } *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); editDist3ConfigDelete(p->pConfig3); sqlite3_free(p->zCostTable); 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); } /* ** Make a copy of a string. Remove leading and trailing whitespace ** and dequote it. */ static char *spellfix1Dequote(const char *zIn){ char *zOut; int i, j; char c; while( isspace(zIn[0]) ) zIn++; zOut = sqlite3_mprintf("%s", zIn); if( zOut==0 ) return 0; i = (int)strlen(zOut); while( i>0 && isspace(zOut[i-1]) ){ i--; } zOut[i] = 0; c = zOut[0]; if( c=='\'' || c=='"' ){ for(i=1, j=0; zOut[i]; i++){ zOut[j++] = zOut[i]; if( zOut[i]==c ){ if( zOut[i+1]==c ){ i++; }else{ zOut[j-1] = 0; break; } } } } return zOut; } /* ** 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 (i.e. "edit_cost_table" parameter) */ 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; int i; 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, matchlen, phonehash, " "top HIDDEN, scope HIDDEN, srchcnt HIDDEN, " "soundslike HIDDEN, command HIDDEN)" ); #define SPELLFIX_COL_WORD 0 #define SPELLFIX_COL_RANK 1 #define SPELLFIX_COL_DISTANCE 2 #define SPELLFIX_COL_LANGID 3 #define SPELLFIX_COL_SCORE 4 #define SPELLFIX_COL_MATCHLEN 5 #define SPELLFIX_COL_PHONEHASH 6 #define SPELLFIX_COL_TOP 7 #define SPELLFIX_COL_SCOPE 8 #define SPELLFIX_COL_SRCHCNT 9 #define SPELLFIX_COL_SOUNDSLIKE 10 #define SPELLFIX_COL_COMMAND 11 } 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 ); } for(i=3; rc==SQLITE_OK && ia[idx].iRowid = sqlite3_column_int64(pStmt, 0); pCur->a[idx].iRank = iRank; pCur->a[idx].iDistance = iDist; pCur->a[idx].iScore = iScore; pCur->a[idx].iMatchlen = iMatchlen; memcpy(pCur->a[idx].zHash, zHash1, iScope+1); 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( iWorstpVTab; /* The virtual table that owns pCur */ MatchQuery x; /* For passing info to RunQuery() */ /* Load the cost table if we have not already done so */ if( p->zCostTable!=0 && p->pConfig3==0 ){ p->pConfig3 = sqlite3_malloc( sizeof(p->pConfig3[0]) ); if( p->pConfig3==0 ) return SQLITE_NOMEM; memset(p->pConfig3, 0, sizeof(p->pConfig3[0])); rc = editDist3ConfigLoad(p->pConfig3, p->db, p->zCostTable); if( rc ) return rc; } memset(&x, 0, sizeof(x)); x.iScope = 3; /* Default scope if none specified by "WHERE scope=N" */ x.iMaxDist = -1; /* Maximum allowed edit distance */ 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 ){ x.iScope = sqlite3_value_int(argv[idx++]); if( x.iScope<1 ) x.iScope = 1; if( x.iScope>SPELLFIX_MX_HASH-2 ) x.iScope = SPELLFIX_MX_HASH-2; } if( idxNum&(16|32) ){ x.iMaxDist = sqlite3_value_int(argv[idx++]); if( idxNum&16 ) x.iMaxDist--; if( x.iMaxDist<0 ) x.iMaxDist = 0; } spellfix1ResetCursor(pCur); spellfix1ResizeCursor(pCur, iLimit); zMatchThis = sqlite3_value_text(argv[0]); if( zMatchThis==0 ) return SQLITE_OK; if( p->pConfig3 ){ x.pLang = editDist3FindLang(p->pConfig3, iLang); pMatchStr3 = editDist3FromStringNew(x.pLang, (const char*)zMatchThis, -1); }else{ x.pLang = 0; } zPattern = (char*)transliterate(zMatchThis, sqlite3_value_bytes(argv[0])); sqlite3_free(pCur->zPattern); pCur->zPattern = zPattern; if( zPattern==0 ) return SQLITE_NOMEM; nPattern = strlen(zPattern); if( zPattern[nPattern-1]=='*' ) nPattern--; zSql = sqlite3_mprintf( "SELECT id, word, rank, k1" " FROM \"%w\".\"%w_vocab\"" " WHERE langid=%d AND k2>=?1 AND k2zDbName, p->zTableName, iLang ); rc = sqlite3_prepare_v2(p->db, zSql, -1, &pStmt, 0); sqlite3_free(zSql); pCur->iLang = iLang; x.pCur = pCur; x.pStmt = pStmt; x.zPattern = zPattern; x.nPattern = nPattern; x.pMatchStr3 = pMatchStr3; x.iLang = iLang; x.rc = rc; x.pConfig3 = p->pConfig3; if( x.rc==SQLITE_OK ){ spellfix1RunQuery(&x, zPattern, nPattern); } #if 0 /* Convert "ght" to "t" in the original pattern and try again */ if( x.rc==SQLITE_OK ){ int i, j; /* Loop counters */ char zQuery[50]; /* Space for alternative query string */ for(i=j=0; ia ){ qsort(pCur->a, pCur->nRow, sizeof(pCur->a[0]), spellfix1RowCompare); pCur->iTop = iLimit; pCur->iScope = iScope; } sqlite3_finalize(pStmt); editDist3FromStringDelete(pMatchStr3); return pCur->a ? x.rc : SQLITE_NOMEM; } /* ** 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); spellfix1ResizeCursor(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 SPELLFIX_COL_WORD: { sqlite3_result_text(ctx, pCur->a[pCur->iRow].zWord, -1, SQLITE_STATIC); break; } case SPELLFIX_COL_RANK: { sqlite3_result_int(ctx, pCur->a[pCur->iRow].iRank); break; } case SPELLFIX_COL_DISTANCE: { sqlite3_result_int(ctx, pCur->a[pCur->iRow].iDistance); break; } case SPELLFIX_COL_LANGID: { sqlite3_result_int(ctx, pCur->iLang); break; } case SPELLFIX_COL_SCORE: { sqlite3_result_int(ctx, pCur->a[pCur->iRow].iScore); break; } case SPELLFIX_COL_MATCHLEN: { int iMatchlen = pCur->a[pCur->iRow].iMatchlen; if( iMatchlen<0 ){ int nPattern = strlen(pCur->zPattern); char *zWord = pCur->a[pCur->iRow].zWord; int nWord = strlen(zWord); if( nPattern>0 && pCur->zPattern[nPattern-1]=='*' ){ char *zTranslit; int res; zTranslit = (char *)transliterate((unsigned char *)zWord, nWord); if( !zTranslit ) return SQLITE_NOMEM; res = editdist1(pCur->zPattern, zTranslit, pCur->iLang, &iMatchlen); sqlite3_free(zTranslit); if( res<0 ) return SQLITE_NOMEM; iMatchlen = translen_to_charlen(zWord, nWord, iMatchlen); }else{ iMatchlen = utf8Charlen(zWord, nWord); } } sqlite3_result_int(ctx, iMatchlen); break; } case SPELLFIX_COL_PHONEHASH: { sqlite3_result_text(ctx, pCur->a[pCur->iRow].zHash, -1, SQLITE_STATIC); break; } case SPELLFIX_COL_TOP: { sqlite3_result_int(ctx, pCur->iTop); break; } case SPELLFIX_COL_SCOPE: { sqlite3_result_int(ctx, pCur->iScope); break; } case SPELLFIX_COL_SRCHCNT: { 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[SPELLFIX_COL_WORD+2]); int nWord = sqlite3_value_bytes(argv[SPELLFIX_COL_WORD+2]); int iLang = sqlite3_value_int(argv[SPELLFIX_COL_LANGID+2]); int iRank = sqlite3_value_int(argv[SPELLFIX_COL_RANK+2]); const unsigned char *zSoundslike = sqlite3_value_text(argv[SPELLFIX_COL_SOUNDSLIKE+2]); int nSoundslike = sqlite3_value_bytes(argv[SPELLFIX_COL_SOUNDSLIKE+2]); char *zK1, *zK2; int i; char c; if( zWord==0 ){ /* Inserts of the form: INSERT INTO table(command) VALUES('xyzzy'); ** cause zWord to be NULL, so we look at the "command" column to see ** what special actions to take */ const char *zCmd = (const char*)sqlite3_value_text(argv[SPELLFIX_COL_COMMAND+2]); if( zCmd==0 ){ pVTab->zErrMsg = sqlite3_mprintf("%s.word may not be NULL", p->zTableName); return SQLITE_CONSTRAINT; } if( strcmp(zCmd,"reset")==0 ){ /* Reset the edit cost table (if there is one). */ editDist3ConfigDelete(p->pConfig3); p->pConfig3 = 0; return SQLITE_OK; } pVTab->zErrMsg = sqlite3_mprintf("unknown value for %s.command: \"%w\"", p->zTableName, zCmd); return SQLITE_ERROR; } 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*)phoneticHash((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_editdist", 3, SQLITE_UTF8, 0, editdistSqlFunc, 0, 0); nErr += sqlite3_create_function(db, "spellfix1_phonehash", 1, SQLITE_UTF8, 0, phoneticHashSqlFunc, 0, 0); nErr += sqlite3_create_function(db, "spellfix1_scriptcode", 1, SQLITE_UTF8, 0, scriptCodeSqlFunc, 0, 0); nErr += sqlite3_create_function(db, "pollock_skeleton", 1, SQLITE_UTF8, 0, pollockSkeletonSqlFunc, 0, 0); nErr += sqlite3_create_function(db, "pollock_omission", 1, SQLITE_UTF8, 0, pollockOmissionSqlFunc, 0, 0); nErr += sqlite3_create_module(db, "spellfix1", &spellfix1Module, 0); nErr += editDist3Install(db); /* Verify sanity of the translit[] table */ for(i=0; i