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

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

Джава

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

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

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

C++

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

Answer 3

Вы также можете посмотреть на структуру дерева для этого (возможно, построение основанного на дереве). Это похоже на приличную "простую" альтернативную структуру.

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

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