Практическая информатика: связанные компоненты в графе

Практическая информатика: связанные компоненты в графе

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

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

Подсчет популярных детских имен

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

Вход состоит из двух частей:

• Набор пар имени и счета.
• Набор пар имен, где оба имени в каждой паре являются синонимами друг друга.

Обратите внимание, что это синонимы:

• Двунаправленный, то есть если ("John", "Jon") - пара синонимов, то Джон является синонимом Джона и наоборот.
• Переходный, то есть если Джон и Джон являются синонимами, а Джон и Джонни являются синонимами, тогда Джон и Джонни также являются синонимами, даже если эта последняя пара не появляется в нашем вводе.

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

Возьмем конкретный пример. Наш вклад:

• Необработанные подсчеты: ("John", 10), ("Kristine", 15), ("Jon", 5), ("Christina", 20), ("Johnny", 8), ("Eve", 5), ("Chris", 12)
• Синонимы: ("John", "Jon"), ("Johnny", "John"), ("Kristine", "Christina")

Один из возможных выходных данных - ("John", 23), ("Christina", 35), ("Eve", 5), ("Chris", 12).

Просмотр синонимов в виде графика

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

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

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

Связанные компоненты на графике

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

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

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

Реализация

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

Представление графа

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

Начнем с представления узла с именем и списком соседей:

class NameNode:
    def __init__(self, name):
        self.name = name
        self.adjacent_nodes = []

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

# 1. Find all unique names with synonyms
names_with_synonyms = set(name for pair in synonyms for name in pair)
# 2. Create nodes for each name in synonyms. Index the nodes by
#    the corresponding names in order to make it easy to look up
#    the nodes.
nodes_by_name = {
    name: NameNode(name)
    for name in names_with_synonyms
}

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

# 3. Add edges in for the names with synonyms
for name1, name2 in synonyms:
    node1 = nodes_by_name[name1]
    node2 = nodes_by_name[name2]
    node1.adjacent_nodes.append(node2)
    node2.adjacent_nodes.append(node1)

Поиск связанных компонентов

Следующим шагом будет поиск связанных компонентов на этом графике. Как упоминалось выше, мы хотим выполнить обход графа, начиная с определенных узлов. Я немного расскажу о том, как выбрать эти отправные точки, но давайте реализуем простой поиск в ширину с использованием структуры данных очереди. В Python я использую collections.deque.

Я не буду вдаваться в подробности этой части, так как это очень стандартная реализация поиска в ширину:

from collections import deque
def nodes_in_connected_component_with(start_node):
    """
    Find all the nodes connected to the given starting node using
    a breadth-first search (BFS).
    """
    visited = set()
    frontier = deque()
    frontier.append(start_node)
    component = []
    while frontier:
        node = frontier.popleft()
        visited.add(node)
        component.append(node)
        for adjacent in node.adjacent_nodes:
            if adjacent not in visited:
                frontier.append(adjacent)
    return component

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

# 4. Find connected components within the synonyms graph
components = []
visited = set()
for node in nodes_by_name.values():
    if node.name in visited:
        continue
    component = nodes_in_connected_component_with(node)
    visited.update(node.name for node in component)
    components.append(component)

Следующая анимация визуализирует этот алгоритм, показывая следующие шаги:

1. Узел «Кристина» посещается, начиная с первого компонента.
2. Из этого узла выполняется поиск в ширину, расширяя компонент за счет включения «Kristine».
3. На этом этапе BFS больше не может посещать узлы, поэтому мы начинаем новый компонент с «John». Обратите внимание, что мы не посещаем «Кристин» на этом этапе, потому что этот узел был посещен как часть предыдущего компонента.
4. BFS расширяет новый компонент, добавляя «Джон».
5. BFS продолжает расширять компонент, чтобы включить в него также «Джонни». Теперь все узлы посещены, поэтому алгоритм завершен.

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

# 5. Map each name to a representative of its connected component
representative_name_by_actual_name = {}
for component in components:
    representative_name = component[0].name
    for node in component:
        representative_name_by_actual_name[node.name] = \
            representative_name

Подсчет по имени представителя

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

# 6. Normalize counts using connected components
counts_by_representative_name = {}
for raw_name, count in raw_counts:
    representative_name = \
        representative_name_by_actual_name[raw_name] \
        if raw_name in representative_name_by_actual_name \
        else raw_name

    previous_count = \
        counts_by_representative_name[representative_name] \
        if representative_name in counts_by_representative_name \
        else 0

    counts_by_representative_name[representative_name] = \
        previous_count + count

И вот, у нас counts_by_representative_name, наши новые частоты!

Если вы возьмете такую ​​задачу, как Baby Names, и попытаетесь решить ее за один присест, вы в конечном итоге попытаетесь решить слишком много не связанных между собой проблем одновременно. Как вы продолжаете вести подсчеты на основе репрезентативных имен? Как вы проследите переходные связи между наборами синонимов? Как выбрать одного постоянного представителя для каждого набора синонимов? Все эти опасения в конечном итоге смешиваются.

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

Не забывайте основы информатики. Они могут появиться в очень интересных местах!

Эта статья также была размещена в моем личном блоге.