Дифференциальный алгоритм C ++ - PullRequest
Новая
       15

Дифференциальный алгоритм C ++

3 голосов
/ 28 мая 2011

Я пытаюсь создать программу на C ++, которая может различать два файла .txt. 

struct line
{
    string text;
    size_t num;
    int status;
};

void compareFiles(vector<line> &buffer_1, vector<line> &buffer_2, size_t index_1, size_t index_2)
{
    while(index_1 < buffer_1.size())
    {
         while(index_2 < buffer_2.size())
         {  
             X = buffer_1[index_1].text;
             Y = buffer_2[index_2].text;
             if(X == Y)
             {
                 ++index_1;
                 ++index_2;
             }
             else
             {
                 LCS();
                 string lcs = printLCS(X.length(), Y.length());

                 /*
                 * Here's my problem
                 */

             }
         }
     }
 }

Как видите, у меня есть два буфера (вектора строк), ранее загруженных содержимым файлов. У меня также есть алгоритм LCS полностью функциональным (проверено). LCS работает со строками X и Y, определенными глобально.

Итак, что мне действительно нужно, это сравнивать буферы построчно с LCS, но мне не удалось найти способ сделать это.

Не могли бы вы мне помочь?

Ответы [ 2 ]

6 голосов
/ 28 мая 2011

Когда сомневаешься, я обычно полагаюсь на того, кто делал это раньше. Почтенная программа diff существует всегда и делает то, что вы хотите. Кроме того, это открытый исходный код, поэтому зайдите на ftp: //mirrors.kernel.org/gnu/diffutils/diffutils-3.0.tar.gz и проверьте его.

После того, как вы распакуете архив, откройте файл src / analysis.c. Функция diff_2_files начинается со строки 472. Код, который выполняет фактическое сравнение, запускается из строк 512 - 537. Они воспроизводятся ниже: 

for (;; cmp->file[0].buffered = cmp->file[1].buffered = 0)
{
    /* Read a buffer's worth from both files.  */
    for (f = 0; f < 2; f++)
        if (0 <= cmp->file[f].desc)
            file_block_read (&cmp->file[f],
                buffer_size - cmp->file[f].buffered);

    /* If the buffers differ, the files differ.  */
    if (cmp->file[0].buffered != cmp->file[1].buffered
            || memcmp (cmp->file[0].buffer,
                    cmp->file[1].buffer,
                    cmp->file[0].buffered))
    {
        changes = 1;
        break;
    }

    /* If we reach end of file, the files are the same.  */
    if (cmp->file[0].buffered != buffer_size)
    {
        changes = 0;
        break;
    }
}

Идея состоит в том, чтобы загрузить два буфера одинакового размера, а затем загрузить каждый файл в буфер. Сравните два файла по одному буферу за раз, используя memcmp, и посмотрите, отличается ли какой-либо буфер от другого. Если какое-либо сравнение буферов не возвращает равных, тогда эти два файла различны. Также важно отметить, что вам никогда не нужно считывать больше двух буферов данных за раз, поэтому этот подход работает и с большими файлами.

0 голосов
/ 28 мая 2011

Прежде всего, я бы переписал LCS(), чтобы взять две строки в качестве параметров и вернуть самую длинную общую последовательность - я представляю сигнатуру функции, подобную std::string LCS(const line& lhs, const line& rhs).Затем я изменил бы ваши циклы while следующим образом. 

for(int i = 0; i < buffer_1.size(); ++i)
{
    for(int j = 0; j < buffer_2.size(); ++j)
    {  
        std::string lcs = LCS(buffer_1[i].text, buffer_2[j].text);
        std::cout << "LCS[" << i << "][" << j << "]: " << lcs << std::endl;
    }
}

Это найдет и напечатает самую длинную общую последовательность для каждой комбинации строк в buffer_1 и buffer_2.Вы хотите этого?Правильно ли я понял ваш вопрос?

...