W for Wikipedia

Что такое «BigData»? Это те данные, которые нельзя просто так переварить. Или нельзя просто так приготовить. Или это вы думаете что нельзя.
Особо сильный «перекос», в этом понимании бигдаты спрятался в web-картографии, в картах на различных сайтах.
И так уж получилось — на протяжении нескольких лет я катался по различным конференциям, и рассказывал про организацию передачи данных с сервера на Карту. Иногда меня спрашивали — «а где же взять эти ваши много данных».
Это не правильные вопросы, правильные вопросы это:
— как данные хранить
— какие данные, когда и почему передавать на клиент
— что такое серверная кластеризация, как она выглядит и почему она нужна
— что с данными делать
— и зачем это все нужно %username%

А насчет откуда взять данные… Есть один такой детский стишок

Весь покрытый метками
Абсолютно весь
Остров Википедии
В океане есть

И на этом острове растет примерно десять миллионов геотегированных статей, которыми мы и воспользуемся.
Но с флорой и фауной там не все так просто — статьи растут на разных языках, в разных местах, и их на само деле много…
Поэтому мы, как настоящие герои, немного усложним задачу и добавим немного агрегатных функций ^[1], Левенштайна ^[2], Мorton ^[3] кодов, esosedi ^[4] и немного здравого смысла.

Повышая связность интернетов…. Примерно такими словами я представлял процесс интеграции википедии в общую кучу геоданных.

Но была проблема — Wikipedia, хоть и сама описывает не самый сложный процесс своего клонирования (Википедия: Как_сделать_копию_Википедии ^[5]), совсем не хотела интегрироваться.
Потому что Wiki большая. Настоящая bigdata, для моего SSD. И скачать нужные данные на локалхост было сложно, и на сервер нельзя (потому что вся работа, описанная в данной статье, как и сама статья написаны в электричке).
Но все решаемо. Буквально за 5 минут (местный мем).

G for Geonames
Некоторое время назад я открыл для себя такой проект как geonames.org ^[6], который, в том числе, предоставляет API к «гео» статьям википедии — www.geonames.org/maps/wikipedia.html ^[7] (И там все «прыгает и скачет»).
Если немного покопать, то можно найти источник их данных — проект Georeferenzierung ^[8], который после всех своих хеплов и обсуждений выливается в маленький файлик, мегабайт на 700 — http://toolserver.org/~kolossos/wp-world/pg-dumps/wp-world/ ^[9]
Прошу любить и очень жаловать — это CSV со всеми нужными нам статьями wikipedia.

D for Database
Шаг 1. Импортируем данные.
Скачиваем с tool server файл new_C.gz. Это обычный csv, формат которого описан в вики ^[8].
Всего возможного добра по факту не нужно — только имя статьи, координаты и длина контента документа — auto_incriment_id, lang:Titel, lat, lon, psize (для ранжирования)
На основе этих данных можно получить список гео-страниц википедии.

Шаг 2. Этап interwiki
Очень многие статьи википедии имеют описание более чем на одном языке. В этом как-бы и смысл. В оригинальном файле формат данных примерно такой:

lang, pageTitle,…, en-page, ru-page, de-page… всего 273 языка из интервики.

Наша задача обьединить группу статей на разных языках в «кластер». По сути последовательность из 273 ссылок на различные языковые версии и есть кластер. Ему можно назначить некий уникальный id (минимальный id страницы в кластере, например. Или CRC32 от компонентов), после чего можно будет ссылаться на него.
Одновременно с этой операцией выясняем, что половина страниц на которые есть ссылки из interwiki — в основном индексе отсутствует.
Их не было на первом этапе.
Потому что в этих статьях нет георазметки (но есть ссылка через интервики), поэтому на первом этапе мы их и «не видели», так как они изначально не попали в файл экспорта.
В данном случае эти страницы надо дописать в основной индекс, но координаты загнать в null (для статистики).
PS: первый камень в огород wikipedia. Никакой связности на уровне данных.
PPS: Иногда в файле встречаются названия с битой кодировкой.

Шаг 3. Смотрим!
Давайте немного остановимся, и посмотрим наконец на то, как выглядит наш шарик, если на него наложить данные Wikipedia

Почти эту картинку вы могли видеть в шапке статьи про тепловые карты Яндекс.Карт ^[10] пару недель назад.

На самом деле картинка кликабельна — это интерактивный пример, можно пощупать на esosedi ^[11] (нормально работает только в WebKit!). По ссылке можно посмотреть не только на покрытие общими данными Вики, но также и на данные различных языковых разделов (en, ru, uk, de). А еще там можно посмотреть на какой-то странный вариант Incorrectenesses distribution map ^[12] (для желающих немного ^[13] математики).

Смысл этого «термина» очень прост:
1. У нас есть статьи в Википедии.
2. У нас есть связь между эти статьями.
3. Мы можем найти разницу между координатами статей одного кластера. То есть разницу в данных одной и тоже статьи, но на разных языках.

INSERT INTO deviance SELECT cluster, MAX( lat ) - MIN( lat ) + MAX( lng ) - MIN( lng ) , STD( lat ) + STD( lng ) , VARIANCE( lat ) + VARIANCE( lng )
FROM pages AS p
LEFT JOIN  `pagecluster` AS pc ON PC.page = p.uid
LEFT JOIN cluster as c on c.clusterId=pc.cluster
WHERE  c.cnt>1
GROUP BY cluster

PS: никакого матана — стандартные функции с результатами на любой вкус

Что что мы получаем?

Кто внимательно читал, должны помнить (из пункта 2 импорта), что в некоторых статьях одного кластера НЕТ геопривязки. А там где есть такие грубые нарушения — могут быть и более мелкие, ну например просто разные координаты в разных статьях. Потому что хоть кластер один — статьи на самом деле разные так как разделы Вики относительно автономны.
PS: Статьи одного кластера могут не только не иметь геопривязку, но и ссылки друг на друга через интервики. Многие статьи не имеют ссылки на те статьи, которые имеют ссылки на них. Или могут иметь исходящие ссылки совсем в другой кластер. Не пытайтесь понять — я сам не понимаю как же такое случилось.

Фактически это значит, что координаты у статей могут быть, могут не быть, могут быть не правильными. А аэропорт имени Сабихи Гёкчен ^[14] в ru версии «висит» над Домодедово. При этом c en версией ^[15] все ок.
В данный момент это уже не так, и с Сабихой все нормально — с августа кто-то статью подправил. Но (!):

SELECT *  FROM `pages` as p LEFT JOIN pageCluster ON pageCluster.page=p.uid LEFT JOIN deviance as dv ON dv.clusterId=cluster WHERE `type` = 'airport' and width>1 ORDER BY cluster

Выдает около 500 аэропортов с дельтой координат больше градуса.
Например Рейвенсторп ^[16] и Ravensthorpe_Airport ^[17]. Там с координатами все ок — просто полушария перепутали (33 и -33 градуса).
PS: Это был второй камень в огород wikipedia

Если чуть копнуть выясниться, что с аэропортами и крупными университетами почти всегда беда. Иногда кажется что какой-то странный робот ставил координаты. И везде одни и те же. Больше всего повезло такому месту как «Горловский государственный педагогический институт иностранных языков» ^[18] — он собрал «в себе» 22 других учебных учреждений, переплюнув и МГУ и Лигу Плюща.

На самом деле в Википедии не так уж много статей для которых можно посчитать «deviance» — просто очень многие материалы описаны только на одном языке и расчет не произвести так просто. Но «порядок» и частота ошибок примерно сохраняется.
Многие статьи привязаны «немного» в стороне. Иногда в сантиметрах, иногда в метрах, иногда хуже. Максимальная найденная ошибка составляет примерно 60 градусов.
Найти такие места сложно, но можно. Например по данным википедии ru: Храм_Вирупакши_в_Хампи ^[19] находится совсем не в Хампи(смещение 290км). При этом имеет ссылку на город Хампи, который стоит в правильном месте. И таких мест, для которых можно определить хотя бы регион привязки, очень много.

PS: Ну например практически для всех аэропортов и институтов.

Но об этом в другой раз. Перейдем в моменту о том «как показать»

Z for Z-code

Для того чтобы отобразить на карте некие данные, эти данные данные надо передать.
Но все данные передать нельзя, потому как это много-много мегабайт (изначально 700). И спасение тут одно — серверная кластеризация.
Она бывает(по моей терминологии) трех видов:

• Первого рода — вы получаете все данные из бд, где-то на сервере кластеризуете, отдаете на клиент.
  Все плачут.
• 2. Второго рода — вы просите БД сгруппировать вам чего-то по координатам. БД долго и упорно считает, потом группирует.
  Если шепотом спросить GROUP BY ROUND(Lat),ROUND(Lng), то можно услышать как плачет планировщик.
• 3. И третьего рода — вы простите БД отдать вам мистически сгруппированные данные. Почти никто не плачет.

В частности — для экспорта данных в пример heatmap заклинание звучало как

SELECT z, lat, lng, SUM(weight) FROM `coordinate_map` as cm GROUP BY z&0xFFFF0000

Где lat,lng — это обычные «земные» координаты, а z это «z-order-curve» ^[3], он же Morton code. В котором вся магия и прячется.

Morton, его собрат Hilbert(geo-hash в MongoDB) и Gray-code выполняют одно и тоже действие — переводят 2D(или 3D) координаты в 1D.

Z-order, Quad-code, Morton order, or Morton code is a function which maps multidimensional data to one dimension while preserving locality of the data points.

Фактически Z это «адресация по квадродереву». Bing так и называет это quadkeys ^[20] и использует для адресации (пирамиды) тайлов карты.
Именно этот «эффект» нам и нужен. Z-code, Quadkeys или как его не назови «указывает» на ноду квадродерева. На квадрат, на тайл.
В uint32 можно «положить» 16 «указаний» пути по дереву. Можно адресовать тайл 16 зума. Это примерно 300х300 метров. В bigint влезет еще 16 уровней.
Для сравнения показываю вам размер тайла 16 зума — для кластеризации, и для выборки данных — этого достаточно.

Но «главный» бонус Z-адресации — в быстрой выборке данных(1D индекс) и очень быстрых агрегатных операциях.
GROUP BY z&BITMASK и все. Для десятков миллионов записей запрос выполняется десятки миллисекунд.
При маске 0xFFFF0000 (16 единиц, 16 нулей) мы «накрываем» тайлы до 8-ого зума, после чего «отбрасываем» дальнейшую вариативность. Производим кластеризацию. На выходе для wiki будет ~22к «серверно закластеризованных» точек для нашего heatmap.
Сам этот процесс не так чтобы просто понять, но почитайте математику. Конечно же в википедии :P

Можно еще посмотреть модуль для друпала ^[21], который работает на основе geoHash.org ^[22], который (по сути своей) тоже «Morton number», но почему-то в base32.
Главное помните строки — это не числа, B-tree из них не построить (нормальное). Хотя — если у вас MongoDB — выбора нет, но все работает — проверено (линк на кленовый REST серверный кластеризатор ^[23] от АПИ Яндекс.Карт и пример ^[24] к нему)

Итак, в самом начале статьи поднимались некоторые вопросы
Q: Как данные хранить?
A: Хранить в базе данных, как данные. Как удобнее, и добить данные z-координатами.

Q: Какие данные, когда и почему передавать на клиент?
A: Использовать умную передачу данных, например RemoteObjectManager ^[25] и компанию. Об этом недавно была статья ^[26].

Q: Что такое серверная кластеризация и как она выглядит и почему она нужна?
A: О! Это совсем не страшный зверь, и позволяет не только снизить нагрузку на клиент, но и обеспечить более ровное покрытие данными (оно же «прыгает и скачет»)

Остается два вопроса, на которые еще не было ответа:
— что с данными делать
— и зачем это все нужно %username%

Значит начинаю рассказать про последний этап — этап где решается что с этими данными делать, и чем они могут быть полезны.

Весь покрытый метками… Абсолютно весь… Шарик есть.

Когда я начинал писать эту статью — на дворе был август. С тех пор минуло много времени, АПИ.Карт выпустил ObjectManager ^[26] и я все хотел сделать для него «ручку», чтобы вы смогли показать обьекты Википедии на своей карте. Но публичную ручку, которая выдержала бы хабраэффект я так и не сделал.
Если вы хотите получить немного «опыта» по размещению и отображению более менее нормального количества данных на карте, этот топик, топик про ObjectManager и наши выступления (раз ^[27], два ^[28]) помогут вам в этом.
Но — это не тема данного повествования. Мы тут про Вики говорим.

PS: Кстати — совсем недавно на the-village вышло интервью ^[29] с главой русской Википедии. Фактически это и побудило меня достать статью из черновиков.

L for Levenshtein

Повышая связность интернетов…. Примерно такими словами я представлял процесс интеграции википедии в общую кучу геоданных esosedi.
Суть проекта esosedi очень проста — добавление на карту различных мест, с целью или без цели. Чем на протяжении пары лет и занимаемся. И если в той куче объектов добавить еще данные вики — будет каша-малаша. Надо как-то поднимать связность.

Именно в этом моменте я призвал на помощь расстояние Левенштейна ^[30]:

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

Итоговый алгоритм выглядит примерно так: для всех мест, найти wikiстатьи вокруг себя, сравнить свое описание с другими кандидатами, записать результат в базу.
Момент «сравнить» не так прост как кажется — на каждую пару надо произвести примерно 16 измерений. В транслите, без гласных, без «скобок», без минус слов, через вторичные справочники…

Именно Левенштайн (и фактор расстояния) помогает понять что Златая и Золотая улочка это одно и тоже, так же как Лисья Гора и Lisa Gora.
Иногда он даже может различить Куангнам, Куангнгай и Куангнинь (это регионы Вьетнама). А вот Bắc, Bạc и Bắc — уже не сможет, потому что транслит совпадает.

Работа осложняется еще и разными наборами данных для сравнения. Никто не идеален. Например — алгоритмы. Но особенно UGC данные. Приходится работать с тем, что есть.

I for Interwiki
И хороший пример ошибок в UGS — это интервики.
Давайте откроем страницу ru:ISO_3166-2:SI ^[31] (Словения). Там, к сожалению, не описан практически ни один регион.
Теперь откроем тоже самое, но на другом языке — en:ISO_3166-2:SI ^[32]. Там, конечно, тоже не все нормально, но какой-то намек на данные есть.
Например там можно найти ссылку на регион SI-060 — Municipality_of_Litija ^[33], у которой есть русская версия — ru: Лития_(город) ^[34]. Вот только страница 3166-2 в русском варианте содержала ссылку на «Лития (Словения)». Не на "_(город)".
Второй момент — en:3166:SI кроме всего прочего имеет ссылку на «статистические регионы» Словении. Например на SI-08 Osrednjeslovenska.
Но! При заходе на en:Osrednjeslovenska_statistical_region ^[35] будет редирект на en:Central_Slovenia_Statistical_Region ^[36], и у этой статьи есть русская версия. Но никакой информации об этом, о такой важной(наверное) вещи как SI-08 в русском разделе 3166:SI… ну как бы просто нет.
Похожая наркомания встречается достаточно часто. C учетом сноски о некоторых проблемах в интервики я скажу вам по секрету — error: foreign key constraint failed.

T for Translate
И есть еще одна проблема — я не знаю испанский. И плохо знаю немецкий. И знаю, что кто-то плохо знает английский. Но моя мама любит отдыхать в Соренто.
С самим Соренто все хорошо, не беспокойтесь. Но 99% статей там исключительно на итальянском. И никакой Левенштаин не поможет понять что «Долина мельниц» и «Vallone dei Mulini ^[37]» это одно и тоже.

При этом, несмотря на то, что это достопримечательность мирового уровня — статья есть только на it. У нас в стране, точнее в разделе Википедии, везде все тоже самое — большая часть информации о каких либо местах или «объектах» на другие языки не переводится. Ну кроме списка наследия ЮНЕСКО.
В итоге получается, что требуется показывать информацию человеку, даже если этот человек эту информацию не сможет прочитать. Просто потому что другой информации нет.
Никаких других вариантов, кроме как использовать АПИ Яндекс.Переводчика ^[38] особо предложить и нельзя.
PS: Очень жаль что АПИ Google.Translate больше не с нами.
PPS: С тех самых пор все думаю свой переводчик написать, так как качество того что есть оставляет желать лучшего...

V — значит Vежливость
Лично у меня с момента нахождения ссылки на toolserver.org и получения первого результата прошло примерно два часа. Вы тоже можете повторить мой путь, и это не займет много времени. А, самое главное, принесет много удовольствия.
Почему модераторы и другие активные ботоводы википедии не могут применить похожий анализ (и вообще «научный подход») — вопрос открытый.
Если у вас в знакомых есть wikipedia-активист — дайте ему знать о существовании этой статьи. Сам то я википедия-пессимист.
PS: Википедия считает любые UGC сайты «не АИ», в том числе esosedi уже несколько лет как внесен в спам листы. Потому что нельзя доверять. Как и самой википедии, по факту.

Итоги
Давным давно, лет 6 назад, в кризис 2008 года, стандартные google maps позволяли отображать наложение wiki. Теперь уже нет.
В этом году, добавив слой ^[39] вики на есоседи, я понял чего был лишен — лавины информации о местах и событиях в этих местах. Одно только надо помнить — Нельзя просто взять, и показать википедию.

PS: Многие страницы, которые в итоге попали на карту никуда не ведут. Потому что существуют «критерии значимости информации» и эти страницы просто стирают ^[40].
PPS: Я знаю что Вики не справочник, и не каталог. И не достаточно полный источник информации.

Послесловие
Быть может, мир станет лучше, и Большая_мечеть_в_Самарре ^[41] наконец будет в Самарре.

Изначально тут было много различного SQL, и именно по этому я добавил статью в хаб SQL. Но потом я решил что это лишнее, да и запросы все банальные и представляют интерес только в рамках решения этой задачи.
Пускай лучше эта статья будет примером про то как кто-то забыл про нормальные формы базы данных, внешние ключи и другие автоматические проверки целостности.
Со своей стороны просто дам SQL дамп ^[42] (Mysql, 150мб) моей базы. Играйтесь. Проверяйте выкладки. Запускайте ботов. Если это кому-то надо.

На самом деле моя история с wikipedia, geonames и «Вирупакши в Хампи» на этом не кончилась. К ним присоединился openstreetmap, прямой и обратный геокодер, и они дружно… Но об этом в другой раз.

Автор: kashey

Источник ^[43]