Когда мы действительно используем Trie?

Question

Я начинаю читать о Trie. Я получил также ссылки от друзей здесь: Tutorials on Trie

Я не ясно следующее:
кажется, что идти дальше и использовать Trie один предполагает, что все входные строки, которые будут пространство поиска и используется для построить Trie разделены в отдельные границы слов.
E.g. все примеры учебники я видел использование сигналов, таких как:

S={ball, bid, byte, car, cat, mac, map etc...} 

Тогда мы строим синтаксического дерева из S и сделать наши поиски (очень быстро)
Мой вопрос: Как мы в конечном итоге с S начать с ?
Я имею в виду, прежде чем начинать читать о попытках, я представил себе, что S будет произвольно длинным текстом, например. A Shakespeare проход.

Затем, используя Trie, мы могли бы найти вещи очень быстро.
Но, похоже, это не тот случай.

Является ли предположение, что входной проход (например, Shakespeare) предварительно обработан для всех слов, чтобы получить S?

Итак, если вы хотите искать шаблоны (так же, как и в Google, и видеть, что все страницы имеют также пробелы в вашем поисковом запросе), Trie не подходит?
Когда мы узнаем, является ли Trie структурой данных, которую мы действительно можем использовать?

Answer 1

Простые методы полезны там, где у вас есть фиксированный словарь, который вы хотите быстро найти. По сравнению с хеш-таблицей может потребоваться меньше хранилища для большого словаря, но может потребоваться больше времени для поиска. Одним из примеров, которые я использовал для сопоставления URL-адресов для операций на веб-сервере, может быть наследование функциональности на основе префикса. Здесь recursing down trie позволяет найти подходящий поиск всех методов, которые необходимо вызвать для определенного URL-адреса. Также было бы удобно хранить словарь.

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

Answer 2

Мы можем использовать попытки для поиска подстроки в линейном времени без предварительной обработки строки каждый раз. Вы можете получить лучший учебник по генерации дерева суффикса @ Ukkonen's suffix tree algorithm in plain English?

Answer 3

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

• My answer to this question использует (слегка модифицированный) для синтаксического дерева согласования предложений: это Trie на основе последовательности слов, а не последовательность символов. (Другие ответы на этот вопрос, вероятно, более четко показывают действие в действии.)
• Я также использовал trie в игре, в которой было большое количество комнат с именами (общее количество и имена были определены во время выполнения), каждое из этих имен должно быть уникальным, и каждый должен был быть способный быстро найти комнату с заданным именем. Также может использоваться хеш-таблица, но в некотором смысле trie проще реализовать и быстрее при использовании строк. (Моя реализация закончилась тем, что была ~ 50 строк C.)

У метки trie, вероятно, есть еще много примеров.

Answer 4

Существует несколько способов использования попыток. Типичным примером является поиск, такой как тот, который вы представили. Однако Tries также можно использовать для полного индексирования полного текста. Либо вы используете алгоритм дерева суффикса Ukkonen, чтобы создать суффикс trie, либо вы явно строите суффикс trie, сохраняя суффиксы (намного медленнее алгоритма Укконена, но также намного проще). Поскольку это предварительная обработка, которая должна быть выполнена только однажды, скорость не является решающей.

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

Так что, если у нас есть текст " Текст «мы вставим следующий набор:

{"The Text", "he Text", "e Text", " Text", "Text", "ext", "xt", "t"} 

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

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

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