Поиск дубликатов текста

Question

Моя главная проблема заключается в попытке найти подходящее решение для автоматического включения этого, например:

d+c+d+f+d+c+d+f+d+c+d+f+d+c+d+f+

в это:

[d+c+d+f+]4

т. е.Нахождение дубликатов рядом друг с другом, затем создание более короткого "цикла" из этих дубликатов.Пока я не нашел подходящего решения для этого, и я с нетерпением жду ответа.P.S.Чтобы избежать путаницы, вышеупомянутый образец - не единственное, что нуждается в "циклировании", он отличается от файла к файлу.О, и это предназначено для программ на C ++ или C #, подойдет и то, и другое, хотя я открыт и для любых других предложений.Кроме того, основная идея заключается в том, что вся работа будет выполняться самой программой, никакого пользовательского ввода, кроме самого файла.Вот полный файл, для справки, мои извинения за растянутую страницу:#0 @16 v225 y10 w250 t76

l16 $ED $ EF $ A9 стр. 20,20 >ecegb> d<bgbgecgec<g>d +<b>d + f + a+>c+<a+f+a+f+d+<b>f + d+<bf+>c<a>cegbgegec<a>ес<ae> d +c + d + f + d + c + d + f + d + c + d + f +d+c +d +f+ r1^1

/ l8 r1r1r1r1 f +<a+>f + g + cg + r4 a + c + a + g + cg + r4f +<a+>f + g + cg + r4 a + c + a + g + cg + r4f +<a+>f + g + cg + r4 a + c + a + g + cg + r4 f +<a+>f + g + cg + r4 a + c + a + g + r4g + 16f16c + a + 2^ g + f + g + 4 f + ff + 4fd + f4 d + c + d + 4c + c<a+2^4>c4d + <g+2^4r4^ a+="">c + d + 4g + 4a + 4 r1 ^2^ 4 ^ a + 2 ^ g + f + g + 4 f + ff + 4fd + f4 d + c + d + 4c + c<a+2^4>c4d + <g+2^4r4^ a+="">c + d + 4g + 4a + 4 r1^2^ 4^ r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1

#4 @22 v250 y10

l8 o3 рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+рг+ / r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1

#2 @4 v155 y10

l8 $ED $ F8 $ 8F o4 r1r1r1 d + 4f4f + 4g + 4 a + 4r1 ^ 4 ^ 2 / d + 4 ^ fr2 f + 4 ^ fr2d + 4^ fr2 f + 4 ^ fr2d + 4 ^ fr2 f + 4 ^ fr2d + 4^fr2 f+4^fr2 > d + 4 ^ fr2 f + 4 ^fr2d + 4 ^ fr2 f + 4^ fr2 < f+4^g+r2 f+4^fr2f+4^ g + r2 f + 4^fr2f + 4^ g + r2 f + 4^ fr2f + 4^ g + r2 f+4^fr2f+4^ g + r2 f + 4^fr2f + 4^ g + r2 f + 4^ fr2f + 4^ g + r2 f + 4 ^fr2f + 4^ g + r2 f + 4 ^ fr2 > a + 4^ g + r2 f + 1a + 4 ^ g + r2 f + 1 f + 4 ^ fr2 d + 1 f + 4 ^ fr2 d + 2 ^ d + 4^ r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1

#3 @10 v210 y10

r1^1 o3 c8r8d8r8 c8r8c8r8c8r8c8r8c8r8c8r8c8r8c8r8c8r8c8r8c8r8c8r8c8r8r8 c8 @10d16d16@21 c8 @10d16d16@21 c8 @10d16d16@21 / c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8 c4@10d8@21c8<b8> @10d16d16d16d16r16 c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8c4@10d8@21c8<b8>c8@10d8@21c8 c4@10d8@21c8 @10b16b16>c16c16

#7 @16 v230 y10

l16 $ED $ EF $ A9 cceeggbbggeeccee <bb>d + d + f + f + a+ a + f + f + d + d + d +<bb>d+ d+ <aa>cceeggeecc<aa>cc <g+g+bb>d+d + ffd +d+

#5 @4 v155 y10

l8 $ED $F8 $ 8F o4 r1r1r1r1 d + 4r1 ^2^ 4 / <a+4^>cr2 c + 4^ cr2<a+4^>cr2 c +4^ cr2<a+4^>cr2 c + 4^ cr2<a+4^>cr2 c + 4^ cr2 a +4^> cr2 c + 4^cr2 <a+4^>cr2 c+4^c r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1 r2 f + 4 ^ fr2 d + 1f + 4 ^fr2 d + 1 c + 4 ^ cr2 <a+1>c + 4^ cr2

Answer 1

Не уверен, что это то, что вы ищете.

Я взял строку "testtesttest4notaduped + c + d + f + d + c + d + f + d + c + d + f + d + c + d + f + testtesttest" и преобразовал ее в "[тест] 4 4notadupe[d + c + d + f+]4 [тест] 3 "

Я уверен, что кто-нибудь придумает лучшее, более эффективное решение, поскольку это немного замедляет обработку вашего полного файла.Я с нетерпением жду других ответов.

        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;
                }
            }
        }

Answer 2

Вы можете использовать алгоритм Смита-Уотермана для выполнения локального выравнивания, сравнивая строку с самой собой.

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

Редактировать:Чтобы адаптировать алгоритм для самостоятельного выравнивания, вам нужно принудительно привести значения по диагонали к нулю - то есть оштрафовать за тривиальное решение точного выравнивания всей строки с самой собой.Тогда вместо этого появится "второе лучшее" выравнивание.Это будут самые длинные две совпадающие подстроки.Повторите то же самое, чтобы найти постепенно сокращающиеся совпадающие подстроки.

Answer 3

LZW может помочь:он использует словарь префиксов для поиска повторяющихся шаблонов и заменяет такие данные ссылками на предыдущие записи.Я думаю, что адаптировать его к вашим потребностям не составит труда.

Answer 4

Почему бы просто не использовать System.IO.Сжатие?