Дубликат поиска текста

Question

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

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

в это:

[d+c+d+f+]4

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

L16 $ ED $ EF $ A9 p20,20 > Ecegb> д Й + d + F + а +> с + <а + е + а + е + D + <b>е + D + <Б.Ф. + > С cegbgegec ес <ая > D + C + D + F + D + C + D + F + D + C + D + F + D + C + D + F + r1 ^ 1

/ L8 r1r1r1r1 е + <а +> F + G + CG + r4 а + с + а + г + CG + R4f + <а +> F + G + CG + r4 а + с + а + г + CG + R4f + <а +> F + G + CG + r4 а + с + а + г + CG + r4 е + <а +> F + G + CG + r4 а + с + а + г + r4g + 16f16c + а + 2 ^ г + F + G + 4 е + ТФ + 4fd + f4 D + C + D + 4c + с <а + 2 ^ 4 > C4d + <Г + 2 ^ 4r4 ^ а +> C + D + 4g + 4а + 4 г1 ^ 2 ^ 4 ^ а + 2 ^ г + F + G + 4 е + ТФ + 4fd + f4 D + C + D + 4c + с <а + 2 ^ 4 > C4d + <Г + 2 ^ 4r4 ^ а +> C + D + 4g + 4а + 4 r1 ^ 2 ^ 4 ^ r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1

# 4 @ 22 v250 y10

L8 а3 гк + гк + гк + гк + гк + гк + гк + гк + гк + гк + гк + гк + гк + гк + гк + гк + гк + гк + гк + гк + гк + гк + гк + гк + / r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1

# 2 @ 4 v155 y10

L8 $ ED $ F8 $ 8F o4 r1r1r1 D + 4f4f + 4g + 4 а + 4r1 ^ 4 ^ 2 / г + 4 ^ FR2 е + 4 ^ fr2d + 4 ^ fr2 е + 4 ^ fr2d + 4 ^ fr2 е + 4 ^ fr2d + 4 ^ fr2 е + 4 ^ fr2 > г + 4 ^ FR2 е + 4 ^ fr2d + 4 ^ fr2 е + 4 ^ fr2 < е + 4 ^ г + г2 е + 4 ^ fr2f + 4 ^ г + г2 е + 4 ^ fr2f + 4 ^ г + г2 е + 4 ^ fr2f + 4 ^ г + г2 е + 4 ^ fr2f + 4 ^ г + г2 е + 4 ^ fr2f + 4 ^ г + г2 е + 4 ^ fr2f + 4 ^ г + г2 е + 4 ^ fr2f + 4 ^ г + г2 е + 4 ^ fr2 > а + 4 ^ г + г2 е + 1 +-^ г + г2 е + 1 е + 4 ^ fr2 D + 1 е + 4 ^ fr2 D + 2 ^ й + 4 ^ r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1

# 3 @ 10 v210 y10

r1 ^ 1 а3 c8r8d8r8 c8r8c8r8c8r8c8r8c8r8c8r8c8r8c8r8c8r8c8r8c8r8 с8 @ 10d16d16 @ 21 с8 @ 10d16d16 @ 21 с8 @ 10d16d16 @ 21 / с4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8 с4 @ 10d8 @ 21c8 @ 10d16d16d16d16d16r16 с4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 < b8> с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 c8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8c4 @ 10d8 @ 21c8 с8 @ 10d8 @ 21c8 с4 @ 10d8 @ 21c8 @ 10b16b16> c16c16 # 7 @ 16 v230 y10

L16 $ ED $ EF $ A9 cceeggbbggeeccee д + д + ж + ж + а + а + е + F + D + D + д + д + cceeggeecc куб.см <Д + д + бб> д + д + FFD + D +

# 5 @ 4 v155 y10

L8 $ ED $ F8 $ 8F o4 r1r1r1r1 д + 4r1 ^ 2 ^ 4 / <А + 4 ^> о2 с + 4 ^ о2 <а + 4 ^> о2 с + 4 ^ о2 <а + 4 ^> о2 с + 4 ^ о2 <а + 4 ^> о2 с + 4 ^ о2 а + 4 ^> о2 с + 4 ^ о2 <А + 4 ^> о2 с + 4 ^ с r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1 r2 е + 4 ^ fr2 D + 1f + 4 ^ FR2 D + 1 с + 4 ^ о2 <А + 1 > С + 4 ^ о2 <А + 2 ^ а + 4 ^ r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1 </p>

Answer 1

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

Я взял строку "testtesttesttest4notaduped + c + d + f + d + c + d + f + d + c + d + f + d + c + d + f + testtesttest" и преобразовал ее в "[test] 4 4notadupe [d + c + d + f +] 4 [test] 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.Compression ?