Trie (Prefix Tree) в Python

Question

Я не знаю, если это место, где можно задать вопрос об алгоритмах. Но посмотрим, получаю ли я ответы ... :)

Если что-то неясно, я очень рад прояснить ситуацию.

Я только что внедрил Trie в python. Однако один бит казался более сложным, чем следовало бы (как человек, который любит простоту). Возможно, у кого-то была аналогичная проблема?

Моя цель состояла в том, чтобы свести к минимуму количество узлов, сохранив в своем корне самый большой общий префикс субтри. Например, если бы мы были слова StackOverflow, stackbase и stackbased, то дерево будет выглядеть примерно так:

   [s]tack 
[o]verflow ______/ \_______ [b]ase 
            \___ [d] 

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

Найти -query прост в применении. вставки не трудно, но несколько сложнее, чем я хочу .. :(

Моя идея состояла в том, чтобы вставить ключи один за другим (начиная с пустого) синтаксического дерева, сначала ища, чтобы быть -интегрированный ключ k (Найти (k)), а затем переставить/разбить узлы локально в том месте, где останавливается процедура поиска. Оказывается, 4 случая: (Пусть k - это ключ, который мы хотим вставить и к «быть ключом узла, где поиск завершившийся)

1. к идентично к»
2. k является «правильным» префиксом для k '
3. k' является «правильным» префиксом k
4. k и k 'совместно используют общий префикс, но ни один из случаев (1), (2) или (3).

Кажется, что каждый из случаев уникален и, следовательно, подразумевает различные модификации Trie. НО: это действительно так сложно? Я что-то упускаю? Есть ли лучший подход?

Спасибо :)

Answer 1

С первого взгляда, похоже, вы внедрили Patricia Trie. Этот подход также называется сжатием путей в некоторой литературе. Должны быть копии этого документа, которые не находятся за платой ACM, который будет включать в себя алгоритм вставки.

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

Уровень сжатия может значительно сократить средний путь, но алгоритмы вставки и удаления становятся довольно сложными, поскольку они нуждаются в управлении узлами три аналогично динамическим массивам. Для правильных наборов данных уровни сжатых деревьев могут быть fast. Из того, что я помню, они являются вторым самым быстрым подходом для хранения таблиц маршрутизации IP, самый быстрый из них - это своего рода хэш-три.

Answer 2

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

Answer 3

Относительно касательной, но если вас очень беспокоит количество узлов в вашей Trie, вы можете посмотреть на присоединение к своим суффиксам. Я бы посмотрел на диаграмму DAWG (Directed Acyclic Word Graph): http://en.wikipedia.org/wiki/Directed_acyclic_word_graph

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

Answer 4

У меня есть вопрос относительно вашей реализации. Каков уровень детализации, который вы решили разделить на свои строки, чтобы создать дерево префикса. Вы можете разделить стек как на s, t, a, c, k, так и на st, ta, ac, ck и многие другие ngrams. В большинстве реализаций дерева префикса учитывается алфавит для языка, основанный на этом алфавите, вы делаете расщепление.

Если вы создаете реализацию Приставка дерева для питона, то ваши алфавитов будет что-то вроде четкости,:, если, еще ... и т.д.

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

Answer 5

Посмотрите: Judy-массивы и интерфейс питон на http://www.dalkescientific.com/Python/PyJudy.html