Найдите элемент HTML, который содержит наибольшее количество упоминаний данного слова

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

Со следующим HTML:

<body>
    <p>
        Hello <b>foo</b>, I like foo, because foo is the best.
    <p>
    <div>
        <blockquote>
            <p><strong>Foo</strong> said: foo foo!</p>
            <p>Smurfs ate the last foo and turned blue. Foo!</p>
            <p>Foo foo.</p>
        </blockquote>
    </div>
</body>

Я хотел бы иметь функцию

find_largest_cluster_wrapper(html, word='foo')

... который проанализирует дерево DOM и вернет мне элемент <blockquote>, потому что он содержит наибольшую плотность упоминаний foo и является ближайшей оболочкой.

Первый <p> содержит foo 3 раза, <b> только один раз, внутренние <p> содержат foo 3 раза, дважды и еще раз дважды, <strong> только один раз. Но <blockquote> содержит foo 4 раза. То же самое относится и к <div>, но это не самая близкая оболочка. Элемент <body> имеет наибольшее количество упоминаний, но это слишком редкий кластер.

Простая реализация без кластеризации всегда давала бы мне <html> или <body> или что-то в этом роде, потому что такие элементы всегда имеют наибольшее количество запрошенных упоминаний и, вероятно, являются ближайшей к ним оболочкой. Однако мне нужно что-то, что займет самый большой кластер, так как меня интересует только часть веб-страницы с наибольшей плотностью слова.

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

Ну, вообще сложно ответить на такой вопрос, потому что условия, как вы указали, расплывчаты. Итак, более конкретно:

Как правило, документ может содержать только один такой кластер. Мое намерение состоит в том, чтобы найти такой кластер и получить его оболочку, чтобы я мог манипулировать им. Это слово можно было бы упомянуть и в другом месте на странице, но я ищу заметную группу таких слов. Если есть два заметных кластера или более, то я должен использовать внешнее смещение для принятия решения (проверить заголовки, заголовок страницы и т. д.). Что значит, что кластер примечательный? Это означает именно то, что я только что представил, - отсутствие "серьезных" конкурентов. Если конкурент серьезный или нет, я могу указать некоторое число (соотношение), например. если есть кластер из 10 и кластер из 2, разница будет 80%. Я мог бы сказать, что если есть кластер с разницей более 50%, он будет заметным. Это означает, что если бы это был кластер из 5 и еще один из 5, функция вернула бы None (не смогла решить).


python html dom html-parsing cluster-analysis
person Honza Javorek    schedule 12.11.2012    source источник
comment
Кстати, проблема кажется довольно расплывчатой, если только у нас нет способа сказать, что один кластер подходит больше, чем другой. Например, если у нас есть узел <blockquote> ... </blockquote> с достаточно высокой плотностью слов foo. И этот узел находится внутри другого блока, например: <div> <blockquote> ... </blockquote> foo foo foo</div>. Какой узел мы выберем? Цитата или div?   -  person alex_jordan    schedule 12.11.2012

Ответы (3)


arrow_upward
3
arrow_downward

Итак, вот подход:

|fitness(node, word) = count of word in node text if node is a leaf
|fitness(node, word) = sum(fitness(child, word) for child in children) / 
                         count of overall elements in node tree

Вот:

import lxml.html

node = """<html><body>
    <p>
        Hello <b>foo</b>, I like foo, because foo is the best.
    <p>
    <div>
        <blockquote>
            <p><strong>Foo</strong> said: foo foo!</p>
            <p>Smurfs ate the last foo and turned blue. Foo!</p>
            <p>Foo foo.</p>
        </blockquote>
    </div>
</body></html>"""

node = lxml.html.fromstring(node)

def suitability(node, word):
    mx = [0.0, None]
    _suitability(node, word, mx)
    return mx[1]

def _suitability(node, word, mx):

    children = node.getchildren()
    sparsity = 1
    result = float(node.text_content().lower().count(word))
    for child in children:
        res, spars = _suitability(child, word, mx)
        result += res
        sparsity += spars
    result /= sparsity
    current_max, max_node = mx
    if current_max < result:
        mx[0] = result
        mx[1] = node
    return result, sparsity

print suitability(node, 'foo')

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

person alex_jordan    schedule 12.11.2012
comment
Не лучше ли вернуть максимальное значение и узел, который его имеет (в дополнение к результату и разреженности), а не использовать параметр входного списка в качестве неявного выходного параметра? - person Sam Mussmann; 12.11.2012
comment
Да, возможно, но где хранить значения? Как атрибут node? Я думал, что это будет довольно грязно. - person alex_jordan; 12.11.2012
comment
Просто верните их из _suitability в дополнение к результату и разреженности. - person Sam Mussmann; 12.11.2012
comment
Наконец-то я использовал что-то в этом роде, алгоритм «пригодности». Я протестировал его на некоторых примерах данных, и он работает как шарм. Он вырезает для меня именно тот контейнер, который я хотел! - person Honza Javorek; 16.11.2012

arrow_upward
1
arrow_downward

Так что это не библиотека, но у меня есть идея.

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

  1. Общее количество слов, которые он содержит.
  2. Сколько раз он содержит ваше целевое слово.

Затем вы можете искать в своем дереве узел, который максимизирует target_count / total_count. Это даст вам свойство наименьшего содержащего элемента, поскольку элемент выше в дереве будет содержать больше слов. На самом деле это дает вам узел с наибольшей плотностью целевого слова.

Вы можете обнаружить, что простое деление не дает желаемых результатов. Например, если узел содержит только одну копию вашего целевого слова, он будет иметь очень высокую плотность, но может не соответствовать понятию кластера, которое вы имеете в виду. В этом случае я бы определил некоторую функцию, которая отображает количество слов, содержащихся в элементе, в размер. Если вы хотите убедиться, что кластер имеет определенный размер, и наказать слишком большие кластеры (например, )<body>), это может быть примерно так:

def size(num_words):
   num_words = max(num_words, 40) # where 40 is the min size of a cluster
   if num_words > 1000: # This is too large, so we penalize
     num_words *= 1.5
   return num_words

Теперь вы можете сделать target_count / size(total_count).

Re: кластеризация scipy

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

person Sam Mussmann    schedule 12.11.2012

arrow_upward
1
arrow_downward

Пакет кластеризации не поможет, потому что это не кластерный анализ.

Это больше похоже на частый анализ шаблонов, возможно, вы захотите изучить его вместо этого.

person Has QUIT--Anony-Mousse    schedule 12.11.2012