при каком виде поисковых инструментов данные структурированы по темам в виде иерархических структур

08.01.202430.06.2023 admin 0 Comments

Поиск информации в Web

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

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

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

Как показывает практика, для поиска разного рода информации наиболее эффективными оказываются различные инструменты (рис. 4.19). Рассмотрим каждую категорию по отдельности.

Индексированные каталоги

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

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

Источник

Иерархические структуры данных и Doctrine

Введение

Хранение иерархических данных (или попросту — деревьев) в реляционных структурах задача довольно нетривиальная и вызывает некоторые проблемы, когда разработчики сталкиваются с подобной задачей.

В первую очередь, это связано с тем, что реляционные базы не приспособлены к хранению иерархических структур (как, например, XML-файлы), структура реляционных таблиц представляет из себя простые списки. Иерархические же данные имеют связь «родитель-наследники», которая не реализована в реляционной структуре.

Тем не менее, задача «хранить деревья в базе данных» рано или поздно возникает перед любым разработчиком.

Ниже мы подробно рассмотрим, какие существуют подходы в организации хранения деревьев в реляционных БД, а также рассмотрим инструментарий, который нам предоставляет ORM Doctrine для работы с такими структурами.

Список смежных вершин (Adjacency List)

Описание структуры

Как правило, такая структура данных предполагает хранение информации о смежных вершинах нашего дерева. Давайте рассмотрим простейший граф с темя вершинами (1,2,3):

Рис. 1. Граф с тремя вершинами

Как видим каждый элемент данного графа хранит информацию о связи с другими элементами, т.е.:

Фактически, для построения дерева такой граф избыточен, т.к. для привычной ветвистой структуры нам нужно хранить только связь «родитель-наследник», т.е.:

Тогда мы получим дерево с одним корневым элементом (1) и двумя ветками (2,3):

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

Итак, чтобы хранить в базе данных иерархическую структуру методом списка смежных вершин (Adjacency List), нам необходимо хранить информацию о связях «наследник-родитель» в таблицах с данными. Давайте рассмотрим реальный пример дерева:

Рис. 3. Древовидная структура методом смежных вершин

На рисунке квадратами обозначены узлы деревьев. У каждого узла есть имя (верхний прямоугольник внутри квадрата), идентификатор (левый нижний квадрат) и ссылка на идентификатор родителя (правый нижний квадрат). Как видно из Рис. 3, каждый наследник в такой структуре ссылается на своего предка. В терминах БД мы можем это отобразить следующим образом в виде таблицы:

Рис. 4. Таблица данных дерева, построенная методом списка смежных вершин

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

Проблемы с чтением из БД менее заметны, если вычитывать все дерево целиком. Это достаточно простой запрос:

Однако в дальнейшем такая выборка подразумевает достаточно емкую программную пост-обработку данных. Сначала нужно рекурсивно перестроить данные с учетом связей «предок-наследник» и лишь потом их можно будет использовать для вывода куда-либо.

Другой вариант чтения дерева целиком:

Результат в данном случае будет такой:

Хотя данные в таком виде уже более приспособлены сразу для вывода, но, как видите, главный недостаток такого подхода — необходимо достоверно знать количество уровней вложенности в вашей иерархии, кроме того, чем больше иерархия, тем больше JOIN’ов — тем ниже производительность.

Тем не менее, данный способ обладает и существенными достоинствами — в дерево легко вносить изменения, менять местами и удалять узлы.

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

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

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

Использование списка смежных вершин в Doctrine

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

Итак, сущности, которыми мы оперируем в ORM Doctrine — это активные записи (Active Record). Т.е. объекты, которые совмещают в себе бизнес-логику и сами умеют взаимодействовать с базой данных. Но разработчики Doctrine предусмотрели расширение функциональности объектов записей не только наследованием, но и применением к этим объектам «шаблонов поведения». Это реализуется пакетом Doctrine/Template.

Т.о., если возникает необходимость воспитать активную запись до какого-либо поведения (например, Versionable — проводит аудит всех изменений, I18N — многоязычная или NestedSet — древовидная вида «вложенное множество»), то это можно сделать как раз с помощью данных шаблонов поведения.

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

Когда придет время, мы покажем на примерах, как это сделать.

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

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

Для этого следует сконфигурировать нашу модель должным образом. Используя YAML опишем структуру нашей таблицы:

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

Теперь соберем нашу модель, запустив команду:

Все. Модель готова. Фактически тоже самое можно было сделать в уже готовом базовом классе BaseAlTree:

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

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

Но в тоже время, реализовать динамически подгружаемое дерево таким способом — одно удовольствие!

Вложенное множество (Nested Set)

Описание структуры

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

При построении дерева на основе вложенных множеств, мы воспользуемся принципом обхода этого дерева слева-направо, как показано стрелками на Рис. 5. Для этого определим для каждого узла дерева целочисленные ключи слева (lft) и справа (rgt) (нижние квадратики внутри узла). И раздадим им во время обхода целочисленные инкрементные значения. Посмотрите что получилось.

Рис. 5. Вложенное множество (Nested Set).

Корневой элемент получил ключи 1 и 14, которые включают в себя диапазон чисел всех остальных ключей. Ветка VEGETABLE получила ключи 2 и 7, которые, в свою очередь, включают весь диапазон чисел ключей всех ее наследников и т.д. Вот они — вложенные множества. Все просто, не так ли?

Давайте воссоздадим такую же структуру в контексте таблицы БД.

Рис. 6. Таблица иерархических данных на основе метода вложенных множеств

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

Чтение дерева из БД

Результат будет таким:

Теоретически, тот же результат мы бы могли получить, вычисляя уровень вложенности на лету:

Попробуйте сравнить результат самостоятельно — он будет идентичен первому. Только сам запрос в данном случае более ресурсоемкий. А так как Nested Set — это оптимальный алгоритм чтения, то небольшая оптимизация в виде кеширования уровня вложенности рядом с остальными данными не такая уж и плохая стратегия.

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

Например, если мы хотим извлечь все овощи (VEGETABLE) из нашего примера, это сделать достаточно просто:

Да, быстрое и гибкое чтение, включая агрегацию с внешними связанными данными — конек данного алгоритма.

Тем не менее, не бывает худа без добра, и в данном случае, значительные трудности начинаются когда нам необходимо внести изменения в Nested Set дерево или удалить какую-либо из его ветвей.

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

Добавление новой ветки

Предположим, что мы хотим добавить новую ветку с именем SEA FOOD в наше дерево на одном уровне с VEGETABLES и FRUIT.

Если вы используете в MySQL таблицы MYISAM, или версию, которая не поддерживает транзакции, вы можете вместо BEGIN и COMMIT использовать блокировки на запись:

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

Удаление ветки

Давайте теперь попробуем удалить вновь созданную ветку:

Вывод — Nested Set действительно хорош, когда нам необходимо считывать структуру деревьев из БД. При этом он одинаково хорош для деревьев любого объема.

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

Использование Nested Set в Doctrine

А вот этот метод имеет отражение в Doctrine в виде реализации шаблона поведения, который мы можем привязать к нашей модели.

Сделать это довольно просто, методом конфигурации модели через YAML-конфиг или прамо в коде базового класса.

Как видите, достаточно просто указать actAs: [NestedSet] в описании класса.

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

В этом случае конфигурацию следовало бы записать так:

Все то же самое могло бы быть проделано в существующем базовом классе модели.

Для первого случая:

Для второго случая (несколько деревьев):

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

Примеры работы с деревьями Nested Set в Doctrine

Извлекаем и печатаем все дерево на экран:

Посмотрите как это просто!

За дополнительными примерами и информацией вы можете обратиться к официальной документации Doctrine, разделы 8.2.4 и 8.2.5

Материализованный путь (Materialized Path)

Описание структуры

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

Рис. 7. Древовидная структура, организованная по принципу «материализованый путь»

Принцип формирования таких путей достаточно прост. Глубина пути — это уровень дерева. Внутри ветки нумерация — инкрементная. Другими словами, VEGETABLE — первый ребенок FOOD, FRUIT — второй ребенок и т.д.

Проще будет взглянуть на это в виде таблицы:

Возможно, так даже более наглядно.

В базе данных все это находит следующее отражение.

Рис. 8. структура таблицы иерархических данных, организованных по принципу «материализованный путь»

В чем же преимущество такого подхода?

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

Поиск пути к узлу:

Вычисление уровня вложенности.

Для решения этой задачи нам в принципе достаточно посчитать кол-во точек (или других разделителей, если вы используете не точку) в путях. К сожалению, MySQL не имеет подходящей функции, но мы можем ее реализовать достаточно просто своими силами:

Выбор ветки:

Обратите внимание, в данном примере мы воспользовались нашей самописной функцией и это было достаточно удобно.

Поиск родителя:

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

Насколько известно автору, алгоритм довольно уверенно себя чувствует на достаточно больших объемах данных.

Следует отметить, что наиболее неприятной в данном алгоритме будет операция вставки узла в середину уже существующей структуры (между другими узлами), т.к. это повлечет изменение всех путей в нижележащих узлах. Хотя, справедливости ради, следует сказать, что такая операция окажется нетривиальной для любой модели хранения данных. Другая тяжелая операция — это перенос одной ветки в другую.

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

Как видно из примеров, данный алгоритм также можно несколько оптимизировать на чтение, путем введения ещё одного поля level, как это было сделано для списков смежных вершин (Nested Set). Однако это несколько усложнит операции добавления, изменения и удаления узлов дерева, т.к. уровни придется пересчитывать для всего или части дерева при каждом изменении. В конечном счете, именно разработчику решать, в какую сторону следует делать перекос производительности.

Использование в Doctrine

К сожалению, на данный момент, этот метод хранения деревьев пока не нашел своей реализации в ORM Doctrine (текущая версия на момент написания материала — 1.0.4, 1.1.0 — в альфа версии также реализации не имеет).

Тем не менее есть все предпосылки полагать, что его реализация появится в будущем, т.к. исходные коды библиотеки содержат в пакете Doctrine/Tree абстракный пустой класс с именем MaterializedPath.

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

Комбинированный подход

Фактически, комбинирование подходов на уровне БД ограничивается вводом поля, хранящего ссылку на родительскую запись в таблицы списков смежности и материализованных путей:

Рис. 9. Таблицы моделей иерархических структур данных AL+MP и AL+NS

Последствия такого подхода очевидны.

AL+MP

AL+NS

Для связки AL+NS взаимовыгодность не столь очевидна. В первую очередь это объясняется тем, что недостатки от проблем изменения узлов дерева в модели NS напрочь убивают в этой сфере все достоинства AL. Это значит, что такую связку следует рассматривать лишь как качественное улучшение поиска родителей и наследников заданного узла в алгоритме NS, а также как повышение надежности самого алгоритма (ключи можно всегда перестроить в случае порчи — информацию о связях хранит AL). Утверждение о повышении надежности справедливо и для предыдущей комбинации методов. Но ведь и это качественное улучшение, хотя и не такое очевидное, не так ли?

Заключение

В данной статье мы рассмотрели несколько основных методов хранения иерархических данных в реляционных БД и очертили все их достоинства и недостатки. Также мы показали на практике, какие из них доступны для использования в реализации ORM Doctrine, и как их использовать.

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

Источник

Поисковые системы

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

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

Инструменты поиска

ля поиска в Интернете предназначены различные инструменты: поисковые машины (поисковики), индексированные каталоги (рубрикаторы), рейтинги и топы, метапоисковые системы и тематические списки ссылок, онлайновые энциклопедии и справочники (рис. 1). При этом для поиска разного рода информации наиболее эффективными оказываются различные инструменты. Рассмотрим каждую категорию по отдельности.

Рис. 1. Для каждого типа информации следует выбирать соответствующий инструмент поиска