Как я могу создать возрастающий направленный нециклический график слова для хранения и строки поиска?
Я пытаюсь сохранить большой список строк кратким способом так, чтобы они могли очень быстро анализироваться/перерываться.
Направленный нециклический график слова (DAWG) удовлетворяет этой цели замечательно. Однако у меня нет списка строк для включения во-первых, таким образом, это должно быть инкрементно buildable. Кроме того, когда я перерываю его для строки, я должен возвратить данные, связанные с результатом (не только булевская переменная, говорящая, присутствовало ли это).
Я нашел информацию о модификации DAWG для строковых данных, отслеживающих здесь: http://www.pathcom.com/~vadco/adtdawg.html Это выглядит чрезвычайно, чрезвычайно сложным и я не уверен, что я способен к записи его.
Я также нашел несколько научно-исследовательских работ, описывающих возрастающие алгоритмы здания, хотя я нашел, что научно-исследовательские работы в целом не очень полезны.
Я не думаю, что совершенствуюсь достаточно, чтобы смочь объединить оба из этих алгоритмов сам. Уже есть ли документация алгоритма что функции они или альтернативный алгоритм с хорошим использованием памяти и скоростью?
3 ответа
Я написал веб-страницу ADTDAWG. Добавление слов после построения - не вариант. Структура представляет собой не более чем 4 массива беззнаковых целочисленных типов. Он был разработан так, чтобы быть неизменным для полного включения кеша ЦП и минимальной сложности многопоточного доступа.
Структура представляет собой автомат, который формирует минимальную и совершенную хеш-функцию. Он был построен для скорости при рекурсивном обходе с использованием явного стека.
Как опубликовано, он поддерживает до 18 символов. Включение всех 26 английских символов потребует дальнейшего увеличения.
Я советую использовать стандартный Trie с индексом массива, хранящимся в каждом узле. Да, это покажется инфантильным, но каждый узел END_OF_WORD представляет только одно слово. ADTDAWG - это решение для каждого узла END_OF_WORD в традиционной DAWG, представляющего много-много слов.
Минимальные и идеальные хеш-таблицы - это не то, что можно просто собрать на лету.
Я ищу другую работу или работу, так что свяжитесь со мной, и я сделаю все, что в моих силах.На данный момент все, что я могу сказать, это то, что нереально использовать тяжелую оптимизацию для структуры, которая часто меняется.
Возможно, вы также захотите рассмотреть trie структуру для этого (потенциально построив radix-tree). Это кажется достойной "простой" альтернативной структурой.
Я предлагаю это по нескольким причинам:
- У меня действительно нет полного понимания вашего результата.
- Определенно, построение будет инкрементальным.
- Листовые узлы могут содержать любые данные, какие вы пожелаете.
- Субъективно, простой алгоритм.
Java
Для проблем с графами, требующих постоянства, я бы взглянул на проект Neo4j graph DB. Neo4j предназначен для хранения больших графов и позволяет инкрементное построение и изменение данных, что, похоже, соответствует описанным вами критериям.
У них есть несколько хороших примеров, которые помогут вам быстро освоить проект, и обычно есть примеры кода для решения большинства проблем.
У них есть пример DAG со ссылкой внизу на полный исходный код.
C++
Если вы используете C++, распространенным решением для построения/анализа графов является использование библиотеки Boost graph library. Для сохранения графа вы можете поддерживать версию графа в файле на основе GraphML (например) и читать и записывать в этот файл по мере изменения графа.