Age Owner Branch data TLA Line data Source code
1 : : /*
2 : : * contrib/pg_trgm/trgm_op.c
3 : : */
4 : : #include "postgres.h"
5 : :
6 : : #include <ctype.h>
7 : :
8 : : #include "catalog/pg_collation_d.h"
9 : : #include "catalog/pg_type.h"
10 : : #include "common/int.h"
11 : : #include "lib/qunique.h"
12 : : #include "miscadmin.h"
13 : : #include "trgm.h"
14 : : #include "tsearch/ts_locale.h"
15 : : #include "utils/formatting.h"
16 : : #include "utils/guc.h"
17 : : #include "utils/lsyscache.h"
18 : : #include "utils/memutils.h"
19 : : #include "utils/pg_crc.h"
20 : :
164 tgl@sss.pgh.pa.us 21 :CBC 3 : PG_MODULE_MAGIC_EXT(
22 : : .name = "pg_trgm",
23 : : .version = PG_VERSION
24 : : );
25 : :
26 : : /* GUC variables */
27 : : double similarity_threshold = 0.3f;
28 : : double word_similarity_threshold = 0.6f;
29 : : double strict_word_similarity_threshold = 0.5f;
30 : :
7768 teodor@sigaev.ru 31 : 2 : PG_FUNCTION_INFO_V1(set_limit);
5332 tgl@sss.pgh.pa.us 32 : 2 : PG_FUNCTION_INFO_V1(show_limit);
33 : 2 : PG_FUNCTION_INFO_V1(show_trgm);
34 : 2 : PG_FUNCTION_INFO_V1(similarity);
3461 teodor@sigaev.ru 35 : 2 : PG_FUNCTION_INFO_V1(word_similarity);
2726 36 : 2 : PG_FUNCTION_INFO_V1(strict_word_similarity);
5332 tgl@sss.pgh.pa.us 37 : 2 : PG_FUNCTION_INFO_V1(similarity_dist);
38 : 2 : PG_FUNCTION_INFO_V1(similarity_op);
3461 teodor@sigaev.ru 39 : 2 : PG_FUNCTION_INFO_V1(word_similarity_op);
40 : 3 : PG_FUNCTION_INFO_V1(word_similarity_commutator_op);
41 : 1 : PG_FUNCTION_INFO_V1(word_similarity_dist_op);
42 : 2 : PG_FUNCTION_INFO_V1(word_similarity_dist_commutator_op);
2726 43 : 2 : PG_FUNCTION_INFO_V1(strict_word_similarity_op);
44 : 2 : PG_FUNCTION_INFO_V1(strict_word_similarity_commutator_op);
45 : 1 : PG_FUNCTION_INFO_V1(strict_word_similarity_dist_op);
46 : 2 : PG_FUNCTION_INFO_V1(strict_word_similarity_dist_commutator_op);
47 : :
48 : : static int CMPTRGM_CHOOSE(const void *a, const void *b);
49 : : int (*CMPTRGM) (const void *a, const void *b) = CMPTRGM_CHOOSE;
50 : :
51 : : /* Trigram with position */
52 : : typedef struct
53 : : {
54 : : trgm trg;
55 : : int index;
56 : : } pos_trgm;
57 : :
58 : : /* Trigram bound type */
59 : : typedef uint8 TrgmBound;
60 : : #define TRGM_BOUND_LEFT 0x01 /* trigram is left bound of word */
61 : : #define TRGM_BOUND_RIGHT 0x02 /* trigram is right bound of word */
62 : :
63 : : /* Word similarity flags */
64 : : #define WORD_SIMILARITY_CHECK_ONLY 0x01 /* only check existence of similar
65 : : * search pattern in text */
66 : : #define WORD_SIMILARITY_STRICT 0x02 /* force bounds of extent to match
67 : : * word bounds */
68 : :
69 : : /*
70 : : * Module load callback
71 : : */
72 : : void
3461 73 : 3 : _PG_init(void)
74 : : {
75 : : /* Define custom GUC variables. */
76 : 3 : DefineCustomRealVariable("pg_trgm.similarity_threshold",
77 : : "Sets the threshold used by the % operator.",
78 : : "Valid range is 0.0 .. 1.0.",
79 : : &similarity_threshold,
80 : : 0.3f,
81 : : 0.0,
82 : : 1.0,
83 : : PGC_USERSET,
84 : : 0,
85 : : NULL,
86 : : NULL,
87 : : NULL);
88 : 3 : DefineCustomRealVariable("pg_trgm.word_similarity_threshold",
89 : : "Sets the threshold used by the <% operator.",
90 : : "Valid range is 0.0 .. 1.0.",
91 : : &word_similarity_threshold,
92 : : 0.6f,
93 : : 0.0,
94 : : 1.0,
95 : : PGC_USERSET,
96 : : 0,
97 : : NULL,
98 : : NULL,
99 : : NULL);
2726 100 : 3 : DefineCustomRealVariable("pg_trgm.strict_word_similarity_threshold",
101 : : "Sets the threshold used by the <<% operator.",
102 : : "Valid range is 0.0 .. 1.0.",
103 : : &strict_word_similarity_threshold,
104 : : 0.5f,
105 : : 0.0,
106 : : 1.0,
107 : : PGC_USERSET,
108 : : 0,
109 : : NULL,
110 : : NULL,
111 : : NULL);
112 : :
1293 tgl@sss.pgh.pa.us 113 : 3 : MarkGUCPrefixReserved("pg_trgm");
3461 teodor@sigaev.ru 114 : 3 : }
115 : :
116 : : #define CMPCHAR(a,b) ( ((a)==(b)) ? 0 : ( ((a)<(b)) ? -1 : 1 ) )
117 : :
118 : : /*
119 : : * Functions for comparing two trgms while treating each char as "signed char" or
120 : : * "unsigned char".
121 : : */
122 : : static inline int
197 msawada@postgresql.o 123 : 7496628 : CMPTRGM_SIGNED(const void *a, const void *b)
124 : : {
125 : : #define CMPPCHAR_S(a,b,i) CMPCHAR( *(((const signed char*)(a))+i), *(((const signed char*)(b))+i) )
126 : :
127 [ + + ]: 5409941 : return CMPPCHAR_S(a, b, 0) ? CMPPCHAR_S(a, b, 0)
128 [ + + + + ]: 16332890 : : (CMPPCHAR_S(a, b, 1) ? CMPPCHAR_S(a, b, 1)
129 [ + + + + : 3426321 : : CMPPCHAR_S(a, b, 2));
+ + ]
130 : : }
131 : :
132 : : static inline int
197 msawada@postgresql.o 133 :UBC 0 : CMPTRGM_UNSIGNED(const void *a, const void *b)
134 : : {
135 : : #define CMPPCHAR_UNS(a,b,i) CMPCHAR( *(((const unsigned char*)(a))+i), *(((const unsigned char*)(b))+i) )
136 : :
137 [ # # ]: 0 : return CMPPCHAR_UNS(a, b, 0) ? CMPPCHAR_UNS(a, b, 0)
138 [ # # # # ]: 0 : : (CMPPCHAR_UNS(a, b, 1) ? CMPPCHAR_UNS(a, b, 1)
139 [ # # # # : 0 : : CMPPCHAR_UNS(a, b, 2));
# # ]
140 : : }
141 : :
142 : : /*
143 : : * This gets called on the first call. It replaces the function pointer so
144 : : * that subsequent calls are routed directly to the chosen implementation.
145 : : */
146 : : static int
197 msawada@postgresql.o 147 :CBC 3 : CMPTRGM_CHOOSE(const void *a, const void *b)
148 : : {
149 [ + - ]: 3 : if (GetDefaultCharSignedness())
150 : 3 : CMPTRGM = CMPTRGM_SIGNED;
151 : : else
197 msawada@postgresql.o 152 :UBC 0 : CMPTRGM = CMPTRGM_UNSIGNED;
153 : :
197 msawada@postgresql.o 154 :CBC 3 : return CMPTRGM(a, b);
155 : : }
156 : :
157 : : /*
158 : : * Deprecated function.
159 : : * Use "pg_trgm.similarity_threshold" GUC variable instead of this function.
160 : : */
161 : : Datum
7678 bruce@momjian.us 162 : 2 : set_limit(PG_FUNCTION_ARGS)
163 : : {
164 : 2 : float4 nlimit = PG_GETARG_FLOAT4(0);
165 : : char *nlimit_str;
166 : : Oid func_out_oid;
167 : : bool is_varlena;
168 : :
3459 teodor@sigaev.ru 169 : 2 : getTypeOutputInfo(FLOAT4OID, &func_out_oid, &is_varlena);
170 : :
171 : 2 : nlimit_str = OidOutputFunctionCall(func_out_oid, Float4GetDatum(nlimit));
172 : :
173 : 2 : SetConfigOption("pg_trgm.similarity_threshold", nlimit_str,
174 : : PGC_USERSET, PGC_S_SESSION);
175 : :
3461 176 : 2 : PG_RETURN_FLOAT4(similarity_threshold);
177 : : }
178 : :
179 : :
180 : : /*
181 : : * Get similarity threshold for given index scan strategy number.
182 : : */
183 : : double
2726 184 : 44245 : index_strategy_get_limit(StrategyNumber strategy)
185 : : {
186 [ + + + - ]: 44245 : switch (strategy)
187 : : {
188 : 31435 : case SimilarityStrategyNumber:
189 : 31435 : return similarity_threshold;
190 : 6828 : case WordSimilarityStrategyNumber:
191 : 6828 : return word_similarity_threshold;
192 : 5982 : case StrictWordSimilarityStrategyNumber:
193 : 5982 : return strict_word_similarity_threshold;
2726 teodor@sigaev.ru 194 :UBC 0 : default:
195 [ # # ]: 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
196 : : break;
197 : : }
198 : :
199 : : return 0.0; /* keep compiler quiet */
200 : : }
201 : :
202 : : /*
203 : : * Deprecated function.
204 : : * Use "pg_trgm.similarity_threshold" GUC variable instead of this function.
205 : : */
206 : : Datum
7678 bruce@momjian.us 207 :CBC 20000 : show_limit(PG_FUNCTION_ARGS)
208 : : {
3461 teodor@sigaev.ru 209 : 20000 : PG_RETURN_FLOAT4(similarity_threshold);
210 : : }
211 : :
212 : : static int
7678 bruce@momjian.us 213 : 3187436 : comp_trgm(const void *a, const void *b)
214 : : {
215 : 3187436 : return CMPTRGM(a, b);
216 : : }
217 : :
218 : : /*
219 : : * Finds first word in string, returns pointer to the word,
220 : : * endword points to the character after word
221 : : */
222 : : static char *
5931 223 : 243429 : find_word(char *str, int lenstr, char **endword, int *charlen)
224 : : {
225 : 243429 : char *beginword = str;
226 : :
4533 tgl@sss.pgh.pa.us 227 [ + + + + ]: 257107 : while (beginword - str < lenstr && !ISWORDCHR(beginword))
6142 teodor@sigaev.ru 228 : 13678 : beginword += pg_mblen(beginword);
229 : :
230 [ + + ]: 243429 : if (beginword - str >= lenstr)
231 : 115090 : return NULL;
232 : :
233 : 128339 : *endword = beginword;
234 : 128339 : *charlen = 0;
4533 tgl@sss.pgh.pa.us 235 [ + + + + ]: 1111739 : while (*endword - str < lenstr && ISWORDCHR(*endword))
236 : : {
6142 teodor@sigaev.ru 237 : 983400 : *endword += pg_mblen(*endword);
238 : 983400 : (*charlen)++;
239 : : }
240 : :
241 : 128339 : return beginword;
242 : : }
243 : :
244 : : /*
245 : : * Reduce a trigram (three possibly multi-byte characters) to a trgm,
246 : : * which is always exactly three bytes. If we have three single-byte
247 : : * characters, we just use them as-is; otherwise we form a hash value.
248 : : */
249 : : void
4535 tgl@sss.pgh.pa.us 250 : 1459 : compact_trigram(trgm *tptr, char *str, int bytelen)
251 : : {
5931 bruce@momjian.us 252 [ + - ]: 1459 : if (bytelen == 3)
253 : : {
254 : 1459 : CPTRGM(tptr, str);
255 : : }
256 : : else
257 : : {
258 : : pg_crc32 crc;
259 : :
3959 heikki.linnakangas@i 260 :UBC 0 : INIT_LEGACY_CRC32(crc);
261 [ # # ]: 0 : COMP_LEGACY_CRC32(crc, str, bytelen);
262 : 0 : FIN_LEGACY_CRC32(crc);
263 : :
264 : : /*
265 : : * use only 3 upper bytes from crc, hope, it's good enough hashing
266 : : */
6142 teodor@sigaev.ru 267 : 0 : CPTRGM(tptr, &crc);
268 : : }
6142 teodor@sigaev.ru 269 :CBC 1459 : }
270 : :
271 : : /*
272 : : * Adds trigrams from words (already padded).
273 : : */
274 : : static trgm *
5931 bruce@momjian.us 275 : 128403 : make_trigrams(trgm *tptr, char *str, int bytelen, int charlen)
276 : : {
277 : 128403 : char *ptr = str;
278 : :
279 [ + + ]: 128403 : if (charlen < 3)
6142 teodor@sigaev.ru 280 : 27 : return tptr;
281 : :
4535 tgl@sss.pgh.pa.us 282 [ - + ]: 128376 : if (bytelen > charlen)
283 : : {
284 : : /* Find multibyte character boundaries and apply compact_trigram */
5931 bruce@momjian.us 285 :UBC 0 : int lenfirst = pg_mblen(str),
286 : 0 : lenmiddle = pg_mblen(str + lenfirst),
287 : 0 : lenlast = pg_mblen(str + lenfirst + lenmiddle);
288 : :
289 [ # # ]: 0 : while ((ptr - str) + lenfirst + lenmiddle + lenlast <= bytelen)
290 : : {
4535 tgl@sss.pgh.pa.us 291 : 0 : compact_trigram(tptr, ptr, lenfirst + lenmiddle + lenlast);
292 : :
6142 teodor@sigaev.ru 293 : 0 : ptr += lenfirst;
294 : 0 : tptr++;
295 : :
5931 bruce@momjian.us 296 : 0 : lenfirst = lenmiddle;
297 : 0 : lenmiddle = lenlast;
298 : 0 : lenlast = pg_mblen(ptr + lenfirst + lenmiddle);
299 : : }
300 : : }
301 : : else
302 : : {
303 : : /* Fast path when there are no multibyte characters */
5931 bruce@momjian.us 304 [ - + ]:CBC 128376 : Assert(bytelen == charlen);
305 : :
6142 teodor@sigaev.ru 306 [ + + ]: 1240206 : while (ptr - str < bytelen - 2 /* number of trigrams = strlen - 2 */ )
307 : : {
308 : 1111830 : CPTRGM(tptr, ptr);
309 : 1111830 : ptr++;
310 : 1111830 : tptr++;
311 : : }
312 : : }
313 : :
314 : 128376 : return tptr;
315 : : }
316 : :
317 : : /*
318 : : * Make array of trigrams without sorting and removing duplicate items.
319 : : *
320 : : * trg: where to return the array of trigrams.
321 : : * str: source string, of length slen bytes.
322 : : * bounds: where to return bounds of trigrams (if needed).
323 : : *
324 : : * Returns length of the generated array.
325 : : */
326 : : static int
2726 327 : 116101 : generate_trgm_only(trgm *trg, char *str, int slen, TrgmBound *bounds)
328 : : {
329 : : trgm *tptr;
330 : : char *buf;
331 : : int charlen,
332 : : bytelen;
333 : : char *bword,
334 : : *eword;
335 : :
7678 bruce@momjian.us 336 [ + - + + ]: 116101 : if (slen + LPADDING + RPADDING < 3 || slen == 0)
3461 teodor@sigaev.ru 337 : 1011 : return 0;
338 : :
339 : 115090 : tptr = trg;
340 : :
341 : : /* Allocate a buffer for case-folded, blank-padded words */
4254 tgl@sss.pgh.pa.us 342 : 115090 : buf = (char *) palloc(slen * pg_database_encoding_max_length() + 4);
343 : :
344 : : if (LPADDING > 0)
345 : : {
7768 teodor@sigaev.ru 346 : 115090 : *buf = ' ';
347 : : if (LPADDING > 1)
7678 bruce@momjian.us 348 : 115090 : *(buf + 1) = ' ';
349 : : }
350 : :
6142 teodor@sigaev.ru 351 : 115090 : eword = str;
5931 bruce@momjian.us 352 [ + + ]: 243429 : while ((bword = find_word(eword, slen - (eword - str), &eword, &charlen)) != NULL)
353 : : {
354 : : #ifdef IGNORECASE
263 peter@eisentraut.org 355 : 128339 : bword = str_tolower(bword, eword - bword, DEFAULT_COLLATION_OID);
6142 teodor@sigaev.ru 356 : 128339 : bytelen = strlen(bword);
357 : : #else
358 : : bytelen = eword - bword;
359 : : #endif
360 : :
361 : 128339 : memcpy(buf + LPADDING, bword, bytelen);
362 : :
363 : : #ifdef IGNORECASE
364 : 128339 : pfree(bword);
365 : : #endif
366 : :
5931 bruce@momjian.us 367 : 128339 : buf[LPADDING + bytelen] = ' ';
368 : 128339 : buf[LPADDING + bytelen + 1] = ' ';
369 : :
370 : : /* Calculate trigrams marking their bounds if needed */
2726 teodor@sigaev.ru 371 [ + + ]: 128339 : if (bounds)
372 : 12397 : bounds[tptr - trg] |= TRGM_BOUND_LEFT;
5931 bruce@momjian.us 373 : 128339 : tptr = make_trigrams(tptr, buf, bytelen + LPADDING + RPADDING,
374 : : charlen + LPADDING + RPADDING);
2726 teodor@sigaev.ru 375 [ + + ]: 128339 : if (bounds)
376 : 12397 : bounds[tptr - trg - 1] |= TRGM_BOUND_RIGHT;
377 : : }
378 : :
7768 379 : 115090 : pfree(buf);
380 : :
3461 381 : 115090 : return tptr - trg;
382 : : }
383 : :
384 : : /*
385 : : * Guard against possible overflow in the palloc requests below. (We
386 : : * don't worry about the additive constants, since palloc can detect
387 : : * requests that are a little above MaxAllocSize --- we just need to
388 : : * prevent integer overflow in the multiplications.)
389 : : */
390 : : static void
391 : 103028 : protect_out_of_mem(int slen)
392 : : {
393 [ + - ]: 103028 : if ((Size) (slen / 2) >= (MaxAllocSize / (sizeof(trgm) * 3)) ||
394 [ - + ]: 103028 : (Size) slen >= (MaxAllocSize / pg_database_encoding_max_length()))
3461 teodor@sigaev.ru 395 [ # # ]:UBC 0 : ereport(ERROR,
396 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
397 : : errmsg("out of memory")));
3461 teodor@sigaev.ru 398 :CBC 103028 : }
399 : :
400 : : /*
401 : : * Make array of trigrams with sorting and removing duplicate items.
402 : : *
403 : : * str: source string, of length slen bytes.
404 : : *
405 : : * Returns the sorted array of unique trigrams.
406 : : */
407 : : TRGM *
408 : 89845 : generate_trgm(char *str, int slen)
409 : : {
410 : : TRGM *trg;
411 : : int len;
412 : :
413 : 89845 : protect_out_of_mem(slen);
414 : :
2999 tgl@sss.pgh.pa.us 415 : 89845 : trg = (TRGM *) palloc(TRGMHDRSIZE + sizeof(trgm) * (slen / 2 + 1) * 3);
3461 teodor@sigaev.ru 416 : 89845 : trg->flag = ARRKEY;
417 : :
2726 418 : 89845 : len = generate_trgm_only(GETARR(trg), str, slen, NULL);
3461 419 : 89845 : SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, len));
420 : :
421 [ + + ]: 89845 : if (len == 0)
7768 422 : 12 : return trg;
423 : :
424 : : /*
425 : : * Make trigrams unique.
426 : : */
4254 tgl@sss.pgh.pa.us 427 [ + - ]: 89833 : if (len > 1)
428 : : {
942 peter@eisentraut.org 429 : 89833 : qsort(GETARR(trg), len, sizeof(trgm), comp_trgm);
2130 tmunro@postgresql.or 430 : 89833 : len = qunique(GETARR(trg), len, sizeof(trgm), comp_trgm);
431 : : }
432 : :
6765 tgl@sss.pgh.pa.us 433 : 89833 : SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, len));
434 : :
7768 teodor@sigaev.ru 435 : 89833 : return trg;
436 : : }
437 : :
438 : : /*
439 : : * Make array of positional trigrams from two trigram arrays trg1 and trg2.
440 : : *
441 : : * trg1: trigram array of search pattern, of length len1. trg1 is required
442 : : * word which positions don't matter and replaced with -1.
443 : : * trg2: trigram array of text, of length len2. trg2 is haystack where we
444 : : * search and have to store its positions.
445 : : *
446 : : * Returns concatenated trigram array.
447 : : */
448 : : static pos_trgm *
3461 449 : 13128 : make_positional_trgm(trgm *trg1, int len1, trgm *trg2, int len2)
450 : : {
451 : : pos_trgm *result;
452 : : int i,
3376 rhaas@postgresql.org 453 : 13128 : len = len1 + len2;
454 : :
3461 teodor@sigaev.ru 455 : 13128 : result = (pos_trgm *) palloc(sizeof(pos_trgm) * len);
456 : :
457 [ + + ]: 121866 : for (i = 0; i < len1; i++)
458 : : {
459 : 108738 : memcpy(&result[i].trg, &trg1[i], sizeof(trgm));
460 : 108738 : result[i].index = -1;
461 : : }
462 : :
463 [ + + ]: 205223 : for (i = 0; i < len2; i++)
464 : : {
465 : 192095 : memcpy(&result[i + len1].trg, &trg2[i], sizeof(trgm));
466 : 192095 : result[i + len1].index = i;
467 : : }
468 : :
469 : 13128 : return result;
470 : : }
471 : :
472 : : /*
473 : : * Compare position trigrams: compare trigrams first and position second.
474 : : */
475 : : static int
476 : 1351319 : comp_ptrgm(const void *v1, const void *v2)
477 : : {
3376 rhaas@postgresql.org 478 : 1351319 : const pos_trgm *p1 = (const pos_trgm *) v1;
479 : 1351319 : const pos_trgm *p2 = (const pos_trgm *) v2;
480 : : int cmp;
481 : :
3461 teodor@sigaev.ru 482 : 1351319 : cmp = CMPTRGM(p1->trg, p2->trg);
483 [ + + ]: 1351319 : if (cmp != 0)
484 : 1311616 : return cmp;
485 : :
568 nathan@postgresql.or 486 : 39703 : return pg_cmp_s32(p1->index, p2->index);
487 : : }
488 : :
489 : : /*
490 : : * Iterative search function which calculates maximum similarity with word in
491 : : * the string. Maximum similarity is only calculated only if the flag
492 : : * WORD_SIMILARITY_CHECK_ONLY isn't set.
493 : : *
494 : : * trg2indexes: array which stores indexes of the array "found".
495 : : * found: array which stores true of false values.
496 : : * ulen1: count of unique trigrams of array "trg1".
497 : : * len2: length of array "trg2" and array "trg2indexes".
498 : : * len: length of the array "found".
499 : : * flags: set of boolean flags parameterizing similarity calculation.
500 : : * bounds: whether each trigram is left/right bound of word.
501 : : *
502 : : * Returns word similarity.
503 : : */
504 : : static float4
3461 teodor@sigaev.ru 505 : 13128 : iterate_word_similarity(int *trg2indexes,
506 : : bool *found,
507 : : int ulen1,
508 : : int len2,
509 : : int len,
510 : : uint8 flags,
511 : : TrgmBound *bounds)
512 : : {
513 : : int *lastpos,
514 : : i,
515 : 13128 : ulen2 = 0,
516 : 13128 : count = 0,
517 : 13128 : upper = -1,
518 : : lower;
519 : : float4 smlr_cur,
520 : 13128 : smlr_max = 0.0f;
521 : : double threshold;
522 : :
2726 523 [ + + - + ]: 13128 : Assert(bounds || !(flags & WORD_SIMILARITY_STRICT));
524 : :
525 : : /* Select appropriate threshold */
526 : 26256 : threshold = (flags & WORD_SIMILARITY_STRICT) ?
2690 tgl@sss.pgh.pa.us 527 [ + + ]: 13128 : strict_word_similarity_threshold :
528 : : word_similarity_threshold;
529 : :
530 : : /*
531 : : * Consider first trigram as initial lower bound for strict word
532 : : * similarity, or initialize it later with first trigram present for plain
533 : : * word similarity.
534 : : */
2726 teodor@sigaev.ru 535 [ + + ]: 13128 : lower = (flags & WORD_SIMILARITY_STRICT) ? 0 : -1;
536 : :
537 : : /* Memorise last position of each trigram */
3461 538 : 13128 : lastpos = (int *) palloc(sizeof(int) * len);
539 : 13128 : memset(lastpos, -1, sizeof(int) * len);
540 : :
541 [ + + ]: 196653 : for (i = 0; i < len2; i++)
542 : : {
543 : : int trgindex;
544 : :
1097 dgustafsson@postgres 545 [ - + ]: 185309 : CHECK_FOR_INTERRUPTS();
546 : :
547 : : /* Get index of next trigram */
548 : 185309 : trgindex = trg2indexes[i];
549 : :
550 : : /* Update last position of this trigram */
3461 teodor@sigaev.ru 551 [ + + + + ]: 185309 : if (lower >= 0 || found[trgindex])
552 : : {
553 [ + + ]: 135781 : if (lastpos[trgindex] < 0)
554 : : {
555 : 133929 : ulen2++;
556 [ + + ]: 133929 : if (found[trgindex])
557 : 30756 : count++;
558 : : }
559 : 135781 : lastpos[trgindex] = i;
560 : : }
561 : :
562 : : /*
563 : : * Adjust upper bound if trigram is upper bound of word for strict
564 : : * word similarity, or if trigram is present in required substring for
565 : : * plain word similarity
566 : : */
2726 567 [ + + + + ]: 274365 : if ((flags & WORD_SIMILARITY_STRICT) ? (bounds[i] & TRGM_BOUND_RIGHT)
2690 tgl@sss.pgh.pa.us 568 : 89056 : : found[trgindex])
569 : : {
570 : : int prev_lower,
571 : : tmp_ulen2,
572 : : tmp_lower,
573 : : tmp_count;
574 : :
3461 teodor@sigaev.ru 575 : 25634 : upper = i;
576 [ + + ]: 25634 : if (lower == -1)
577 : : {
578 : 4695 : lower = i;
579 : 4695 : ulen2 = 1;
580 : : }
581 : :
582 : 25634 : smlr_cur = CALCSML(count, ulen1, ulen2);
583 : :
584 : : /* Also try to adjust lower bound for greater similarity */
585 : 25634 : tmp_count = count;
586 : 25634 : tmp_ulen2 = ulen2;
587 : 25634 : prev_lower = lower;
588 [ + + ]: 208558 : for (tmp_lower = lower; tmp_lower <= upper; tmp_lower++)
589 : : {
590 : : float smlr_tmp;
591 : : int tmp_trgindex;
592 : :
593 : : /*
594 : : * Adjust lower bound only if trigram is lower bound of word
595 : : * for strict word similarity, or consider every trigram as
596 : : * lower bound for plain word similarity.
597 : : */
2726 598 [ + + ]: 184708 : if (!(flags & WORD_SIMILARITY_STRICT)
599 [ + + ]: 145160 : || (bounds[tmp_lower] & TRGM_BOUND_LEFT))
600 : : {
601 : 59678 : smlr_tmp = CALCSML(tmp_count, ulen1, tmp_ulen2);
602 [ + + ]: 59678 : if (smlr_tmp > smlr_cur)
603 : : {
604 : 3511 : smlr_cur = smlr_tmp;
605 : 3511 : ulen2 = tmp_ulen2;
606 : 3511 : lower = tmp_lower;
607 : 3511 : count = tmp_count;
608 : : }
609 : :
610 : : /*
611 : : * If we only check that word similarity is greater than
612 : : * threshold we do not need to calculate a maximum
613 : : * similarity.
614 : : */
615 [ + + ]: 59678 : if ((flags & WORD_SIMILARITY_CHECK_ONLY)
616 [ + + ]: 37114 : && smlr_cur >= threshold)
617 : 1784 : break;
618 : : }
619 : :
3461 620 : 182924 : tmp_trgindex = trg2indexes[tmp_lower];
621 [ + + ]: 182924 : if (lastpos[tmp_trgindex] == tmp_lower)
622 : : {
623 : 180665 : tmp_ulen2--;
624 [ + + ]: 180665 : if (found[tmp_trgindex])
625 : 46576 : tmp_count--;
626 : : }
627 : : }
628 : :
629 [ + + ]: 25634 : smlr_max = Max(smlr_max, smlr_cur);
630 : :
631 : : /*
632 : : * if we only check that word similarity is greater than threshold
633 : : * we do not need to calculate a maximum similarity.
634 : : */
2726 635 [ + + + + ]: 25634 : if ((flags & WORD_SIMILARITY_CHECK_ONLY) && smlr_max >= threshold)
3461 636 : 1784 : break;
637 : :
638 [ + + ]: 40598 : for (tmp_lower = prev_lower; tmp_lower < lower; tmp_lower++)
639 : : {
640 : : int tmp_trgindex;
641 : :
642 : 16748 : tmp_trgindex = trg2indexes[tmp_lower];
643 [ + + ]: 16748 : if (lastpos[tmp_trgindex] == tmp_lower)
644 : 16000 : lastpos[tmp_trgindex] = -1;
645 : : }
646 : : }
647 : : }
648 : :
649 : 13128 : pfree(lastpos);
650 : :
651 : 13128 : return smlr_max;
652 : : }
653 : :
654 : : /*
655 : : * Calculate word similarity.
656 : : * This function prepare two arrays: "trg2indexes" and "found". Then this arrays
657 : : * are used to calculate word similarity using iterate_word_similarity().
658 : : *
659 : : * "trg2indexes" is array which stores indexes of the array "found".
660 : : * In other words:
661 : : * trg2indexes[j] = i;
662 : : * found[i] = true (or false);
663 : : * If found[i] == true then there is trigram trg2[j] in array "trg1".
664 : : * If found[i] == false then there is not trigram trg2[j] in array "trg1".
665 : : *
666 : : * str1: search pattern string, of length slen1 bytes.
667 : : * str2: text in which we are looking for a word, of length slen2 bytes.
668 : : * flags: set of boolean flags parameterizing similarity calculation.
669 : : *
670 : : * Returns word similarity.
671 : : */
672 : : static float4
673 : 13128 : calc_word_similarity(char *str1, int slen1, char *str2, int slen2,
674 : : uint8 flags)
675 : : {
676 : : bool *found;
677 : : pos_trgm *ptrg;
678 : : trgm *trg1;
679 : : trgm *trg2;
680 : : int len1,
681 : : len2,
682 : : len,
683 : : i,
684 : : j,
685 : : ulen1;
686 : : int *trg2indexes;
687 : : float4 result;
688 : : TrgmBound *bounds;
689 : :
690 : 13128 : protect_out_of_mem(slen1 + slen2);
691 : :
692 : : /* Make positional trigrams */
2999 tgl@sss.pgh.pa.us 693 : 13128 : trg1 = (trgm *) palloc(sizeof(trgm) * (slen1 / 2 + 1) * 3);
694 : 13128 : trg2 = (trgm *) palloc(sizeof(trgm) * (slen2 / 2 + 1) * 3);
2726 teodor@sigaev.ru 695 [ + + ]: 13128 : if (flags & WORD_SIMILARITY_STRICT)
696 : 6662 : bounds = (TrgmBound *) palloc0(sizeof(TrgmBound) * (slen2 / 2 + 1) * 3);
697 : : else
698 : 6466 : bounds = NULL;
699 : :
700 : 13128 : len1 = generate_trgm_only(trg1, str1, slen1, NULL);
701 : 13128 : len2 = generate_trgm_only(trg2, str2, slen2, bounds);
702 : :
3461 703 : 13128 : ptrg = make_positional_trgm(trg1, len1, trg2, len2);
704 : 13128 : len = len1 + len2;
705 : 13128 : qsort(ptrg, len, sizeof(pos_trgm), comp_ptrgm);
706 : :
707 : 13128 : pfree(trg1);
708 : 13128 : pfree(trg2);
709 : :
710 : : /*
711 : : * Merge positional trigrams array: enumerate each trigram and find its
712 : : * presence in required word.
713 : : */
714 : 13128 : trg2indexes = (int *) palloc(sizeof(int) * len2);
715 : 13128 : found = (bool *) palloc0(sizeof(bool) * len);
716 : :
717 : 13128 : ulen1 = 0;
718 : 13128 : j = 0;
719 [ + + ]: 313961 : for (i = 0; i < len; i++)
720 : : {
721 [ + + ]: 300833 : if (i > 0)
722 : : {
3376 rhaas@postgresql.org 723 : 287705 : int cmp = CMPTRGM(ptrg[i - 1].trg, ptrg[i].trg);
724 : :
3461 teodor@sigaev.ru 725 [ + + ]: 287705 : if (cmp != 0)
726 : : {
727 [ + + ]: 253505 : if (found[j])
728 : 101138 : ulen1++;
729 : 253505 : j++;
730 : : }
731 : : }
732 : :
733 [ + + ]: 300833 : if (ptrg[i].index >= 0)
734 : : {
735 : 192095 : trg2indexes[ptrg[i].index] = j;
736 : : }
737 : : else
738 : : {
739 : 108738 : found[j] = true;
740 : : }
741 : : }
742 [ + + ]: 13128 : if (found[j])
743 : 7600 : ulen1++;
744 : :
745 : : /* Run iterative procedure to find maximum similarity with word */
746 : 13128 : result = iterate_word_similarity(trg2indexes, found, ulen1, len2, len,
747 : : flags, bounds);
748 : :
749 : 13128 : pfree(trg2indexes);
750 : 13128 : pfree(found);
751 : 13128 : pfree(ptrg);
752 : :
753 : 13128 : return result;
754 : : }
755 : :
756 : :
757 : : /*
758 : : * Extract the next non-wildcard part of a search string, i.e. a word bounded
759 : : * by '_' or '%' meta-characters, non-word characters or string end.
760 : : *
761 : : * str: source string, of length lenstr bytes (need not be null-terminated)
762 : : * buf: where to return the substring (must be long enough)
763 : : * *bytelen: receives byte length of the found substring
764 : : * *charlen: receives character length of the found substring
765 : : *
766 : : * Returns pointer to end+1 of the found substring in the source string.
767 : : * Returns NULL if no word found (in which case buf, bytelen, charlen not set)
768 : : *
769 : : * If the found word is bounded by non-word characters or string boundaries
770 : : * then this function will include corresponding padding spaces into buf.
771 : : */
772 : : static const char *
5332 tgl@sss.pgh.pa.us 773 : 119 : get_wildcard_part(const char *str, int lenstr,
774 : : char *buf, int *bytelen, int *charlen)
775 : : {
776 : 119 : const char *beginword = str;
777 : : const char *endword;
778 : 119 : char *s = buf;
4765 779 : 119 : bool in_leading_wildcard_meta = false;
780 : 119 : bool in_trailing_wildcard_meta = false;
5263 bruce@momjian.us 781 : 119 : bool in_escape = false;
782 : : int clen;
783 : :
784 : : /*
785 : : * Find the first word character, remembering whether preceding character
786 : : * was wildcard meta-character. Note that the in_escape state persists
787 : : * from this loop to the next one, since we may exit at a word character
788 : : * that is in_escape.
789 : : */
5332 tgl@sss.pgh.pa.us 790 [ + + ]: 241 : while (beginword - str < lenstr)
791 : : {
792 [ + + ]: 186 : if (in_escape)
793 : : {
4533 794 [ + - ]: 3 : if (ISWORDCHR(beginword))
5332 795 : 3 : break;
4765 tgl@sss.pgh.pa.us 796 :UBC 0 : in_escape = false;
797 : 0 : in_leading_wildcard_meta = false;
798 : : }
799 : : else
800 : : {
5332 tgl@sss.pgh.pa.us 801 [ + + ]:CBC 183 : if (ISESCAPECHAR(beginword))
802 : 3 : in_escape = true;
803 [ + - + + ]: 180 : else if (ISWILDCARDCHAR(beginword))
4765 804 : 104 : in_leading_wildcard_meta = true;
4533 805 [ + + ]: 76 : else if (ISWORDCHR(beginword))
5332 806 : 61 : break;
807 : : else
4765 808 : 15 : in_leading_wildcard_meta = false;
809 : : }
5332 810 : 122 : beginword += pg_mblen(beginword);
811 : : }
812 : :
813 : : /*
814 : : * Handle string end.
815 : : */
816 [ + + ]: 119 : if (beginword - str >= lenstr)
817 : 55 : return NULL;
818 : :
819 : : /*
820 : : * Add left padding spaces if preceding character wasn't wildcard
821 : : * meta-character.
822 : : */
823 : 64 : *charlen = 0;
4765 824 [ + + ]: 64 : if (!in_leading_wildcard_meta)
825 : : {
826 : : if (LPADDING > 0)
827 : : {
5332 828 : 15 : *s++ = ' ';
829 : 15 : (*charlen)++;
830 : : if (LPADDING > 1)
831 : : {
832 : 15 : *s++ = ' ';
833 : 15 : (*charlen)++;
834 : : }
835 : : }
836 : : }
837 : :
838 : : /*
839 : : * Copy data into buf until wildcard meta-character, non-word character or
840 : : * string boundary. Strip escapes during copy.
841 : : */
842 : 64 : endword = beginword;
843 [ + - ]: 244 : while (endword - str < lenstr)
844 : : {
845 : 244 : clen = pg_mblen(endword);
846 [ + + ]: 244 : if (in_escape)
847 : : {
4533 848 [ + - ]: 3 : if (ISWORDCHR(endword))
849 : : {
5332 850 : 3 : memcpy(s, endword, clen);
851 : 3 : (*charlen)++;
852 : 3 : s += clen;
853 : : }
854 : : else
855 : : {
856 : : /*
857 : : * Back up endword to the escape character when stopping at an
858 : : * escaped char, so that subsequent get_wildcard_part will
859 : : * restart from the escape character. We assume here that
860 : : * escape chars are single-byte.
861 : : */
4765 tgl@sss.pgh.pa.us 862 :UBC 0 : endword--;
5332 863 : 0 : break;
864 : : }
4765 tgl@sss.pgh.pa.us 865 :CBC 3 : in_escape = false;
866 : : }
867 : : else
868 : : {
5332 869 [ - + ]: 241 : if (ISESCAPECHAR(endword))
5332 tgl@sss.pgh.pa.us 870 :UBC 0 : in_escape = true;
5332 tgl@sss.pgh.pa.us 871 [ + - + + ]:CBC 241 : else if (ISWILDCARDCHAR(endword))
872 : : {
4765 873 : 55 : in_trailing_wildcard_meta = true;
5332 874 : 55 : break;
875 : : }
4533 876 [ + + ]: 186 : else if (ISWORDCHR(endword))
877 : : {
5332 878 : 177 : memcpy(s, endword, clen);
879 : 177 : (*charlen)++;
880 : 177 : s += clen;
881 : : }
882 : : else
883 : 9 : break;
884 : : }
885 : 180 : endword += clen;
886 : : }
887 : :
888 : : /*
889 : : * Add right padding spaces if next character isn't wildcard
890 : : * meta-character.
891 : : */
4765 892 [ + + ]: 64 : if (!in_trailing_wildcard_meta)
893 : : {
894 : : if (RPADDING > 0)
895 : : {
5332 896 : 9 : *s++ = ' ';
897 : 9 : (*charlen)++;
898 : : if (RPADDING > 1)
899 : : {
900 : : *s++ = ' ';
901 : : (*charlen)++;
902 : : }
903 : : }
904 : : }
905 : :
906 : 64 : *bytelen = s - buf;
907 : 64 : return endword;
908 : : }
909 : :
910 : : /*
911 : : * Generates trigrams for wildcard search string.
912 : : *
913 : : * Returns array of trigrams that must occur in any string that matches the
914 : : * wildcard string. For example, given pattern "a%bcd%" the trigrams
915 : : * " a", "bcd" would be extracted.
916 : : */
917 : : TRGM *
918 : 55 : generate_wildcard_trgm(const char *str, int slen)
919 : : {
920 : : TRGM *trg;
921 : : char *buf,
922 : : *buf2;
923 : : trgm *tptr;
924 : : int len,
925 : : charlen,
926 : : bytelen;
927 : : const char *eword;
928 : :
3461 teodor@sigaev.ru 929 : 55 : protect_out_of_mem(slen);
930 : :
2999 tgl@sss.pgh.pa.us 931 : 55 : trg = (TRGM *) palloc(TRGMHDRSIZE + sizeof(trgm) * (slen / 2 + 1) * 3);
5332 932 : 55 : trg->flag = ARRKEY;
933 : 55 : SET_VARSIZE(trg, TRGMHDRSIZE);
934 : :
935 [ + - - + ]: 55 : if (slen + LPADDING + RPADDING < 3 || slen == 0)
5332 tgl@sss.pgh.pa.us 936 :UBC 0 : return trg;
937 : :
5332 tgl@sss.pgh.pa.us 938 :CBC 55 : tptr = GETARR(trg);
939 : :
940 : : /* Allocate a buffer for blank-padded, but not yet case-folded, words */
941 : 55 : buf = palloc(sizeof(char) * (slen + 4));
942 : :
943 : : /*
944 : : * Extract trigrams from each substring extracted by get_wildcard_part.
945 : : */
946 : 55 : eword = str;
947 : 119 : while ((eword = get_wildcard_part(eword, slen - (eword - str),
948 [ + + ]: 119 : buf, &bytelen, &charlen)) != NULL)
949 : : {
950 : : #ifdef IGNORECASE
263 peter@eisentraut.org 951 : 64 : buf2 = str_tolower(buf, bytelen, DEFAULT_COLLATION_OID);
5332 tgl@sss.pgh.pa.us 952 : 64 : bytelen = strlen(buf2);
953 : : #else
954 : : buf2 = buf;
955 : : #endif
956 : :
957 : : /*
958 : : * count trigrams
959 : : */
960 : 64 : tptr = make_trigrams(tptr, buf2, bytelen, charlen);
961 : :
962 : : #ifdef IGNORECASE
963 : 64 : pfree(buf2);
964 : : #endif
965 : : }
966 : :
967 : 55 : pfree(buf);
968 : :
969 [ + + ]: 55 : if ((len = tptr - GETARR(trg)) == 0)
970 : 24 : return trg;
971 : :
972 : : /*
973 : : * Make trigrams unique.
974 : : */
4254 975 [ + + ]: 31 : if (len > 1)
976 : : {
942 peter@eisentraut.org 977 : 17 : qsort(GETARR(trg), len, sizeof(trgm), comp_trgm);
2130 tmunro@postgresql.or 978 : 17 : len = qunique(GETARR(trg), len, sizeof(trgm), comp_trgm);
979 : : }
980 : :
5332 tgl@sss.pgh.pa.us 981 : 31 : SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, len));
982 : :
983 : 31 : return trg;
984 : : }
985 : :
986 : : uint32
6142 teodor@sigaev.ru 987 : 34829 : trgm2int(trgm *ptr)
988 : : {
5931 bruce@momjian.us 989 : 34829 : uint32 val = 0;
990 : :
991 : 34829 : val |= *(((unsigned char *) ptr));
6142 teodor@sigaev.ru 992 : 34829 : val <<= 8;
5931 bruce@momjian.us 993 : 34829 : val |= *(((unsigned char *) ptr) + 1);
6142 teodor@sigaev.ru 994 : 34829 : val <<= 8;
5931 bruce@momjian.us 995 : 34829 : val |= *(((unsigned char *) ptr) + 2);
996 : :
6142 teodor@sigaev.ru 997 : 34829 : return val;
998 : : }
999 : :
1000 : : Datum
7678 bruce@momjian.us 1001 : 7 : show_trgm(PG_FUNCTION_ARGS)
1002 : : {
3100 noah@leadboat.com 1003 : 7 : text *in = PG_GETARG_TEXT_PP(0);
1004 : : TRGM *trg;
1005 : : Datum *d;
1006 : : ArrayType *a;
1007 : : trgm *ptr;
1008 : : int i;
1009 : :
1010 [ - + - - : 7 : trg = generate_trgm(VARDATA_ANY(in), VARSIZE_ANY_EXHDR(in));
- - - - -
+ - + ]
7678 bruce@momjian.us 1011 : 7 : d = (Datum *) palloc(sizeof(Datum) * (1 + ARRNELEM(trg)));
1012 : :
6631 tgl@sss.pgh.pa.us 1013 [ + + ]: 44 : for (i = 0, ptr = GETARR(trg); i < ARRNELEM(trg); i++, ptr++)
1014 : : {
5931 bruce@momjian.us 1015 [ + - ]: 37 : text *item = (text *) palloc(VARHDRSZ + Max(12, pg_database_encoding_max_length() * 3));
1016 : :
1017 [ + - + - : 37 : if (pg_database_encoding_max_length() > 1 && !ISPRINTABLETRGM(ptr))
+ + + - +
- + + + -
+ - + + -
+ ]
1018 : : {
6142 teodor@sigaev.ru 1019 :UBC 0 : snprintf(VARDATA(item), 12, "0x%06x", trgm2int(ptr));
1020 : 0 : SET_VARSIZE(item, VARHDRSZ + strlen(VARDATA(item)));
1021 : : }
1022 : : else
1023 : : {
6142 teodor@sigaev.ru 1024 :CBC 37 : SET_VARSIZE(item, VARHDRSZ + 3);
1025 : 37 : CPTRGM(VARDATA(item), ptr);
1026 : : }
6631 tgl@sss.pgh.pa.us 1027 : 37 : d[i] = PointerGetDatum(item);
1028 : : }
1029 : :
1163 peter@eisentraut.org 1030 : 7 : a = construct_array_builtin(d, ARRNELEM(trg), TEXTOID);
1031 : :
6631 tgl@sss.pgh.pa.us 1032 [ + + ]: 44 : for (i = 0; i < ARRNELEM(trg); i++)
1033 : 37 : pfree(DatumGetPointer(d[i]));
1034 : :
7768 teodor@sigaev.ru 1035 : 7 : pfree(d);
1036 : 7 : pfree(trg);
7678 bruce@momjian.us 1037 [ - + ]: 7 : PG_FREE_IF_COPY(in, 0);
1038 : :
7768 teodor@sigaev.ru 1039 : 7 : PG_RETURN_POINTER(a);
1040 : : }
1041 : :
1042 : : float4
3461 1043 : 67819 : cnt_sml(TRGM *trg1, TRGM *trg2, bool inexact)
1044 : : {
1045 : : trgm *ptr1,
1046 : : *ptr2;
7678 bruce@momjian.us 1047 : 67819 : int count = 0;
1048 : : int len1,
1049 : : len2;
1050 : :
7768 teodor@sigaev.ru 1051 : 67819 : ptr1 = GETARR(trg1);
1052 : 67819 : ptr2 = GETARR(trg2);
1053 : :
1054 : 67819 : len1 = ARRNELEM(trg1);
1055 : 67819 : len2 = ARRNELEM(trg2);
1056 : :
1057 : : /* explicit test is needed to avoid 0/0 division when both lengths are 0 */
4588 tgl@sss.pgh.pa.us 1058 [ + + - + ]: 67819 : if (len1 <= 0 || len2 <= 0)
1059 : 1 : return (float4) 0.0;
1060 : :
7678 bruce@momjian.us 1061 [ + + + + ]: 861105 : while (ptr1 - GETARR(trg1) < len1 && ptr2 - GETARR(trg2) < len2)
1062 : : {
1063 : 793287 : int res = CMPTRGM(ptr1, ptr2);
1064 : :
1065 [ + + ]: 793287 : if (res < 0)
7768 teodor@sigaev.ru 1066 : 175582 : ptr1++;
7678 bruce@momjian.us 1067 [ + + ]: 617705 : else if (res > 0)
7768 teodor@sigaev.ru 1068 : 206329 : ptr2++;
1069 : : else
1070 : : {
1071 : 411376 : ptr1++;
1072 : 411376 : ptr2++;
1073 : 411376 : count++;
1074 : : }
1075 : : }
1076 : :
1077 : : /*
1078 : : * If inexact then len2 is equal to count, because we don't know actual
1079 : : * length of second string in inexact search and we can assume that count
1080 : : * is a lower bound of len2.
1081 : : */
3461 1082 [ + + ]: 67818 : return CALCSML(count, len1, inexact ? count : len2);
1083 : : }
1084 : :
1085 : :
1086 : : /*
1087 : : * Returns whether trg2 contains all trigrams in trg1.
1088 : : * This relies on the trigram arrays being sorted.
1089 : : */
1090 : : bool
5332 tgl@sss.pgh.pa.us 1091 : 190 : trgm_contained_by(TRGM *trg1, TRGM *trg2)
1092 : : {
1093 : : trgm *ptr1,
1094 : : *ptr2;
1095 : : int len1,
1096 : : len2;
1097 : :
1098 : 190 : ptr1 = GETARR(trg1);
1099 : 190 : ptr2 = GETARR(trg2);
1100 : :
1101 : 190 : len1 = ARRNELEM(trg1);
1102 : 190 : len2 = ARRNELEM(trg2);
1103 : :
1104 [ + + + + ]: 622 : while (ptr1 - GETARR(trg1) < len1 && ptr2 - GETARR(trg2) < len2)
1105 : : {
1106 : 599 : int res = CMPTRGM(ptr1, ptr2);
1107 : :
1108 [ + + ]: 599 : if (res < 0)
1109 : 167 : return false;
1110 [ + + ]: 432 : else if (res > 0)
1111 : 320 : ptr2++;
1112 : : else
1113 : : {
1114 : 112 : ptr1++;
1115 : 112 : ptr2++;
1116 : : }
1117 : : }
1118 [ + + ]: 23 : if (ptr1 - GETARR(trg1) < len1)
1119 : 4 : return false;
1120 : : else
1121 : 19 : return true;
1122 : : }
1123 : :
1124 : : /*
1125 : : * Return a palloc'd boolean array showing, for each trigram in "query",
1126 : : * whether it is present in the trigram array "key".
1127 : : * This relies on the "key" array being sorted, but "query" need not be.
1128 : : */
1129 : : bool *
4532 1130 : 2150 : trgm_presence_map(TRGM *query, TRGM *key)
1131 : : {
1132 : : bool *result;
1133 : 2150 : trgm *ptrq = GETARR(query),
1134 : 2150 : *ptrk = GETARR(key);
1135 : 2150 : int lenq = ARRNELEM(query),
1136 : 2150 : lenk = ARRNELEM(key),
1137 : : i;
1138 : :
1139 : 2150 : result = (bool *) palloc0(lenq * sizeof(bool));
1140 : :
1141 : : /* for each query trigram, do a binary search in the key array */
1142 [ + + ]: 507560 : for (i = 0; i < lenq; i++)
1143 : : {
1144 : 505410 : int lo = 0;
1145 : 505410 : int hi = lenk;
1146 : :
1147 [ + + ]: 2373653 : while (lo < hi)
1148 : : {
1149 : 1876282 : int mid = (lo + hi) / 2;
1150 : 1876282 : int res = CMPTRGM(ptrq, ptrk + mid);
1151 : :
1152 [ + + ]: 1876282 : if (res < 0)
1153 : 784082 : hi = mid;
1154 [ + + ]: 1092200 : else if (res > 0)
1155 : 1084161 : lo = mid + 1;
1156 : : else
1157 : : {
1158 : 8039 : result[i] = true;
1159 : 8039 : break;
1160 : : }
1161 : : }
1162 : 505410 : ptrq++;
1163 : : }
1164 : :
1165 : 2150 : return result;
1166 : : }
1167 : :
1168 : : Datum
7678 bruce@momjian.us 1169 : 31452 : similarity(PG_FUNCTION_ARGS)
1170 : : {
3100 noah@leadboat.com 1171 : 31452 : text *in1 = PG_GETARG_TEXT_PP(0);
1172 : 31452 : text *in2 = PG_GETARG_TEXT_PP(1);
1173 : : TRGM *trg1,
1174 : : *trg2;
1175 : : float4 res;
1176 : :
1177 [ - + - - : 31452 : trg1 = generate_trgm(VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1));
- - - - +
+ + + ]
1178 [ - + - - : 31452 : trg2 = generate_trgm(VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2));
- - - - -
+ - + ]
1179 : :
3461 teodor@sigaev.ru 1180 : 31452 : res = cnt_sml(trg1, trg2, false);
1181 : :
7768 1182 : 31452 : pfree(trg1);
1183 : 31452 : pfree(trg2);
7678 bruce@momjian.us 1184 [ - + ]: 31452 : PG_FREE_IF_COPY(in1, 0);
1185 [ - + ]: 31452 : PG_FREE_IF_COPY(in2, 1);
1186 : :
7768 teodor@sigaev.ru 1187 : 31452 : PG_RETURN_FLOAT4(res);
1188 : : }
1189 : :
1190 : : Datum
3461 1191 : 902 : word_similarity(PG_FUNCTION_ARGS)
1192 : : {
1193 : 902 : text *in1 = PG_GETARG_TEXT_PP(0);
1194 : 902 : text *in2 = PG_GETARG_TEXT_PP(1);
1195 : : float4 res;
1196 : :
1197 [ - + - - : 902 : res = calc_word_similarity(VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
- - - - -
+ - + ]
3376 rhaas@postgresql.org 1198 [ - + - - : 902 : VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
- - - - +
- + - ]
1199 : : 0);
1200 : :
2726 teodor@sigaev.ru 1201 [ - + ]: 902 : PG_FREE_IF_COPY(in1, 0);
1202 [ - + ]: 902 : PG_FREE_IF_COPY(in2, 1);
1203 : 902 : PG_RETURN_FLOAT4(res);
1204 : : }
1205 : :
1206 : : Datum
1207 : 882 : strict_word_similarity(PG_FUNCTION_ARGS)
1208 : : {
1209 : 882 : text *in1 = PG_GETARG_TEXT_PP(0);
1210 : 882 : text *in2 = PG_GETARG_TEXT_PP(1);
1211 : : float4 res;
1212 : :
1213 [ - + - - : 882 : res = calc_word_similarity(VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
- - - - -
+ - + ]
1214 [ - + - - : 882 : VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
- - - - +
- + - ]
1215 : : WORD_SIMILARITY_STRICT);
1216 : :
3461 1217 [ - + ]: 882 : PG_FREE_IF_COPY(in1, 0);
1218 [ - + ]: 882 : PG_FREE_IF_COPY(in2, 1);
1219 : 882 : PG_RETURN_FLOAT4(res);
1220 : : }
1221 : :
1222 : : Datum
5390 tgl@sss.pgh.pa.us 1223 : 1004 : similarity_dist(PG_FUNCTION_ARGS)
1224 : : {
1225 : 1004 : float4 res = DatumGetFloat4(DirectFunctionCall2(similarity,
1226 : : PG_GETARG_DATUM(0),
1227 : : PG_GETARG_DATUM(1)));
1228 : :
1229 : 1004 : PG_RETURN_FLOAT4(1.0 - res);
1230 : : }
1231 : :
1232 : : Datum
7678 bruce@momjian.us 1233 : 6000 : similarity_op(PG_FUNCTION_ARGS)
1234 : : {
5390 tgl@sss.pgh.pa.us 1235 : 6000 : float4 res = DatumGetFloat4(DirectFunctionCall2(similarity,
1236 : : PG_GETARG_DATUM(0),
1237 : : PG_GETARG_DATUM(1)));
1238 : :
3461 teodor@sigaev.ru 1239 : 6000 : PG_RETURN_BOOL(res >= similarity_threshold);
1240 : : }
1241 : :
1242 : : Datum
1243 : 1924 : word_similarity_op(PG_FUNCTION_ARGS)
1244 : : {
1245 : 1924 : text *in1 = PG_GETARG_TEXT_PP(0);
1246 : 1924 : text *in2 = PG_GETARG_TEXT_PP(1);
1247 : : float4 res;
1248 : :
1249 [ - + - - : 1924 : res = calc_word_similarity(VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
- - - - -
+ - + ]
3376 rhaas@postgresql.org 1250 [ - + - - : 1924 : VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
- - - - +
- + - ]
1251 : : WORD_SIMILARITY_CHECK_ONLY);
1252 : :
3461 teodor@sigaev.ru 1253 [ - + ]: 1924 : PG_FREE_IF_COPY(in1, 0);
1254 [ - + ]: 1924 : PG_FREE_IF_COPY(in2, 1);
1255 : 1924 : PG_RETURN_BOOL(res >= word_similarity_threshold);
1256 : : }
1257 : :
1258 : : Datum
1259 : 2926 : word_similarity_commutator_op(PG_FUNCTION_ARGS)
1260 : : {
1261 : 2926 : text *in1 = PG_GETARG_TEXT_PP(0);
1262 : 2926 : text *in2 = PG_GETARG_TEXT_PP(1);
1263 : : float4 res;
1264 : :
1265 [ - + - - : 2926 : res = calc_word_similarity(VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
- - - - -
+ - + ]
3376 rhaas@postgresql.org 1266 [ - + - - : 2926 : VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
- - - - +
- + - ]
1267 : : WORD_SIMILARITY_CHECK_ONLY);
1268 : :
3461 teodor@sigaev.ru 1269 [ - + ]: 2926 : PG_FREE_IF_COPY(in1, 0);
1270 [ - + ]: 2926 : PG_FREE_IF_COPY(in2, 1);
1271 : 2926 : PG_RETURN_BOOL(res >= word_similarity_threshold);
1272 : : }
1273 : :
1274 : : Datum
3461 teodor@sigaev.ru 1275 :UBC 0 : word_similarity_dist_op(PG_FUNCTION_ARGS)
1276 : : {
1277 : 0 : text *in1 = PG_GETARG_TEXT_PP(0);
1278 : 0 : text *in2 = PG_GETARG_TEXT_PP(1);
1279 : : float4 res;
1280 : :
1281 [ # # # # : 0 : res = calc_word_similarity(VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
# # # # #
# # # ]
3376 rhaas@postgresql.org 1282 [ # # # # : 0 : VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
# # # # #
# # # ]
1283 : : 0);
1284 : :
3461 teodor@sigaev.ru 1285 [ # # ]: 0 : PG_FREE_IF_COPY(in1, 0);
1286 [ # # ]: 0 : PG_FREE_IF_COPY(in2, 1);
1287 : 0 : PG_RETURN_FLOAT4(1.0 - res);
1288 : : }
1289 : :
1290 : : Datum
3461 teodor@sigaev.ru 1291 :CBC 714 : word_similarity_dist_commutator_op(PG_FUNCTION_ARGS)
1292 : : {
1293 : 714 : text *in1 = PG_GETARG_TEXT_PP(0);
1294 : 714 : text *in2 = PG_GETARG_TEXT_PP(1);
1295 : : float4 res;
1296 : :
1297 [ - + - - : 714 : res = calc_word_similarity(VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
- - - - -
+ - + ]
3376 rhaas@postgresql.org 1298 [ - + - - : 714 : VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
- - - - +
- + - ]
1299 : : 0);
1300 : :
2726 teodor@sigaev.ru 1301 [ - + ]: 714 : PG_FREE_IF_COPY(in1, 0);
1302 [ - + ]: 714 : PG_FREE_IF_COPY(in2, 1);
1303 : 714 : PG_RETURN_FLOAT4(1.0 - res);
1304 : : }
1305 : :
1306 : : Datum
1307 : 2530 : strict_word_similarity_op(PG_FUNCTION_ARGS)
1308 : : {
1309 : 2530 : text *in1 = PG_GETARG_TEXT_PP(0);
1310 : 2530 : text *in2 = PG_GETARG_TEXT_PP(1);
1311 : : float4 res;
1312 : :
1313 [ - + - - : 2530 : res = calc_word_similarity(VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
- - - - -
+ - + ]
1314 [ - + - - : 2530 : VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
- - - - +
- + - ]
1315 : : WORD_SIMILARITY_CHECK_ONLY | WORD_SIMILARITY_STRICT);
1316 : :
1317 [ - + ]: 2530 : PG_FREE_IF_COPY(in1, 0);
1318 [ - + ]: 2530 : PG_FREE_IF_COPY(in2, 1);
1319 : 2530 : PG_RETURN_BOOL(res >= strict_word_similarity_threshold);
1320 : : }
1321 : :
1322 : : Datum
1323 : 2530 : strict_word_similarity_commutator_op(PG_FUNCTION_ARGS)
1324 : : {
1325 : 2530 : text *in1 = PG_GETARG_TEXT_PP(0);
1326 : 2530 : text *in2 = PG_GETARG_TEXT_PP(1);
1327 : : float4 res;
1328 : :
1329 [ - + - - : 2530 : res = calc_word_similarity(VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
- - - - -
+ - + ]
1330 [ - + - - : 2530 : VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
- - - - +
- + - ]
1331 : : WORD_SIMILARITY_CHECK_ONLY | WORD_SIMILARITY_STRICT);
1332 : :
1333 [ - + ]: 2530 : PG_FREE_IF_COPY(in1, 0);
1334 [ - + ]: 2530 : PG_FREE_IF_COPY(in2, 1);
1335 : 2530 : PG_RETURN_BOOL(res >= strict_word_similarity_threshold);
1336 : : }
1337 : :
1338 : : Datum
2726 teodor@sigaev.ru 1339 :UBC 0 : strict_word_similarity_dist_op(PG_FUNCTION_ARGS)
1340 : : {
1341 : 0 : text *in1 = PG_GETARG_TEXT_PP(0);
1342 : 0 : text *in2 = PG_GETARG_TEXT_PP(1);
1343 : : float4 res;
1344 : :
1345 [ # # # # : 0 : res = calc_word_similarity(VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
# # # # #
# # # ]
1346 [ # # # # : 0 : VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
# # # # #
# # # ]
1347 : : WORD_SIMILARITY_STRICT);
1348 : :
1349 [ # # ]: 0 : PG_FREE_IF_COPY(in1, 0);
1350 [ # # ]: 0 : PG_FREE_IF_COPY(in2, 1);
1351 : 0 : PG_RETURN_FLOAT4(1.0 - res);
1352 : : }
1353 : :
1354 : : Datum
2726 teodor@sigaev.ru 1355 :CBC 720 : strict_word_similarity_dist_commutator_op(PG_FUNCTION_ARGS)
1356 : : {
1357 : 720 : text *in1 = PG_GETARG_TEXT_PP(0);
1358 : 720 : text *in2 = PG_GETARG_TEXT_PP(1);
1359 : : float4 res;
1360 : :
1361 [ - + - - : 720 : res = calc_word_similarity(VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
- - - - -
+ - + ]
1362 [ - + - - : 720 : VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
- - - - +
- + - ]
1363 : : WORD_SIMILARITY_STRICT);
1364 : :
3461 1365 [ - + ]: 720 : PG_FREE_IF_COPY(in1, 0);
1366 [ - + ]: 720 : PG_FREE_IF_COPY(in2, 1);
1367 : 720 : PG_RETURN_FLOAT4(1.0 - res);
1368 : : }
|
