Представление сжатого графика?

Question

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

Мой вопрос: есть ли способ без потерь сжать граф, слишком большой, чтобы поместиться в память, чтобы он поместился в памяти? Если нет, то есть ли хороший алгоритм с потерями, который при некотором определении «структуры» не теряет слишком много структуры из исходного графа?

Answer 1

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

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

Их код(для Java, Python и C ++) доступен на их веб-странице в качестве среды сжатия графов, так что вы сможете поэкспериментировать с ней без особого программирования.

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

Answer 2

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

Answer 3

Вообще говоря, если у вас есть N узлов и среднее число X исходящих ссылок на узел, X намного меньше, чем N, вам потребуется XN ln N битов информации, чтобы представить это, если вы не можете найти шаблоны в структура ссылок (которую вы можете использовать для снижения энтропии). XN ln N находится на порядок от сложности вашего 32-битного списка смежности.

Есть несколько трюков, которые вы могли бы сделать, чтобы уменьшить размер:

• Используйте коды Хаффмана для кодирования ссылок. Назначьте более короткие коды часто используемым страницам и более длинные коды нечастым страницам.
• Найдите способ разбить набор страниц на классы. Сохраняйте каждую ссылку между страницами в одном классе как «0» + «# в классе»; ссылки между страницами в разных категориях как «1» + «целевой класс» + «# в пределах класса».

Ссылки от Джузеппе стоит проверить, но только эксперимент покажет вам, насколько хорошо эти алгоритмы применимы к Википедии.

Answer 4

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

Предположим, у вас есть 2 ³⁰ (миллиард) страниц, и у каждого есть ровно 2 ⁴ исходящих ссылок, и что ссылки действительно распределены случайным образом. Ссылки на каждой странице представляют почти 16 * 30 бит информации (не полностью, потому что все 16 ссылок различны, и это добавляет незначительную избыточность). Таким образом, у вас есть 2 ³⁰ * 16 * 30 = 2 ³² * 120 = 15 ГБ информации там, и теория информации говорит, что вы не можете найти меньшее общее представление. Вам нужно использовать особую структуру графа Википедии, чтобы опуститься ниже этой теоретико-информационной нижней границы.

Answer 5

Если вам не нужна изменяемость, посмотрите, как BGL представляет график в формате сжатой разреженной строки .Согласно документам, он «минимизирует использование памяти до O (n + m), где n и m - количество вершин и ребер соответственно».В Boost Graph Library даже есть пример , который отражает ваш вариант использования.

Прежде чем углубляться в это, вы должны действительно выяснить, как вы намереваетесь опросить свой график.Вам нужны ссылки, указывающие на страницу, а также ссылки со страницы?Вы должны быть в состоянии эффективно найти количество ссылок на данной странице?Для довольно хорошо продуманного списка основных операций с графами взгляните на понятия Boost Graph Library (BGL) .Затем вы можете сопоставить это с требованиями для различных алгоритмов. Для кратчайшего пути Дейкстры , например, требуется граф, который моделирует «Граф списка вершин» и «Граф инцидентности».

Answer 6

А как насчет записи ваших узлов, ссылок и ассоциаций в существующую масштабируемую систему баз данных (MySQL, SQL Server, Oracle и т. Д.)? При необходимости вы можете создавать индексы и хранимые процедуры для более быстрой обработки на уровне БД.

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