ansaurus

Question

Answer 1

+2 A:

You can use the Smith-Waterman algorithm to do local alignment, comparing the string against itself.

http://en.wikipedia.org/wiki/Smith-Waterman_algorithm

EDIT: To adapt the algorithm for self alignment, you need to force values in the diagonal to zero - that is, penalize the trivial solution of aligning the whole string exactly with itself. Then the "second best" alignment will pop out instead. This will be the longest two matching substrings. Repeat the same sort of thing to find progressively shorter matching substrings.

Kevin Beck 2009-05-13 19:06:58

Answer 2

A:

Why not just use System.IO.Compression?

Mike Curry 2009-05-13 19:20:43

Mainly because "The strings need to be longer than 3-400 characters" kind of makes this method unwanted.

Onion 2009-05-13 19:25:29

Answer 3

+1 A:

Not sure if this is what you are looking for.

I took the string "testtesttesttest4notaduped+c+d+f+d+c+d+f+d+c+d+f+d+c+d+f+testtesttest" and converted it to "[test]4 4notadupe[d+c+d+f+]4 [test]3 "

I'm sure someone will come up with a better more efficient solution as it's a bit slow when processing your full file. I look forward to other answers.

        string stringValue = "testtesttesttest4notaduped+c+d+f+d+c+d+f+d+c+d+f+d+c+d+f+testtesttest";

        for(int i = 0; i < stringValue.Length; i++)
        {
            for (int k = 1; (k*2) + i <= stringValue.Length; k++)
            {
                int count = 1;

                string compare1 = stringValue.Substring(i,k);
                string compare2 = stringValue.Substring(i + k, k);

                //Count if and how many duplicates
                while (compare1 == compare2) 
                {
                    count++;
                    k += compare1.Length;
                    if (i + k + compare1.Length > stringValue.Length)
                        break;

                    compare2 = stringValue.Substring(i + k, compare1.Length);
                } 

                if (count > 1)
                {
                    //New code.  Added a space to the end to avoid [test]4 
                    //turning using an invalid number ie: [test]44.
                    string addString = "[" + compare1 + "]" + count + " ";

                    //Only add code if we are saving space
                    if (addString.Length < compare1.Length * count)
                    {
                        stringValue = stringValue.Remove(i, count * compare1.Length);
                        stringValue = stringValue.Insert(i, addString);
                        i = i + addString.Length - 1;
                    }
                    break;
                }
            }
        }

Chris Persichetti 2009-05-13 21:19:50

Thanks, this works perfectly. I'm not sure what you meant when you said it was slow for the whole file, as it seems quite quick to me. (1-3 seconds at most) But thank you very much, regardless.

Onion 2009-05-16 11:21:45

Answer 4

+1 A:

LZW can help: it uses prefixes dictionary to search for repetitive patterns and replaces such data with references to previous entries. I think it should not be hard to adapt it for your needs.

Rageous 2009-05-14 07:11:14

Interactive LZW compression applet: http://www.cs.sfu.ca/CC/365/li/squeeze/LZW.html

Rageous 2009-05-14 07:17:12

ansaurus

tags:

views:

answers:

Duplicate text-finding

related questions