Длинное вступление
Совсем недавно мне пришлось подготовить работу для университета. Ну и как всегда в области, которая мне не интересна. Задание было принято без какого либо энтузиазм и хотелось побыстрее от этого избавиться. Задача стояла так «Извлечение центральных статей из гипертекстовых документов».
Я не стану расписывать возможные варианты использования подобных алгоритмов. Я уверен, что каждый из вас без проблем придумает хотя бы пять различных вариантов применения.
Бегло пробежавшись по просторам глобальной сети я понял, что за 10 лет в этой области никто не крикнул «Эврика!» и все подходы основываются на анализе Dom-модели документа. Кто-то использует одни принципы, кто-то другие, но все поголовно следуют набору правил для анализа Dom-модели документа. Побродив еще немного по просторам Хабра я наткнулся на статью, в которой автор рассказывал про алгоритм VIPS, разработанный в недрах Microsoft Research. Идея показалась очень привлекательной, и я решил придумать что-то свое и принялся за мыслительную деятельность. День, два, три… Ничего необычного в голову не приходит. Пришлось отбросить идею поиска центральной статьи с помощью компьютерного зрения. Такой подход к решению проблемы оказался мне не по зубам.
Что же делать? Писать еще один парсер Dom-дерева, как это делают люди уже больше 10 лет? Хочется уточнить, что работа должна быть больше исследовательская и не нацелена на получение конкретного результата. Немного пообщавшись с людьми, я наткнулся на язык разметки Markdown. Интересная штука, подумал я и лег спать…
Утром, на свежую голову я рискнул предположить, что в огромном мире талантливых людей уже кто-то разработал приложение, которое транслирует не markdown в html, а наоборот. Предположение, поисковик, результат. Было найдено несколько приложений авторов, но мне приглянулась минималистичная библиотека html2text. Привлекли меня не ее возможности, а то, что реализация выполнена на языке Python. С языком Python я не дружу и сталкиваюсь с ним в третий раз в жизни, но всему виной требования к работе.
Понеслась
Итак, в основе метода поиска центральной статьи web-документа, изложенного в данной статье, лежит идея анализа markdown-документа, который мы получаем в результате конвертирования web-документа с помощью библиотеки html2text.
В основе метода лежит идея о том, что центральная статья – это целостный элемент, который находится в определенном месте markdown-документа. Следовательно, для того, что бы выделить центральную статью из markdown-документа, нам необходимо найти начало и конец этой статьи.
Верхняя граница
Как найти верхнюю границу центральной статьи? Давайте откроем любой новостной сайт. Задумайтесь, как вы определяете начало статьи? С детства мы привыкаем, что любая книга, статья, заметка, глава начинаются с заголовка. А если вспомнить книги русских народных сказок, то там даже первая буква слова, с которого начинается сказка, выделена ярко и красочно.
Все это перенеслось и в Web. Статья начинается с заголовка! Нам нужно найти заголовок статьи и можно считать, что козырь у нас в кармане. Но чтобы найти что-нибудь нужное, нужно сначала знать, что искать. Так вот же оно, у нас под носом! Прошу обратить ваше внимание на заголовок web-документа. Любой, уважающий себя портал, размещает название статьи в заголовке web-страницы. А еще он любит размещать там название себя любимого.
Вот мы и подошли к истине. Чтобы найти начало центральной статьи, нам необходимо найти самую большую подстроку заголовка web-страницы в markdown-документе. В результате испытаний я обнаружил, что такая подстрока может встречаться несколько раз, а значит мы опять стоим перед выбором. Выбирать нужно тот вариант, где заголовок не является ссылкой. К этому можно добавить, что заголовки выделяют тегами «Заголвок» (я не реализовывал).
Нижняя граница
Итак, с верхней границей мы разделались быстро. Что с нижней? Вот тебе и приехали… Тут нам так легко не отделаться.
Хочется сказать, что я очень много экспериментировал, придумывал разнообразные правила, критерии и прочее прочее. В итоге я остановился на очень примитивном варианте, который постараюсь изложить ниже.
Искать нижнюю границу мы будем анализируя каждый параграф документа, начиная с заголовка статьи. В результате, для каждого абзаца мы будем принимать решение, несет ли он в себе информационную нагрузку или нет. Очень часто статью снизу отделяет некоторое количество абзацев, не несущих смысловой нагрузки. Их-то нам и необходимо найти – они и будут считаться нижней границей центральной статьи.
Поиск нижней границы происходит в два этапа. Давайте еще раз посмотрим на начало центральной статьи. Заметно, что заголовок статьи и само содержание разделяет некий «мусор». Мы понимаем, что этот мусор попал в наш markdown-документ и нам его надо отфильтровать, иначе он всю малину испортит. Для этого я ввел понятие реального начала статьи. Да, мы помним, что верхняя граница статьи – это ее начало. Но нам нужно найти реальное начало – начало содержательной части. Поэтому мы введем константу: минимальное количество параграфов, из которых может состоять статья. Я долго экспериментировал с этим значением и выбрал число 3. Нет, не наугад. Естественно собрал базу данных статей и посмотрел минимальное число параграфов.
Что дальше? Дальше идем по параграфам и ищем 3 идущих подряд параграфа, несущих смысловую нагрузку. Параллельно, запоминаем номера параграфов, которые мы посчитали «мусором». Мы их потом удалим, а сейчас пускай пока живут.
Нашли? А дальше все по-старому. Анализируем параграфы дальше и ищем несколько параграфов, идущих подряд и не несущих смысловой нагрузки. Нашли? Они то и будут нашей нижней границей центральной статьи. По иронии судьбы, для значения количества не смысловых параграфов я снова выбрал 3. Опять же, не с потолка, а на основе анализа и статистики.
Вот как бы и все. Но я так мило обошел вопрос «А как же определить, несет абзац в себе информацию или нет?».
А как же определить…
Не сосчитать, сколько баранов, свиней и телят было съедено, пока я приблизился к решению данной задачи на пушечный выстрел. К сожалению еще ближе подойти не удалось, но для начала и этого хватило.
Я выделил два критерия, по которым оценивается параграф:
- Критерий отношения количества слов со ссылками к количеству слов без ссылок.
- Критерий средней длинны предложения.
Критерий отношения количества слов со ссылками к количеству слов без ссылок.
Подсчитывается количество слов в параграфе, которые являются ссылкой и количество слов в параграфе, которые не являются ссылкой. Дальше делим первое значение на второе. Коэффициент может принимать значения больше нуля. Если же в параграфе нет слов, которые не являются ссылкой, то значение критерия равно количеству слов со ссылками.
Для того, что бы определить, несет ли в себе предложение смысловую нагрузку на базе этого критерия нам необходимо некое граничное значение. Экспериментальным путем я получил значение 0.9. Соответственно, если значение критерия меньше граничного значения – считается, что параграф несет смысловую нагрузку.
Перед выполнением подсчетов следует исключить из параграфа все ссылки на изображения а так же подсказки к ним ну и знаки препинания естественно.
Критерий средней длинны предложения
Тут все просто. Считаем длину (количество слов) каждого предложения в параграфе и берем среднее. Опять-таки, нам необходимо граничное значение. Экспериментальным путем я получил константу 5. Хотя и 4 тоже неплохо подходит. Если значение критерия меньше граничного значения, он считается таким, что не несет смысловой нагрузки.
Быть или не быть?
Использовать критерии порознь не представляет возможности. А вот вместе они представляют из себя довольно неплохую парочку. Итак, если по обоим критериям считается что параграф несет в себе смысловую нагрузку, то в целом параграф можно считать частью центральной статьи. Если хотя бы по одному критерию параграф не несет смысловой нагрузке, то считается, что он не принадлежит центральной статье.
В заключение
Подобное решение не претендует на конечное, правильное, быстрое и адекватное. Это всего лишь мое творчество.
Что радует:
- Мы практически не зависим от структуры сайта и его внутреннего устройства (dom-дерева).
Что печалит:
- Таблицы и блоки кода, которые могут встречаться в статьях пагубно влияют на определение нижней границы статьи. В принципе, этот недостаток можно легко исправить внедрив в алгоритм дополнительный анализ на наличие этих элементов.
- Нету гарантии, что на одном и том же сайте будет возможность пропарcить все статьи. Да, алгоритм не зависит от структуры сайта, но теперь он зависит от содержания статьи.
В дополнение я выкладываю небольшой файл с реализацией, которая ни на что не претендует. Как уже отмечал выше, пишу на Python третий раз в жизни.
Запускаем так:
python dataext.py -H korrespondent.net/showbiz/music/1372856-dzhennifer-lopes-vystupit-v-kieve
Параметр «-H» означает, что результат будет обратно преобразован в html. Если же его не указать, то на выходе мы получим markdown.
Естественно, не забываем установить все модули, используемые в приложении. Все они должны быть в репозиториях вашего любимого дистрибутива Linux.
PS: Сайт Корреспондента выбран абсолютно случайно. Сам я его не читаю :)
Автор: surik
