Что такое «BigData»? Это те данные, которые нельзя просто так переварить. Или нельзя просто так приготовить. Или это вы думаете что нельзя.
Особо сильный «перекос», в этом понимании бигдаты спрятался в web-картографии, в картах на различных сайтах.
И так уж получилось — на протяжении нескольких лет я катался по различным конференциям, и рассказывал про организацию передачи данных с сервера на Карту. Иногда меня спрашивали — «а где же взять эти ваши много данных».
Это не правильные вопросы, правильные вопросы это:
— как данные хранить
— какие данные, когда и почему передавать на клиент
— что такое серверная кластеризация, как она выглядит и почему она нужна
— что с данными делать
— и зачем это все нужно %username%
А насчет откуда взять данные… Есть один такой детский стишок
Весь покрытый метками
Абсолютно весь
Остров Википедии
В океане есть
И на этом острове растет примерно десять миллионов геотегированных статей, которыми мы и воспользуемся.
Но с флорой и фауной там не все так просто — статьи растут на разных языках, в разных местах, и их на само деле много…
Поэтому мы, как настоящие герои, немного усложним задачу и добавим немного агрегатных функций, Левенштайна, Мorton кодов, esosedi и немного здравого смысла.
Повышая связность интернетов…. Примерно такими словами я представлял процесс интеграции википедии в общую кучу геоданных.
Но была проблема — Wikipedia, хоть и сама описывает не самый сложный процесс своего клонирования (Википедия: Как_сделать_копию_Википедии), совсем не хотела интегрироваться.
Потому что Wiki большая. Настоящая bigdata, для моего SSD. И скачать нужные данные на локалхост было сложно, и на сервер нельзя (потому что вся работа, описанная в данной статье, как и сама статья написаны в электричке).
Но все решаемо. Буквально за 5 минут (местный мем).
G for Geonames
Некоторое время назад я открыл для себя такой проект как geonames.org, который, в том числе, предоставляет API к «гео» статьям википедии — www.geonames.org/maps/wikipedia.html (И там все «прыгает и скачет»).
Если немного покопать, то можно найти источник их данных — проект Georeferenzierung, который после всех своих хеплов и обсуждений выливается в маленький файлик, мегабайт на 700 — http://toolserver.org/~kolossos/wp-world/pg-dumps/wp-world/
Прошу любить и очень жаловать — это CSV со всеми нужными нам статьями wikipedia.
D for Database
Шаг 1. Импортируем данные.
Скачиваем с tool server файл new_C.gz. Это обычный csv, формат которого описан в вики.
Всего возможного добра по факту не нужно — только имя статьи, координаты и длина контента документа — 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
Почти эту картинку вы могли видеть в шапке статьи про тепловые карты Яндекс.Карт пару недель назад.
На самом деле картинка кликабельна — это интерактивный пример, можно пощупать на esosedi (нормально работает только в WebKit!). По ссылке можно посмотреть не только на покрытие общими данными Вики, но также и на данные различных языковых разделов (en, ru, uk, de). А еще там можно посмотреть на какой-то странный вариант Incorrectenesses distribution map (для желающих немного математики).
Смысл этого «термина» очень прост:
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 clusterPS: никакого матана — стандартные функции с результатами на любой вкус
Что что мы получаем?
Кто внимательно читал, должны помнить (из пункта 2 импорта), что в некоторых статьях одного кластера НЕТ геопривязки. А там где есть такие грубые нарушения — могут быть и более мелкие, ну например просто разные координаты в разных статьях. Потому что хоть кластер один — статьи на самом деле разные так как разделы Вики относительно автономны.
PS: Статьи одного кластера могут не только не иметь геопривязку, но и ссылки друг на друга через интервики. Многие статьи не имеют ссылки на те статьи, которые имеют ссылки на них. Или могут иметь исходящие ссылки совсем в другой кластер. Не пытайтесь понять — я сам не понимаю как же такое случилось.
Фактически это значит, что координаты у статей могут быть, могут не быть, могут быть не правильными. А аэропорт имени Сабихи Гёкчен в ru версии «висит» над Домодедово. При этом c en версией все ок.
В данный момент это уже не так, и с Сабихой все нормально — с августа кто-то статью подправил. Но (!):
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 аэропортов с дельтой координат больше градуса.
Например Рейвенсторп и Ravensthorpe_Airport. Там с координатами все ок — просто полушария перепутали (33 и -33 градуса).
PS: Это был второй камень в огород wikipedia
Если чуть копнуть выясниться, что с аэропортами и крупными университетами почти всегда беда. Иногда кажется что какой-то странный робот ставил координаты. И везде одни и те же. Больше всего повезло такому месту как «Горловский государственный педагогический институт иностранных языков» — он собрал «в себе» 22 других учебных учреждений, переплюнув и МГУ и Лигу Плюща.
На самом деле в Википедии не так уж много статей для которых можно посчитать «deviance» — просто очень многие материалы описаны только на одном языке и расчет не произвести так просто. Но «порядок» и частота ошибок примерно сохраняется.
Многие статьи привязаны «немного» в стороне. Иногда в сантиметрах, иногда в метрах, иногда хуже. Максимальная найденная ошибка составляет примерно 60 градусов.
Найти такие места сложно, но можно. Например по данным википедии ru: Храм_Вирупакши_в_Хампи находится совсем не в Хампи(смещение 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», он же 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 и использует для адресации (пирамиды) тайлов карты.
Именно этот «эффект» нам и нужен. 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
Можно еще посмотреть модуль для друпала, который работает на основе geoHash.org, который (по сути своей) тоже «Morton number», но почему-то в base32.
Главное помните строки — это не числа, B-tree из них не построить (нормальное). Хотя — если у вас MongoDB — выбора нет, но все работает — проверено (линк на кленовый REST серверный кластеризатор от АПИ Яндекс.Карт и пример к нему)
Итак, в самом начале статьи поднимались некоторые вопросы
Q: Как данные хранить?
A: Хранить в базе данных, как данные. Как удобнее, и добить данные z-координатами.
Q: Какие данные, когда и почему передавать на клиент?
A: Использовать умную передачу данных, например RemoteObjectManager и компанию. Об этом недавно была статья.
Q: Что такое серверная кластеризация и как она выглядит и почему она нужна?
A: О! Это совсем не страшный зверь, и позволяет не только снизить нагрузку на клиент, но и обеспечить более ровное покрытие данными (оно же «прыгает и скачет»)
Остается два вопроса, на которые еще не было ответа:
— что с данными делать
— и зачем это все нужно %username%
Значит начинаю рассказать про последний этап — этап где решается что с этими данными делать, и чем они могут быть полезны.
Весь покрытый метками… Абсолютно весь… Шарик есть.
Когда я начинал писать эту статью — на дворе был август. С тех пор минуло много времени, АПИ.Карт выпустил ObjectManager и я все хотел сделать для него «ручку», чтобы вы смогли показать обьекты Википедии на своей карте. Но публичную ручку, которая выдержала бы хабраэффект я так и не сделал.
Если вы хотите получить немного «опыта» по размещению и отображению более менее нормального количества данных на карте, этот топик, топик про ObjectManager и наши выступления (раз, два) помогут вам в этом.
Но — это не тема данного повествования. Мы тут про Вики говорим.
PS: Кстати — совсем недавно на the-village вышло интервью с главой русской Википедии. Фактически это и побудило меня достать статью из черновиков.
L for Levenshtein
Повышая связность интернетов…. Примерно такими словами я представлял процесс интеграции википедии в общую кучу геоданных esosedi.
Суть проекта esosedi очень проста — добавление на карту различных мест, с целью или без цели. Чем на протяжении пары лет и занимаемся. И если в той куче объектов добавить еще данные вики — будет каша-малаша. Надо как-то поднимать связность.
Именно в этом моменте я призвал на помощь расстояние Левенштейна:
Расстояние Левенштейна — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.
Итоговый алгоритм выглядит примерно так: для всех мест, найти wikiстатьи вокруг себя, сравнить свое описание с другими кандидатами, записать результат в базу.
Момент «сравнить» не так прост как кажется — на каждую пару надо произвести примерно 16 измерений. В транслите, без гласных, без «скобок», без минус слов, через вторичные справочники…
Именно Левенштайн (и фактор расстояния) помогает понять что Златая и Золотая улочка это одно и тоже, так же как Лисья Гора и Lisa Gora.
Иногда он даже может различить Куангнам, Куангнгай и Куангнинь (это регионы Вьетнама). А вот Bắc, Bạc и Bắc — уже не сможет, потому что транслит совпадает.
Работа осложняется еще и разными наборами данных для сравнения. Никто не идеален. Например — алгоритмы. Но особенно UGC данные. Приходится работать с тем, что есть.
I for Interwiki
И хороший пример ошибок в UGS — это интервики.
Давайте откроем страницу ru:ISO_3166-2:SI (Словения). Там, к сожалению, не описан практически ни один регион.
Теперь откроем тоже самое, но на другом языке — en:ISO_3166-2:SI. Там, конечно, тоже не все нормально, но какой-то намек на данные есть.
Например там можно найти ссылку на регион SI-060 — Municipality_of_Litija, у которой есть русская версия — ru: Лития_(город). Вот только страница 3166-2 в русском варианте содержала ссылку на «Лития (Словения)». Не на "_(город)".
Второй момент — en:3166:SI кроме всего прочего имеет ссылку на «статистические регионы» Словении. Например на SI-08 Osrednjeslovenska.
Но! При заходе на en:Osrednjeslovenska_statistical_region будет редирект на en:Central_Slovenia_Statistical_Region, и у этой статьи есть русская версия. Но никакой информации об этом, о такой важной(наверное) вещи как SI-08 в русском разделе 3166:SI… ну как бы просто нет.
Похожая наркомания встречается достаточно часто. C учетом сноски о некоторых проблемах в интервики я скажу вам по секрету — error: foreign key constraint failed.
T for Translate
И есть еще одна проблема — я не знаю испанский. И плохо знаю немецкий. И знаю, что кто-то плохо знает английский. Но моя мама любит отдыхать в Соренто.
С самим Соренто все хорошо, не беспокойтесь. Но 99% статей там исключительно на итальянском. И никакой Левенштаин не поможет понять что «Долина мельниц» и «Vallone dei Mulini» это одно и тоже.
При этом, несмотря на то, что это достопримечательность мирового уровня — статья есть только на it. У нас в стране, точнее в разделе Википедии, везде все тоже самое — большая часть информации о каких либо местах или «объектах» на другие языки не переводится. Ну кроме списка наследия ЮНЕСКО.
В итоге получается, что требуется показывать информацию человеку, даже если этот человек эту информацию не сможет прочитать. Просто потому что другой информации нет.
Никаких других вариантов, кроме как использовать АПИ Яндекс.Переводчика особо предложить и нельзя.
PS: Очень жаль что АПИ Google.Translate больше не с нами.
PPS: С тех самых пор все думаю свой переводчик написать, так как качество того что есть оставляет желать лучшего...
V — значит Vежливость
Лично у меня с момента нахождения ссылки на toolserver.org и получения первого результата прошло примерно два часа. Вы тоже можете повторить мой путь, и это не займет много времени. А, самое главное, принесет много удовольствия.
Почему модераторы и другие активные ботоводы википедии не могут применить похожий анализ (и вообще «научный подход») — вопрос открытый.
Если у вас в знакомых есть wikipedia-активист — дайте ему знать о существовании этой статьи. Сам то я википедия-пессимист.
PS: Википедия считает любые UGC сайты «не АИ», в том числе esosedi уже несколько лет как внесен в спам листы. Потому что нельзя доверять. Как и самой википедии, по факту.
Итоги
Давным давно, лет 6 назад, в кризис 2008 года, стандартные google maps позволяли отображать наложение wiki. Теперь уже нет.
В этом году, добавив слой вики на есоседи, я понял чего был лишен — лавины информации о местах и событиях в этих местах. Одно только надо помнить — Нельзя просто взять, и показать википедию.
PS: Многие страницы, которые в итоге попали на карту никуда не ведут. Потому что существуют «критерии значимости информации» и эти страницы просто стирают.
PPS: Я знаю что Вики не справочник, и не каталог. И не достаточно полный источник информации.
Послесловие
Быть может, мир станет лучше, и Большая_мечеть_в_Самарре наконец будет в Самарре.
Изначально тут было много различного SQL, и именно по этому я добавил статью в хаб SQL. Но потом я решил что это лишнее, да и запросы все банальные и представляют интерес только в рамках решения этой задачи.
Пускай лучше эта статья будет примером про то как кто-то забыл про нормальные формы базы данных, внешние ключи и другие автоматические проверки целостности.
Со своей стороны просто дам SQL дамп (Mysql, 150мб) моей базы. Играйтесь. Проверяйте выкладки. Запускайте ботов. Если это кому-то надо.
На самом деле моя история с wikipedia, geonames и «Вирупакши в Хампи» на этом не кончилась. К ним присоединился openstreetmap, прямой и обратный геокодер, и они дружно… Но об этом в другой раз.
Автор: kashey
