Как я могу построить инкрементно направленный ациклический граф слов для хранения и поиска строк?

Question

Я пытаюсь сохранить большой список строк в сжатой форме, чтобы их можно было очень быстро проанализировать / найти.

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

Я нашел информацию о модификации DAWG для отслеживания строковых данных здесь: http://www.pathcom.com/~vadco/adtdawg.html Это выглядит чрезвычайно, очень сложно, и я не уверен, что способен написать это.

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

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

Answer 1

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

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

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

Мой совет - использовать стандартный Trie с индексом массива, хранящимся в каждом узле. Да, это будет казаться инфантильным, но каждый узел END_OF_WORD представляет только одно слово. ADTDAWG - это решение для каждого узла END_OF_WORD в традиционной DAWG, представляющее много-много слов.

Минимальные и совершенные хеш-таблицы - это не та вещь, которую вы можете просто собрать на лету.

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

Answer 2

Java

Для задач с графами, требующих постоянства, я бы взглянул на проект Neo4j graph DB .Neo4j предназначен для хранения больших графиков и позволяет наращивать и модифицировать данные, что, по-видимому, соответствует описанным вами критериям.

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

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

C ++

Если вы используете C ++, общее решение для построения / анализа графиков состоит в использовании библиотеки графов Boost .Чтобы сохранить график, вы можете сохранить файловую версию графика в GraphML (например) и читать и записывать в этот файл при изменении графика.

Answer 3

Вы также можете посмотреть структуру trie для этого (возможно построение radix-tree ). Это похоже на приличную «простую» альтернативную структуру.

Я предлагаю это по нескольким причинам:

1. У меня действительно нет полного понимания вашего результата.
2. Определенно добавочный для построения.
3. Конечные узлы могут содержать любые данные, которые вы хотите.
4. Субъективно , простой алгоритм.