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

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

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

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

class Vertex
{
  public:
	Vertex();
	Vertex(const string& name);
	void addlink(Vertex* v);
	string getname(){return name;}
	VertexStorage& getnext(){return next;}
  private:
   string name;
   VertexStorage next;
};

class Vertex

{

public:

Vertex();

Vertex(const string& name);

void addlink(Vertex* v);

string getname(){return name;}

VertexStorage& getnext(){return next;}

private:

string name;

VertexStorage next;

};

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

class VertexStorage
{
  public:
	void add(Vertex* v);
	Vertex* add(const string& word);
	Vertex* find(const string& word)const;
	int count(const string& word)const;
	int count(Vertex* v)const;
	iterator begin()const{return storage.begin();} 
	iterator end()const{return storage.end();} 
  private:
   ??? storage;
   ???
};

class VertexStorage

{

public:

void add(Vertex* v);

Vertex* add(const string& word);

Vertex* find(const string& word)const;

int count(const string& word)const;

int count(Vertex* v)const;

iterator begin()const{return storage.begin();}

iterator end()const{return storage.end();}

private:

??? storage;

???

};

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

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

class Vertex;

1	class Vertex;

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

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

class Graph
{
  public:
	Graph(); //создает безымянный граф
	Graph(const string& name); //граф с именем
	~Graph(); //деструктор - все вершины нужно удалить
	Vertex* addword(const string& word); 
        //добавить вершину, соответствующую слову word в граф 
        //результатом функции будет указатель
        //на созданную / уже имеющуюся вершину
	string getname()const{return name;}
	VertexStorage& getV(){return next;}
	void printDOT();//распечатывает в формате DOT 
  private:
   string name; //имя графа
   VertexStorage V; //хранит вершины и их кратности
};

class Graph

{

public:

Graph(); //создает безымянный граф

Graph(const string& name); //граф с именем

~Graph(); //деструктор - все вершины нужно удалить

Vertex* addword(const string& word);

//добавить вершину, соответствующую слову word в граф

//результатом функции будет указатель

//на созданную / уже имеющуюся вершину

string getname()const{return name;}

VertexStorage& getV(){return next;}

void printDOT();//распечатывает в формате DOT

private:

string name; //имя графа

VertexStorage V; //хранит вершины и их кратности

};

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

class VertexStorage
{
  public:
	void add(Vertex* v);
	Vertex* add(const string& word);
	Vertex* find(const string& word)const;
	int count(const string& word)const;
	int count(Vertex* v)const;
	iterator begin()const{return storage.begin();} 
	iterator end()const{return storage.end();} 
  private:
   ??? storage;
   ???
};

class VertexStorage

{

public:

void add(Vertex* v);

Vertex* add(const string& word);

Vertex* find(const string& word)const;

int count(const string& word)const;

int count(Vertex* v)const;

iterator begin()const{return storage.begin();}

iterator end()const{return storage.end();}

private:

??? storage;

???

};

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

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

Vertex* v;
...
for (VertexStorage::iterator it=v->getnext().begin();
                             it!=v->getnext().end();
                             ++it)
   //обрабатываем содержимое it

Vertex* v;

...

for (VertexStorage::iterator it=v->getnext().begin();

it!=v->getnext().end();

++it)

//обрабатываем содержимое it

или еще лучше

Vertex* v;
...
for (auto element: v->getnext())
     //обрабатываем element

Vertex* v;

...

for (auto element: v->getnext())

//обрабатываем element

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

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

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

vector< pair<Vertex*,int> > storage;

1	vector< pair<Vertex*,int> > storage;

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

typedef vector< pair<Vertex*,int> >::iterator iterator;

1	typedef vector< pair<Vertex*,int> >::iterator iterator;

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

class VertexStorage
{
  public:
	typedef vector< pair<Vertex*,int> >::iterator iterator;
	void add(Vertex* v);
	Vertex* add(const string& word);
	Vertex* find(const string& word)const;
	int count(const string& word)const;
	int count(Vertex* v)const;
	iterator begin()const{return storage.begin();} 
	iterator end()const{return storage.end();} 
  private:
	vector< pair<Vertex*,int> > storage;
};

class VertexStorage

{

public:

typedef vector< pair<Vertex*,int> >::iterator iterator;

void add(Vertex* v);

Vertex* add(const string& word);

Vertex* find(const string& word)const;

int count(const string& word)const;

int count(Vertex* v)const;

iterator begin()const{return storage.begin();}

iterator end()const{return storage.end();}

private:

vector< pair<Vertex*,int> > storage;

};

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

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

class VertexStorage
{
  public:
	typedef map<Vertex*,int>::iterator iterator;
	void add(Vertex* v);
	Vertex* add(const string& word);
	Vertex* find(const string& word)const;
	int count(const string& word)const;
	int count(Vertex* v)const;
	iterator begin()const{return storage.begin();} 
	iterator end()const{return storage.end();} 
  private:
	map<Vertex*,int> storage;
};

class VertexStorage

{

public:

typedef map<Vertex*,int>::iterator iterator;

void add(Vertex* v);

Vertex* add(const string& word);

Vertex* find(const string& word)const;

int count(const string& word)const;

int count(Vertex* v)const;

iterator begin()const{return storage.begin();}

iterator end()const{return storage.end();}

private:

map<Vertex*,int> storage;

};

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

class VertexStorage
{
  public:
	typedef map<Vertex*,int>::iterator iterator;
	void add(Vertex* v);
	Vertex* add(const string& word);
	Vertex* find(const string& word)const;
	int count(const string& word)const;
	int count(Vertex* v)const;
	iterator begin()const{return storage.begin();} 
	iterator end()const{return storage.end();} 
  private:
	map<Vertex*,int> storage;
	map<string,Vertex*> index;
};

class VertexStorage

{

public:

typedef map<Vertex*,int>::iterator iterator;

void add(Vertex* v);

Vertex* add(const string& word);

Vertex* find(const string& word)const;

int count(const string& word)const;

int count(Vertex* v)const;

iterator begin()const{return storage.begin();}

iterator end()const{return storage.end();}

private:

map<Vertex*,int> storage;

map<string,Vertex*> index;

};

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

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

http://ideone.com/PPkGKQ

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

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

Related Images:

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