Три (дерево префиксов) в Python
Я не знаю, если это место, чтобы спросить об алгоритмах. Но посмотрим, получу ли я какие-нибудь ответы...:)
Если что-то неясно, я очень рад уточнить вещи.
Я только что реализовал Trie в Python. Тем не менее, один бит казался более сложным, чем следовало бы (как тот, кто любит простоту). Возможно, у кого-то была похожая проблема?
Моя цель состояла в том, чтобы минимизировать количество узлов, храня самый большой общий префикс поддерева в его корне. Например, если бы у нас были слова stackru, stackbase и stackbase, дерево могло бы выглядеть примерно так:
[s]tack
[o]verflow ______/ \_______ [b]ase
\___ [d]
Обратите внимание, что все еще можно думать о ребрах, имеющих один символ (первый из дочерних узлов).
Find-query прост в реализации.Вставка не сложно, но несколько сложнее, чем я хочу..:(
Моя идея заключалась в том, чтобы вставлять ключи один за другим (начиная с пустой строки), сначала ища вставляемый ключ k (Find(k)), а затем переставляя / разделяя узлы локально в том месте, где процедура поиска останавливается. Оказывается, 4 случая: (пусть k будет ключом, который мы хотим вставить, и k'будет ключом узла, где поиск закончился)
- k идентично k'
- k является "правильным" префиксом k'
- k'является "правильным" префиксом k
- k и k'имеют общий префикс, но ни один из случаев (1), (2) или (3) не встречается.
Кажется, что каждый из случаев уникален и, следовательно, предполагает различные модификации Три. НО: это действительно так сложно? Я что-то пропустил? Есть ли лучший подход?
Спасибо:)
5 ответов
На первый взгляд кажется, что вы реализовали Патрицию Три. Этот подход также называется сжатием пути в некоторых литературных источниках. Там должны быть копии этого документа, которые не находятся за платным доступом ACM, который будет включать алгоритм вставки.
Есть также другой метод сжатия, который вы можете рассмотреть: сжатие по уровням. Идея, лежащая в основе сжатия пути, заключается в замене строк одиночных дочерних узлов одним суперузлом, который имеет счетчик пропусков. Идея сжатия уровня заключается в замене полных или почти полных поддеревьев на суперузел со счетчиком "степени", который говорит, сколько цифр ключа декодирует узел. Есть также третий подход, называемый сжатием по ширине, но я боюсь, что моя память подвела меня, и я не смог найти описание этого с быстрым поиском в Google.
Сжатие на уровне может значительно сократить средний путь, но алгоритмы вставки и удаления становятся довольно сложными, поскольку им необходимо управлять узлами Trie так же, как и динамическими массивами. Для правильных наборов данных, сжатые деревья уровня могут быть быстрыми. Из того, что я помню, это 2-й самый быстрый подход к хранению таблиц IP-маршрутизации, самый быстрый - это своего рода хеш-код.
Немного странно, но если вас очень беспокоит количество узлов в вашем Trie, вы также можете взглянуть на соединение суффиксов своих слов. Я хотел бы взглянуть на идею DAWG (направленный график ациклических слов): http://en.wikipedia.org/wiki/Directed_acyclic_word_graph
Недостатком этого является то, что они не очень динамичны, и их создание может быть трудным. Но если ваш словарь статичен, он может быть очень компактным.
Я не вижу ничего плохого в вашем подходе. Если вы ищете решение с резким скачком, возможно, действие, предпринятое в случае 4, реально выполнимо для первых трех случаев, IE найдет общий префикс для k а также k' и восстановить узел с учетом этого. Если случится так, что ключи были префиксами друг друга, то полученное дерево все равно будет правильным, только реализация сделала немного больше работы, чем на самом деле. но опять же, без какого-либо кода, трудно сказать, работает ли это в вашем случае.
У меня есть вопрос относительно вашей реализации. Каков уровень детализации, на котором вы решили разделить свои строки, чтобы создать дерево префиксов. Вы можете разделить стек как s, t, a, c, k или st, ta, ac, ck и многие другие нграммы. Большинство реализаций префиксного дерева учитывают алфавит для языка, на основе этого алфавита вы выполняете разбиение.
Если бы вы строили реализацию дерева префиксов для python, то ваши алфавиты были бы такими, как def,:, if, else... и т. Д.
Выбор правильного алфавита имеет огромное значение для построения эффективных деревьев префиксов. Что касается ваших ответов, вы можете найти пакеты PERL на CPAN, которые выполняют самые длинные вычисления общих подстрок с использованием trie. Возможно, вам повезет, так как большая часть их реализации довольно надежна.
Посмотрите на: Judy-массивы и интерфейс Python по адресу http://www.dalkescientific.com/Python/PyJudy.html