Кажется, я все-таки придумал кое-что насчет применения идеи RT в сжатии, даже два способа: 1) Генерация "словаря" для быстрого кодера при помощи медленного. Т.е., условно говоря, делаем вариант lzma с возможностью кодирования матчей в двух разных окнах - одно обычное, скользящее по файлу, а второе фиксированное - как бы словарь. Можно, конечно, использовать и специально подготовленный словарь, но его тогда надо сжимать вместе с файлом. А можно, скажем, после обработки LZ-кодеком первого блока в 64k, натравить на этот блок CM-модель, а потом отключить в ней апдейты счетчиков и сгенерировать несколько мегабайт случайных данных, основанных на реальной статистике. Т.о. получается, что скорость, асимптотически, остается как у LZ, размер сжатого словаря учитывать не надо, но возможность ссылок на него останется, т.е. при удаче сжатие улучшится. Также, можно периодически повторять генерацию словаря, с расчетом на сохранение приличной средней скорости. 2) Главная проблема с прямым применением RT для поиска матчей в терабайтных объемах - что матчи размером с обычно хранящиеся в RT пароли (8-10 символов) никого тут не интересуют, а матчи по несколько килобайт не получится сгенерировать из хэша, и даже если получится - вероятность коллизий будет слишком низкой. Так вот, новая идея - генерить из хэшей не целиком строки данных, а патчи к ним. Т.е. - сохраняем некую строку в памяти; - изобретаем "функцию редактирования" строки - с операциями, скажем, флип бита по номеру, дублирование заданного байта, удаление заданного байта; - список операций для этой функции генерим из хэша, можно с учетом статистики (т.е. грубо говоря, декодируем список операций из хэша, как из куска арифметического кода; получается случайный список операций, строго соответствующий данному хэшу) - далее, прогоняем несколько тысяч итераций, начиная с сохраненной строки h=hash(str); str=edit(str,h) [...] - останавливаемся, например, при h%1000==0 А теперь смысл этой затеи: Если взять какую-то новую строку, и прокрутить над ней тот же процесс, с тем же условием завершения, то при наличии коллизий, придем к тому же значению хэша. Получается, что мы можем сохранить целый список из нескольких тысяч похожих строк, в виде пары {начальная строка; последний хэш в цепочке}. Также, для полного счастья, можно в качестве начальной строки не записывать первую попавшуюся (хотя так по идее тоже сработает), а некую обработанную версию, из серии LSH. Нужно это для задач типа системы дедупликации для терабайтного стореджа - если поиск матча по хэшу реализовать при помощи обычной хэш-таблицы, то при совпадении хэша придется лезть на диск, за hash chain, дальше искать матч. А тут идея в том, чтобы за счет алгоритма RT, заменить обращение к диску на цикл хэширования без обращения - речь именно о случаях, когда оперативки заведомо недостаточно. Когда-то я такую систему писал, на базе anchor hashing. Там данные резались на чанки, а списки хэшей чанков хранились так же, как такие же данные, и тоже резались на чанки. Получалась такая "пирамида" хэширования, по которой в итоге каждому файлу соответствует один хэш, по которому можно найти верний уровень списка хэшей и т.д. Ну и дальше все просто и единообразно. Причем смысл этой затеи - синхронизация между хостами - для новых файлов достаточно начать передавать слои "пирамиды", и пропускать чанки, для которых та сторона отвечает "есть такой". Так вот, во всем этом есть одна проблема - крайне нежелательно допускать появление дубликатов, т.е. чтобы один и тот же чанк хранился в нескольких копиях. Cкажем, потому что при обработке в результате коллизии его выбросило из хэш-таблицы. Для задач типа srep это некритично - ну, немного сжатие хуже будет, а тут это чревато глюками (это фактически утечка памяти, для коррекции потребуется сложная дефрагментация). Ну и получилось что хэш-таблицу в памяти надо чем больше, тем лучше, а потом с нее все равно лезть на диск чтобы ресолвить хэш в данные. А ведь задача по смыслу очень близкая к RT, такой же поиск строк по хэшам. Ну вот я с тех пор и думал, как бы все-таки эту идею применить, и, кажется, придумал (уже объяснил, как). А вообще, эта идея из той же серии что anchor hashing т.е. поиск выполняется только в "критических точках". Только тут еще и вторая идея прикручена - генерация контента на ходу вместо выборки из памяти по хэшу. Конечно, еще интереснее было бы найти способ применения этих идей и в обычных алгоритмах сжатия. RT же это фактически алгоритм сжатия, который позволяет достигать недоступных обычно коэффициентов сжатия типа 1000x. В принципе, это алгоритм сжатия с потерями, но потери тут в обратную сторону - теряется не сама информация, а соответствие индексов чанков с самими чанками. Т.е. добавляется "спам" и мы не можем определить что было на самом деле, а что сгенерировано. Но с т.з. объема словаря - RT выигрывает на порядки. На диск лезть надо, потому что оперативка ограничена, а в хэш-таблице коллизии. у меня получилась система с ограничением объема стореджа. Грубо говоря, для индексирования 10T данных надо 100G оперативки. Работает и так, конечно, но хотелось бы убрать ограничение по размеру стореджа и требования по оперативке. Новая идея позволит получить одинаковый хэш для похожих чанков, грубо говоря, у которых edit distance в рамках объема хэша. > т.е. расчёт идёт на то что среди чанков будут похожие? Конечно, но они же обычно бывают. Вопрос в том, как их найти за вменяемое время. Ну допустим чанки в среднем по 1k, а хэш sha1 по 20 байт. Тогда из исходного чанка можно получить любой, сжатый дифф которого с данным - меньше 20 байт. Вполне может быть польза, имхо. Это вот напрямую метод RT не сработает, поскольку сгенерить 1k чанк из 20-байтного хэша и получить коллизию с реальным чанком - не получится. А смысл в том, что мы сможем получить любой чанк из цепочки генерации просто по хэшу этого чанка, не читая чанк с диска. Т.е. даже если 99% чанков в цепочке на 10000 будут несуществующими все равно останутся 100, за которыми не надо будет лезть на диск Ну, надо так настроить систему, чтобы были коллизии, конечно :) И заведомо предполагается, что контент у нас сжимаемый. > чем это лучше просто ссылки на чанк + набора операций модификации? Тем что для коллизий вообще ничего дополнительно хранить не надо. Хранится начальная строка и последний хэш. Т.е. расход RAM на поддержку поиска одинаковый что на одну строку/чанк, что на все ее модификации. Ну, можно еще добавить поле "длина цепочки", чтобы применять этот подход в меру "популярности" конкретного шаблона чанка. Это как в anchor hashing - в процессе получается много значений rolling hash, но ищем мы только по одному, но все равно находим. А, ну и насчет "начальной строки". LSH знаешь? Это такой метод (точнее теория разработки методов) понижения размерности данных. Из серии, как умучать текст, чтобы спеллчекер находил по хэшам слова даже с ошибками. Вот и тут в качестве первой строки в цепочки надо брать какую-то урезанную версию чанка, из которой можно получить как можно больше полезных вариантов. А насчет реалистичности - RT же реально работает, и экономит объем таблиц на несколько порядков а тут идея та же, просто для чанков данных с небольшими диффами. Конечно, для чанков с небольшими различиями (например, одна и та же строка с подстановкой параметров) моя обычная функция anchor hashing очень вряд ли выдаст разбиение в тех же точках. Хотя тоже, тут все зависит от длины контекста rolling hash. Если чанк ~1k, а контекст 16 байт, то для aligned разбиения похожих чанков потребуется только совпадение этого контекста т.е. 2x16 байт однозначно совпадающих по краям. Можно заметить, что я не предлагал ничего инкрементировать, когда объяснял про "функцию редактирования" - простые методы полного перебора тут не подходят. Ну в том и задача - как сделать это эффективным. Если рассуждать в более общем виде, об объемах диффа или hamming distance то достаточно близких строк не так мало. Ну и это же не произвольные строки, а заведомо похожие, одинаково разбитые anchor hashing и т.п. > тем не менее. из этих кусков с 32 байтами одинаковыми на границах твой > метод позволит заместить только те, которые похожи в первых 3 байтах Ну тут надо более умное что-то придумывать, с использование вероятностных методов. С подходом типа перебора первых байтов и обычная RT не работала бы - там же тоже не просто берется необходимое число байт из хэша для получения очередного пароля, а используется чарсет, а то и марковская модель. А это то же самое, просто генерируются диффы вместо полных чанков. И "функцию редактирования", которая с большей вероятностью будет превращать чанки в другие существующие тоже можно придумать. Например, есть разные билды одной программы. Там много похожего кода, но в разных версиях в коде различаются адреса. Делаем функцию, которая парсит код и все адреса превращает в относительные. Все, у нас может получится даже чистый матч, без всякого edit distance. Ну а если добавить возможность байт-другой изменить, то будет еще больше таких приблизительных совпадений. Скажем, один чанк может совпадать с другим только после обработки вышеописанным E8-фильтром, а другой наоборот, совпадает в исходном виде, но не в обработанном. В таком случае, один бит дополнительной информации задает выбор одного из вариантов, и дает нам два потенциальных совпадения вместо одного. Понятно, что если в сторедже одно видео, то толку не будет а вот если html всякий, или исходники... И это же чистый выигрыш, фактически, мы в любом случае ничего не теряем. Кроме лишних вычислений. Но если иначе все равно лезть на диск, то это несущественно, да и просто обращение к хэш-таблице (~600 тактов) получается намного медленней локального вычисления хэш-функции. Конечно, 1000 итераций хэширования все равно медленней, чем обращение к хэш-таблице (пока), но все еще быстрее обращения к диску (да даже и к кэшу ОС). Конечно, для LZ77 это не подходит, в таком виде. Но для моей задачи - мб и подойдет, особенно если размер чанков уменьшить. (что я давно хотел сделать, и на что не хватало памяти). Получается, что если взять bcj, delta, capital conversion и прочие текстовые фильтры, еще что-то придумать, то даже в десяток итераций можно вместить несколько потенциальных матчей. Причем для любой из версии обращение к хэш-таблице будет только одно.