Browse by Tags

Про метаданные документов. Без примеров
08 декабря 10 10:45

Последний раз про метаданные в офисных документах я писал более года назад в этой заметке «Извлечение скрытых метаданных из документов MS Office«.

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

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

Итак метаданные.

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

Фактически я бы разделил эту идентификационную информацию на 4 типа:

метаданные документа – свойства (properties)  документа которые обычно забывают удалить при сохранении и пересылке.

метаданные вложенных объектов – свойства вложенных OLE объектов и изображений.

маркеры – данные в гипертексте документа идентифицирующие его владельца.

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

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

1. Метаданные документа

Это свойства документа которые видны если открыть его «Свойства» в Эксплорере Windows или открыв в соответствующей программе MS Office. Про эти свойства, казалось бы, должны знать все и последние версии MS Office включают возможности удаления этих метаданных. Однако на практике это далеко не так. Часто метаданные забывают почистить и удалить и там можно увидеть «чувствительную информацию» о том кто был на самом деле автором документа,

2. Метаданные вложенных объектов

Об этом я писал в прошлой заметке и повторю сейчас. Вложенные объекты – это так называемые OLE объекты или контейнеры StructuredStorage содержащие другие документы/объекты с которыми умеет работать MS Office. Ещё вернее что объекты с которыми вообще умеет работать MS Windows, но в данном случае чуть упростим.

Если описать это ещё проще, то когда Вы готовите таблицу в Excel, а потом вставляете её в презентацию – это вставка OLE объекта. Точно также если вы делаете диаграмму в Visio и потом вставляете её в презентацию или документ – это вставка OLE объекта, если только вы не преобразовали вначале диаграмму в изображение.

Особенность этих вложенных объектов в том что каждый из них несёт свой собственный набор свойств заданных в той программе в которой данный объект создавался. Если Вы вложили таблицу Excel – значит у документа будут свойства которые указаны в Excel. Если объект Visio, то свойства заданные в Visio.

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

Вложенные объекты можно извлечь несколькими способами, но большая часть из них весьма техническая и требует знаний того как устроены документы MS Office внутри, поэтому самый практичный способ – сохранить документ в одном из форматов OpenXML и распаковать его любимым ZIP распаковщиком. В результате, OLE объекты будут в папке embeddings. Впрочем  я ранее уже это описывал и заметке на которую я сослался вначале этого поста есть подробное описание процесса.

Однако, вложенными объектами могут быть не только OLE объекты. К этой же категории носителей информации можно отнести изображения. В изображениях может сохранятся информация EXIF (в JPEG файлах) и XMP. Подобное встречается гораздо реже, в основном если кто-то необдуманно вставляет в документы необработанные фотографии. Извлечь изображения можно по тому же рецепту – преобразовать в OpenXML, распаковать и заглянуть в папку media.

3. «Маркёры»

Это очень условное название для той информации которая может присутствовать в тексте документа и позволяет узнать более о его авторе. К подобной информации можно отнести:

обсуждения и комментарии в режим правки. Иногда (в последнее время всё реже) авторы документов забывают про режим правки и публикуют документ со всей историей обсужения, заметками и так далее.

ссылки. В некоторых случаях, сознательно или по ошибке в документах остаются ссылки на локальные документы того же пользователя или документы в его локальной сети. Чаще всего эти ссылки указывают на файлы на Desktop или же в папке «Мои документы«. Главное что такие ссылки позволяют узнать – локальное имя пользователя извлекаемой из пути к данному документу.

4. Скрытые данные

Кроме вполне очевидных данных (маркёров) в тексте есть некое количество данных которые скрыты в блоках бинарных файлов о предназначении которых можно знать или догадываться. Например, в Excel файлах есть специальный блок PLS содержащий информацию о принтерах.  Он содержит точно название модели принтера и его название и, скорее всего некую дополнительную информацию.

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

А как собственно получить все эти данные?

Инструменты

Существует довольно большое число инструментов по работе с метаданными, но чего-то универсального не нет. Каждый из инструментов имеет свои плюсы и минусы и многие из них (но не все) описаны в статье Document Metadata Extraction в Forensics Wiki -http://www.forensicswiki.org/wiki/Document_Metadata_Extraction здесь много ссылок на инструменты и библиотеки.

Набор инструментов:

MS Office 2007-2010 для преобразования из бинарных форматов MS Office в OpenXML. В данном случае OpenOffice не подойдёт поскольку он не сохраняет OLE объекты

Strings - утилитка из пакета Sysinternals позволяющая извлечь строковые переменные.

OffVis – это такая специальная утилита от Microsoft позволяющая копатся в глубинах офисных документов. При глубоком анализе документов и выковыриванию PLS блоков из файлов Excel – незаменима. Скачать можно здесь http://download.techworld.com/3214034/microsoft-offvis-11/

Metadata Extraction Tool – бесплатная утилитка по извлечению метаданных из офисных документов, PDF, изображений и так далее. заглядывает неглубоко и находит не всё  http://meta-extractor.sourceforge.net/

Catalogue – собирает метаданные из разного типа файлов http://peccatte.karefil.com/software/Catalogue/CatalogueENG.htm

- Metadata Analyzer – извлекает метаданные (только базовые) http://smartpctools.com/metadata/

Document Trace Remover – убирает метаданные http://smartpctools.com/trace_remover/

- Oracle Outside In - инструмент для разработчиков, поддерживает около 500 форматов файлов http://www.oracle.com/us/technologies/embedded/025613.htm

Это, конечно, совсем не предел тем вокруг извлечения информации. Есть также метаданные и способы их выковыривания из документов PDF и OpenOffice, электронных писем и так далее.

Кроме того есть масса нераскрытых возможностей связанных с неполным описанием бинарных проприетарных форматов.

Originally published at Иван Бегтин. You can comment here or there.

Пространство решений
12 ноября 10 04:54

Я тут почитал обсуждения вокруг моего прошлого поста по работе с регулярными выражениями и упоминания про FPGA и не только и вспомнился мне мой личный опыт по работе с FPGA и вообще решением сложных задач. К тому же NDA у меня давно уже истёк так что можно рассказывать.

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

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

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

а. Преобразовать картинку отпечатка пальцев в специальную модель.

б. Проводить нечёткое сравнение одной модели с другими.

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

И как раз для этой цели компания заказала разработку специального FPGA-девайса который мог бы обрабатывать ну очень много отпечатков, до сотен тысяч и более.

Девайс этот был разработан и передан нам в отдел качества в формате «надо принять». А то есть было понятно что он как-то работает, но разработка извне никак не курировалась, документации было минимум, никаких тесткейсов и так далее.

Собственно что это было. Это был действительно мощный компьютер со встроенным Linux’ом с огромным числом спец-процессоров в которые заливалась специальная прошивка с алгоритмом, а далее заливались модели отпечатков пальцев, вплоть до миллиона отпечатков. Далее в девайс должны были отправлять отдельные отпечатки на сравнение и он возвращал ID’шники отпечатков ранее в него загруженных прогоняя задачу через все процессоры. Девайс был реально ОЧЕНЬ БЫСТРЫМ то есть возникни задача загрузить в него миллион настоящих отпечатков, то он мог бы в проводить аутентификацию по новым в течении нескольких секунд.  Те кто сталкивался с подобными задачами знают насколько это непросто.

Однако, были и свою нюансы и с избытком. Первый и ключевой нюанс в том что девайс работал через TCP/IP где у него был специальный демон через который загружались прошивки, модели отпечатков и модели на аутентификацию. Этот демон работал асинхронно, работать с ним было реально непросто и многих возможностей нехватало.

Второй нюанс был в том что при нагрузочном тестировании время от времени у него «отключались» отдельные процессоры, а то есть переставали по тем или иным причинам отвечать, видимо из-за каких-то внутренних программно-аппаратных проблем о которых могли знать только его разработчики.

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

И что делать? Особенно что делать мне как человеку весьма ленивому, а тут не не до лени – надо бы заставить эту штуку работать хоть как-то. Кроме того разработчиков тоже больше одного и у них тоже конфликты кто и как с устройством работает.

Моё решение было очень простым. Я хорошенько покопался в документации и клиентских библиотеках и написал свой эмулятор этого девайса на Python. Эмулятор мог быть установлен на любой компьютер и поддерживал  все команды этого девайса. Вплоть до того что к нему была прикручена библиотека для матчинга отпечатков от серверного продукта и он мог сравнивать небольшое число отпечатков, до тысячи. То есть это был не только полнофункциональный эмулятор, а практически сервер и с ним то мы все дружно и заработали. Далее последовательно по мере обнаружения я добавлял в эмулятор новые фичи по эмуляции известных багов девайса и опять же смог автоматизировать всё что только можно отработав все свои тесты на десятках эмуляторов одновременно.

Однако мою идею в том что можно использовать кластер из моих «эмуляторов» вместо одного FPGA-устройства тогда не поддержали. Увы и ах, а было бы интересно если бы было по другому.

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

Лично я тогда приобрёл опыт в том что некоторые решения могут быть весьма некрасивыми, но объективно необходимыми и действенными. И каким-бы ни был тот самый FPGA-девайс с точки зрения его сопровождения, он был одним из немногих способных решать такие задачи.

Originally published at Иван Бегтин. You can comment here or there.

Техническое: про регулярные выражения и Яндекс PIRE
11 ноября 10 11:37

Что-то давно я не писал про технологии и алгоритмы.

А тем временем, на днях, представители Яндекса выложили в открытый доступ ряд open source проектов – http://clubs.ya.ru/company/replies.xml?item_no=30753

Самый интересный из которых, на мой взгляд – это PIRE, https://github.com/dprokoptsev/pire Perl Incompatible Regular Expressions Library.

Весьма интересная штука для тех кто когда либо прогонял через шаблоны большие объёмы текста/файлов/сетевого трафика и прочего файлового счастья.

Как я понимаю авторы обещают производительность до 400MB в секунду на «common hardware», конечно, с кучей ограничений по тому что в регулярных выражениях может быть, но тем не менее – это быстро. Жаль там нет враппера для Питона, я бы попробовал на своих данных, благо их у меня накопилось много и есть с чем сравнивать. Пока поверю авторам на слово и исхожу из того что это так и есть, благо подход описанный у них в документации вполне понятен и должен работать.

Однако, жаль что подобных открытых разработок небыло хотя бы пары лет назад. Когда я разрабатывал Скиур – http://www.skyur.ru (это такой сервис по преобразованию веб-страниц в RSS), то решал задачи для которых как раз были необходимы такие инструменты  поскольку частью алгоритма является большое число тогда ещё регулярных выражений. В совокупности чуть менее 200, точно не скажу поскольку происходит их сборка из некого базового набора.

Но не имея таких инструментов я пошёл другим путём с решением «в лоб», также оказавшего эффективным.

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

2. Собственно автоматы проанализированы и разбиты на повторяющиеся блоки.

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

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

То есть, фактически, это путь эффективен только в случае:

a.  Управляемости входного потока выражений.

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

Лично я нашёл что PyParsing - http://pyparsing.wikispaces.com при соблюдении описанных выше действий обеспечивает ускорение сравнения по сравнению с регулярными выражениями в разы. Собственно он и является весьма удобным конструктором.

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

Originally published at Иван Бегтин. You can comment here or there.

Postedfrom Иван Бегтин | 0 Comments    
Google Refine – новое название для Gridworks
11 октября 10 09:40

Для тех кто может быть ещё не знает Google купили компанию Metaweb – создателей FreeBase и Gridworks.

Теперь Gridworks называется Google Refine и доступно по другому адресу https://code.google.com/p/google-refine/

Gridworks, а теперь Google Refine – это один из мощнейших и инструментов по очистке данных. Ему можно на вход подать данные в CSV формате и далее различными способами перетасовывать колонки, фильтровать, обогащать, формировать производные колонки с помощью встроенных интерпретаторов Jython и GEL.

В общем и целом очень мощная штука, пожалуй, лучшая из бесплатных.

Originally published at Иван Бегтин. You can comment here or there.

Продолжение по поводу анализа структуры сайтов
04 октября 10 12:13

Хотя на сайте MS Research много интересных материалов, но, на самом деле отправной точкой во всём что касается извлечения информации из веб-сайтов, классификации, аннотирования и так далее – это страничка профессора Bing Liu http://www.cs.uic.edu/~liub/ из Института Иллинойса Чикаго.

Помимо того что он автор книги Web Data Mining http://www.cs.uic.edu/~liub/WebMiningBook.html где охватывает почти все темы, но у него же на сайте есть обучающий курс по Data Mining and Text Mining http://www.cs.uic.edu/~liub/teach/cs583-fall-10/cs583.html где как раз очень много материалов или ссылок на материалы других исследователей по структуре веб-сайтов.

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

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

Некоторые интересные и очевидные мысли которые я в его презентациях разглядел:

  • данные в Веб сильно зашумлены и алгоритмы по автоматическому анализу должны уметь от этого шума избавляться
  • большая часть данных в Веб представлена фиксированным набором способов её представления – шаблонами в виде HTML тэгов
  • для выявления повторяющихся объектов на странице нужна их топологизация, формирование шаблонов в виде последовательностей полей и меток
  • для определения структуры сайта можно использовать tree edit distance используя DOM как дерево
  • главные проблемы работы с врапперами в их сопровождении и повторном обучении. В ответах на вопросы: как определить что враппер не работает? как его автоматически починить? должно ли переобучение менять текущий враппер или создавать новый?

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

Originally published at Иван Бегтин. You can comment here or there.

Postedfrom Иван Бегтин | 0 Comments    
Filed under:
Понимание структуры веб-сайтов
02 октября 10 07:04

Оказывается в Microsoft Research есть проект Website Structure Understanding and It’s applications с весьма впечатляющей коллекцией материалов по этой теме.

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

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

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

И, конечно, разница в подходе – они основываются на произвольных выборках веб-страниц, кластеризации ссылок, кластеризации структуры веб-страниц и последующих вероятностных предположениях.

Я же пытался зайти со стороны предварительной классификации сайта целиком, идентификации CMS, выявлению микро-признаков с «переупаковкой» структуры веб-страницы из DOM в специального рода таблицы.

Если бы я в последние годы не увлёкся проектами в области общественного блага (РосГосЗатраты, Открытые данные), то пожалуй самое интересное это было бы закончить исследования в этой области. Так что читаю такие материалы не без лёгкой белой зависти потому как очень увлекательно.

Originally published at Иван Бегтин. You can comment here or there.

Postedfrom Иван Бегтин | 0 Comments    
Filed under:
Сервисы извлечения информации о веб-сайтах
29 июля 10 10:58

В последнее время всё больше появляется сервисов по извлечению информации из веб-сайтов. Например, сравнительно давно существует BuiltWith и недавно появился W3Tech.com.

Оба позволяют увидеть о сайте много всего интересного типа какие счетчики используются, какие технологии используются и какая CMS применяется.

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

Правда эти сервисы позволяют анализировать тренды в технологиях, их распространённость и так далее.

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

Например, данные о сайте Российской Газеты в обоих сервисах – http://w3techs.com/sites/info/rg.ru и http://builtwith.com/rg.ru. BuiltWith подробнее, но вообще Российской специфики маловато.

Или вот посмотрим Roem.ru – http://builtwith.com/roem.ru и http://w3techs.com/sites/info/roem.ru. Тут информации побольше, но, опять же Российской специфики мало.

Я, честно говоря, в своё время тоже интересовался этой же темой. Однако у меня цели были несколько иные – набивка базы массой вспомогательных метрик для улучшения различных алгоритмов обработки веб-страниц. Но промежуточный результат примерно такой же как в сервисах выше – извлечение массы признаков по группе правил, всего этих правил около 500. Этот механизм уже 1.5 года существует как веб-сервис и этот сервис использовался в ГосСети (www.govweb.ru) для сбора технологий на сайтах.

Сейчас у него есть простенький веб-интерфейс, http://data.skyur.ru в котором можно посмотреть как это работает на практике. Тем кому интересно могут посмотреть там те же сайты http://data.skyur.ru/?host=www.rg.ru и http://data.skyur.ru/?host=www.roem.ru или вот http://data.skyur.ru/?host=www.opennet.ru.

Но, в общем-то, это демка. Так что визуально всё без изысков. А вот стоит ли делать доступным веб-сервис пока не решил.

Originally published at Иван Бегтин. You can comment here or there.

Postedfrom Иван Бегтин | 0 Comments    
Filed under: ,
FreeBase Gridworks released
10 мая 10 12:27

Появился исходный код Gridworks – http://code.google.com/p/freebase-gridworks/ , а также всяческие интересные примеры там же, в Wiki проекта. Этой такой инструмент по очистке и преобразованию данных сделанный внутри Metaweb’а, компании разработчика проекта Freebase.

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

Багу я им уже зарегистрировал, но сколько ждать придётся неизвестно.

Originally published at Иван Бегтин. You can comment here or there.

Систематизация распознавания пола и этноса по ФИО
04 мая 10 05:03

Какое-то время назад я эту тему поднимал в посте «Распознавание национальности по имени» – http://ivbeg.livejournal.com/119528.html

Но там было нечто вроде результатов экспериментов, сейчас же затрону тему систематизации того как можно обрабатывать ФИО и какую информацию можно на основе ФИО извлечь.

Предыстория этого текста исключительно практическая, поскольку я очень много с данными работаю, то периодически возникают задачи по тому как обогатить, улучшить, извлечь и отклассифицировать данные.  Так, например, анализ  ФИО даёт возможность  добавить как минимум 2 новых среза – гендерный и этнический (более правильное название определения национальности).

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

Этнический же срез интересен только на больших выборках, но поскольку эту информацию хотя бы частично можно извлечь, то опишу этот процесс.

Почему систематизация ? Лично я придерживаюсь того мнения что систематизации мало не бывает. Иногда это вредит – поскольку приводит к значительному углублению в детали, но чаще это помогает поскольку позволяет лучше понять предметную область и прежде чем приступать к воплощению в коде каких-либо алгоритмов – понять, с чем же имеем дело и как обеспечить простоту анализа данных в сочетании с максимально возможным охватом.

В случае ФИО, начало систематизации начинается с шаблонов.

Шаблоны

Форм записи ФИО не очень много и они вполне поддаются систематизации и укладываются в несколько шаблонов которые, в свою очередь, разделяются на несколько элементов.

Этих элементов немного и их можно перечислить:

s – Фамилия (surname)

f – Личное имя (first name)

m – Отчество (midname)

S – Однобуквенная запись фамилии

F – Однобуквенная запись имени

M – Обнобуквенная запись отчества.

Далее при анализе ФИО я буду исходить из того что ФИО – это не только фамилия, имя и отчество, но в реальной жизни это гораздо большее число форм написания того же.

При этом у использования этих элементов есть свои особенности в частности есть устоявшиеся сочетания в которых они присутствуют. Далее я приведу перечень шаблонов для определения этих сочетаний:

sfm – Фамилия, имя и отчество. Например, Пилипенко Мария Геннадьевна

fms – Имя, Отчество, Фамилия. Например, Александр Аронович Хромов

sFM – Фамилия и по первой букве от имени и отчества. Например, Васильев И. И. или Минниханов Р Е

FMs – первые буквы от имени и отчества и фамилия полностью. Пример: А. Ю. Макаренко, Н.Г. Буранов

sfM – фамилия и имя полностью и первая буква от отчества. Примеры: Ефимов Борис А., Карманова Мария В.

Fs – Первая буква имени и фамилия. Например, А. Румянцев или В Ручкин .

sF – фамилия полностью и первая буква от имени. Примеры: Борисов Г., Рахмонова Е.

s – только фамилия. Например: Хазанов, Минниханов, Дудкина, Малых

fs  - имя, фамилия. Например: Арут Карапетян, Борис Рыбин

sf – фамилия, имя. Например: Климов Максим, Мирных Алексей, Дудяк Елена

fm – имя, отчество. Например: Иван Петрович, Василий Аркадьевич, Рахиль Альбертовна

f – личное имя. Примеры: Иван, Петр, Алексей, Равиль, Аслан и т.д.

SFM – по первой букве от фамилии, имени, отчества. Примеры: В.Р.Е, Е.Н.М.

Является ли этот список шаблонов исчерпывающим? Весьма вероятно что нет, однако все остальные случаи будут достаточно редкими чтобы рассматривать их как исключения и систематизировать именно с точки зрения исключений.

Правила разбора ФИО

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

Прежде чем определять пол персоны или этнос важно разложить ФИО на элементы и для этой цели необходимо определить каким шаблоном ФИО написано. Как это сделать?

1. Вначале разбить ФИО на элементы исходя из того что разделителями могут выступать пробелы и точки.

2. Определяется количество частей после чего идёт ветвление на проверку по шаблонам. Если 1 часть (1 слово) – то шаблон s или f. Если две части, то sf, fm, fs, sF или Fs

3. Для ФИО из 3-х частей проводится простая проверка не состоят ли какие-либо части из одной буквы. Если да и более двух, то быстро определяются такие шаблоны как SFM, sFM и FMs

4. Далее как определить какая из частей каким типом элементов является. Есть два способа и их комбинация.

Способ 1. Базы имён, фамилий и отчеств

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

Способ 2. Регулярные выражения

Для отчеств – окончания на -вич и -вна. Для фамилий выражений больше. Например, таки как: ^(.*)(о|е|ё)в$, ^(.*)швили$ и так далее, несколько десятков.  А также есть набор выражений для имён, но там всё несколько сложнее и это отдельная тема.

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

Способ 3. Использование баз и выражений совместно

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

-

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

6. В конечном итоге результатом являются:

- выявленный формат шаблона

- размеченные элементы (фамилия, имя, отчество)

А также, или все имеющиеся или один производный признак пола и, при возможности определения, этноса.

Или же возврат,  и производного, и всех признаков. Об особенностях определения признаков в следующем пункте.

Особенности

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

1. Есть множество случаев когда пол определить невозможно даже определив шаблон и отдельные элементы. Связано это не с несовершенством методов проверки, а с тем что далеко не всегда информация о поле содержится в ФИО. Вот несколько примеров: Малых А.А. – имя и отчество присутствуют только в виде первых букв, а фамилия Малых является универсальной и может принадлежать, как женщине, так и мужчине. Точно также с фамилиями на -ко, -их и множестве других. Фактически во всех случаях шаблонов sFM, FMs, Fs, sF и s у нас недостаточно элементов несущих информацию и определение ограничено имеющейся информацией. В виду этого результатом метода по определению пола по ФИО могут быть 4 варианта ответа: женский, мужской, универсальный и неизвестно.

2. Есть множество региональной специфики в том что касается написания имён и отчеств. В частности в  азербайжанских казахских ФИО часто присутствует «Оглы» или «Кызы». Например, Асланов Ази Ахад оглы

3. Много специфики в именах используемых в национальных республиках России и бывшем СССР. Точность распознавания будет зависеть от наличия датасетов по регионам.

4. Описанный подход не охватывает случаи намерянных и случайных искажений. Например, когда вместо точки используют запятую или указывают ФИО вроде «Гадя Петрович Хренова». А также случаи с опечатками – это несколько более сложная, но не сверхсложная задача.

5. Определения этноса задача сложная, в первую очередь, в виду значительных объёмов классифицируемой информации. Фактически её можно разделить на принципы определения различных этнических особенностей в ФИО разных народов. Например, окончания фамилий на «-ян» у армян или «-дзе» и «-швили» у грузин. А также на основе баз имён разных народов.  Однако есть много случаев когда определить этнос сложно поскольку имя может указывать лишь на то из какого языка оно происходит. А в некоторых случаях имена могут иметь множественное значение. Например имя Артур – весьма популярно среди армян и это армянское имя переводящееся как «свет истины» и одновременно это нередкое современное имя в России среди русских.

Примеры

Собственно всё вышеперечисленное какое-то время я реализовал довольно давно в виде довольно простого закрытого веб-сервиса который на входе кушает текст, а на выходе выдаёт JSON с результатами. Работает это всё настолько просто назвать это алгоритмом у меня язык не поворачивается – просто «полезная штука», ничего более.

Вот несколько примеров.

Текст: Бегтин И.В.

Разбор в формате JSON:

{‘format’: ’sFM’, ‘gender’: ‘m’, ’sn’: u’Бегтин’, ‘fn_s’: u’И’, ‘text’: u’Бегтин И.В.’, ‘mn_s’: u’В’, ‘parsed’: True}

Текст: Иван Викторович Бегтин

Разбор в формате JSON:

{‘format’: ‘fms’, ‘gender’: u’m', ‘mn’: u’Викторович’, ’sn’: u’Бегтин’, ‘text’: u’Бегтин Иван Викторович’, ‘parsed’: True, ‘fn’: u’Иван’}

Где: fn – имя, sn – фамилия, mn – отчество, fn_s – первая буква имени, format – выявленный формат описания ФИО, parsed – флаг что формат был определён, gender – пол в виде одного из признаков m, f, u и «-» если определение пола не прошло.

Нет только признаков этноса, поскольку сейчас они присутствуют только для имён

Статистика

В качестве небольшого дополнения приведу некоторые статистические наблюдения.

Для проверки точности я взял небольшой массив примерно в  5 600 000 неуникальных записей из публичных официальных документов. А то есть с частыми повторениями одного и того же ФИО, но в разных формах. Например: где-то упоминается: Кудрявцев Е.В., где-то Кудрявцев Евгений, где-то Кудрявцев Евгений Викторович и так далее.

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

<tr height="20"> <td width="64" height="20">Шаблон</td> <td width="64">Частота</td> </tr> <tr height="20"> <td height="20">sfm</td> <td align="right">49,38%</td> </tr> <tr height="20"> <td height="20">sFM</td> <td align="right">35,71%</td> </tr> <tr height="20"> <td height="20">FMs</td> <td align="right">13,42%</td> </tr> <tr height="20"> <td height="20">fms</td> <td align="right">1,24%</td> </tr> <tr height="20"> <td height="20">sF</td> <td align="right">0,069%</td> </tr> <tr height="20"> <td height="20">sf</td> <td align="right">0,055%</td> </tr> <tr height="20"> <td height="20">Fs</td> <td align="right">0,038%</td> </tr> <tr height="20"> <td height="20">sfM</td> <td align="right">0,029%</td> </tr> <tr height="20"> <td height="20">s</td> <td align="right">0,026%</td> </tr> <tr height="20"> <td height="20">fs</td> <td align="right">0,0010%</td> </tr> <tr height="20"> <td height="20">f</td> <td align="right">0.0007%</td> </tr>

Фактически можно увидеть что при 4 основных написания – sfm, sFM, FMs и fms лидируют по частоте встречаемости. Но, как я упоминал ранее, здесь есть специфика в официальности. Если же анализировать другие массивы, то распределение шаблонов по популярности будет иным.

В качестве резюме

В общем-то разбор ФИО – это довольно простой пример на уровне «систематизации очевидного». Куда сложнее задачи по разбору адресов или, например, товарных позиций. Но ничего неразрешимого нет при условии последовательного упрощения и шаблонизации форматов представления, иногда многоуровневой.

Originally published at Иван Бегтин. You can comment here or there.

Совсем без SQL&#8217;ные базы данных
14 апреля 10 04:35

Шаг-за шагом объектные и безсхемные базы данных превращаются из экзотики в нечто общепринятое.

На nosql-database.org обнаружилась большая подборка ссылок и материалов по этой теме.

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

На мой взгляд самые интересные это:

Но, в принципе, это интересная тенденция. Даже глаза разбегаются что лучше выбрать и использовать.

Originally published at Иван Бегтин. You can comment here or there.

Postedfrom Иван Бегтин | 0 Comments    
Filed under:
Техническое: Про ускорение RSS и протоколы SUP и PubSubHub
11 апреля 10 12:12

На TechCrunch почти год назад была пара интересных статей RSS is dying и Speeding up RSS.

В первой рассказывается про то как Twitter вытесняет RSS из повседневного использования, а вторая про протоколы PubSubHub и SUP.

PubSubHub – это инициатива Брэда Фицпатрика с открытой спецификаций и открытым исходным кодом http://code.google.com/p/pubsubhubbub/. Где главная идея в том создатели RSS лент регистрируют их на одном из PubSubHub сервисов и далее пингуют сервисы при обновлении своих лент, а хабы мультикастом распространяют контент по всем подписчикам. Конечно, в такой схеме нужно чтобы клиент мог принимать новые сообщения и такие клиенты появляются, их список можно посмотреть здесь – http://code.google.com/p/pubsubhubbub/wiki/SubscriberClients
Однако изменения нужны, и на сервере, и на клиенте, и необходим внешний сервис.

SUP (Simple Update Protocol) – это протокол разработанный для FriendFeed. Также с открытой спецификацией и исходным кодом доступными здесь http://code.google.com/p/simpleupdateprotocol/
Он очень просто устроен и отличается тем что никак не специфицирует работу клиентов, а описывает механизм публикации при котором в новостные ленты сайта добавляются указания на ленту SUP где с заданной периодичностью указываются те новостные ленты где произошли изменения. Тем самым, в случае если с одного ресурса извлекается более одной RSS ленты, то число обращений можно существенно ограничить. А также за счёт того что в заголовках HTTP ответов указывается текущий статус RSS ленты, то и существенно сократить число выгрузок лент.

Лично мне оба подхода в равной степени нравятся/не нравятся. На мой взгляд они вполне равновесны.
Однако они не решают другой большой и сложной задачи которая заключается в том что же делать когда вероятность что разработчики сайтов добавят поддержку одного из протоколов очень невлика. И это, в общем-то, обыденная ситуация если вспомнить что не все сайты до сих пор поддерживают технологию RSS. А если говорить про наиболее интересующую меня категорию веб-сайтов, то до 80% из них RSS не отдают.

И вот вопрос как быть в этом случае?
Свои размышления по этому поводу я собрал в виде нескольких тезисов:
1. В зависимости от характера решаемых задач подход может быть различным. Главный критерий здесь – ожидаемый интервал оперативности в получении новостной информации и это может определять стратегии сбора информации. К примеру, если новости собранные за сутки используются лишь для дайджеста
2. У подавляющего числа RSS лент есть свои «временные паттерны». Которые можно охарактеризовать как периоды времени активности в данной RSS ленте. В большинстве случаев эти временные паттерны напрямую завязаны на суточный цикл дня и ночи привязанный к источнику этих данных и недельный/календарный цикл с учётом падения активности в выходные и праздничные дни. Разумеется в случаях когда речь идёт «естественных» новостных лентах формируемых людьми, а не ботами. При выявлении характеристик этих циклов могут быть определены интервалы опроса источников информации. Это может позволить соблюсти баланс между использованием ресурсов и частотой обновления.
3. Некоторые сервера честно возвращают даты фактического обновления в «Last Modified», некоторые отдают заголовок «ETag» и чаще отдают информацию о размере страницы/ленты. При наличии этой информации её можно использовать для сокращения числа GET запросов. Правда, при этом сразу возникают другие особенности – в том необходимо убедится в том что информация в заголовках от сервера корректна. Например, несколько раз я сталкивался с тем что возвращалось неверное значение ETag, в том что «Last Modified» возвращает корректные значения также необходимо убеждаться, равно как и есть определённые риски в использовании «Content-Length» для принятия решения об обновлении или необновлении RSS ленты.

Минусы этих подходов – необходимости предварительного сбора накопления информации перед тем как выбирать правильную стратегию опроса RSS лент. И, конечно, универсальным решением это не является, в отличии от SUP’а и PubSubHub. Правда, подозреваю что до тех пор пока разработчики CMS не начнут включать поддержку одного из них в свои продукты по умолчанию, на большинстве сайтов мы их так и не увидим.

Originally published at Иван Бегтин. You can comment here or there.

Postedfrom Иван Бегтин | 0 Comments    
Filed under:
OData: Open Data Protocol
29 марта 10 01:55


Оказывается Microsoft сделали и предложили протокол OData – Open Data Protocol используемый для раскрытия данных в машиночитаемой форме.

Подробнее можно почитать здесь http://www.odata.org

А вот его полное описание –
There is a vast amount of data available today and data is now being collected and stored at a rate never seen before. Much, if not most, of this data however is locked into specific applications or formats and difficult to access or to integrate into new uses. Public data is often unfortunately held private or needlessly buried behind random, inefficient, and cumbersome interfaces.

The Open Data Protocol (OData) provides a way to unlock your data and free it from silos that exist in applications today, making it easy for data to be shared in a manner that follows the philosophy of Open Data. OData enables a new level of data integration and interoperability across a broad range of clients, servers, services, and tools.

Это реально радует. Во первых сама спецификация протокола довольно проста и понятна, во вторых она без жёсткой привязки к сервисам MS.

А я тем временем всё больше понимаю что на OpenGovData.ru должны быть инструкции и разъяснения как именно надо публиковать информацию.

Originally published at Иван Бегтин. You can comment here or there.

Анализ веб-страниц, выявление новостей и не только
17 февраля 10 01:10

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

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

Пока я могу рассказать как сбором и анализом данных для алгоритмов занимаюсь я. Собственно ничего сложного в этом нет:

- у меня есть специально написанная система и пол-сервера на Amazon’е которая используется с единственной целью находить извлекать информацию с веб-сайтов. При этом извлечение происходит на нескольких уровнях: HTTP заголовки, meta информация HTML, скрипты, ссылки на изображения, любые ссылки, стилевые страницы и статистику по использованию тэгов их иерархии и структуре. В совокупности там хранится порядка 100 000 веб-страниц, в основном главных «морд» сайтов в виде нескольких выборок от 10 000 до 25 000 тысяч страниц.

- далее несколько очень простых алгоритмов разбирают эти первичные (веб-страницу) и вторичные (объекты на странице) данные и классифицируют сайт по целому ряду метрик – какая CMS используется, поддерживается ли кэширование страниц, используется ли CDN, какой-сервер используется, если реклама, какие используются виджеты и так далее. Фактически эта система аналог http://builtwith.com/ для Рунета с учётом его специфики и сервисов и с тем отличием что она не публична.  Эту штуку я называл под кодовым названием «Урлум», сейчас я передумал её делать публичной – поскольку пока не вижу в этом пользы.

- после этого начинают работать сложные алгоритмы: определения коммерциализованности сайта, извлечение структурированных блоков, определения структурной карты сайта (не путать с объектной!)  - структурная карта это совокупность правил навигаций по сайту. Того как происходят переходы – через запросы GET, именованными подразделами, AJAX’ом или иначе, а также выявление непосредственно навигационного меню сайта.

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

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

Другой недостаток – это высокое ресурсопотребление. После структурного разбора веб-страницы хранение всех признаков и её блоков может превосходить её объём в несколько раз. Да, конечно, можно использовать эффективные структуры данных, оптимизировать переписав ключевые участки на C++, но тут уже вопрос стоимости усилий к гибкости решения.

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

Для работы алгоритма в Скиуре минимально необходимы дата + текст, а желательны дата + текст + ссылка на новость. Но дата в ленте новостей нужна не потому что нельзя RSS ленту построить на других данных и дату сформировать динамически или извлечь из сопутствующей информации. Смысл в другом, смысл в идентификации блоков. На самом деле на любой веб странице могут присутствовать множество различных информационных блоков.  Ленты новостей, избранные статьи, навигационные меню, ссылки с обзорами и без, галереи фотографий, списки книг и так далее. Далеко не все из них могут быть представлены как новостные ленты, как раз наоборот большинство из них новостными лентами не являются и новостные ленты без дат на сайте это скорее исключение чем норма. В свою очередь упрощённый алгоритм скиура делался под полную автоматику – то есть так чтобы можно было запустить робота по сайтам и он сам восстанавливал RSS ленты. Для случаев когда дат нет требуется обязательное подтверждение от человека что новостная лента найдена и определена верно. А это уже полу-автомат, а не автомат и сделать его возможно, фактически, для него всё готово, но уже не так интересно и практических задач для него пока ещё мало.

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

Потому как есть 3 основных режима работы алгоритма:

- универсальный: алгоритм, фактически всегда работает в режиме обучения и распознает новостную ленту даже если сменится движок на сайте или поменяется вёрстка, расположение блоков на странице или форматы описания дат. Универсальный режим определяет все блоки динамически и формирует ленту также динамически. Это наиболее эффективный и медленный способ выявления новостей на веб-странице и самый медленный тоже.

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

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

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

Суть проблемы остаётся одна – постоянная изменчивость структуры веб-страниц. Если для сотен сайтов – это будет происходить нечасто, то для тысяч и десятков тысяч, это уже заметно. В то время как «обучение на изменчивость» процесс непростой, так как требует накопления версий одной и той же страницы во временном разрезе.

Однако, по прежнему, я считаю что структурный анализ веб-страниц возможен и становится всё проще и проще.

Originally published at Иван Бегтин. You can comment here or there.

Postedfrom Иван Бегтин | 0 Comments    
Языки программирования и регулярные выражения
15 декабря 09 02:22

Оказывается на http://shootout.alioth.debian.org/ публикуют метрики большинства современных языков программирования из тех что можно запустить на Ubuntu, а то есть практически всех.

Из особенно интересного там есть метрики применения регулярных выражений – http://shootout.alioth.debian.org/u32q/benchmark.php?test=regexdna&lang=all&box=1 на Intel QuadCore Q6600.

Кстати, там много и других интересных сравнений реализаций алгоритмов.

Ну а для регулярных выражений, судя по тестам, там лидирует V8 JavaScript engine из Chromium. Ещё в феврале этого года они писали про движок Irregexp у себя в блоге и то что там реализовали компиляцию регулярных выражений в промежуточный автомат.  Что и говорить, результаты впечатляющие, обгоняют даже C++ реализацию на Boost, а мой любимый язык разработки Python так вообще отстаёт в 6 раз.

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

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

P.S. Кстати, бегло посмотрев код могу констатировать тот факт что в другие языки irregexp вполне можно перенести и вся реализация там укладывается в 700 строк, и, конечно, важно проверить его работу на живых, а не синтетических примерах дабы понять производительность на не-ASCII символах.

Originally published at Иван Бегтин. You can comment here or there.

Postedfrom Иван Бегтин | 0 Comments    
Filed under:
Ссылки на 10.12.2009: Проекты Microsoft
10 декабря 09 04:54

Что радует, у Microsoft появляется всё больше более чем интересных проектов и, если абстрагироваться от провала Висты и нынешнего давления на покупателя чтобы переходили на W7, то есть о чём любопытном упомянуть:

  • Codename Dallas  - http://pinpoint.microsoft.com/en-US/Dallas. Проект/сервис для поддержки разработчиков желающих распространять и использовать большие массивы данных. Включает как бесплатные так и платные данные в большом количестве.
  • Microsoft Academic Search – http://academic.research.microsoft.com. Поисковик по научным работам в разных областях науки, в основном, околокомпьютерных. Мне понравилось наличие разных полезных срезов – по журналам и конференциям
  • eGov 2.0 kit – http://egov.codeplex.com/. Движок на базе Sharepoint’а по построению сайтов для eGov. При том что мне не особо нравится реализация, сама идея довольно разумна – CMS или полуфабрикат для госсайтов.
  • EntityCube – http://entitycube.research.microsoft.com/. Проект по выявлению “именованных сущностей”, различных осмысленных фактов о персонах и организациях. На мой взгляд он тесно пересекается идеологически и информационно с Powerset’ом купленным Microsoft недавно и интересно как дальше будут развиваться события. Будут ли их объединять в гибрид, например.

Кстати в Research  же занимаются ещё одной наработкой/небольшой библиотекой – Site Analyzer  http://research.microsoft.com/en-us/downloads/58e8953e-3626-4994-bf95-19039e978223/default.aspx

Проектом это назвать рановато, но возможность структурировать веб-страницы форумов, определять шаблоны URL’ов туда уже закладывается. А это уже ровно то же самое чем я занимаюсь, только подходы разные.

Они используют извлечение признаков, кластеризацацию и анализ коэффициентов сходства, в данном случае, коэффициентов Жаккара, а я использую модель предварительного выявления типовых шаблонов и построения карты микропризнаков или “объектной карты”.

Кстати, для анализа HTML в Site Analyzer’е свой парсер который кроме обычной информации об элементе DOM-дерева фиксирует поля о его глубине, числе потомков и так далее. Я знал, я знал что не один я об этом ломал голову, что приятно.

Originally published at Иван Бегтин. You can comment here or there.

Postedfrom Иван Бегтин | 0 Comments    
More Posts Next page »

This Blog

Tags

Archives

Syndication