Обсуждение: Index for Levenshtein distance

Hi,

I'm searching for a suitable Index for my query witch compares Strings with the Levenshtein distance.

I read that a prefix index would fit, but I don't know how to build it. I only know that its supported by Gist.

I couldn't find an instructions so I hope someone can help me.

 

Best regards,
Janek

 

 

Hi,

Im searching for a suitable Index for my query witch compares Strings with the Levenshtein distance.

I read that a prefix index would fit, but I dont know how to build it. I only know that its supported by Gist.

I couldn't find an instructions so I hope someone can help me.
 
Best regards,
Janek
 
 

Hi Janek,

Il 21/07/2013 16:46, Janek Sendrowski ha scritto:
> Hi,
>
> Im searching for a suitable Index for my query witch compares Strings with the Levenshtein distance.
>
> I read that a prefix index would fit, but I dont know how to build it. I only know that its supported by Gist.
>
> I couldn't find an instructions so I hope someone can help me.

Consider this simple example: suppose you have a table "table1" with a
column "string" of type TEXT, and you are interested to find "string" in
your table equal to 'ciao' basing your query in Levenshtein distance.
Then, improve your query creating an index based on gist.

First of all, create extensions to use levenshtein() function, and gist
indexing for types different from PostGIS objects:

CREATE EXTENSION fuzzystrmatch;
CREATE EXTENSION btree_gist;

You can check that all works fine trying a query like:

SELECT string FROM table1 WHERE levenshtein(string,'ciao') = 0;

which finds also "string" equal to 'ciao'. Create now the index to
improve this query:

CREATE INDEX lev_idx ON table1 USING GIST(levenshtein(string,'ciao'));

And relaunch the same query. I made a simple check with a very simple
table1 example with ten raws using EXPLAIN ANALYSE to exploit the
performances: query time changes from 1.077 ms to 0.677 ms after gist
index creation.

Hope it helps,

Giuseppe.

--
Giuseppe Broccolo - 2ndQuadrant Italy
PostgreSQL Training, Services and Support
giuseppe.broccolo@2ndQuadrant.it  |www.2ndQuadrant.it

Hi,

I'm searching for an algorithm/Index to find similar sentences in a database.

The Fulltextsearch is not really suitable because it doesn't have a tolerance.

The Levenshtein-distance ist to slow.

I also tried pg_trgm module, which works with tri-grams, but it's also very slow with 100.000+ rows.

I hope someone can help, I can't really find sth. which is fast enough.

Best regards,
Janek
 
 

Of course, you can use regular expressions and LIKE.  Without understanding the structure of your database, I don't
knowif that can be made efficient.  For a collection of sentences, I suspect it would get complicated.  It would
probablybe slow.  I guess that what you want to do will be hard to perform  in an efficient manner using a standard
relationaldatabase with commonly used functions such as LIKE and REGEX.
 

Perhaps one of the bioinformatics projects like PostBIO or PostBIS can be adapted to suit your needs.  They deal with
quicklyfinding similar sequences that are very complex, but they are designed specifically for DNA sequences.
 
Just a thought.

-----Original Message-----
From: pgsql-general-owner@postgresql.org [mailto:pgsql-general-owner@postgresql.org] On Behalf Of Janek Sendrowski
Sent: Thursday, July 25, 2013 3:55 PM
To: pgsql-general@postgresql.org
Subject: [GENERAL] Fastest Index/Algorithm to find similar sentences

Hi,

I'm searching for an algorithm/Index to find similar sentences in a database.

The Fulltextsearch is not really suitable because it doesn't have a tolerance.

The Levenshtein-distance ist to slow.

I also tried pg_trgm module, which works with tri-grams, but it's also very slow with 100.000+ rows.

I hope someone can help, I can't really find sth. which is fast enough.

Best regards,
Janek
 
 


--
Sent via pgsql-general mailing list (pgsql-general@postgresql.org) To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general

On Fri, Jul 26, 2013 at 7:54 AM, Janek Sendrowski <janek12@web.de> wrote:
> Hi,
>
> I'm searching for an algorithm/Index to find similar sentences in a database.
>
> The Fulltextsearch is not really suitable because it doesn't have a tolerance.
>
> The Levenshtein-distance ist to slow.
>
> I also tried pg_trgm module, which works with tri-grams, but it's also very slow with 100.000+ rows.
>
> I hope someone can help, I can't really find sth. which is fast enough.
>

Have you tried pg_bigm (a bi-gram based implementation)? It's still in
development phase, but you could give it a try and see if it can
perform better where pg_trgm can not.


--
Amit Langote

Thanks for your answers.

@Amit Langote: I had a look and found out that pg_bigm doesn't support similar matches 

@Dann Corbit: The idea with the sequences makes sence. I had a look and I'm not sure, if they support similar sequences

Janek

On Thu, Jul 25, 2013 at 3:54 PM, Janek Sendrowski <janek12@web.de> wrote:
> The Fulltextsearch is not really suitable because it doesn't have a tolerance.

What do you exactly mean by tolerance here?

--
Kind regards,
Sergey Konoplev
PostgreSQL Consultant and DBA

Profile: http://www.linkedin.com/in/grayhemp
Phone: USA +1 (415) 867-9984, Russia +7 (901) 903-0499, +7 (988) 888-1979
Skype: gray-hemp
Jabber: gray.ru@gmail.com

Hi Sergey Konoplev,
 
If I'm searching for a sentence like "The tiger is the largest cat species" for example.
 
I can only find the sentences, which include the words "tiger, largest, cat, species", but I also like to have the
sentenceswith only three or even two of these words. 
 
Janek

On Sat, Jul 27, 2013 at 10:04 AM, Janek Sendrowski <janek12@web.de> wrote:
> If I'm searching for a sentence like "The tiger is the largest cat species" for example.
> I can only find the sentences, which include the words "tiger, largest, cat, species", but I also like to have the
sentenceswith only three or even two of these words. 

You can use & (AND), | (OR), and ! (NOT) operators in tsquery, so you
can achieve what you want just like this:

[local]:5432 grayhemp@grayhemp=# select to_tsquery('tiger | largest |
cat | species') @@ to_tsvector('The tiger is the largest cat');
 ?column?
----------
 t

Or may be I understand something wrong again?

>
> Janek
>
>
> --
> Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-general



--
Kind regards,
Sergey Konoplev
PostgreSQL Consultant and DBA

Profile: http://www.linkedin.com/in/grayhemp
Phone: USA +1 (415) 867-9984, Russia +7 (901) 903-0499, +7 (988) 888-1979
Skype: gray-hemp
Jabber: gray.ru@gmail.com

I worked on a library project once that needed to perform similarity searches.

The first thing needed was to construct a word dictionary where there was a number corresponding to each word.
1, 'aardvark'
...
99999, 'zygote'

Then you need a list of stop words like 'AND', 'THE':
https://en.wikipedia.org/wiki/Stop_words

Then, you write a sentence parser that turns words into their numbers
So now, a bibliography entry (for example) will be a vector of numbers.

You can query with things like wordcount, word x NEAR word y, etc.
If the database supports it, you can also query with bitmap indexes.
I have not used the PostgreSQL bitmap indexes much, but they look like they might be quite useful:
http://wiki.postgresql.org/wiki/Bitmap_Indexes

We used something called ALA library parsing rules that stripped off special characters, made capitalization uniform,
etc.
http://www.ala.org/tools/guidelines/standardsguidelines
Something like this project was the outcome:
http://www.ala.org/lita/ital/21/4/su

You might look into library software.  Maybe you can find something useful here:
http://www.loc.gov/marc/marctools.html

I see that there are some sourceforge MARC record projects:
http://sourceforge.net/directory/os:windows/freshness:recently-updated/?q=marc%20records

Janek Sendrowski <janek12@web.de> wrote:

> I also tried pg_trgm module, which works with tri-grams, but it's
> also very slow with 100.000+ rows.

Hmm.  I found the pg_trgm module very fast for name searches with
millions of rows *as long as I used KNN-GiST techniques*.  Were you
careful to do so?  Check out the "Index Support" section of this
page:

http://www.postgresql.org/docs/current/static/pgtrgm.html

While I have not tested this technique with a column containing
sentences, I would expect it to work well.  As a quick
confirmation, I imported the text form of War and Peace into a
table, with one row per *line* (because that was easier than
parsing sentence boundaries for a quick test).  That was over
65,000 rows.

test=# select * from war_and_peace order by linetext <-> 'young wealthy gay gentlemen' limit 3;
 lineno |                               linetext                                
--------+-----------------------------------------------------------------------
   9082 | The gentlemen assembled at Bilibin's were young, wealthy, gay society
  36575 | "Gentlemen, you are crushing me!..."
  55997 | * "Good day, gentlemen."
(3 rows)

test=# explain analyze select * from war_and_peace order by linetext <-> 'young wealthy gay gentlemen' limit 3;
                                                               QUERY PLAN

-----------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.28..0.80 rows=3 width=53) (actual time=37.986..38.002 rows=3 loops=1)
   ->  Index Scan using wap_text on war_and_peace  (cost=0.28..11216.42 rows=65007 width=53) (actual
time=37.984..37.999rows=3 loops=1) 
         Order By: (linetext <-> 'young wealthy gay gentlemen'::text)
 Total runtime: 38.180 ms
(4 rows)

To me, 38 milliseconds to search War and Peace for best matches to
a text string seems reasonable; I'm not sure what you're looking
for, since you didn't give any numbers.

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Sun, Aug 11, 2013 at 6:20 AM, Janek Sendrowski <janek12@web.de> wrote:
> the ranking functions are nice, but if I search for one more word, which is not included in the sentence I'm
searchingfor, It doesn't find the sentence. 

I have already wrote you earlier about it. You can solve the problem
by using & (AND), | (OR), and ! (NOT) operators in tsquery.

select to_tsquery('tiger | largest | cat | species') @@
to_tsvector('The tiger is the largest cat');
 ?column?
----------
 t

The query contains one word more than the sentence (the word is
"species"), and it successfully finds it.

--
Kind regards,
Sergey Konoplev
PostgreSQL Consultant and DBA

http://www.linkedin.com/in/grayhemp
+1 (415) 867-9984, +7 (901) 903-0499, +7 (988) 888-1979
gray.ru@gmail.com

As I understand, you need to search strings by similarity (using levenshtein
or any other metric distance). In that case, you can use metric indexes like
FHQT or FQA (this is better if you are using a relational database, like
postgres). But they are not implemented yet in most DBMS, so you need to
program the index. It s not too hard, but you need to understand the base
concepts. You can look for "searching in metric spaces" to read about it. If
you are in a hurry, you can mail me and maybe I can help you.

Andres.



--
View this message in context:
http://postgresql.1045698.n5.nabble.com/Index-for-Levenshtein-distance-tp5764546p5768127.html
Sent from the PostgreSQL - general mailing list archive at Nabble.com.

On Fri, Aug 2, 2013 at 10:25 AM, Kevin Grittner <kgrittn@ymail.com> wrote:
> Janek Sendrowski <janek12@web.de> wrote:
>
>> I also tried pg_trgm module, which works with tri-grams, but it's
>> also very slow with 100.000+ rows.
>
> Hmm.  I found the pg_trgm module very fast for name searches with
> millions of rows *as long as I used KNN-GiST techniques*.  Were you
> careful to do so?  Check out the "Index Support" section of this
> page:
>
> http://www.postgresql.org/docs/current/static/pgtrgm.html
>
> While I have not tested this technique with a column containing
> sentences, I would expect it to work well.  As a quick
> confirmation, I imported the text form of War and Peace into a
> table, with one row per *line* (because that was easier than
> parsing sentence boundaries for a quick test).  That was over
> 65,000 rows.

+ 1 this.  pg_trgm is black magic.  search time (when using index) is
mostly dependent on number of trigrams in search string vs average
number of trigrams in database.

merlin