Словарный граф

Задание: На вход подается текст на английском языке. Создать по нему словарный ориентированный граф, в котором будут хранится все связи между словами: а именно, вершинами графа будут все слова текста, а дуга [latex]w_1 \to w_2[/latex] присутствует в графе в том случае, если в одном предложении встречаются подряд слова [latex]w_1[/latex] и [latex]w_2[/latex].

Начнем с описания типа для вершины графа. Конечно же называться тип будет Vertex. Объекты этого класса будут хранить имя вершины и список смежных вершин. Но вместо того, чтобы использовать какой-то фиксированный контейнер для хранения вершин, создадим еще один класс VertexStorage, который предназначен для хранения вершин, добавления новых вершин и поиска вершин (по строковому имени).

Вот заготовки классов: класс Vertex

— хранится имя вершины, а также хранилище вершин, с которыми она связана, есть метод добавления дуги addlink (конечная вершина v должна быть уже создана) и класс

У Вас может возникнуть вопрос, как же класс Vertex использует VertexStorage и наоборот. Какой из них расположить раньше?

В данном случае можно расположить раньше класс VertexStorage, но перед ним указать, что у нас будет класс Vertex при помощи следующей строки:

Это предварительное объявление класса или, если по аналогии с функциями, «прототип» класса.

Конечно же, созданный нами контейнер для вершин (ну ладно, создаваемый) можно использовать не только для хранения вершин, смежных с некоторой, а и для хранения всего графа. Вот заготовка для класса Graph:

 

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

Итак, логика работы методов: первый метод add добавляет в хранилище уже созданную вершину, второй метод add — добавляет в хранилище вершину, соответствующую слову (при этом вершина создается при необходимости), find ищет слово и возвращает указатель на вершину (nullptr если не найдено), методы count — сколько раз слово или вершина встречаются (ноль, если слово / вершина не найдены).

Вопрос, а что же за загадочный тип iterator, которые возвращают методы begin() и end()? И зачем эти методы вообще нужны? Ответ: для того, чтобы можно было перебрать все содержимое хранилища вершин, одним из следующих образов

или еще лучше

Только вот тип iterator зависит

  1. от того что будет храниться в контейнере,
  2. от того какой вид контейнера будет выбран.

Что же логично хранить в контейнере. На первый взгляд — указатели на вершины. Но с другой стороны вершина в контейнер может быть добавлена несколько раз. И нужно где-то хранить кратность — это может быть как кратность дуги, так и сколько раз встретилась вершина. Поэтому логично, чтобы в хранилище были пары (вершина, количество). Для этого опишем storage пока что так:

и тогда тип итератор:

Тогда VertexStorage выглядит так:

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

Будем использовать более подходящее хранилище map или unordered_map, таким образом:

Контейнеры map и unordered_map как раз и предназначены для хранения пар (ключ, значение), причем поиск по ключу — это эффективная операция для этих контейнеров. Другими словами, эти контейнеры реализуют математическую абстракцию «отображение» — где каждому ключу (из области определения), поставлено в соответствие некоторое значение (из области значений). Теперь поиск эффективен по значению указателя, но увы, не по слову!  Что делать? Давайте добавим еще один map:

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

Если кому совсем не терпится увидеть работоспособное и эффективное (но неаккуратное) решение, то вот моя первая попытка:

http://ideone.com/PPkGKQ

 

Latest posts by Антоненко Александр Сергеевич (see all)

Добавить комментарий