in reply to Re^5: Suffix-prefix matching done right
in thread Suffix-prefix matching done right
A disagree, rather at most O(N*log N) for base64 input and a given max distance.
My algorithm based on Re: Suffix-prefix matching done right correctly calculated 1million overlaps with up to 6 errors in 2 seconds 53 sec , without being particularly tuned for speed.
You just have to avoid impossible matches right from the beginning and to bail out with the longest match.
Nobody needs all Levenshtein distances for all combinations.
Parameters:
my $n_tests = 1_000_000; my $error= 1+ int rand 5; my $A = rand64($n_err + 1 + rand 50); my $B = rand64($n_err + 1 + rand 50); my $prefix = rand64($n_err + 1 + rand 20); > Took: 2.20354223251343 sec
update
sorry> Took: 53.5716695785522
I forgot a bail-out flag.
I'll try now strings with 2000 bytes ...
update
my $n_tests = 100_000; my $min_str = 2000;# 50; my $max_overlap = 500; #20; > Took: 56.4621770381927
as I said, it's still tuned for correctness not for performance
Cheers Rolf
(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^7: Suffix-prefix matching done right (updated)
by NERDVANA (Deacon) on Nov 06, 2021 at 18:24 UTC | |
by LanX (Saint) on Nov 06, 2021 at 18:35 UTC | |
by NERDVANA (Deacon) on Nov 07, 2021 at 08:02 UTC |