From: | janek12(at)web(dot)de |
---|---|
To: | pgsql-general(at)postgresql(dot)org |
Subject: | Re: Levenshtein Distance with more than 255 characters |
Date: | 2013-09-06 21:00:23 |
Message-ID: | trinity-d02c0ca8-a3b5-475e-8735-b4ae04c3e67a-1378501223587@msvc084 |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-general |
Where can I change levensthein_max_length?
Janek Sendrowski
Von: "Szymon Guz" <mabewlun(at)gmail(dot)com>
An: "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Betreff: Re: [GENERAL] Levenshtein Distance with more than 255 characters
On 6 September 2013 08:47, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Szymon Guz <mabewlun(at)gmail(dot)com> writes:
> > On 6 September 2013 01:00, Janek Sendrowski <janek12(at)web(dot)de> wrote:
> >> I'm searching for an optimized Levenshtein Distance like Postgresql's.
> My
> >> problem is that I want to compare strings with a length over 255
> characters.
> >> Does anyone know a solution?
>
> > I'm not sure there is anything different from what you've found in
> > core/contribs. But you can always use pg/plpython or pg/plperl procedure
> > with some external library calculating the distance.
>
> Well, you could just rebuild the fuzzystrmatch module with a different
> value for MAX_LEVENSHTEIN_STRLEN. The comments in the code note that the
> comparison cost is roughly O(N^2) in the string length, and the reason for
> having a limit at all is to ensure the function runtime doesn't get out of
> hand --- but it seems likely to me that 255 is an unnecessarily
> conservative limit. If you wanted to do a few tests and report back on
> just how slow it can get, we might be persuaded to raise the stock
> setting.
>
> regards, tom lane
>
I've checked that and I think we could raise the limit without any problem
I've set
#define MAX_LEVENSHTEIN_STRLEN 255 * 255
I was using the levenshtein function comparing two strings of the same
length
Strings length: 640
Difference: 531
Time: 2.5ms
Strings length: 1920
Difference: 1258
Time: 20ms
Strings length: 5760
Difference: 1811
Time: 146ms
regards,
Szymon
From | Date | Subject | |
---|---|---|---|
Next Message | John R Pierce | 2013-09-06 21:19:33 | Re: Levenshtein Distance with more than 255 characters |
Previous Message | pg noob | 2013-09-06 20:54:58 | select DISTINCT |