Иван Бегтин

Сегодня 30 сентября и по 3 октября я буду на выставке в 8-м павильоне, стенд E35 рядом со стендом ОГИЦ (Общероссийский Государственный Информационный Центр).

Если будете на выставке и есть темы для разговора милости прошу.

Спасибо, всем кто накидал ссылок и материалов по теме, в данной записи я опишу собранное.

Вот некоторые публикации:

• Wu, Manber «A Fast Algorithm For Multi-Pattern Searching» – описание алгоритма и его реализации в виде Agrep с построением NFA на базе регулярных выражений.
  
• Публикации Gonzalo Navaro и nrgrep – развитие алгоритма построения NFA на базе регулярных выражений, плюс учёт минимальной размерности строк подпадающих под шаблон.
• Parsing Techniques by Grune and Jacobs – описание алгоритма Томпсона на который ссылаются авторы выше.

Самые интересные – это публикации Navaro. Читая его я подтвердился в своих зарождающихся предположениях насчёт учёта минимальной длины строк подпадающей под данное регулярное выражение.

Но что не менее важно так это то как такие решения создаются. Например, минимальный размер подходящий под выражение строки – это метрика, характеристика данного выражения. Наличие символов начала и конца выражения ^ и $ – это также метрики влияющие на то какие строки могут через данные выражения проходить.

Обеспечив предварительную классификацию выражений можно обеспечить разбиение их в коллекции с последующей фильтрацией по данным метрикам на основе которых могут строиться индексы.

Это очень похоже на то что я описывал с построением индексов для исправления опечаток, но случай с регулярными выражениями значительно сложнее.

Ещё одна интересная тема – это оценка предсказуемости поступающих данных и выработка метрик оценки этой предсказуемости.

В любом можно говорить что решение у этой задачи есть, пусть даже и не самое простое.

Моё знакомство с регулярными выражениями началось более чем давно, ещё в то время когда я активно встречал в кодах скриптов и использовал сам для подготовки скриптов при администрировании юникс серверов.

Признаться, особой любви к ним я никогда не испытвал. Лично мне никогда не нравился подобный способ «упаковки правил», иногда их просто сложно читать. Гораздо позже размышляя над принципами анализа HTML и любых иных полуструктурированных данных, моя антипатия к регулярным выражениям сохранилась на прежнем уровне. Зачем использовать медленное и, зачастую неэффективное решение для задач которые могут быть решены другим образом? Что, в общем то, я и сейчас считаю верным – разбор полуструктурированных данных регулярными выражениями на текущем уровне развития алгоритмов и библиотек их анализа – это сущий анахронизм, ко всему ещё и неэффективный и не позволяющий набирать промежуточную статистику, равно как и многие другие возможности.

Но есть и задачи где без регулярных выражений если не невозможно,  но, скажем, отнюдь не просто. Конечно их можно заменить собственными и существующими правилами анализа текста, примеров множество, но собственные правила – это заведомое ограничение на пользователей или операторов вынужденных с этими правилами работать.

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

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

При этом существует задача принятия решения или упрощение его принятия с использованием ряда правил и построения дерева решений в конечном итоге.

Continue reading «Магия множеств регулярных выражений»

Поскольку уже было несколько вопросов о том на чём Скиур основан и как работает приведу некоторые подробности.

В проекте используется 3 технологии:

- CouchDb

- Python

- Django

Насколько я знаю, в России, это первое практическое использование CouchDb, но рад буду ошибиться если кто-либо приведёт примеры обратного.

Почему CouchDb? Потому как для подобного типа задач, когда есть понимание что структуры хранимых данных однозначно будут меняться – это наилучший подход. Можно также подумать о Thrudb или HBase, но первый слабодокументирован, а второй откровенно тяжеловат.

О том как Скиур работает.

Скиур (в переводе с армянского «белка») – на самом деле это хвост от белки, но ещё не она сама. Публичный алгоритм – это упрощённая и сильно оптимизированная под скорость версия основного алгоритма автоматизированного анализа и восстановления структуры веб страниц в общем случае.

Основной Скиура является закрытая библиотека persimmon – это набор правил, структур, алгоритмов по анализу данных с нечёткой структурой или её отсутствием. Фактически эта библиотека началась как свалка мыслей по природе информации и экспериментам основанных на моих предыдущих исследованиях по этой теме, сейчас же именно в ней и находятся все те алгоритмы которые можно отнести к ноу-хау, по определению типов смысловых блоков, классификации ссылок, гео классификации плюс ряд других алгоритмов использованных в Скиуре.

Сюда входит как «сборка регулярных выражений», расчёт особых метрик для HTML тэгов, алгоритмы классификации и выявления микро-блоков в деревьях элементов.

Цена оптимизации в производительности и в ограничении применимости алгоритма только к новостным лентам, страницам где у записей есть даты.

В итоге я возьму на себя смелость в виде 3-х утверждений:

1. Возможно построение системы направленного индексирования без предварительной настройки её человеком под каждый новый тип ресурса.

2. Возможно создание систем направленного индексирования отслеживающих и учитывающих аномалии и изменения на анализируемых сайтах. Не автоматика, но значительная автоматизация

3. Возможно построение поисковых систем общего типа а ля Cuill с углублённым и автоматическим распознаванием смысла индексируемых данных и предоставлением различных форм поиска в зависимости от их типа.

Кто знает, может быть и моё хобби – Скиур один из шагов к достижению этих утверждений.

Читаю ссылки по предложению сенатора Владимира Слуцкера по созданию юридического определения термина Интернет-СМИ. Всё бы хорошо, может быть и идея с выводом блогов из этого термин мудра, но… прежде чем сказать Б надо сказать А.

Как можно писать про Интернет СМИ не дав вначале чёткого юридического определения что такое Интернет?

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

Вот предположим я через Skype организую регулярные ежедневные подкасты – это Интернет СМИ?

А если это сделаю не я, а какой-либо медиахолдинг? В чём отличия – в наличии юрлица, периодичности, затрагиваемых темах?

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

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

Пара ссылок ссылок по теме:

• Статья на Cnews: «Сенатор предложил ввести в России юридическое понятие «Интернет-СМИ»»
• Статья на fc-info.ru: «Сенатор Владимир Слуцкер предлагает ввести Интернет-СМИ в правовое поле»

Копия из анонса в skyur_project

Завершилось первое обновление алгоритма. Это обновление является промежуточным и будет дополнятся в дальнейшем.

В это обновление вошли:
- поддержка 44 форматов дат (по сравнению с 20 в прошлой версии);
- поддержка дат обрамлённых текстом слева или справа, например, blog.lexa.ru
- ряд малых исправлений в точности интерпретации заголовков и ссылок в новостных блоках

Чего пока нет и планируется в следующем обновлении:
- поддержка англоязычных дат: сейчас они собираются и анализируются

Текущие ограничения:
- ряд ошибок распознавания связаны с неправильным распознаванием кодировки веб страницы, это сейчас решается.
- в некоторых случаях дата в тексте новости или страницы может восприниматься как метка даты новостного блока.

В последнее время всё активнее обсуждают тему можно ли регулировать / модерировать Рунет или нет и что для этого нужно.

Внесу и мои 5 копеек. Проблема контроля и регулирования Рунета той же природы что и проблема модерирования крупных социальных сетей вроде Одноклассники, Вконтракте, Facebook и так далее. Эта проблема в необходимости в огромном и постоянно растущем штате людей которые бы вычитывали новые и уже опубликованные материалы, просматривали бы подозрительные сайты.

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

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

На втором – группа экспертов подтверждает или отвергает народную оценку, фиксируя и беря на себя принятие решение голосованием по модели прямого большинства.

На третьем – модератор/администратор принимает решение о включение ресурса или материала в как кандидата на принятие мер в соответствии с законодательством.

Особенность всего вышеописанного в том что если Интернет-цензура будет неизбежной, то она должна быть:

a. Публичной.

б. Прозрачной.

в. Начиная с 2-го уровня в виде экспертной оценки – неанонимной.
В эффективность всех остальных моделей я, признаться, неверю.

Как я и обещал и даже с некоторым опережением Скиур запущен и доступен всем желающим по ссылке http://www.skyur.ru

Что такое Скиур?

Скиур – это сервис и алгоритм извлечения новостных блоков из веб страниц. Он не просто отслеживает изменения на страницах, но восстанавливает даты, текст, заголовки и ссылки новости и предоставляет их в форматах RSS или ATOM максимально приближенной к той которую сайт мог бы отдавать самостоятельно.

Какова точность распознавания?

Сейчас для того чтобы восстановить новость алгоритму необходимо чтобы у каждой новостной записи присутствовала дата в поддерживаемом им формате. На сегодняшний день алгоритм поддерживает более 20 форматов дат и, по мере обнаружения, подключаются новые форматы. Если Вы уверены что на новостной странице даты присутствуют, но алгоритм не может восстановить новости с этой страницы – дайте мне знать, возможно что эта проблема имеет очень быстрое решение.

Предварительные проверки алгоритма

Примерно 22 000 сайтов по которым  алгоритм проверялся, он успешно выявляет новостные блоки  с головных страниц у  4600.  При направленном анализе новостных страниц этих же сайтов, цифры будут ещё точнее.

Каков статус проекта?

Скиур, в текущем виде – это заведомо некоммерческий проект. Возможно что в будущем в той или иной форме он будет подвергаться коммерциализации и показу рекламы, но врядли это будет скоро, если будет вообще. Целью вывода алгоритма и сервиса на публику является апробация технологии реальными пользователями и накопление экспериментальных данных для дальнейшего его усовершенствования, соответственно сам сервис предоставляется AS IS.

Частота обновления

Сейчас частота обновления страниц составляет 2 часа. В дальнейшем, в зависимости от числа страниц, эти цифры могут меняться, но не более чем в пределах 1 суток. Всё это связано как с трафиком, так и с производительностью алгоритма. При необходимости более частых обновлений, можно связаться со мной и договорится об отдельном сервисе с более частым обновлением.

Юридические аспекты

Сервис предназначен для личного и некоммерческого использования с оговоркой на то что вебмастера могут использовать его для генерации своих RSS лент, но при трансляциях и агрегациях лент на коммерческие сайты могут применятся меры по блокировке выгрузки подобных обращений. Соответственно, вся ответственность за использование содержимого сайтов полностью лежит на пользователе как конечном потребителе информации.

Сообщество

В Livejournal было создано сообщество skyur_project в котором далее и будут происходить анонсы развития сервиса. Приходите, обсуждайте, оставляйте замечания и пожелания.

Примеры:

• http://www.skyur.ru/?url=http://www.ach.gov.ru/news/ – новости Счетной палаты РФ
• http://www.skyur.ru/?url=http%3A%2F%2Fcorp.mail.ru%2Fnews.html – корпоративные новости Mail.ru
• http://www.skyur.ru/?url=http%3A%2F%2Fwww.ashmanov.com%2Fcompany%2Fnews%2F – новости Ашманов и партнёры (удивительно, да, но RSS у них нет)
• http://www.skyur.ru/?url=http%3A%2F%2Fwww.rsoc.ru%2F – новости Россвязькомназора
• http://www.skyur.ru/?url=http%3A%2F%2Fminkomsvjaz.ru%2Fnews%2F%3Fsection%3D1%26mode%3Darchive%26page%3D – новости Минкомсвязи РФ

Поскольку удалось поднять хотя бы часть информации с дисков,  удалось восстановить и часть результатов обновлённого алгорима Скиура.

Суммарно по результату анализа 22 000 сайтов, новостные ленты были обнаружены у 4 600. Что порядка 21% от всех ресурсов где было найдено 86 тысяч новостных сообщений. При этом анализировались только «морды сайтов», начальные страницы, а при использовании на них же новостных страниц результаты могут быть ещё лучше.

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

В итоге как я и обещал ориентировочно в начале октября Скиур будет доступен публично, поначалу в форме похожей на Page2RSS.

Для тех кто не читал моих предыдущих записей.

Скиур – это название сервиса и алгоритма по восстановлению структуры новостной ленты по её HTML представлению.

В качестве параметра ему передаётся ссылка на страницу и по этой ссылке из HTML страницы извлекаются новостные ленты и преобразуются в RSS или ATOM формат. В отличии от Page2RSS отслеживаются не все изменения, а именно новости причём восстановленные включая даты, заголовки и ссылки.

В отличии от Dapper’а и других подобных сервисов где подобное можно сделать вручную, Скиур работает полностью автоматически, никакой иной информации кроме собственно веб страницы ему ненужно.

Про эту задачку и что у неё есть решения я писал раньше и всё таки решил описать один из способов как её можно решить без использования n-gram.

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

Рассмотрим что у нас есть:

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

2. Массив слов словаря по которым мы проверяем данное слово. Условно не менее 100 000 слов, в реальности до 1 миллиона.

3. Формула расчёта расстояния Левенштейна для определения отличий между словами.

4. Необходимо найти не просто первое совпадение, но всех потенциальных кандидатов.

Если решать эту задачу в лоб, то несложно понять что прямым перебором нам придётся совершить 100 000 сравнений. Это может быть немного для работы в оффлайне, но много для работы с потоками слов и работой онлайн.

Вопрос: как можно сократить число сравнений?

Continue reading «Техническое: Решение с расчетом расстояния Левенштейна для исправления опечаток»