Revision control
Copy as Markdown
Other Tools
/*
** 2006 September 30
**
** 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.
**
*************************************************************************
** Implementation of the full-text-search tokenizer that implements
** a Porter stemmer.
**
*/
/*
* This file is based on the SQLite FTS3 Porter Stemmer implementation.
*
* This is an attempt to provide some level of full-text search to users of
* Thunderbird who use languages that are not space/punctuation delimited.
* This is accomplished by performing bi-gram indexing of characters fall
* into the unicode space occupied by character sets used in such languages.
*
* Bi-gram indexing means that given the string "12345" we would index the
* pairs "12", "23", "34", and "45" (with position information). We do this
* because we are not sure where the word/semantic boundaries are in that
* string. Then, when a user searches for "234" the FTS3 engine tokenizes the
* search query into "23" and "34". Using special phrase-logic FTS3 requires
* the matches to have the tokens "23" and "34" adjacent to each other and in
* that order. In theory if the user searched for "2345" we we could just
* search for "23 NEAR/2 34". Unfortunately, NEAR does not imply ordering,
* so even though that would be more efficient, we would lose correctness
* and cannot do it.
*
* The efficiency and usability of bi-gram search assumes that the character
* space is large enough and actually observed bi-grams sufficiently
* distributed throughout the potential space so that the search bi-grams
* generated when the user issues a query find a 'reasonable' number of
* documents for each bi-gram match.
*
* Mozilla contributors:
* Makoto Kato <m_kato@ga2.so-net.ne.jp>
* Andrew Sutherland <asutherland@asutherland.org>
*/
/*
** The code in this file is only compiled if:
**
** * The FTS3 module is being built as an extension
** (in which case SQLITE_CORE is not defined), or
**
** * The FTS3 module is being built into the core of
** SQLite (in which case SQLITE_ENABLE_FTS3 is defined).
*/
#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3)
# include <assert.h>
# include <stdlib.h>
# include <stdio.h>
# include <string.h>
# include <ctype.h>
# include "fts3_tokenizer.h"
/* need some defined to compile without sqlite3 code */
# define sqlite3_malloc malloc
# define sqlite3_free free
# define sqlite3_realloc realloc
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,
};
typedef unsigned char u8;
/**
* SQLite helper macro from sqlite3.c (really utf.c) to encode a unicode
* character into utf8.
*
* @param zOut A pointer to the current write position that is updated by
* the routine. At entry it should point to one-past the last valid
* encoded byte. The same holds true at exit.
* @param c The character to encode; this should be an unsigned int.
*/
# define WRITE_UTF8(zOut, c) \
{ \
if (c < 0x0080) { \
*zOut++ = (u8)(c & 0xff); \
} else if (c < 0x0800) { \
*zOut++ = 0xC0 + (u8)((c >> 6) & 0x1F); \
*zOut++ = 0x80 + (u8)(c & 0x3F); \
} else if (c < 0x10000) { \
*zOut++ = 0xE0 + (u8)((c >> 12) & 0x0F); \
*zOut++ = 0x80 + (u8)((c >> 6) & 0x3F); \
*zOut++ = 0x80 + (u8)(c & 0x3F); \
} else { \
*zOut++ = 0xf0 + (u8)((c >> 18) & 0x07); \
*zOut++ = 0x80 + (u8)((c >> 12) & 0x3F); \
*zOut++ = 0x80 + (u8)((c >> 6) & 0x3F); \
*zOut++ = 0x80 + (u8)(c & 0x3F); \
} \
}
/**
* Fudge factor to avoid buffer overwrites when WRITE_UTF8 is involved.
*
* Our normalization table includes entries that may result in a larger
* utf-8 encoding. Namely, 023a maps to 2c65. This is a growth from 2 bytes
* as utf-8 encoded to 3 bytes. This is currently the only transition possible
* because 1-byte encodings are known to stay 1-byte and our normalization
* table is 16-bit and so can't generate a 4-byte encoded output.
*
* For simplicity, we just multiple by 2 which covers the current case and
* potential growth for 2-byte to 4-byte growth. We can afford to do this
* because we're not talking about a lot of memory here as a rule.
*/
# define MAX_UTF8_GROWTH_FACTOR 2
/**
* Helper from sqlite3.c to read a single UTF8 character.
*
* The clever bit with multi-byte reading is that you keep going until you find
* a byte whose top bits are not '10'. A single-byte UTF8 character will have
* '00' or '01', and a multi-byte UTF8 character must start with '11'.
*
* In the event of illegal UTF-8 this macro may read an arbitrary number of
* characters but will never read past zTerm. The resulting character value
* of illegal UTF-8 can be anything, although efforts are made to return the
* illegal character (0xfffd) for UTF-16 surrogates.
*
* @param zIn A pointer to the current position that is updated by the routine,
* pointing at the start of the next character when the routine returns.
* @param zTerm A pointer one past the end of the buffer.
* @param c The 'unsigned int' to hold the resulting character value. Do not
* use a short or a char.
*/
# define READ_UTF8(zIn, zTerm, c) \
{ \
c = *(zIn++); \
if (c >= 0xc0) { \
c = sqlite3Utf8Trans1[c - 0xc0]; \
while (zIn != zTerm && (*zIn & 0xc0) == 0x80) { \
c = (c << 6) + (0x3f & *(zIn++)); \
} \
if (c < 0x80 || (c & 0xFFFFF800) == 0xD800 || \
(c & 0xFFFFFFFE) == 0xFFFE) { \
c = 0xFFFD; \
} \
} \
}
/* end of compatible block to complie codes */
/*
** Class derived from sqlite3_tokenizer
*/
typedef struct porter_tokenizer {
sqlite3_tokenizer base; /* Base class */
} porter_tokenizer;
/*
** Class derived from sqlit3_tokenizer_cursor
*/
typedef struct porter_tokenizer_cursor {
sqlite3_tokenizer_cursor base;
const char* zInput; /* input we are tokenizing */
int nInput; /* size of the input */
int iOffset; /* current position in zInput */
int iToken; /* index of next token to be returned */
unsigned char* zToken; /* storage for current token */
int nAllocated; /* space allocated to zToken buffer */
/**
* Store the offset of the second character in the bi-gram pair that we just
* emitted so that we can consider it being the first character in a bi-gram
* pair.
* The value 0 indicates that there is no previous such character. This is
* an acceptable sentinel value because the 0th offset can never be the
* offset of the second in a bi-gram pair.
*
* For example, let us say we are tokenizing a string of 4 CJK characters
* represented by the byte-string "11223344" where each repeated digit
* indicates 2-bytes of storage used to encode the character in UTF-8.
* (It actually takes 3, btw.) Then on the passes to emit each token,
* the iOffset and iPrevGigramOffset values at entry will be:
*
* 1122: iOffset = 0, iPrevBigramOffset = 0
* 2233: iOffset = 4, iPrevBigramOffset = 2
* 3344: iOffset = 6, iPrevBigramOffset = 4
* (nothing will be emitted): iOffset = 8, iPrevBigramOffset = 6
*/
int iPrevBigramOffset; /* previous result was bi-gram */
} porter_tokenizer_cursor;
/* Forward declaration */
static const sqlite3_tokenizer_module porterTokenizerModule;
/* from normalize.c */
extern unsigned int normalize_character(const unsigned int c);
/*
** Create a new tokenizer instance.
*/
static int porterCreate(int argc, const char* const* argv,
sqlite3_tokenizer** ppTokenizer) {
porter_tokenizer* t;
t = (porter_tokenizer*)sqlite3_malloc(sizeof(*t));
if (t == NULL) return SQLITE_NOMEM;
memset(t, 0, sizeof(*t));
*ppTokenizer = &t->base;
return SQLITE_OK;
}
/*
** Destroy a tokenizer
*/
static int porterDestroy(sqlite3_tokenizer* pTokenizer) {
sqlite3_free(pTokenizer);
return SQLITE_OK;
}
/*
** Prepare to begin tokenizing a particular string. The input
** string to be tokenized is zInput[0..nInput-1]. A cursor
** used to incrementally tokenize this string is returned in
** *ppCursor.
*/
static int porterOpen(
sqlite3_tokenizer* pTokenizer, /* The tokenizer */
const char* zInput, int nInput, /* String to be tokenized */
sqlite3_tokenizer_cursor** ppCursor /* OUT: Tokenization cursor */
) {
porter_tokenizer_cursor* c;
c = (porter_tokenizer_cursor*)sqlite3_malloc(sizeof(*c));
if (c == NULL) return SQLITE_NOMEM;
c->zInput = zInput;
if (zInput == 0) {
c->nInput = 0;
} else if (nInput < 0) {
c->nInput = (int)strlen(zInput);
} else {
c->nInput = nInput;
}
c->iOffset = 0; /* start tokenizing at the beginning */
c->iToken = 0;
c->zToken = NULL; /* no space allocated, yet. */
c->nAllocated = 0;
c->iPrevBigramOffset = 0;
*ppCursor = &c->base;
return SQLITE_OK;
}
/*
** Close a tokenization cursor previously opened by a call to
** porterOpen() above.
*/
static int porterClose(sqlite3_tokenizer_cursor* pCursor) {
porter_tokenizer_cursor* c = (porter_tokenizer_cursor*)pCursor;
sqlite3_free(c->zToken);
sqlite3_free(c);
return SQLITE_OK;
}
/*
** Vowel or consonant
*/
static const char cType[] = {0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1,
1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 2, 1};
/*
** isConsonant() and isVowel() determine if their first character in
** the string they point to is a consonant or a vowel, according
** to Porter ruls.
**
** A consonate is any letter other than 'a', 'e', 'i', 'o', or 'u'.
** 'Y' is a consonant unless it follows another consonant,
** in which case it is a vowel.
**
** In these routine, the letters are in reverse order. So the 'y' rule
** is that 'y' is a consonant unless it is followed by another
** consonant.
*/
static int isVowel(const char*);
static int isConsonant(const char* z) {
int j;
char x = *z;
if (x == 0) return 0;
assert(x >= 'a' && x <= 'z');
j = cType[x - 'a'];
if (j < 2) return j;
return z[1] == 0 || isVowel(z + 1);
}
static int isVowel(const char* z) {
int j;
char x = *z;
if (x == 0) return 0;
assert(x >= 'a' && x <= 'z');
j = cType[x - 'a'];
if (j < 2) return 1 - j;
return isConsonant(z + 1);
}
/*
** Let any sequence of one or more vowels be represented by V and let
** C be sequence of one or more consonants. Then every word can be
** represented as:
**
** [C] (VC){m} [V]
**
** In prose: A word is an optional consonant followed by zero or
** vowel-consonant pairs followed by an optional vowel. "m" is the
** number of vowel consonant pairs. This routine computes the value
** of m for the first i bytes of a word.
**
** Return true if the m-value for z is 1 or more. In other words,
** return true if z contains at least one vowel that is followed
** by a consonant.
**
** In this routine z[] is in reverse order. So we are really looking
** for an instance of of a consonant followed by a vowel.
*/
static int m_gt_0(const char* z) {
while (isVowel(z)) {
z++;
}
if (*z == 0) return 0;
while (isConsonant(z)) {
z++;
}
return *z != 0;
}
/* Like mgt0 above except we are looking for a value of m which is
** exactly 1
*/
static int m_eq_1(const char* z) {
while (isVowel(z)) {
z++;
}
if (*z == 0) return 0;
while (isConsonant(z)) {
z++;
}
if (*z == 0) return 0;
while (isVowel(z)) {
z++;
}
if (*z == 0) return 1;
while (isConsonant(z)) {
z++;
}
return *z == 0;
}
/* Like mgt0 above except we are looking for a value of m>1 instead
** or m>0
*/
static int m_gt_1(const char* z) {
while (isVowel(z)) {
z++;
}
if (*z == 0) return 0;
while (isConsonant(z)) {
z++;
}
if (*z == 0) return 0;
while (isVowel(z)) {
z++;
}
if (*z == 0) return 0;
while (isConsonant(z)) {
z++;
}
return *z != 0;
}
/*
** Return TRUE if there is a vowel anywhere within z[0..n-1]
*/
static int hasVowel(const char* z) {
while (isConsonant(z)) {
z++;
}
return *z != 0;
}
/*
** Return TRUE if the word ends in a double consonant.
**
** The text is reversed here. So we are really looking at
** the first two characters of z[].
*/
static int doubleConsonant(const char* z) {
return isConsonant(z) && z[0] == z[1] && isConsonant(z + 1);
}
/*
** Return TRUE if the word ends with three letters which
** are consonant-vowel-consonent and where the final consonant
** is not 'w', 'x', or 'y'.
**
** The word is reversed here. So we are really checking the
** first three letters and the first one cannot be in [wxy].
*/
static int star_oh(const char* z) {
return z[0] != 0 && isConsonant(z) && z[0] != 'w' && z[0] != 'x' &&
z[0] != 'y' && z[1] != 0 && isVowel(z + 1) && z[2] != 0 &&
isConsonant(z + 2);
}
/*
** If the word ends with zFrom and xCond() is true for the stem
** of the word that precedes the zFrom ending, then change the
** ending to zTo.
**
** The input word *pz and zFrom are both in reverse order. zTo
** is in normal order.
**
** Return TRUE if zFrom matches. Return FALSE if zFrom does not
** match. Not that TRUE is returned even if xCond() fails and
** no substitution occurs.
*/
static int stem(
char** pz, /* The word being stemmed (Reversed) */
const char* zFrom, /* If the ending matches this... (Reversed) */
const char* zTo, /* ... change the ending to this (not reversed) */
int (*xCond)(const char*) /* Condition that must be true */
) {
char* z = *pz;
while (*zFrom && *zFrom == *z) {
z++;
zFrom++;
}
if (*zFrom != 0) return 0;
if (xCond && !xCond(z)) return 1;
while (*zTo) {
*(--z) = *(zTo++);
}
*pz = z;
return 1;
}
/**
* Voiced sound mark is only on Japanese. It is like accent. It combines with
* previous character. Example, "サ" (Katakana) with "゛" (voiced sound mark)
* is "ザ". Although full-width character mapping has combined character like
* "ザ", there is no combined character on half-width Katanaka character
* mapping.
*/
static int isVoicedSoundMark(const unsigned int c) {
if (c == 0xff9e || c == 0xff9f || c == 0x3099 || c == 0x309a) return 1;
return 0;
}
/**
* How many unicode characters to take from the front and back of a term in
* |copy_stemmer|.
*/
# define COPY_STEMMER_COPY_HALF_LEN 10
/**
* Normalizing but non-stemming term copying.
*
* The original function would take 10 bytes from the front and 10 bytes from
* the back if there were no digits in the string and it was more than 20
* bytes long. If there were digits involved that would decrease to 3 bytes
* from the front and 3 from the back. This would potentially corrupt utf-8
* encoded characters, which is fine from the perspective of the FTS3 logic.
*
* In our revised form we now operate on a unicode character basis rather than
* a byte basis. Additionally we use the same length limit even if there are
* digits involved because it's not clear digit token-space reduction is saving
* us from anything and could be hurting. Specifically, if no one is ever
* going to search on things with digits, then we should just remove them.
* Right now, the space reduction is going to increase false positives when
* people do search on them and increase the number of collisions sufficiently
* to make it really expensive. The caveat is there will be some increase in
* index size which could be meaningful if people are receiving lots of emails
* full of distinct numbers.
*
* In order to do the copy-from-the-front and copy-from-the-back trick, once
* we reach N characters in, we set zFrontEnd to the current value of zOut
* (which represents the termination of the first part of the result string)
* and set zBackStart to the value of zOutStart. We then advanced zBackStart
* along a character at a time as we write more characters. Once we have
* traversed the entire string, if zBackStart > zFrontEnd, then we know
* the string should be shrunk using the characters in the two ranges.
*
* (It would be faster to scan from the back with specialized logic but that
* particular logic seems easy to screw up and we don't have unit tests in here
* to the extent required.)
*
* @param zIn Input string to normalize and potentially shrink.
* @param nBytesIn The number of bytes in zIn, distinct from the number of
* unicode characters encoded in zIn.
* @param zOut The string to write our output into. This must have at least
* nBytesIn * MAX_UTF8_GROWTH_FACTOR in order to compensate for
* normalization that results in a larger utf-8 encoding.
* @param pnBytesOut Integer to write the number of bytes in zOut into.
*/
static void copy_stemmer(const unsigned char* zIn, const int nBytesIn,
unsigned char* zOut, int* pnBytesOut) {
const unsigned char* zInTerm = zIn + nBytesIn;
unsigned char* zOutStart = zOut;
unsigned int c;
unsigned int charCount = 0;
unsigned char *zFrontEnd = NULL, *zBackStart = NULL;
unsigned int trashC;
/* copy normalized character */
while (zIn < zInTerm) {
READ_UTF8(zIn, zInTerm, c);
c = normalize_character(c);
/* ignore voiced/semi-voiced sound mark */
if (!isVoicedSoundMark(c)) {
/* advance one non-voiced sound mark character. */
if (zBackStart) READ_UTF8(zBackStart, zOut, trashC);
WRITE_UTF8(zOut, c);
charCount++;
if (charCount == COPY_STEMMER_COPY_HALF_LEN) {
zFrontEnd = zOut;
zBackStart = zOutStart;
}
}
}
/* if we need to shrink the string, transplant the back bytes */
if (zBackStart > zFrontEnd) { /* this handles when both are null too */
size_t backBytes = zOut - zBackStart;
memmove(zFrontEnd, zBackStart, backBytes);
zOut = zFrontEnd + backBytes;
}
*zOut = 0;
*pnBytesOut = zOut - zOutStart;
}
/*
** Stem the input word zIn[0..nIn-1]. Store the output in zOut.
** zOut is at least big enough to hold nIn bytes. Write the actual
** size of the output word (exclusive of the '\0' terminator) into *pnOut.
**
** Any upper-case characters in the US-ASCII character set ([A-Z])
** are converted to lower case. Upper-case UTF characters are
** unchanged.
**
** Words that are longer than about 20 bytes are stemmed by retaining
** a few bytes from the beginning and the end of the word. If the
** word contains digits, 3 bytes are taken from the beginning and
** 3 bytes from the end. For long words without digits, 10 bytes
** are taken from each end. US-ASCII case folding still applies.
**
** If the input word contains not digits but does characters not
** in [a-zA-Z] then no stemming is attempted and this routine just
** copies the input into the input into the output with US-ASCII
** case folding.
**
** Stemming never increases the length of the word. So there is
** no chance of overflowing the zOut buffer.
*/
static void porter_stemmer(const unsigned char* zIn, unsigned int nIn,
unsigned char* zOut, int* pnOut) {
unsigned int i, j, c;
char zReverse[28];
char *z, *z2;
const unsigned char* zTerm = zIn + nIn;
const unsigned char* zTmp = zIn;
if (nIn < 3 || nIn >= sizeof(zReverse) - 7) {
/* The word is too big or too small for the porter stemmer.
** Fallback to the copy stemmer */
copy_stemmer(zIn, nIn, zOut, pnOut);
return;
}
for (j = sizeof(zReverse) - 6; zTmp < zTerm; j--) {
READ_UTF8(zTmp, zTerm, c);
c = normalize_character(c);
if (c >= 'a' && c <= 'z') {
zReverse[j] = c;
} else {
/* The use of a character not in [a-zA-Z] means that we fallback
** to the copy stemmer */
copy_stemmer(zIn, nIn, zOut, pnOut);
return;
}
}
memset(&zReverse[sizeof(zReverse) - 5], 0, 5);
z = &zReverse[j + 1];
/* Step 1a */
if (z[0] == 's') {
if (!stem(&z, "sess", "ss", 0) && !stem(&z, "sei", "i", 0) &&
!stem(&z, "ss", "ss", 0)) {
z++;
}
}
/* Step 1b */
z2 = z;
if (stem(&z, "dee", "ee", m_gt_0)) {
/* Do nothing. The work was all in the test */
} else if ((stem(&z, "gni", "", hasVowel) || stem(&z, "de", "", hasVowel)) &&
z != z2) {
if (stem(&z, "ta", "ate", 0) || stem(&z, "lb", "ble", 0) ||
stem(&z, "zi", "ize", 0)) {
/* Do nothing. The work was all in the test */
} else if (doubleConsonant(z) && (*z != 'l' && *z != 's' && *z != 'z')) {
z++;
} else if (m_eq_1(z) && star_oh(z)) {
*(--z) = 'e';
}
}
/* Step 1c */
if (z[0] == 'y' && hasVowel(z + 1)) {
z[0] = 'i';
}
/* Step 2 */
switch (z[1]) {
case 'a':
(void)(stem(&z, "lanoita", "ate", m_gt_0) ||
stem(&z, "lanoit", "tion", m_gt_0));
break;
case 'c':
(void)(stem(&z, "icne", "ence", m_gt_0) ||
stem(&z, "icna", "ance", m_gt_0));
break;
case 'e':
(void)(stem(&z, "rezi", "ize", m_gt_0));
break;
case 'g':
(void)(stem(&z, "igol", "log", m_gt_0));
break;
case 'l':
(void)(stem(&z, "ilb", "ble", m_gt_0) || stem(&z, "illa", "al", m_gt_0) ||
stem(&z, "iltne", "ent", m_gt_0) || stem(&z, "ile", "e", m_gt_0) ||
stem(&z, "ilsuo", "ous", m_gt_0));
break;
case 'o':
(void)(stem(&z, "noitazi", "ize", m_gt_0) ||
stem(&z, "noita", "ate", m_gt_0) ||
stem(&z, "rota", "ate", m_gt_0));
break;
case 's':
(void)(stem(&z, "msila", "al", m_gt_0) ||
stem(&z, "ssenevi", "ive", m_gt_0) ||
stem(&z, "ssenluf", "ful", m_gt_0) ||
stem(&z, "ssensuo", "ous", m_gt_0));
break;
case 't':
(void)(stem(&z, "itila", "al", m_gt_0) ||
stem(&z, "itivi", "ive", m_gt_0) ||
stem(&z, "itilib", "ble", m_gt_0));
break;
}
/* Step 3 */
switch (z[0]) {
case 'e':
(void)(stem(&z, "etaci", "ic", m_gt_0) || stem(&z, "evita", "", m_gt_0) ||
stem(&z, "ezila", "al", m_gt_0));
break;
case 'i':
(void)(stem(&z, "itici", "ic", m_gt_0));
break;
case 'l':
(void)(stem(&z, "laci", "ic", m_gt_0) || stem(&z, "luf", "", m_gt_0));
break;
case 's':
(void)(stem(&z, "ssen", "", m_gt_0));
break;
}
/* Step 4 */
switch (z[1]) {
case 'a':
if (z[0] == 'l' && m_gt_1(z + 2)) {
z += 2;
}
break;
case 'c':
if (z[0] == 'e' && z[2] == 'n' && (z[3] == 'a' || z[3] == 'e') &&
m_gt_1(z + 4)) {
z += 4;
}
break;
case 'e':
if (z[0] == 'r' && m_gt_1(z + 2)) {
z += 2;
}
break;
case 'i':
if (z[0] == 'c' && m_gt_1(z + 2)) {
z += 2;
}
break;
case 'l':
if (z[0] == 'e' && z[2] == 'b' && (z[3] == 'a' || z[3] == 'i') &&
m_gt_1(z + 4)) {
z += 4;
}
break;
case 'n':
if (z[0] == 't') {
if (z[2] == 'a') {
if (m_gt_1(z + 3)) {
z += 3;
}
} else if (z[2] == 'e') {
(void)(stem(&z, "tneme", "", m_gt_1) ||
stem(&z, "tnem", "", m_gt_1) || stem(&z, "tne", "", m_gt_1));
}
}
break;
case 'o':
if (z[0] == 'u') {
if (m_gt_1(z + 2)) {
z += 2;
}
} else if (z[3] == 's' || z[3] == 't') {
(void)(stem(&z, "noi", "", m_gt_1));
}
break;
case 's':
if (z[0] == 'm' && z[2] == 'i' && m_gt_1(z + 3)) {
z += 3;
}
break;
case 't':
(void)(stem(&z, "eta", "", m_gt_1) || stem(&z, "iti", "", m_gt_1));
break;
case 'u':
if (z[0] == 's' && z[2] == 'o' && m_gt_1(z + 3)) {
z += 3;
}
break;
case 'v':
case 'z':
if (z[0] == 'e' && z[2] == 'i' && m_gt_1(z + 3)) {
z += 3;
}
break;
}
/* Step 5a */
if (z[0] == 'e') {
if (m_gt_1(z + 1)) {
z++;
} else if (m_eq_1(z + 1) && !star_oh(z + 1)) {
z++;
}
}
/* Step 5b */
if (m_gt_1(z) && z[0] == 'l' && z[1] == 'l') {
z++;
}
/* z[] is now the stemmed word in reverse order. Flip it back
** around into forward order and return.
*/
*pnOut = i = strlen(z);
zOut[i] = 0;
while (*z) {
zOut[--i] = *(z++);
}
}
/**
* Indicate whether characters in the 0x30 - 0x7f region can be part of a token.
* Letters and numbers can; punctuation (and 'del') can't.
*/
static const char porterIdChar[] = {
/* x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF */
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, /* 3x */
0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 4x */
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, /* 5x */
0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 6x */
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, /* 7x */
};
/**
* Test whether a character is a (non-ascii) space character or not. isDelim
* uses the existing porter stemmer logic for anything in the ASCII (< 0x80)
* space which covers 0x20.
*
* 0x2000-0x206F is the general punctuation table. 0x2000 - 0x200b are spaces.
* The spaces 0x2000 - 0x200a are all defined as roughly equivalent to a
* standard 0x20 space. 0x200b is a "zero width space" (ZWSP) and not like an
* 0x20 space. 0x202f is a narrow no-break space and roughly equivalent to an
* 0x20 space. 0x205f is a "medium mathematical space" and defined as roughly
* equivalent to an 0x20 space.
*/
# define IS_UNI_SPACE(x) \
(((x) >= 0x2000 && (x) <= 0x200a) || (x) == 0x202f || (x) == 0x205f)
/**
* What we are checking for:
* - 0x3001: Ideographic comma (-> 0x2c ',')
* - 0x3002: Ideographic full stop (-> 0x2e '.')
* - 0xff0c: fullwidth comma (~ wide 0x2c ',')
* - 0xff0e: fullwidth full stop (~ wide 0x2e '.')
* - 0xff61: halfwidth ideographic full stop (~ narrow 0x3002)
* - 0xff64: halfwidth ideographic comma (~ narrow 0x3001)
*
* It is possible we should be treating other things as delimiters!
*/
# define IS_JA_DELIM(x) \
(((x) == 0x3001) || ((x) == 0xFF64) || ((x) == 0xFF0E) || \
((x) == 0x3002) || ((x) == 0xFF61) || ((x) == 0xFF0C))
/**
* The previous character was a delimiter (which includes the start of the
* string).
*/
# define BIGRAM_RESET 0
/**
* The previous character was a CJK character and we have only seen one of them.
* If we had seen more than one in a row it would be the BIGRAM_USE state.
*/
# define BIGRAM_UNKNOWN 1
/**
* We have seen two or more CJK characters in a row.
*/
# define BIGRAM_USE 2
/**
* The previous character was ASCII or something in the unicode general scripts
* area that we do not believe is a delimiter. We call it 'alpha' as in
* alphabetic/alphanumeric and something that should be tokenized based on
* delimiters rather than on a bi-gram basis.
*/
# define BIGRAM_ALPHA 3
static int isDelim(
const unsigned char* zCur, /* IN: current pointer of token */
const unsigned char* zTerm, /* IN: one character beyond end of token */
int* len, /* OUT: analyzed bytes in this token */
int* state /* IN/OUT: analyze state */
) {
const unsigned char* zIn = zCur;
unsigned int c;
int delim;
/* get the unicode character to analyze */
READ_UTF8(zIn, zTerm, c);
c = normalize_character(c);
*len = zIn - zCur;
/* ASCII character range has rule */
if (c < 0x80) {
// This is original porter stemmer isDelim logic.
// 0x0 - 0x1f are all control characters, 0x20 is space, 0x21-0x2f are
// punctuation.
delim = (c < 0x30 || !porterIdChar[c - 0x30]);
// cases: "&a", "&."
if (*state == BIGRAM_USE || *state == BIGRAM_UNKNOWN) {
/* previous maybe CJK and current is ascii */
*state = BIGRAM_ALPHA; /*ascii*/
delim = 1; /* must break */
} else if (delim == 1) {
// cases: "a.", ".."
/* this is delimiter character */
*state = BIGRAM_RESET; /*reset*/
} else {
// cases: "aa", ".a"
*state = BIGRAM_ALPHA; /*ascii*/
}
return delim;
}
// (at this point we must be a non-ASCII character)
/* voiced/semi-voiced sound mark is ignore */
if (isVoicedSoundMark(c) && *state != BIGRAM_ALPHA) {
/* ignore this because it is combined with previous char */
return 0;
}
/* this isn't CJK range, so return as no delim */
// Anything less than 0x2000 (except to U+0E00-U+0EFF and U+1780-U+17FF)
// is the general scripts area and should not be bi-gram indexed.
// 0xa000 - 0a4cf is the Yi area. It is apparently a phonetic language whose
// usage does not appear to have simple delimiter rules, so we're leaving it
// as bigram processed. This is a guess, if you know better, let us know.
// (We previously bailed on this range too.)
// Addition, U+0E00-U+0E7F is Thai, U+0E80-U+0EFF is Laos,
// and U+1780-U+17FF is Khmer. It is no easy way to break each word.
// So these should use bi-gram too.
// cases: "aa", ".a", "&a"
if (c < 0xe00 || (c >= 0xf00 && c < 0x1780) || (c >= 0x1800 && c < 0x2000)) {
*state = BIGRAM_ALPHA; /* not really ASCII but same idea; tokenize it */
return 0;
}
// (at this point we must be a bi-grammable char or delimiter)
/* this is space character or delim character */
// cases: "a.", "..", "&."
if (IS_UNI_SPACE(c) || IS_JA_DELIM(c)) {
*state = BIGRAM_RESET; /* reset */
return 1; /* it actually is a delimiter; report as such */
}
// (at this point we must be a bi-grammable char)
// cases: "a&"
if (*state == BIGRAM_ALPHA) {
/* Previous is ascii and current maybe CJK */
*state = BIGRAM_UNKNOWN; /* mark as unknown */
return 1; /* break to emit the ASCII token*/
}
/* We have no rule for CJK!. use bi-gram */
// cases: "&&"
if (*state == BIGRAM_UNKNOWN || *state == BIGRAM_USE) {
/* previous state is unknown. mark as bi-gram */
*state = BIGRAM_USE;
return 1; /* break to emit the digram */
}
// cases: ".&" (*state == BIGRAM_RESET)
*state = BIGRAM_UNKNOWN; /* mark as unknown */
return 0; /* no need to break; nothing to emit */
}
/**
* Generate a new token. There are basically three types of token we can
* generate:
* - A porter stemmed token. This is a word entirely comprised of ASCII
* characters. We run the porter stemmer algorithm against the word.
* Because we have no way to know what is and is not an English word
* (the only language for which the porter stemmer was designed), this
* could theoretically map multiple words that are not variations of the
* same word down to the same root, resulting in potentially unexpected
* result inclusions in the search results. We accept this result because
* there's not a lot we can do about it and false positives are much
* better than false negatives.
* - A copied token; case/accent-folded but not stemmed. We call the porter
* stemmer for all non-CJK cases and it diverts to the copy stemmer if it
* sees any non-ASCII characters (after folding) or if the string is too
* long. The copy stemmer will shrink the string if it is deemed too long.
* - A bi-gram token; two CJK-ish characters. For query reasons we generate a
* series of overlapping bi-grams. (We can't require the user to start their
* search based on the arbitrary context of the indexed documents.)
*
* It may be useful to think of this function as operating at the points between
* characters. While we are considering the 'current' character (the one after
* the 'point'), we are also interested in the 'previous' character (the one
* preceding the point).
* At any 'point', there are a number of possible situations which I will
* illustrate with pairs of characters. 'a' means alphanumeric ASCII or a
* non-ASCII character that is not bi-grammable or a delimiter, '.'
* means a delimiter (space or punctuation), '&' means a bi-grammable
* character.
* - aa: We are in the midst of a token. State remains BIGRAM_ALPHA.
* - a.: We will generate a porter stemmed or copied token. State was
* BIGRAM_ALPHA, gets set to BIGRAM_RESET.
* - a&: We will generate a porter stemmed or copied token; we will set our
* state to BIGRAM_UNKNOWN to indicate we have seen one bigram character
* but that it is not yet time to emit a bigram.
* - .a: We are starting a token. State was BIGRAM_RESET, gets set to
* BIGRAM_ALPHA.
* - ..: We skip/eat the delimiters. State stays BIGRAM_RESET.
* - .&: State set to BIGRAM_UNKNOWN to indicate we have seen one bigram char.
* - &a: If the state was BIGRAM_USE, we generate a bi-gram token. If the state
* was BIGRAM_UNKNOWN we had only seen one CJK character and so don't do
* anything. State is set to BIGRAM_ALPHA.
* - &.: Same as the "&a" case, but state is set to BIGRAM_RESET.
* - &&: We will generate a bi-gram token. State was either BIGRAM_UNKNOWN or
* BIGRAM_USE, gets set to BIGRAM_USE.
*/
static int porterNext(
sqlite3_tokenizer_cursor* pCursor, /* Cursor returned by porterOpen */
const char** pzToken, /* OUT: *pzToken is the token text */
int* pnBytes, /* OUT: Number of bytes in token */
int* piStartOffset, /* OUT: Starting offset of token */
int* piEndOffset, /* OUT: Ending offset of token */
int* piPosition /* OUT: Position integer of token */
) {
porter_tokenizer_cursor* c = (porter_tokenizer_cursor*)pCursor;
const unsigned char* z = (unsigned char*)c->zInput;
int len = 0;
int state;
while (c->iOffset < c->nInput) {
int iStartOffset, numChars;
/*
* This loop basically has two modes of operation:
* - general processing (iPrevBigramOffset == 0 here)
* - CJK processing (iPrevBigramOffset != 0 here)
*
* In an general processing pass we skip over all the delimiters, leaving us
* at a character that promises to produce a token. This could be a CJK
* token (state == BIGRAM_USE) or an ALPHA token (state == BIGRAM_ALPHA).
* If it was a CJK token, we transition into CJK state for the next loop.
* If it was an alpha token, our current offset is pointing at a delimiter
* (which could be a CJK character), so it is good that our next pass
* through the function and loop will skip over any delimiters. If the
* delimiter we hit was a CJK character, the next time through we will
* not treat it as a delimiter though; the entry state for that scan is
* BIGRAM_RESET so the transition is not treated as a delimiter!
*
* The CJK pass always starts with the second character in a bi-gram emitted
* as a token in the previous step. No delimiter skipping is required
* because we know that first character might produce a token for us. It
* only 'might' produce a token because the previous pass performed no
* lookahead and cannot be sure it is followed by another CJK character.
* This is why
*/
// If we have a previous bigram offset
if (c->iPrevBigramOffset == 0) {
/* Scan past delimiter characters */
state = BIGRAM_RESET; /* reset */
while (c->iOffset < c->nInput &&
isDelim(z + c->iOffset, z + c->nInput, &len, &state)) {
c->iOffset += len;
}
} else {
/* for bigram indexing, use previous offset */
c->iOffset = c->iPrevBigramOffset;
}
/* Count non-delimiter characters. */
iStartOffset = c->iOffset;
numChars = 0;
// Start from a reset state. This means the first character we see
// (which will not be a delimiter) determines which of ALPHA or CJK modes
// we are operating in. (It won't be a delimiter because in a 'general'
// pass as defined above, we will have eaten all the delimiters, and in
// a CJK pass we are guaranteed that the first character is CJK.)
state = BIGRAM_RESET; /* state is reset */
// Advance until it is time to emit a token.
// For ALPHA characters, this means advancing until we encounter a delimiter
// or a CJK character. iOffset will be pointing at the delimiter or CJK
// character, aka one beyond the last ALPHA character.
// For CJK characters this means advancing until we encounter an ALPHA
// character, a delimiter, or we have seen two consecutive CJK
// characters. iOffset points at the ALPHA/delimiter in the first 2 cases
// and the second of two CJK characters in the last case.
// Because of the way this loop is structured, iOffset is only updated
// when we don't terminate. However, if we terminate, len still contains
// the number of bytes in the character found at iOffset. (This is useful
// in the CJK case.)
while (c->iOffset < c->nInput &&
!isDelim(z + c->iOffset, z + c->nInput, &len, &state)) {
c->iOffset += len;
numChars++;
}
if (state == BIGRAM_USE) {
/* Split word by bigram */
// Right now iOffset is pointing at the second character in a pair.
// Save this offset so next-time through we start with that as the
// first character.
c->iPrevBigramOffset = c->iOffset;
// And now advance so that iOffset is pointing at the character after
// the second character in the bi-gram pair. Also count the char.
c->iOffset += len;
numChars++;
} else {
/* Reset bigram offset */
c->iPrevBigramOffset = 0;
}
/* We emit a token if:
* - there are two ideograms together,
* - there are three chars or more,
* - we think this is a query and wildcard magic is desired.
* We think is a wildcard query when we have a single character, it starts
* at the start of the buffer, it's CJK, our current offset is one shy of
* nInput and the character at iOffset is '*'. Because the state gets
* clobbered by the incidence of '*' our requirement for CJK is that the
* implied character length is at least 3 given that it takes at least 3
* bytes to encode to 0x2000.
*/
// It is possible we have no token to emit here if iPrevBigramOffset was not
// 0 on entry and there was no second CJK character. iPrevBigramOffset
// will now be 0 if that is the case (and c->iOffset == iStartOffset).
if ( // allow two-character words only if in bigram
(numChars == 2 && state == BIGRAM_USE) ||
// otherwise, drop two-letter words (considered stop-words)
(numChars >= 3) ||
// wildcard case:
(numChars == 1 && iStartOffset == 0 && (c->iOffset >= 3) &&
(c->iOffset == c->nInput - 1) && (z[c->iOffset] == '*'))) {
/* figure out the number of bytes to copy/stem */
int n = c->iOffset - iStartOffset;
/* make sure there is enough buffer space */
if (n * MAX_UTF8_GROWTH_FACTOR > c->nAllocated) {
c->nAllocated = n * MAX_UTF8_GROWTH_FACTOR + 20;
c->zToken = sqlite3_realloc(c->zToken, c->nAllocated);
if (c->zToken == NULL) return SQLITE_NOMEM;
}
if (state == BIGRAM_USE) {
/* This is by bigram. So it is unnecessary to convert word */
copy_stemmer(&z[iStartOffset], n, c->zToken, pnBytes);
} else {
porter_stemmer(&z[iStartOffset], n, c->zToken, pnBytes);
}
*pzToken = (const char*)c->zToken;
*piStartOffset = iStartOffset;
*piEndOffset = c->iOffset;
*piPosition = c->iToken++;
return SQLITE_OK;
}
}
return SQLITE_DONE;
}
/*
** The set of routines that implement the porter-stemmer tokenizer
*/
static const sqlite3_tokenizer_module porterTokenizerModule = {
0, porterCreate, porterDestroy, porterOpen, porterClose, porterNext,
};
/*
** Allocate a new porter tokenizer. Return a pointer to the new
** tokenizer in *ppModule
*/
void sqlite3Fts3PorterTokenizerModule(
sqlite3_tokenizer_module const** ppModule) {
*ppModule = &porterTokenizerModule;
}
#endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3) */