Графики - найти общие данные - PullRequest
Новая
       27

Графики - найти общие данные

2 голосов
/ 10 августа 2010

Я только начал читать графическую теорию и структуры данных.

Я создаю пример приложения, которое должно быть в состоянии найти xpath для наиболее распространенных ссылок. Представьте себе Google Serp, мое приложение должно найти xpath для всех ссылок, указывающих на результат.

Представьте, что эти xpaths были найдены: 

/html/body/h2/a
/html/body/p/a
/html/body/p/strong/a
/html/body/p/strong/a
/html/body/p/strong/a
/html/body/div[@class=footer]/span[@id=copyright]/a

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

                            html
                             |
                            body
                        h2 -     p           - div[@class=footer]
                        |        |                     |
                        a (1)  a - strong      span[@id=copyright]
                                      |                |
                                      a (3)            a (1)

Это лучший подход к этой проблеме?

Каков наилучший способ (структура данных) для сохранения этого в памяти? Язык не имеет значения. Мы видим, что у нас есть 3 ссылки, соответствующие пути html -> body -> p -> strong -> a.

Как я уже сказал, я совершенно новичок в этом, поэтому, пожалуйста, прости меня, если я подумал об этом совершенно неправильно.

РЕДАКТИРОВАТЬ : Возможно, я ищу структуру данных три?

1 Ответ

1 голос
/ 11 августа 2010

Пока не беспокойтесь о попытках.Просто создайте дерево, используя стандартное представление графа (node ​​= {value, count, parent}, одновременно сворачивая те же ветви и увеличивая счетчик. Затем сортируйте все листья по count в порядке убывания и перемещайтесь от каждого листа вверх, чтобы получить путь.

...