Как изменить структуру данных префикса Trie для обработки слов, которые находятся в середине?

Question

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

Позвольте мне объяснить, что я имею в виду. Представьте, что у меня есть эти названия продуктов:

• плитка для ванной
• плитка для гостиной
• кухонная плитка
• кухонная плитка, черная
• какая-то другая плитка, зелёная

Пользователь ищет «плитку», и он увидит первые 2 результата только в том случае, если я использую трификсный префикс, но я хочу, чтобы все эти результаты всплыли, однако я не знаю какой-либо эффективной структуры данных, чтобы справиться с этим , Можете ли вы предложить что-нибудь? Можно ли изменить префикс Trie для этого?

Я думал о некоторых модификациях, таких как вставка всех суффиксов и т. Д., Но они дадут неправильные результаты, например, я вставил суффиксы для

• кухонная плитка, черная
• какая-то другая плитка, зелёная

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

Answer 1

Структура данных Trie действительно работает для операций сопоставления префиксов, а не для поиска по среднему тексту

Обычной структурой данных, поддерживаемой при поиске по среднему тексту, является дерево суффиксов: https://en.wikipedia.org/wiki/Suffix_tree

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

Суффиксный массив является альтернативой с эффективным использованием пространства: https://en.wikipedia.org/wiki/Suffix_array

Answer 2

Не переусердствуйте. Компьютеры быстры. Если вы говорите о порядке тысяч продуктов в памяти, то последовательный поиск с проверкой содержимого будет достаточно быстрым: всего несколько миллисекунд, если это так.

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

Answer 3

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

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

Давайте рассмотрим приведенный выше пример, чтобы понять этот подход.

1. Take each sentence, say tile for bathroom. 
2. Split the sentences into words as - tile, for, bathroom.
3. Create a tuple of [String, String], so for above example we will get three tuples.
  (i)  [tile, tile for bathroom]
  (ii) [for, tile for bathroom]
  (iii)[bathroom, tile for bathroom]
4. Now insert the first String of the above tuple into your trie and store the 
other tuple (which is the whole sentence) as a String object to the 
last character node for the word. i.e when inserting tile, the node at 
character e will store the sentence string value.
5. One case to handle here is, like the tile word appears in two strings, so in that case
the last character e will store a List of string having values - tile for bathroom and tile for living room.

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

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

Надеюсь, это поможет!