LINUX.ORG.RU
ФорумTalks

Карта википедии

 , ,


2

3

Тут, наверное, пару недель назад кто-то сказал, что было бы интересно взглянуть на карту русской википедии по ссылкам внутри статей. Заюзав все свои 4 гб оперативы и сутки времени, я закодил и сгенерил таковую карту (в качестве helloworld, просто хотел освоить python).

Характеристики:

1 пиксель может содержать от 1 до 4 статей. Чем больше статей в пикселе, тем он светлее. Пиксели без статей чёрные.

Оттенок пикселя определяется средним количеством исходящих и входящих ссылок данной статьи таким образом:

1-33: голубой
34-66: зелёный
67-99: жёлтый

99: красный

Очевидно, красные пиксели — классификаторы разного рода: по датам, по направлениям и т.п, а голубые и зелёные — обыкновенные статьи среднего размера.

На карте видно:

  • Ядро энциклопедии, статья «Россия», а также статьи о других странах (маленький красный кружок в центре)
  • 9 сравнительно независимых участков энциклопедии
  • сотни статей, не связанных с остальными (плавают вокруг основной области связности)
  • 8 основных веток классификаторов, простирающихся от ядра

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

Ссылка
Зеркало

★★★

Последнее исправление: Klymedy (всего исправлений: 3)
Ответ на: комментарий от nerdogeek

А координаты пикселя от чего зависят?

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

Sadler ★★★
() автор топика
Последнее исправление: Sadler (всего исправлений: 1)
Ответ на: комментарий от CYB3R

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

Sadler ★★★
() автор топика

Москву на яндекс.пробках напоминает. Даже замкадные районы есть.

Kiborg ★★★
()
Ответ на: комментарий от Sadler

И ещё...

1-33: голубой
34-66: зелёный
67-99: жёлтый
>99: красный

Слишком большие промежутки. Быть может, лучше сделать кучу разных оттенков, тогда картинка будет более забавной: местами плавнее, местами хаотичнее.

CYB3R ★★★★★
()
Ответ на: комментарий от true_admin

омг, сколько занимаешь обсчёт? Сколько итераций делается?

Ну, часов 6 занял. 100 итераций я сделал (смотрел, когда карта перестала меняться значительным образом). Считал по своему алгоритму (который я защищал год назад), правда, сильно упрощённому.

Sadler ★★★
() автор топика
Ответ на: И ещё... от CYB3R

Слишком большие промежутки. Быть может, лучше сделать кучу разных оттенков, тогда картинка будет более забавной: местами плавнее, местами хаотичнее.

Я пробовал. Неинтуитивно.

Sadler ★★★
() автор топика
Ответ на: комментарий от Xellos

Правда тогда ЛОР положит википедию...

Не положит. Скрипт работает с XML-кой текстов википедии, а не выкачивает страницы.

Вот скрипт парсинга ссылок: http://pastebin.com/pL6pxWgZ . Засовываешь результат его работы (~2.5 ГБ) в свой любимый алгоритм Graph Layout и уходишь курить на продолжительное время =)

Тексты можно взять здесь: http://dumps.wikimedia.org/ruwiki/latest/ .

Sadler ★★★
() автор топика
Последнее исправление: Sadler (всего исправлений: 1)

Неплохо. Но требует допилки, имхо. Ждём новых результатов. :}

geekless ★★
()

Очевидно, красные пиксели — классификаторы разного рода: по датам, по направлениям и т.п, а голубые и зелёные — обыкновенные статьи среднего размера.

В смысле, статьи со списком ссылок на другие статьи? Ты про кластер справа вверху. Если да, то почему статьи-списки имеют ссылки друг на друга?

maggotroot
()
Ответ на: комментарий от maggotroot

В смысле, статьи со списком ссылок на другие статьи? Ты про кластер справа вверху.

Я про основной участок, линии от центра. Кластер справа меня самого интересует, что там за статьи такие с кучей перекрёстных ссылок. Как сгенерирую полную расшифровку, узнаю.

Sadler ★★★
() автор топика

А теперь надо взять исходник, переписать его на правильный язык и снизить потребление RAM и времени в несколько раз.

PolarFox ★★★★★
()
Ответ на: комментарий от PolarFox

А теперь надо взять исходник, переписать его на правильный язык и снизить потребление RAM и времени в несколько раз.

Да, на сях было бы менее затратно. Но я не очень умею на сях работать с уникодом, да и питон хотелось изучить.

Sadler ★★★
() автор топика
Ответ на: комментарий от Bad_ptr

но в тоже время полная ерунда

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

Sadler ★★★
() автор топика
Последнее исправление: Sadler (всего исправлений: 1)
Ответ на: комментарий от PolarFox

А теперь надо взять исходник, переписать его на правильный язык и снизить потребление RAM и времени в несколько раз.

За то время, что он будет переписывать на «правильный язык», он бы успел заработать на новые память и проц.

geekless ★★
()
Ответ на: комментарий от true_admin

пружинная сеть? :)

Ну, это силовой алгоритм, да, но у классического силового алгоритма сложность O(N^2), что не очень приятно. Я расчитываю только притяжение по связанным вершинам, силами отталкивания занимается простой клеточный автомат, сдвигающий вершину по сетке, если она расположена близко к другим вершинам. Получается такая своеобразная карта. Есть ещё несколько аспектов, позволяющих улучшить сходимость, но не суть. Если сетка достаточно большая, то этот алгоритм Graph Layout работает очень быстро с приемлемой точностью. Я года два назад писал статью об этом в рецензируемый журнал.

Из неудобств: 1) приходится держать карту в памяти, а она бывает достаточно большой; 2) алгоритм сильно зависит от связности графа. Заметное ускорение даёт лишь при связности << числа вершин графа. Для википедии вполне подходит.

Sadler ★★★
() автор топика
Последнее исправление: Sadler (всего исправлений: 2)

python
чуть-чуть не хватило RAM
по половине ссылок (порядка 600 000)
и половине связей (около 16 млн)

Питон такой питон, да.

invy ★★★★★
()

Очень похоже на медузу.

XoFfiCEr ★★☆☆
()
Ответ на: комментарий от Sadler

Кластер справа меня самого интересует, что там за статьи такие с кучей перекрёстных ссылок

Притом похоже, что они больше связаны ссылками друг с другом, нежели с «обычными» статьями.

static_lab ★★★★★
()
Ответ на: комментарий от static_lab

Я подозреваю, что это КОАТУУ. Каждая статья связана с классификатором и, возможно, другими статьями справочника, но очень слабо связана с другими статьями.

Sadler ★★★
() автор топика
Ответ на: комментарий от invy

ну из расчета 1kb per node, 8 b per link, ты в гиг вписаться должен.

Но там ведь ещё нужно хранить веса связей, карту для алгоритма, pixelmap для отрисовки и т.п. Да и в python я не нашёл возможности реализации компактного 2d array, потому юзаю dict.

Sadler ★★★
() автор топика
Ответ на: комментарий от Sadler

Я подозреваю, что это КОАТУУ

Классификатор объектов административно-территориального устройства Украины? В русской википедии? Что-то даже сама статья про сабж не даёт никаких намёков на это. И на мове в том числе.

static_lab ★★★★★
()
Ответ на: комментарий от static_lab

Зато на КОАТУУ ссылается 20000+ статей. Я ведь не отличаю входящие и исходящие ссылки. Т.е. он должен занимать примерно 60x60 пикселей на карте, что мы и видим.

Sadler ★★★
() автор топика

Это случайно не результат нашего (вроде) разговора об автоматическом поиске синонимов?

dmfd
()
Ответ на: комментарий от dmfd

Не, это результат треда о поиске кратчайшего пути по википедии =) Для поиска синонимов словарей достаточно, здесь скорее поиск ассоциированных элементов.

Например: Россия -> Москва, города-миллионеры России, православие, СССР, США...

Sadler ★★★
() автор топика
Ответ на: комментарий от static_lab

Ну так на ОКАТО, наверное, ещё больше статей ссылается.

10000+ . Но это только из той половины википедии, которую я распарсил. Памяти докуплю, будет полная картина.

Sadler ★★★
() автор топика

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

Зачем докупать раму? Заюзай жосткий диск.

Siado ★★★★★
()
Ответ на: комментарий от silw

могу запустить на лабораторных машинках 16-48Гб памяти. интересно, что получится.

Я посмотрю, если в среду не куплю себе достаточно оперативы, то так и сделаем.

Меня смущает то, что в текущей реализации я до невозможности упростил алгоритм, чтобы расчёт шёл быстрее:

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

Вот, если я случайно пойму, что одно из этих упрощений портит картинку, придётся переделывать.

Sadler ★★★
() автор топика
Последнее исправление: Sadler (всего исправлений: 1)
Ответ на: комментарий от Sadler

А как насчёт определения структуры в духе http://www.almaden.ibm.com/almaden/webmap_press.html ?

Придётся учитывать направления в графе. Для тех, на кого не ссылаются, добавь дополнительную силу влево, а для тех, кто не ссылается, добавь силу влево. И пересчёт координат, чтобы центр тяжести был посередине.

i-rinat ★★★★★
()
Ответ на: комментарий от i-rinat

Хм, можно попробовать. Если бы не большая связность, я бы просто разделил всё на компоненты связности, там структуру куда проще выявить. Но основная компонента связности — 87% всех данных.

Sadler ★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.