Как построить обратное дерево?

Question

Я следил за этой веб-страницей https://nlp.stanford.edu/IR-book/html/htmledition/wildcard-queries-1.html для изучения подстановочных запросов.

Но не в состоянии понять, как будет выглядеть обратное B-дерево в словаре.

Например, если у меня есть Btree, как это:

**

Как построить обратное Btree на основе этого btree?

**

Answer 1

Обратное B-дерево будет просто обычной структурой данных B-Tree, построенной на обратной строке.

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

(Рассмотрим строку Lemon) Например 'Le*' Вы проходите через L, затем e, а затем перечисляете все возможности. Если вы сохранили обратное дерево (где Lemon становится nomeL), тогда запрос '*mon' который является префиксным запросом, может быть изменен (обращен) на 'nom*' который становится суффиксным запросом, и на него можно ответить с большей сложностью во время выполнения.

С практической точки зрения, поисковые системы, такие как Solr, используют аналогичную технику для обслуживания основных подстановочных запросов. Производительность улучшается за счет более высокой сложности пространства (компромисс между пространством и временем). Для получения дополнительной информации вы можете проверить Solr ReversedWildcardFilterFactory.