Делфи. Вопросы возникающие в ходе обучения

[Student2007]

PAV
понял. Спасибо.

[Student2007]

За реализацию пока не брался.. Собираю информацию:)... Нашел алгоритм, применяемый в rsync.
http://www.openbsd.ru/docs/rsync.html
Особое внимание уделил именно механизму поиска сигнатур. Может такой алгоритм производительный?. Пока разобрался только с работой Adler32 (получение контрльных сум). Однако есть ряд вопросов, весь день провел в размышлениях и поиске информации. Описание начиная с поиска сигнатур - сверхкраткое...

Цитата:

На первом уровне формируется хеш-таблица размером в 2^16 элементов.

тут, я так понимаю просто выделяется память под элементы (динамический массив, напрример.

Цитата:

Ключом хеш-функции является быстрая 32 битная сигнатура.

тоесть полученная контрльная сумма последовательности из двух байт.

Цитата:

Для каждой пары быстрой и стойкой сигнатуры, полученной от Beta, вычисляется 16 битный хеш 32 битной сигнатуры, после чего все это сортируется согласно 16 битному хешу.

здесь уже не понятно, откуда взялась стойкая сигнатура? Так же не понятно каким образом вычисляется хеш и какой сигнатуры (чувствую, что нестойкой). На счет сортировки понятно вроде.

Цитата:

Каждый элемент хеш-таблицы указывает на первый элемент сортированных сигнатур, хеш значения которых совпадают, либо хранит в себе NULL, если сигнатур с таким хешом нет.

Тут тоже непонятно. Происходит сравнение сигнатур пар байт, содержащикся в файле со всевозможными пар-байтами, тоесть с выделенным и уже заполненным масивом?.

Цитата:

Номер элемента хеш-таблицы соответствует значению хеш-функции, а именно сумме двух половин быстрой 32 битной сигнатуры.

на счет суммы двух половин понятно, в принципе и начало понятно, номер же всегда должен чему-то соответствовать, только вот тут складывается впечатление, что используется еще какая-то хэш-таблица...
****
что усложняет ситуацию, так это то, что данный материал один-в-один выложен на многих ресурсах. Другими словами, после тщатильных поисков ни чего, кроме копий этой статьи найдено не было....

[PAV]

Я вроде примерно понимаю, в чем тут дело, но это ничего нового для Вашей задачи не дает. Идея в том, что имеется способ сравнительно быстро посчитать 32-битную быструю сигнатуру для всех блоков длины L. Результаты мы хотим запомнить, чтобы уметь по заданной сигнатуре быстро находить все соответствующие блоки. Но использовать ключ длиной 32 бита нельзя, их слишком много. Поэтому используется 16-битный хеш. Все сигнатуры с одинаковым значением хеша объединяются в одну группу. Число групп таким образом не превосходит $2^{16}$, что вполне разумно. Имея сигнатуру, которую нужно найти, мы просто последовательно просматриваем всю группу (линейный поиск) и ищем.

[Student2007]

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

[PAV]

Мы ищем все блоки, имеющие заданную сигнатуру. Ничего более детального сказать не могу, но я не вижу здесь ничего особенно экстраординарного. Достаточно стандартное применение хеш-функций.

Добавлено спустя 38 секунд:

Не заморачивайтесь, в Вашем случае все выглядит проще.

[Student2007]

сейчас реально запутался... текст уже раз 4й стираю... Вобщем, еслы пока мыслить в масштабе двух строчек, то требуется сделать:
сформировать массив из 200-1 слов, в котором будут последовательно размещены 1 и 2 байт, потом 2 и 3 байт и т.д..
После этого, брать, начиная с первого по 2 байта и сравнивать их с массивом, если совпадение есть, то взять еще 2 байта, на этот раз 2 - 3 и сравнить с массивом и атк далее до первого несовпадения.. После несовпадения запомнить номера байтов, которые совпали и из них сформировать последовательность, которую отправить в буфер; и снова брать по два байта и производить аналогичные сравнения, таким образом мы получим повторяющиеся последовательности в масштабах 2х строк.. Аналогичные сравнения призвести с третьей строкой, четвертой и т.д. Верно?

Добавлено спустя 11 минут 10 секунд:

перед этим нужно сформированный массив отсортировать и тогда можно применить уже бинарный поиск в этом массиве

[Student2007]

не, бред.. Как оказалось, много думать - тоже вредно..

[PAV]

Вы планируете действовать по той схеме, которую я описывал? Для начала я предлагал для каждой пары байтов подсчитать количество строк,в которых эта пара встречается. Это понятно, как сделать?

[Student2007]

PAV
да, по вашей схеме.. Как подсчитать количество строк, в которой есть пара байтов понятно, чуть позже код приведу.

Добавлено спустя 13 минут 26 секунд:

пока так думаю сделать, но это не правильно..:

      SetLength(Table,65536); //динамический массив
      for i:=0 to 65535 do Table[i]:=i;
      new(node2); //второй список в котором сохраняем номер строки, символ, его позицию.
      curr2:=head2; //текущий элемент 2го списка
      pre2:=nil; //предыдущий элемент второго списка
      CountElements2:=0; //счетчик количества элементов в списке
      for i:=0 to 65535 do begin
        for j:=1 to 199 do begin
          curr:=head; //в первом списке хранятся строки по 200 байт
          for a:=1 to CountElements do begin
            wordBuf:=curr^.field1[j]; //field1 - собственно строки
            wordBuf:=WordBuf shl 8;
            wordBuf:=WordBuf+curr^.field1[j+1];
            if Table[i]=wordbuf then begin
              node2^.Element:=wordbuf; //сохраняем элемент
              node2^.Count:=node2^.Count+1; //сколько раз встречался в строке
              node2^.pos:=j; // позиция символа в строке
              node2^.numberStr:=a; //номер строки
              Node2^.next:=head2; 
              head2:=node2;
              CountElements2:=CountElements2+1;
            end;
            curr:=curr^.next;
          end;
        end;
      end;

Это однозначно не правильно, но суть о чем я думаю видна наверное:)

Добавлено спустя 4 минуты 26 секунд:

тоесть, если словестно описать, то я сначала формирую массив из 65536 элементов. Каждый элемент - слово.
Далее я с каждой строки беру 2 байта и склеиваю их в переменную wordBuf.
На следующем этапа я сравниваю с 1го по 65536 элемент массива Table сначала с первыми двумя байтами каждой строки. Затем массив TABLE со вторым-третим байтами каждой строки и т.д. Результат записываю в список (кстати в приведенном коде не правильно записываю - это очевидно. Не вдумывался, потому что цикл от 1 до 65536 слишком долгий и я хочу от него избавиться).

[PAV]

Хорошо. Также для увеличения скорости было бы полезно сохранять информацию обо всех местах вхождения каждой пары, чтобы их можно было быстро перебирать. Можно обойтись и без этого, тогда придется перебирать полным поиском.

Далее так. В цикле перебираем все пары байтов ab, которые встречаются в половине всех строк.

Для каждой такой пары находим все ее вхождения в строки. Для каждого вхождения смотрим на следующий байт и по той же схеме, что и в начале, подсчитываем вхождения всех троек вида abc в строки. Таким образом найдем все тройки, которые встречаются в половине всех строк. Здесь вопросы есть?

Добавлено спустя 2 минуты 14 секунд:

Нет, Ваш способ выше однозначно неправильный. Не нужно цикла по всем возможным парам байтов. Нужно взять наблюдаемую пару и интерпретировать ее как целое число от 0 до 65535. Это будет индекс в массиве.

[Student2007]

Что-то не понимаю... Давайте тогда мыслить в пределах определенного количества строк, может тогда смогу понять. Пусть строк, например 3. В них точно есть последовательость байт, которая встречается в о всех трех строках. Тогда нужно:
1. Взять первый и второй байт с первой строки, склеить их (тоесть интерпертировать как число от 0 до 65535. (пусть мы их сохраним в wordBuf1).
2. Взять первый и второй байт со второй строки, так же представить их в виде числа от 0 до 65535. (пусть мы их сохраним в wordBuf2).
3. Сравнить wordBuf1 и wordBuf2, если они равны, то запомнить номер второй строки, нипример в список, если совпадения нет то перейти к 4му шагу.
4. Взять первый и второй байты уже с третей строки. Так же представить их в виде числа и занести в wordBuf2 для сравнения.

Количество элементов списка будет являться количеством строк, в которых встречается пара байтов..
**
это как бы первый подэтап, если правильно - продолжу...

Добавлено спустя 3 минуты 32 секунды:

хм.. сейчас подумал.. строки то мы сохраним, да, но строки, в которых не встретится первая пара байт мы из обработки исключаем, а здесь может так получиться, что результата на выходе мы не получим. Вдруг в исключеных строках есть более интересная последвоательность, встречающаяся только в исключенных строках?.. Более интересная - в смысле более длинная.

[PAV]

Нет, нет. Все не так.

Имеем два массива длиной 65536. Первый назовем LinesCount, второй - LastLineIndex. В начале работы LinesCount заполнен нулями, а LastLineIndex - минус единицами (например).

Последовательно перебираем все пары байт с первой строки. Каждую пару интерпретируем как целое число i - индекс в этих массивах.

Взяв очередную пару байт и пребразовав ее в индекс i, смотрим сначала значение LastLineIndex[i]. Если оно равно индексу текущей строки, то это означает, что данная пара байтов уже встречалась в этой строке раньше и считать ее повторно не нужно. Если же не равно, то кладем его туда и увеличиваем на единицу значение LinesCount[i].

После окончания этой процедуры значение LinesCount[i] будет равно числу строк, в которых встретилась пара байтов с индексом i.

[Student2007]

А что Вы понимаете под словом "интерпретируем"? тоесть каждую пару байт преобразуем в соответствующее число и сохраняем в массив LastLineIndex[i] ?

вот например строка (для удобства разделил пробелами
):

Цитата:

ByteStr: array [0..15] of byte
= 70 72 69 76 65 74 20 6B 61 6B 20 64 65 6C 61 3F

тогда:

      SetLength(LinesCount,65536);
      for i:=0 to 65535 do LinesCount[i]:=0;
      SetLength(LastLineIndex,65536);
      for i:=0 to 65535 do LastLineIndex[i]:=-1;
{Последовательно перебираем все пары байт с первой строки. Каждую пару интерпретируем как целое число i - индекс в этих массивах.}
      for i:=0 to Length(ByteStr)-1 do begin
         wordBuf:=ByteStr[i]; 
         wordBuf:=WordBuf shl 8; 
         wordBuf:=WordBuf+ByteStr[i+1];
         LastLineIndex[i]:=wordBuf;
      end;

массив LinesCount определить как массив of word, а массив LastLineIndex - как integer?

Добавлено спустя 1 минуту 51 секунду:

PAV в сообщении #207761 писал(а):

Последовательно перебираем все пары байт с первой строки. Каждую пару интерпретируем как целое число i - индекс в этих массивах.

тоесть я пока вот это описал:)

[PAV]

Число wordBuf - это и есть индекс, по которому надо обращаться в массивах. LastLineIndex[wordBuf] и LinesCount[wordBuf]

[Student2007]

PAV
кажись теперь понял, спасибо. сейчас оформлю свои мысли=)

Добавлено спустя 41 минуту 43 секунды:

Думаю так:

      SetLength(LinesCount,65536);
      for i:=0 to 65535 do LinesCount[i]:=0;
      SetLength(LastLineIndex,65536);
      for i:=0 to 65535 do LastLineIndex[i]:=-1;
      curr:=head;
      for j:=0 to CountElements-2 do begin
        curr:=Curr^.next;
        for i:=1 to 199 do begin
          wordBuf:=Curr^.field1[i];
          wordBuf:=WordBuf shl 8;
          wordBuf:=WordBuf+Curr^.field[i];
          if LastLineIndex[WordBuf]<>j then begin
            LinesCount[WordBuf]:=LinesCount[WordBuf]+1;
            LastLineIndex[WordBuf]:=j;
          end;
        end;
      end;

мысль я уловил.. Пишу дальше

Добавлено спустя 12 минут 56 секунд:

CountElements - это количество элементов в списке или другими словами общее количество строк

Добавлено спустя 39 минут 45 секунд:

Не, дальше написать ни чего не получилось... Вобщем написание я сейчас немного поменяю, что бы еще запомнить номера строк, где встречается пара байтов. Пригодится в будущем. Пока идей нет.