| PostgreSQL 8.3.0 Documentation | ||||
|---|---|---|---|---|
| Prev | Fast Backward | Appendix F. Additional Supplied Modules | Fast Forward | Next |
The pg_trgm module provides functions and operators for determining the similarity of text based on trigram matching, as well as index operator classes that support fast searching for similar strings.
A trigram is a group of three consecutive characters taken from a string. We can measure the similarity of two strings by counting the number of trigrams they share. This simple idea turns out to be very effective for measuring the similarity of words in many natural languages.
Note: A string is considered to have two spaces prefixed and one space suffixed when determining the set of trigrams contained in the string. For example, the set of trigrams in the string "cat" is " c", " ca", "cat", and "at ".
Table F-29. pg_trgm functions
| Function | Returns | Description |
|---|---|---|
similarity(text, text) | real | Returns a number that indicates how similar the two arguments are. The range of the result is zero (indicating that the two strings are completely dissimilar) to one (indicating that the two strings are identical). |
show_trgm(text) | text[] | Returns an array of all the trigrams in the given string. (In practice this is seldom useful except for debugging.) |
show_limit() | real | Returns the current similarity threshold used by the % operator. This sets the minimum similarity between two words for them to be considered similar enough to be misspellings of each other, for example. |
set_limit(real) | real | Sets the current similarity threshold that is used by the % operator. The threshold must be between 0 and 1 (default is 0.3). Returns the same value passed in. |
The pg_trgm module provides GiST and GIN index operator classes that allow you to create an index over a text column for the purpose of very fast similarity searches. These index types support the % similarity operator (and no other operators, so you may want a regular btree index too).
Example:
CREATE TABLE test_trgm (t text); CREATE INDEX trgm_idx ON test_trgm USING gist (t gist_trgm_ops);
or
CREATE INDEX trgm_idx ON test_trgm USING gin (t gin_trgm_ops);
At this point, you will have an index on the t column that you can use for similarity searching. A typical query is
SELECT t, similarity(t, 'word') AS sml FROM test_trgm WHERE t % 'word' ORDER BY sml DESC, t;
This will return all values in the text column that are sufficiently similar to word, sorted from best match to worst. The index will be used to make this a fast operation even over very large data sets.
The choice between GiST and GIN indexing depends on the relative performance characteristics of GiST and GIN, which are discussed elsewhere. As a rule of thumb, a GIN index is faster to search than a GiST index, but slower to build or update; so GIN is better suited for static data and GiST for often-updated data.
Trigram matching is a very useful tool when used in conjunction with a full text index. In particular it can help to recognize misspelled input words that will not be matched directly by the full text search mechanism.
The first step is to generate an auxiliary table containing all the unique words in the documents:
CREATE TABLE words AS SELECT word FROM
ts_stat('SELECT to_tsvector(''simple'', bodytext) FROM documents');
where documents is a table that has a text field
bodytext that we wish to search. The reason for using
the simple configuration with the to_tsvector
function, instead of using a language-specific configuration,
is that we want a list of the original (unstemmed) words.
Next, create a trigram index on the word column:
CREATE INDEX words_idx ON words USING gin(word gin_trgm_ops);
Now, a SELECT query similar to the previous example can be used to suggest spellings for misspelled words in user search terms. A useful extra test is to require that the selected words are also of similar length to the misspelled word.
Note: Since the words table has been generated as a separate, static table, it will need to be periodically regenerated so that it remains reasonably up-to-date with the document collection. Keeping it exactly current is usually unnecessary.
GiST Development Site http://www.sai.msu.su/~megera/postgres/gist/
Tsearch2 Development Site http://www.sai.msu.su/~megera/postgres/gist/tsearch/V2/
Oleg Bartunov <[email protected]>, Moscow, Moscow University, Russia
Teodor Sigaev <[email protected]>, Moscow, Delta-Soft Ltd.,Russia
Documentation: Christopher Kings-Lynne
This module is sponsored by Delta-Soft Ltd., Moscow, Russia.