Как распарсить строку и построить дерево категорий товаров и услуг?

Question

[nevro]

Scrapy и прочие варианты - здорово, но для самообразования и прокачки логики не годится.
К примеру, нужно распарсить строку и построить дерево категорий товаров и услуг (из прошедшего конкурса яндекса по android-разработке): https://money.yandex.ru/api/categories-list
кусок: [{"title":"Телефон","subs":[{"id":157291,"title":"Мобильная связь"},

Тут информация структурирована, а не просто массив. И так же в условии сказано про дерево. Значит,
1. сначала нужно выбрать тип данных, подходящий для хранения информации в такой структуре? Для такой структуры как в условии, лучше взять dict, или писать свой?
2. В общем виде, алгоритм выглядит как циклы прохождения по строке и проверки каждого символа на все эти скобки, двоеточия, запятые, кавычки и остальное?
3. В питоне для таких проходов и сравнений используются регулярные выражения? Только начал языком интересоваться - успел узнать только про split у строкового типа.

Comments

[Владимир Мартьянов]

Приведенный кусок кода очень похож на JSON. В Питоне есть готовая реализация его парсера. Если вас интересует поковыряться - lex + yacc.

[Сергей]

А вы уверены, что вам нужно вручную парсить это текст? Это же обычный JSON.

[nevro]

Сергей: мне для практики надо - с алгоритмикой совсем плохо, надо мозг обучать как-то. Как пойму и научусь писать парсеры, буду пользоваться готовыми библиотеками. А иначе стремно получается.

[nevro]

Владимир Мартьянов: добавлю к scrapy для изучения, спасибо.

[Владимир Мартьянов]

nevro: По ним даже книга была у O'Reily, может и на русском тоже.

Answer 1

[Vitaliy Orlov]

Я напишу в целом, т.к. это подойдет для любого языка

Алгоритм работы парсера довольно прост, и по большей части делится на 3и этапа:
1) Получить данные
2) Разобрать данные
3) Сохранить данные

1) Для того чтобы получить данные, надо изучить стек функций для работы с сетью. Можно гуглить по такому запросу "Как скачать веб-страницу" + твой ЯП (PHP, Java, Python и т.д.). Тут ты должен написать функцию которой на вход передашь url, а на выход получишь данные (html, json, xml и т.д.)

2) Разобрать данные можно либо с помощью готовых библиотек под нужный формат, либо с помощью регулярных выражений, либо с помощью строковых функций. Тут на помощь придет запрос "Строковые функции" + твой ЯП или "регулярные выражения" + твой ЯП. На этом этапе ты должен написать функцию, которой на вход поступают данные, а на выходе получаешь заранее утвержденную структуру.

3) Сохранять данные в необходимой структуре можно в файлы или в БД. Опять в гугл с запросом "Работа с бд " + твой ЯП, либо "Работа с файлами" + твой ЯП. Тут твоя задача написать функцию, на вход которой приходит заранее утвержденная структура, а на выходе ты получаешь результат "сохраненные данные"

Ну, собственно и всё. Идешь в гугл, изучаешь матчасть и пишешь парсер.

Если же тебя в большей степени интересуют алгоритмы разбора, тогда советую посмотреть код "калькуляторов" на твоем ЯП, погуглить можно по запросу "калькулятор со скобками", "Разбор и вычисление выражений". Это классическая задача, разбор твоего куска будет очень похож.

Comments

[nevro]

Спасибо за алгоритм. Да, в большей степени интересует навык самому составлять алгоритмы. Разобранное выражение предварительно сохраняется в программе, прежде чем будет записано в файл либо базу? Применительно к питону не подскажете, какой тип использовать для такого промежуточного хранилища? В языках вроде ява наверняка есть подходящий тип, а вот питон сильно аскетичен по сравнению с ними.

[Василий Пупкин]

Хороший ответ. Могу добавить, что для реального парсера может понадобиться эмуляция яваскрипта, ну и почти на всех ресурсах, которые может быть интересно парсить - есть свои алгоритмы распознавания роботов, капчи, и просто ограничения по запросам с баном за злоупотребления. Поэтому следующим этапом вам нужно будет научиться работать в несколько потоков через прокси/тор, обходить капчи (антигейт), знать лимиты (экспериментально, когда нет API), эмулировать js, например NodeJS + Selenium(ищите на хабре), есть ещё что-то на PHP и другие варанты.

[Vitaliy Orlov]

nevro: разобранные данные хранятся в момент разбора очень по разному, все зависит от задачи. Например, представь тебе надо спарсить imdb, все фильмы, комментарии, актеров, их фото и т.д. В общем это оооочень много разных данных, хранить их в памяти не имеет смысла. Скачал страницу, разобрал, записал данные в базу, повторяешь все по-новому. С другой стороны, например есть футбольные команды, у них есть состав, например человек 50 включая тренеров, менеджеров у каждого своя страница. В таком случае можно в цикле обойти все 50 ссылок, обработать данные, и только потом записать.. Хранить данные можно в чем угодно, это может быть как обычный массив, так и какой-нибудь большой объект.. Все зависит от задачи. В любом случае, как заметил @Vasya_32, горлышком будет не хранение и запись данных, а загрузка данных из сети.

[nevro]

Vitaliy Orlov: То есть сначала анализируется, какая нужна информация и какие у нее есть взаимосвязи? Ведь в базу просто так не засунешь, нужно сначала ее разработать: таблицы, связи. Результат анализа исходной информации - создать структуру таблиц и алгоритм парсера (в случае, если парсить надо не структуру-каталог или нечто уже известное и реализованное)?

[nevro]

Василий Пупкин: Спасибо, не подозревал о такой неожиданности.

[Vitaliy Orlov]

nevro: Бывает по-разному, но в целом так как ты написал: прежде чем сохранять уже разобранную, нужную информацию, нужно создать базу для хранения этой информации. Либо если такая база со связями уже есть (например блог wordpress), значит разобраться как там что устроено и написать класс адаптер, в который ты передашь данные из парсера и который запишет их в нужном формате в соответствующую бд. Бывают и другие задачи, например, твоя задача спарсить данные, а дальше отдельный программист будет писать на их основе постер в свою систему. Как пример парсить Яндекс.Маркет (фото+описание) и заливать данные в Magento. Тогда вы договариваетесь в каком формате ты передашь данные и тогда ты можешь их сохранить, например в json или вообще передать класс парсера, которому на вход будут передавать url в Я.Маркете, а на выходе он будет возвращать ссылки на фото + описание. А уже другой человек, интегрирует этот класс в свою систему... В общем бывает по-разному.

Answer 2

[olexande]

Для хранения, возможно деревья помогут ...
habrahabr.ru/post/112421

Answer 3

[nonlux]

Почитай банду четырех )
Например интерпритатор
Ну и многое другое от них, позволит создать лаконичный парсер.