Три (дерево префиксов) в Python

Question

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

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

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

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

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

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

Find - запрос прост в реализации. Вставка не сложно, но несколько сложнее, чем я хочу ..: (

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

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

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

Спасибо:)

Answer 1

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

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

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

Answer 2

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

Если бы вы строили реализацию дерева префиксов для python, то вашими алфавитами были бы такие вещи, как def,:, if, else ... etc

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

Answer 3

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

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

Answer 4

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

Answer 5

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