Сжатие с распределенным файлом

Question

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

Хорошо, поэтому здесь идет.

Интернет заполнен избыточными данными, включая текст, изображения, видео и т. Д. В результате в gzip и bzip2 на сжатие и декомпрессию по HTTP в результате много усилий. Крупные сайты, такие как Google и Facebook, имеют все команды, которые посвящают свое время более быстрой загрузке своих страниц.

Мой «вопрос» относится к тому, что сжатие делается исключительно на в файл базиса (gzip file.txt дает file.txt.gz). Несомненно, существует много общности между кажущимися несвязанными данными, разбросанными по Интернету. Что делать, если вы можете сохранить эти общие куски и объединить их, как на стороне клиента, так и на стороне сервера, для динамического создания контента?

Для этого вам нужно будет найти наиболее распространенные «куски» данных в Интернете. Эти куски могут быть любого размера (вероятно, здесь есть оптимальный выбор), и в совокупности они должны быть способны выражать любые данные, которые только можно вообразить.

Для иллюстрации предположим, что у нас есть следующие 5 кусков общих данных - a, b, c, d, and e. У нас есть два файла, которые только содержат эти куски. У нас есть программы под названием chunk и combine. chunk принимает данные, сжимает их через bzip2, gzip или какой-либо другой алгоритм сжатия и выводит куски, которые содержат указанные данные (после сжатия). combine расширяет фрагменты и распаковывает конкатенированный результат. Вот как они могут быть использованы:

$ cat gettysburg.txt 
"Four score and seven years ago...cont'd" 
$ cat test.txt 
"This is a test" 
$ chunk gettysburg.txt test.txt 
$ cat gettysburg.txt.ck 
abdbdeabcbdbe 
$ cat test.txt.ck 
abdeacccde 
$ combine gettysburg.txt.ck test.txt.ck 
$ cat gettysburg.txt 
"Four score and seven years ago...cont'd" 
$ cat test.txt 
"This is a test" 

При передаче файла через HTTP, например, сервер может chunk данные и отправить его клиенту, который затем имеет возможность combine фрагментации данных, и сделать его ,

Пробовал ли кто-нибудь это раньше? Если нет, я хотел бы знать, почему, и если да, напишите, как вы можете это сделать. Хорошим первым шагом было бы подробное описание того, как вы можете понять, что это за куски. Как только мы выяснили, как получить куски, мы выясним, как могут работать эти две программы: chunk и combine.

Я, вероятно, поставлю щедрость на это (в зависимости от приема), потому что я думаю, что это очень интересная проблема с реальными последствиями.

Answer 1

Вы спросили, если кто-то сделал что-то подобное раньше и что размер куска должен быть, и я думал, что я укажу вам на двух работах, которые пришли мне на ум:

• (командой на) Google пытается ускорить веб-запросы, используя данные, которые совместно используются документами. Сервер связывает предварительно вычисленный словарь с клиентом, который содержит данные, общие между документами, и ссылается на более поздние запросы. Это работает только для одного домена в то время, и - в настоящее время - только с Google Chrome: Shared Dictionary Compression Over HTTP

• (команда в) Microsoft определяется в своей работе Optimizing File Replication over Limited-Bandwidth Networks using Remote Differential Compression, что для их случае синхронизации файловой системы размера куска около 2KiB хорошо работает. Они используют уровень косвенности, так что список кусков, необходимых для воссоздания файла, сам разделяется на куски - бумага увлекательна для чтения и может дать вам новые идеи о том, как это можно сделать.

Не уверен, что это вам поможет, но вот оно на случай, если это произойдет. :-)

Answer 2

Вам не нужно анализировать его для наиболее распространенных кусков - на самом деле, такое распределенное принятие решений может действительно быть довольно сложным. Что-то вроде этого:

Возьмем случай передачи данных HTTP. Блокируйте каждый файл в блоки размером 10 мегабайт (или независимо от того, какой размер вам нужен, я уверен, что каждый из них имеет последствия для производительности) и вычисляют их SHA-256 (или некоторый хэш, который вы достаточно уверенны, должен быть безопасен от коллизий)

Например, у вас есть файл F1 с блоками B1..Bn и контрольные суммы C1..Cn. Теперь HTTP-сервер может ответить на запрос файла F1 просто списком C1 ..Cn

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

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

Теперь это не касается случая, когда имеется смещение (например, один файл

AAAAAAAA 

и другой

BAAAAAAAA 

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

Мысли

Answer 3

Не совсем связано с вашим ответом, но вы уже это видите. Microsoft (и другие) уже предоставляют пограничные сети для размещения библиотек jquery. Вы можете обратиться к этим же URI и получить преимущества доступа пользователя к файлу с другого сайта и его кеширования браузера.

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

Answer 4

Существует более простой способ обработки текстовых данных. В настоящее время мы сохраняем текст в виде потоков букв, представляющих звуки. Однако единица языка - это слово не звук. Поэтому, если у нас есть словарь всех слов, а затем хранить «указатели» на такие слова в файлах, мы можем динамически пересоздать текст с помощью указателей и поиска списка слов.

Это должно уменьшить размер вещей в 3 или 4 раза. В этом методе слова такие же, как и куски, которые вы имеете в виду.Следующий шаг - это общие группы слов, такие как «это», «я», «полная луна», «серьезно чувак», «о детка» и т. Д.

Список слов также помогает проверять орфографию и должен быть реализованный операционной системой. Есть ли причина, почему проверки орфографии не являются частью операционной системы?