Здравствуйте, mkopachev, Вы писали:
M> Я решал такую же задачу, только специфика требовала минимизации пакетов, по-этому требовалось находить самые большие повторяющиеся вхождения. Использовал суффиксную сортировку файла с последующим поиском.
Я поступил очень просто.
1)Нарезал исходный фаил на блоки одинаковой длинны
2)Посчитал контрольную сумму для каждого блока(причем контрольная сумма не простая, а позволяющая двигатся по последовательности без полного пересчета)
3)Загнал все это в хэш таблицу
Далие двигаю контрольную сумму по новому файлу и произвожу поиск по хэш-таблице. Если совпало то нашли повторяющеяся данные.
Этот алгоритм не очень точен, любит память но меня вполне устраивает ибо работает быстро.
В принципе можно немного повысить точность если при совпадении контрольных сумм проверять не только вперед но и назад. Еще можно сделать так чтобы поиск повторений производился в уже просмотренной части нового файла.
Возможно позже я это реализую ибо это не скажется на скорости востановления файлов.
Сейчас посчитал разницу между двумя файлами весом 10М за 1.5 секунды комп celeron 1.7G. И это при том что там еще можно коечто пооптимизировать.
M> Вообще идеи бродили всякие — часть была испробована, часть нет. Вот то что могу сейчас вспомнить:
Спасибо посмотрю.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Здравствуйте, mkopachev, Вы писали:
M> Я сделал эксперимент, увы такой подход мне не подходит — степнь сжатия падает аж в 2.5 — 3 раза, а мне трафик минимизировать надо 
.
Я трафик ZLib'ом минимизировать буду
M>Но работает действительно быстро.
Это мне важно ибо система должна в идеале быть интерактивной.
M>Ты какой хэш использовал? Я использовал накапливающуюся сумму по простому модулю. Сначала по 1, потом по 5 разным — получил ускорение примерно в 1.3 раза (правда файл был со множественными периодическими повторениями — они мне больше всего крови портят), дальше замедление пошло 
.
Пока такой.
using CheckSumType = System.UInt32;
namespace BinaryDiff
{
public struct CheckSum
{
private static CheckSumType[] table = new CheckSumType[256]
{
0xC857A0F3, 0x25030742, 0x821800AA, 0x9D0D0A68, 0xEB6CC802, 0x34C14079, 0xEC453C2E, 0x38F76287,
0x4D32D266, 0xFF239AA5, 0xCA7AD44E, 0x71B8C3EC, 0x5B49B067, 0x2E0B2EAF, 0x4240211B, 0x3F61AA2B,
0xD3333B64, 0x927EA4B8, 0x6A8B9DAD, 0x7313585B, 0xF5D9C60E, 0xD273F956, 0x5CDF5F36, 0x86529586,
0x199C1E41, 0x54426F4D, 0x905410D1, 0x03CC7E04, 0xD87D7D03, 0xA93F9372, 0x4BA189CF, 0x9B256D3C,
0xCE857CC9, 0xD055E012, 0xA09DBB1A, 0xE0ED1B5A, 0xDB4647BA, 0x02CA52E2, 0x41CFE12A, 0x75154869,
0x5FE5F357, 0x3E6212A9, 0x7DB944D9, 0x6C5EB531, 0xE93066C4, 0xFDB6A671, 0x49F1703B, 0x8C4C368A,
0xA28DAECC, 0x1A72D9F2, 0x277F353A, 0xB6C47299, 0xD15F86E6, 0x951264A4, 0xF7220329, 0x62B72A91,
0x2F9405E4, 0x7B2B6876, 0x31286989, 0xCB2F39FC, 0xBF07176A, 0x049A5421, 0xF05B2973, 0xC2A07520,
0x8BA2D339, 0x40B16C49, 0xF8FE8796, 0xC505CB52, 0xF43EEC81, 0x2AD3A516, 0xA86519A2, 0xDA904A24,
0xE526CEDD, 0xBB29799C, 0xD409DAE8, 0x0DC2C0FF, 0x2C17DB27, 0xE6580D8F, 0xF90FF18C, 0x7E1ADD0A,
0x48D72707, 0x1D7B819B, 0x0E2CB7E5, 0xE43DA13F, 0xB44FC195, 0x97A911FD, 0x1F00B44F, 0x300C1460,
0x464DA714, 0xAB2D22BF, 0x77DC5585, 0xC73913FA, 0xCDCB9BEB, 0xD9F51526, 0xACC3E9EE, 0x8EB37F7C,
0x36A6A2D3, 0xE1818EF8, 0x0A86F68E, 0x4398971D, 0xF28FD651, 0xAF1F78BB, 0x17F391F1, 0xC151989E,
0x600AEEA8, 0x9391BFE3, 0xEF645E28, 0x72BC56A1, 0x518A2040, 0xE8508FDB, 0x67473118, 0xAEA3EF7B,
0x8441F4D5, 0x21A7F7F4, 0xB2746717, 0x228741BE, 0x4E960FB1, 0x641E7B1F, 0xB5970C0D, 0x8988C9E7,
0xC67C8D7E, 0x15AA2411, 0x0B20D02C, 0x586A9C82, 0x5DFB99F5, 0xBEEF6EFB, 0xDC53C5AB, 0x11EEE3BC,
0x809FCF98, 0xD769C290, 0xF635FDC3, 0x9F8E4D25, 0x5AA58CD4, 0x88B45CD2, 0x2DDAED08, 0x29E3E74A,
0xCF0E2BB3, 0x573A4B01, 0x66370677, 0x6E6E0B22, 0x3911BAC1, 0x33E86578, 0x164438DF, 0xBD0146C5,
0x7F08DF70, 0x695CDE63, 0x0004D7A6, 0x374A2D37, 0x61750950, 0x058357A3, 0x4C67F5B0, 0x4A92AC47,
0xC0FFA37F, 0x28C08B93, 0x44F93219, 0x1CA4D1D6, 0x4763CC06, 0x76663EB4, 0x141BCD84, 0xB9BBB96F,
0x3AD151DC, 0xCCFAB615, 0xEDB0EA4C, 0xB3E0FB58, 0x20F0BD05, 0xAD5A9083, 0x834B8AEA, 0x6D704374,
0x7931FF7D, 0x7A93F010, 0x7CD61ACD, 0x522AB1DE, 0x3DE437FE, 0x249BC492, 0xA7D52CED, 0x9E06A988,
0x2B82E645, 0x98B5420B, 0x1E192561, 0x5999A8CB, 0x5021CA80, 0x1BC8602D, 0xB7DD1C13, 0xDE1D235E,
0x8D77C7F9, 0xC98C3D34, 0x65389EC0, 0xA3EB3335, 0x70277446, 0x9CA86B9D, 0xBA346348, 0xFBBE8823,
0x3B3B08A7, 0x01CE16E1, 0xF3955AE0, 0xD5F230C7, 0x56E2E81E, 0xBC24F238, 0x26D0710C, 0xF1E60E65,
0x6FDB859F, 0x532E965C, 0xFE10AB75, 0x08CDE4CA, 0x18D2AFDA, 0x3C804C09, 0x68C96A0F, 0xEABA263D,
0x9160BC59, 0x747176B9, 0xA69E01EF, 0x13BD73AE, 0xDFFD4F44, 0x8579941C, 0x55162F3E, 0xB068189A,
0x87E97A7A, 0x1259B3B6, 0xEEABEB6C, 0xE2435B6B, 0x0CD4FA54, 0x066BDCB5, 0x636F828B, 0x32ADD833,
0xD6EC9F97, 0xE3BFB8E9, 0x9936618D, 0x5EDE025D, 0xAA76ADC6, 0x071C3A43, 0xA548E5F0, 0xC3FCFEB7,
0x9A78D562, 0xB1D8596E, 0xFA5604F6, 0x94C7832F, 0x23AF49CE, 0x10C6B26D, 0x966D8055, 0xB84E4ED8,
0x0FAE4500, 0x09F63F30, 0xFCEA53B2, 0x78E7E2F7, 0x8FF81FC2, 0x453CFCBD, 0xA1B284AC, 0x6BAC92D7,
0xA402BE53, 0x4F84F85F, 0xDD5D5032, 0xC4E13494, 0xE7891DA0, 0x35F4284B, 0x811477D0, 0x8AC55DC8,
};
private CheckSumType hi;
private CheckSumType lo;
public void Init(byte[] arr, int ofs, int size)
{
unchecked
{
hi = 0u;
lo = 0u;
size += ofs;
for (int i = ofs; i < size; ++i)
{
lo += table[arr[i]];
hi += lo;
}
}
}
public void Increment(byte include, byte exlude, int size)
{
unchecked
{
CheckSumType e = table[exlude];
CheckSumType i = table[include];
lo -= e;
lo += i;
hi -= e * ((CheckSumType) size);
hi += lo;
}
}
public override int GetHashCode()
{
unchecked
{
CheckSumType hash = lo ^ hi;
hash ^= hash >> 7;
hash ^= hash >> 11;
hash ^= hash >> 13;
return (int) (hash & 0x7fffffffu);
}
}
// public override bool Equals(object obj)
// {
// if (obj is CheckSum)
// {
// CheckSum sum = (CheckSum) obj;
// return Equals(ref sum);
// }
// else
// return false;
// }
public bool Equals(ref CheckSum that)
{
return (lo == that.lo) && (hi == that.hi);
}
// public static bool operator ==(CheckSum l, CheckSum r)
// {
// return l.Equals(ref r);
// }
//
// public static bool operator !=(CheckSum l, CheckSum r)
// {
// return !l.Equals(ref r);
// }
}
}
Я тут проверил на >500 метровых файлах эта контрольная сумма промахнулась всего 12 раз
. И справляется она с ними за 4 с половиной минуты.
M>Ты с длиной блока не экспериментировал?
Он у меня плавает в зависимости от размера файла и доступной памяти.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
