Вопрос отделения нужного и полезного контента от остальных рюшечек встает довольно часто перед теми, кто занимается сбором той или иной информации в Web.
Думаю нет особой причины останавливаться на алгоритме разбора HTML в дерево, тем более, что в обобщенном виде такие парсеры учат писать курсе на 3-4 ВУЗа. Обычный стек, немного фишечек по пропуску аргументов (кроме тех что потом понадобятся), и выходное дерево как результат разбора. Текст разбивается на слова прямо в процессе разбора, и слова отправляются в отдельный список, где запомнены кроме общей информации и все позиции слова в документе. Понятное дело слова в списке уже в 1-й нормальной форме, про морфологию уже писал, здесь просто скопирую из предыдущей статьи.
Сначала на основе морфологического словаря Зализняка выбираем наибольшую основу, отрезаем окончание, подставляем 1-ю словарную форму. Весь этот процесс собран в дерево для быстрого разбора по буквам, в конечных листьях содержатся варианты окончаний. Бежим по слову, параллельно спускаясь по дереву исходя из встреченной буквы, пока не дойдем до самого нижнего возможного листа – там, исходя из окончаний, подставляем нормализованное.
Если же нормальной формы не нашлось, то применяем стемминг – исходя из текстов книг скачанных с lib.ru, я построил таблицу частоты встречаемости окончаний, ищем наиболее встречаемое из подходящих (тоже деревом) и заменяем на нормальную форму. Стемминг хорошо работает, если слова не было в языке еще лет 5-10 назад – легко разберет «краулеры» в «краулер»
После долгих экспериментов с разбором HTML обратил внимание на то, что одинаковые блоки в HTML очевидно составляют одинаковые поддеревья – грубо говоря если есть 2 страницы, и 2 дерева и между ними сделать XOR то останется только нужный контент. Ну или если так проще – пересечение большинства таких деревьев по одному сайту даст вероятностную модель – чем в большем количестве деревьев встречен блок, тем меньше его значимость. Все что встречено более чем в 20% -30% — я выкидываю, смысла нет тратить время на дублированный контент.
Очевидно родилось и решение: научится считать некую CRC от поддерева, для каждого поддерева тогда легко посчитать кол-во повторений. Тогда при повторном разборе обнулить вершины дерева которое встретилось слишком часто – легко, а из оставшегося дерева всегда можно обратно собрать текст страницы (хотя это и не требуется по сути нигде).
Итак в 2 прогона по всем страницам сайта – сначала собираем статистику, потом индексим – вопрос вычленения паттернов легко решается. Получаем, кроме того, много плюсов – конструкции типа
Полное содержание и список моих статей будет обновлятся вот здесь: http://habrahabr.ru/blogs/search_engines/123671/
Думаю нет особой причины останавливаться на алгоритме разбора HTML в дерево, тем более, что в обобщенном виде такие парсеры учат писать курсе на 3-4 ВУЗа. Обычный стек, немного фишечек по пропуску аргументов (кроме тех что потом понадобятся), и выходное дерево как результат разбора. Текст разбивается на слова прямо в процессе разбора, и слова отправляются в отдельный список, где запомнены кроме общей информации и все позиции слова в документе. Понятное дело слова в списке уже в 1-й нормальной форме, про морфологию уже писал, здесь просто скопирую из предыдущей статьи.
Сначала на основе морфологического словаря Зализняка выбираем наибольшую основу, отрезаем окончание, подставляем 1-ю словарную форму. Весь этот процесс собран в дерево для быстрого разбора по буквам, в конечных листьях содержатся варианты окончаний. Бежим по слову, параллельно спускаясь по дереву исходя из встреченной буквы, пока не дойдем до самого нижнего возможного листа – там, исходя из окончаний, подставляем нормализованное.
Если же нормальной формы не нашлось, то применяем стемминг – исходя из текстов книг скачанных с lib.ru, я построил таблицу частоты встречаемости окончаний, ищем наиболее встречаемое из подходящих (тоже деревом) и заменяем на нормальную форму. Стемминг хорошо работает, если слова не было в языке еще лет 5-10 назад – легко разберет «краулеры» в «краулер»
После долгих экспериментов с разбором HTML обратил внимание на то, что одинаковые блоки в HTML очевидно составляют одинаковые поддеревья – грубо говоря если есть 2 страницы, и 2 дерева и между ними сделать XOR то останется только нужный контент. Ну или если так проще – пересечение большинства таких деревьев по одному сайту даст вероятностную модель – чем в большем количестве деревьев встречен блок, тем меньше его значимость. Все что встречено более чем в 20% -30% — я выкидываю, смысла нет тратить время на дублированный контент.
Очевидно родилось и решение: научится считать некую CRC от поддерева, для каждого поддерева тогда легко посчитать кол-во повторений. Тогда при повторном разборе обнулить вершины дерева которое встретилось слишком часто – легко, а из оставшегося дерева всегда можно обратно собрать текст страницы (хотя это и не требуется по сути нигде).
Итак в 2 прогона по всем страницам сайта – сначала собираем статистику, потом индексим – вопрос вычленения паттернов легко решается. Получаем, кроме того, много плюсов – конструкции типа
<td></td>, <b></b> и остальные бессмысленные будут выкинуты в первую очередьПолное содержание и список моих статей будет обновлятся вот здесь: http://habrahabr.ru/blogs/search_engines/123671/
