> at least O(N^2)

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
[download]

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
[download]

as I said, it's still tuned for correctness not for performance

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

OP said it could also be deletions and insertions. So the xor trick won't work. Without more information from OP, we can only guess, but I was guessing this was a genetics problem trying to build DNA sequences from fragments, and the mention of base64 was just mock data to test the algorithm. If the data can have random insertions, deletions, and swaps, then you need the full DP algorithm. *IF* the number of acceptable errors is low, then yes you can short-circuit it and maybe end up close to linear, but then there's stil the added complexity of deciding how much overlap gives the best result.

What about a correct algorithm plus parallelization? If this problem is embarrassingly parallel. And I think it is. Or may be it is. I always have doubts. Best regards, Karl

I haven't seen a parallelizable disk drive yet...

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

I haven't seen a parallelizable disk drive yet...

Here you go ;-)

Please take a look at mce_loop_f { code } file from MCE::Loop. And didn’t we have a debate here some years ago where marioroy convinced our beloved former leader BrowserUk that some things look different today? I couldn’t find this inspiring thread in a hurry as I’m on a mobile device and in a hurry. Best regards, Karl

«The Crux of the Biscuit is the Apostrophe»