Высокоэффективный иерархический текстовый поиск
Я нахожусь теперь в заключительных этапах обновления дизайна иерархии в главной системе обработки транзакций, и я смотрел некоторое время на этот запрос с 150 строками (который я сэкономлю Вас вся скука чтения), и думая, что должен быть лучший путь.
Быстрая сводка вопроса следующие:
Как Вы реализовали бы иерархический поиск, который соответствует нескольким критериям поиска на разных уровнях в иерархии, оптимизированной в течение самого быстрого времени поиска?
Я нашел несколько связанный вопрос, но это - действительно только приблизительно 20% ответа, в котором я на самом деле нуждаюсь. Вот полный сценарий/спецификация:
- Конечная цель должна найти один или несколько произвольных объектов в произвольных положениях в иерархии.
- Полная иерархия является приблизительно 80 000 узлов, спроектированных для выращивания к 1M в течение нескольких лет.
- Полный текст всего пути вниз иерархия является уникальным и описательным; однако, текст отдельного узла не может быть. Это - бизнес-действительность и не решение, которое было принято слегка.
- Пример: узел мог бы иметь имя как "Дверь", которая бессмысленна отдельно, но полный контекст, "Aaron> Дом> Гостиная> Бар> Дверь", имеет четкое значение, это описывает определенную дверь в определенном месте. (Обратите внимание, что это - просто пример, реальный дизайн намного менее тривиален),
- Для нахождения этой определенной двери пользователь мог бы ввести "aaron дверь алкоголя", которая, вероятно, поднимет только один результат. Запрос переводится как последовательность: объект, содержащий текст "дверь", под объектом, содержащим текст "алкоголь", под другим объектом, содержащим текст "aaron".
- Или, пользователь мог бы просто ввести "алкоголь дома" для списка всех баров в народных домах (не будет это быть хорошим). Я упоминаю этот пример явно, чтобы указать, что поисковая потребность не соответствует какому-то конкретному корневому или уровню листа. Этот пользователь знает точно, какую дверь он ищет, но не может помнить бесцеремонно, кто владеет ею и помнил бы, открылось ли имя перед ним.
- Все условия должны быть подобраны в указанной последовательности, но поскольку вышеупомянутые примеры предлагают, уровни в иерархии могут быть "пропущены". Термин "aaron корпус выпивки" не соответствовал бы этому узлу.
- Платформа является SQL Server 2008, но я полагаю, что это - платформенно независимая проблема и предпочло бы не ограничивать ответы на ту платформу.
- Сама иерархия на основе
hierarchyid(осуществленный путь), индексированный и в ширину и в глубину. Каждый узел/запись иерархии имеет aNameстолбец, который должен быть запрошен на. Запросы иерархии на основе узла чрезвычайно быстры, не волнуйтесь о тех. - Нет никакой строгой иерархии - корень не может содержать узлы вообще или может содержать 30 поддеревьев, разветвляющихся к 10 000 вершин.
- Максимальное вложение произвольно, но на практике оно имеет тенденцию быть не больше, чем 4-8 уровнями.
- Иерархия может и действительно изменяться, хотя нечасто. Любой узел может быть перемещен в любой другой узел, за очевидными исключениями (родитель не может быть перемещен в его собственного ребенка, и т.д.),
- В случае, если это уже не подразумевалось: Я действительно управляю дизайном и могу добавить индексы, поля, таблицы, независимо от того, что могло бы быть необходимым для получения лучших результатов.
Моя "мечта" состоит в том, чтобы предоставить мгновенную обратную связь пользователю, как в прогрессивном поиске/фильтре, но я понимаю, что это может быть невозможно или чрезвычайно трудно. Я был бы доволен любым существенным улучшением по существующему методу, который обычно берет между 0,5 с к 1 с в зависимости от количества результатов.
Ради полноты существующий запрос (хранимая процедура) запускается путем сбора всех вершин, содержащих заключительный термин, затем присоединяется вверх и исключает любого, пути которого не соответствуют более ранним условиям. Если это кажется обратным кому-либо, пребывайте в уверенности, это более эффективно, чем запуск с корней и разветвление на выходе. Это было "старым" путем и могло легко занять несколько секунд на поиск.
Так мой вопрос снова: существует ли лучший (более эффективный) способ выполнить этот поиск?
Я не обязательно ищу код, просто подходы. Я рассмотрел несколько возможностей, но у них всех, кажется, есть некоторые проблемы:
- Создайте разграниченный "текстовый столбец" пути и индексируйте его с Полнотекстовым поиском. Проблема состоит в том, что поиск на этом столбце возвратил бы все дочерние узлы также; "дом aaron" также соответствует "aaron кухне дома", и "aaron содержат подвал".
- Созданный a
NamePathстолбец, который является на самом деле вложенной последовательностью строк, с помощью типа CLR, подобногоhierarchyidсамостоятельно. Проблема, я понятия не имею, как Microsoft может "перевести" запросы на этом типе для индексации операций, и я даже не уверен, возможно ли сделать на UDT. Если конечным результатом является просто полное индексное сканирование, я ничего не получил этим подходом.
Это не действительно конец света, если я не могу добиться большего успеха, чем, что я уже имею; поиск "довольно быстр", никто не жаловался на это. Но я готов держать пари, что кто-то занялся этой проблемой прежде и имеет некоторые идеи. Совместно используйте их!
2 ответа
Привет, Ааррон, у меня следующая идея:
Судя по вашему описанию, у меня в голове следующее изображение:
Aaron
/ \
/ \
/ \
House Cars
| / \
Living Room Ferrari Mercedes
|
Liquor Cabinet
/ | \
Table Door WindowВот как может выглядеть ваше дерево поиска. Теперь я бы сортировал узлы на каждом уровне:
Aaron
/ \
/ \
/ \
Cars House
/ \ /
/ \ /
/ \ /
/ \ /
/ X
/ / \
/ / \
/ / \
/ / \
| / \
| / \
Ferrari Living Room Mercedes
|
Liquor Cabinet
/ | \
Door Table WindowТеперь обработка запроса должна быть простой и быстрой:
- Начните с последнего слова в запросе и самого нижнего уровня узла(листьев)
- Поскольку все узлы отсортированы в пределах одного уровня, Вы можете использовать бинарный поиск и, следовательно, найти совпадение во времени O(log N), где N - счетчик узлов.
- Сделайте это для каждого уровня. В дереве есть уровни O(log N).
- Как только Вы найдете совпадение, обработайте все родительские узлы, чтобы посмотреть, соответствует ли путь Вашему запросу. Путь имеет длину O(log N). Если он совпадает, сохраните его в результатах, которые должны быть показаны пользователю.
Пусть будет M - количество общих совпадений (количество узлов, совпадающих с последним словом в запросе). Тогда наше время обработки: O( (log N)^2 + M * (log N) ):
.
Двоичный поиск занимает время O(log N) для каждого уровня, а уровни O(log N) существуют, поэтому мы должны потратить как минимум время O( (log N)^2). Теперь, для каждого совпадения, мы должны проверить, совпадает ли полный путь от нашего совпадающего узла до корня с полным запросом. Путь имеет длину O(log N). Таким образом, учитывая M совпадений в целом, мы проводим еще одно M * O(log N) время, таким образом, результирующее время выполнения - O( (log N)^2 + M * (log N) ).
Когда у вас мало совпадений, время обработки приближается к O( (log N)^2 ), что довольно неплохо. Наоборот, если происходит наихудший случай (каждый путь соответствует запросу (M = N)), время обработки приближается к O(N log N), что не слишком хорошо, но и не слишком вероятно.
Реализация:.
Ты сказал, что тебе нужна только идея. Далее мои знания о базах данных очень ограничены, поэтому я не буду здесь много писать, просто опишу некоторые идеи.
.
Таблица узлов может выглядеть следующим образом:
- ID : int
- Text : string
- Parent : int -> node ID
- Level : int //I не ожидает, что это будет меняться слишком часто, поэтому Вы можете сохранить и обновить ее по мере изменения БД.
Эта таблица должна быть отсортирована по столбцу "Текст". Используя описанный выше алгоритм, sql запрос внутри цикла мог бы выглядеть следующим образом:
SELECT ID FROM node WHERE Level = $i AND Text LIKE $text
Надеюсь, вы меня поняли.
Еще больше ускорить процесс можно не только сортировкой таблицы по столбцу "Текст", но и комбинированными столбцами "Текст" и "Уровень", т.е. все записи внутри Level=20 отсортированы, все записи внутри Level=19 отсортированы и т.д.(но никакой общей сортировки по всей таблице не требуется). Впрочем, счетчик узлов PER LEVEL находится в O(N), поэтому асимптотического улучшения времени исполнения нет, но я думаю, что стоит попробовать, учитывая более низкие константы, которые вы получаете в реальности.
Правка: Улучшение
Я только что заметил, что итеративный алгоритм совершенно не нужен (таким образом, от информации об Уровне можно отказаться). Этого вполне достаточно, чтобы:
- Хранить все узлы, отсортированные по их текстовому значению
- Найти все совпадения по последнему слову запроса сразу, используя двоичный поиск по всем узлам.
- От каждого совпадения отследить путь до корня и проверить, совпадает ли путь со всем запросом.
Это улучшает время выполнения до O(log N + M * (log N)).
.взгляните на Апача Лусена. Вы можете реализовать очень гибкий и в то же время эффективный поиск с помощью Lucene. Это может быть полезно.
Также посмотрите на шаблоны поиска - то, что вы описываете, может вписаться в шаблон Грановидного поиска.
Довольно легко реализовать тривиальный алгоритм "Живая дверь Аарона Хауса", но не уверен, что обычные алгоритмы, основанные на SVM/классификации/энтропии, масштабируются до большого массива данных. Возможно, вам также захочется взглянуть на концепции "поиска аппроксимации" Мотвани и Рагхавана.
Пожалуйста, отправьте назад то, что вы нашли, если это возможно :-)
.