Существует периодическая последовательность данных, в которой непрерывно друг за другом идут одинаковые блоки данных по 64 бит. Границ между блоками нет, то есть, начиная с любого места мы можем взять 64 бита данных — это некий код, который раз за разом повторяется.
Вопрос. Существует ли какой-нибудь алгоритм сравнения двух таких последовательностей, помимо брутфорса (то есть сдвига на единичку и сравнения 64*64)? Может, например, можно вычислить какой-нибудь хеш, значение которого не будет зависеть от места, с которого мы начали его вычислять?
Здравствуйте, sz36, Вы писали:
S>Hi, All!
S> Существует периодическая последовательность данных, в которой непрерывно друг за другом идут одинаковые блоки данных по 64 бит. Границ между блоками нет, то есть, начиная с любого места мы можем взять 64 бита данных — это некий код, который раз за разом повторяется.
S> Вопрос. Существует ли какой-нибудь алгоритм сравнения двух таких последовательностей, помимо брутфорса (то есть сдвига на единичку и сравнения 64*64)? Может, например, можно вычислить какой-нибудь хеш, значение которого не будет зависеть от места, с которого мы начали его вычислять?
Любой алгоритм поиска подстроки в строке — ищете подстроку первой последовательности длиной 64 бита в подстроке второй длиной 128 бит.
Правда с учётом маленькой длины строк это может оказаться не слишком оптимально — вполне вероятно что быстрее всего будет как раз 64 раза сделать циклический сдвиг в int64.
Здравствуйте, dilmah, Вы писали:
D>это небольшая вариация задачи http://en.wikipedia.org/wiki/Cycle_detection
Ну не знаю... Я что-то не улавливаю связи. В моем случае не нужно находить ни период цикла — он известен, ни его начало — это первый бит, с которого мы начали. А вопрос алгоритма вычисления текущего хеша зайца и черепахи в конкретной точке с минимальной трудоемкостью остается в описании за кадром. Как определить на очередном шаге алгоритма, догнал он ее или нет?
Здравствуйте, RomikT, Вы писали:
RT>Любой алгоритм поиска подстроки в строке — ищете подстроку первой последовательности длиной 64 бита в подстроке второй длиной 128 бит.
Ну это способ очевидный, но он не кажется мне слишком хорошим, во всяком случае, самым лучшим.
1) Все это крутится на 8-битном процессоре с серьезными ограничениями как по памяти, так и по быстродействию.
2) В принятой последовательности возможны отдельные ошибки, то есть надо еще выбрать кусок для сравнения, от них свободный
3) Задача, собс-но, в том, чтобы приняв несколько последовательностей-образцов (которые тоже, возможно, содержат ошибки) в дальнейшем сравнивать их с вновь принятыми. Для чего для каждой последовательности-образца нужно сохранять некий код, который потом и сравнивать.
Если решать в лоб, то нужно взять 64 бита образца, убедиться, что они совпадают со следующими 64 битами (если нет — взять другой кусок), сохранить, и затем искать эти 64 бита в новой последовательности как подстроку в строке. Меня интересует, нет ли какого-нибудь более изящного решения.
S> В моем случае не нужно находить ни период цикла — он известен, ни его начало — это первый бит, с которого мы начали.
тогда нужно просто взять любой хэш от байт в пределах длины цикла, но для того чтобы хэш сдвинутых последовательностей был одинаковым нужно просто перед взятием хэша "нормализовать" последовательность -- выбрать начало от которого вычислять хэш каким-то нормализованным способом -- скажем начать с минимального 64-битного блока (если таковых несколько в пределах одного цикла, то рассамтривать и следующие биты).
Вообще, очевидно, что эта возня с хэшами будет оправданной только если нужно сравнивать не 2 последовательности, а много.
Здравствуйте, sz36, Вы писали:
S>Здравствуйте, RomikT, Вы писали:
RT>>Любой алгоритм поиска подстроки в строке — ищете подстроку первой последовательности длиной 64 бита в подстроке второй длиной 128 бит. S> Ну это способ очевидный, но он не кажется мне слишком хорошим, во всяком случае, самым лучшим. S>1) Все это крутится на 8-битном процессоре с серьезными ограничениями как по памяти, так и по быстродействию. S>2) В принятой последовательности возможны отдельные ошибки, то есть надо еще выбрать кусок для сравнения, от них свободный S>3) Задача, собс-но, в том, чтобы приняв несколько последовательностей-образцов (которые тоже, возможно, содержат ошибки) в дальнейшем сравнивать их с вновь принятыми. Для чего для каждой последовательности-образца нужно сохранять некий код, который потом и сравнивать.
S> Если решать в лоб, то нужно взять 64 бита образца, убедиться, что они совпадают со следующими 64 битами (если нет — взять другой кусок), сохранить, и затем искать эти 64 бита в новой последовательности как подстроку в строке. Меня интересует, нет ли какого-нибудь более изящного решения.
Если адресация восьми битная, то операция (1) «И» байтов i и i+4. Если попадается повторяющаяся последовательность, то она либо четко попадет на границу, тогда получим все нули. Если есть частичное попадание в повторяющуюся последовательность(сдвиг) то дадут подряд нули последние биты, но, по любому должны дать нули и операции «И» с байтами (2) i+1 и i+5, (3)i+2 и i+6. А дальше операция (4) i+3 и i+7 должна дать нули в тех разрядах, что в первом сравнении (операция 1) были единицы (отот сдвиг). Скомбинируй логическую операцию из первого и последнего сравнения. Мне в лом думать. Вот и получишь..чего хочешь.
Могу подсказать, что проверку на последние нули, я бы сделал инвертированием результата, а потом есть, кажется, команда вычисляющая количество ненулевых битов. И переход по таблице с полученным значением. Там не так много вариантов будет. Ну, думаю, мысль понял. Удачи! Будут вопросы пиши.
Здравствуйте, sz36, Вы писали:
S> Вопрос. Существует ли какой-нибудь алгоритм сравнения двух таких последовательностей, помимо брутфорса (то есть сдвига на единичку и сравнения 64*64)? Может, например, можно вычислить какой-нибудь хеш, значение которого не будет зависеть от места, с которого мы начали его вычислять?
Возьмите из произвольного места последовательности 64 бита, и приведите их в "каноническую форму". Скажем, циклически разверните так, чтобы получилось наименьшее из возможных 64-битных чисел. Сделайте то же самое со второй последовательностью. Если полученные числа совпали, совпадают и последовательности
Здравствуйте, sz36, Вы писали:
S>1) Все это крутится на 8-битном процессоре с серьезными ограничениями как по памяти, так и по быстродействию. S>2) В принятой последовательности возможны отдельные ошибки, то есть надо еще выбрать кусок для сравнения, от них свободный S>3) Задача, собс-но, в том, чтобы приняв несколько последовательностей-образцов (которые тоже, возможно, содержат ошибки) в дальнейшем сравнивать их с вновь принятыми. Для чего для каждой последовательности-образца нужно сохранять некий код, который потом и сравнивать.
Если последовательности совпадают не точно, можно воспользоваться следующим алгоритмом. Берите из обеих последовательностей по одному биту, считая 1 как +1, а 0 как -1, попарно их перемножайте, а результат перемножения накапливайте, прибавляя к некоторому аккумулятору. Если последовательности совпадают или почти совпадают, накопленная сумма будет стремиться к нулю. В противном случае она будет куда-нибудь двигаться.
Здравствуйте, batu, Вы писали:
B>Здравствуйте, sz36, Вы писали:
S>>Здравствуйте, RomikT, Вы писали:
Сори. Это сработает только если сдвиг постоянный у образца и исследуемой последовательности.
Здравствуйте, Pzz, Вы писали:
Pzz>Возьмите из произвольного места последовательности 64 бита, и приведите их в "каноническую форму". Скажем, циклически разверните так, чтобы получилось наименьшее из возможных 64-битных чисел.
Да, видимо что-то типа такого и придется. Правда, минимум искать более трудоемко, чем 64 раза сдвинуть и сравнить.
Придумать бы какое-нибудь преобразование, инвариантное к циклическому сдвигу... Ну, например, число единиц посчитать. Это дает 6-битный хеш — этого, конечно, мало, но хеш 32, 24, или даже 16 бит меня бы устроил более чем.
Здравствуйте, sz36, Вы писали:
S> Придумать бы какое-нибудь преобразование, инвариантное к циклическому сдвигу... Ну, например, число единиц посчитать. Это дает 6-битный хеш — этого, конечно, мало, но хеш 32, 24, или даже 16 бит меня бы устроил более чем.
Вместо количества единиц можно посчитать количество битовых "n-грамм" каждого вида для n=2..4 в строке из 64+n-1 бит (исходные 64 бита + копия первых n-1 бит).
Считаем количество всех видов n-грамм для каждой позиции 0..63, получаем 2^n*6 бит.
Для экономии можно не учитывать в хэше количество какого-нибудь одного вида строк, например, состоящих полностью из единиц: это значение зависит от остальных (сумма по всем n-граммам равна 64).
Другой вариант — выбрать желаемое значение длины хэша h, дополнить битовую строку первыми h-1 битами, потом пробежать от начала и посчитать xor для каждой из 64 позиций. Еще проще и гибче.
D.K. << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Все на свете должно происходить медленно и неправильно...
Здравствуйте, sz36, Вы писали:
S> Вопрос. Существует ли какой-нибудь алгоритм сравнения двух таких последовательностей, помимо брутфорса (то есть сдвига на единичку и сравнения 64*64)? Может, например, можно вычислить какой-нибудь хеш, значение которого не будет зависеть от места, с которого мы начали его вычислять?
А сколько памяти не жалко? Вообще, есть набросок идеи, чтобы держать таблицу байт magic_forward[256][256] и magic_back[256][256], которая показывает, какие смещения друг относительно друга для этих байт допустимы. Например, Если взять 10101110 и 11111110, то
Соответственно, сравнив первый байт последовательности A со всеми байта последовательности B, мы получим некоторое множество допустимых смещений для него. Проверив все байты получим множество всех смещений, если множество непусто, то все совпало. Такой общий набросок. Если входные данных имеют случайный характер, должно работать хорошо
Перед этим можно сравнить пару инвариантов, например, число бит, которые установлены в единицу.
Здравствуйте, sz36, Вы писали:
Pzz>>Возьмите из произвольного места последовательности 64 бита, и приведите их в "каноническую форму". Скажем, циклически разверните так, чтобы получилось наименьшее из возможных 64-битных чисел. S> Да, видимо что-то типа такого и придется. Правда, минимум искать более трудоемко, чем 64 раза сдвинуть и сравнить.
Ну в принципе, найти минимум, это то же самое, что подчитать число нулевых бит справа и сдвинуть вправо на это количество. Не такое уж и трудоемкое мероприятие...
Здравствуйте, conraddk, Вы писали:
C>Здравствуйте, sz36, Вы писали:
S>> Придумать бы какое-нибудь преобразование, инвариантное к циклическому сдвигу... Ну, например, число единиц посчитать. Это дает 6-битный хеш — этого, конечно, мало, но хеш 32, 24, или даже 16 бит меня бы устроил более чем.
C>Вместо количества единиц можно посчитать количество битовых "n-грамм" каждого вида для n=2..4
Такой хеш будет инвариантен только при n-кратном сдвиге. При сдвиге на 1 не прокатит. Можно посчитать длины всех цепочек нулей и единиц и как-то упаковать рез-т.
Здравствуйте, sz36, Вы писали:
C>>Вместо количества единиц можно посчитать количество битовых "n-грамм" каждого вида для n=2..4 S> Такой хеш будет инвариантен только при n-кратном сдвиге. При сдвиге на 1 не прокатит.
Нет, инвариант будет при любом сдвиге. Мы считаем подцепочки из n бит для каждой(!) позиции, "внахлест".
Пример для 8 бит, n=2, исходная цепочка — 01100101.
Копируем слева направо n-1=1 бит
011001010
01
11
10
00
01
10
01
10
Итого имеем
00 = 1
01 = 3
10 = 3
11 = 1
Можно повторить процедуру для любого сдвига исходной цепочки, результат не изменится.
Второй вариант (с использованием xor) нужно применять тоже к перекрывающимся подцепочкам.
D.K. << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Все на свете должно происходить медленно и неправильно...
Здравствуйте, sz36, Вы писали:
S>Здравствуйте, Pzz, Вы писали:
Pzz>>Возьмите из произвольного места последовательности 64 бита, и приведите их в "каноническую форму". Скажем, циклически разверните так, чтобы получилось наименьшее из возможных 64-битных чисел. S> Да, видимо что-то типа такого и придется. Правда, минимум искать более трудоемко, чем 64 раза сдвинуть и сравнить.
S> Придумать бы какое-нибудь преобразование, инвариантное к циклическому сдвигу... Ну, например, число единиц посчитать. Это дает 6-битный хеш — этого, конечно, мало, но хеш 32, 24, или даже 16 бит меня бы устроил более чем.
Посмотри темку что я предложил. Сначала я погорячился. А потом подумал разумное зерно там есть. Работать не с битами, а с байтами. Собрав только эталоны со сдвигами. Получится массив 8 по 4 байта эталонов. И начинай проверку этих эталонов операцией "и" со вторым и 3-им байтом. При совпадении даже со сдвигом они точно дадут нули. Первый и последний байт проверишь в случае если средние нули. Что не так уж часто будет случаться. Во всяком случае работать не с битами а с байтами прийдется. Что мабуть легче.
Здравствуйте, conraddk, Вы писали:
C>Нет, инвариант будет при любом сдвиге. Мы считаем подцепочки из n бит для каждой(!) позиции, "внахлест".
Да, это интересно. Пошел думать...
Здравствуйте, sz36, Вы писали:
S>Hi, All!
S> Существует периодическая последовательность данных, в которой непрерывно друг за другом идут одинаковые блоки данных по 64 бит. Границ между блоками нет, то есть, начиная с любого места мы можем взять 64 бита данных — это некий код, который раз за разом повторяется.
S> Вопрос. Существует ли какой-нибудь алгоритм сравнения двух таких последовательностей, помимо брутфорса (то есть сдвига на единичку и сравнения 64*64)? Может, например, можно вычислить какой-нибудь хеш, значение которого не будет зависеть от места, с которого мы начали его вычислять?
Прийдется повторится. Лучше никто не предложил. Итак, адресация у тебя побайтная. Т.е. 64 разряда это 8 байт. Берем то что проверяем (эталон) и собираем массив из 8 элементов по 4 байта первый из которых эталон, а остальные получается сдвигом на 1, 2, 3..7 эталона. Сдвиг больше чем на 8 не имеет смысла, это уже другой байт получится. Обозначим байты этого массива Aij -где i-количество сдвигов относительно эталона (от 0 до 7). j-номер байта эталона или сдвинутого элемента (от 0 до 7).
Начинаем проверку входящей последовательности со второго байта, и сравниваем его со всеми элементами Ai2. Если ни один не совпадет, то нет смысла проверять дальше. Все возможные комбинации перебраны. Середина (а именно второй байт) не совпадает ни с каким сдвигом. Это означает что у первого байта входной последовательности совпадений с эталоном нет. Можно смело проверять следующий (третий) байт входящей последовательности на те же элементы Ai2.
Если какой-то (i) из сдвигов совпадает, то проверяем третий байт входной последовательности на совпадение с элементом Ai3 (подозреваемй сдвиг уже определен как i). Итак, должны совпасть все байты вплоть до 6-го (Ai6). Первый и последний байт проверяется соответсвующей логической операцией что уже просто так как подозреваемый сдвиг (i) определен.
Фактически хэшем является набор сдвинутых вторых байтов. Эдакий хэш-массив. И этот хэш продолжается третьим и т.д. до шестого байта.
)
