Обновляемая библиотека DAWG или конструкция DAWG из несортированных данных
dawgdic является отличной библиотекой DAWG, но она имеет существенный недостаток, поскольку она является статической (не обновляемой) и должна быть построена из строк формы, отсортированных в алфавитном порядке. Если исходные данные, из которых создается DAWG, большие (несколько гигабайт), первоначальная конструкция DAWG, включающая сортировку огромного массива строк, может потребовать слишком много ресурсов.
Есть ли библиотека, которая обеспечивает эффективную память как dawgdic что позволяет строить из несортированного словаря?
Решение
В настоящее время я не думаю, что есть какая-либо библиотека, которая позволяет создавать DAWG из несортированных словарей.
Но после долгих поисков я нашел эту статью, «Инкрементальное построение минимальных ациклических конечных автоматов»
, который, я думаю, имеет именно то, что вы хотите. Может быть, вы могли бы сделать свою собственную библиотеку после прочтения этого, и поделиться ею со всеми!
РЕДАКТИРОВАТЬ: Вы смотрели на этот вопрос?
Другие решения
Я нашел несколько отличных библиотек, которые позволяют строить онлайн из несортированных данных, хотя они не основаны на DAWG:
- кедр — очень быстрый двойной массив
- Мариса-Trie — очень компактная библиотека соответствия строк
В настоящее время я не знаю ни одной реализации C ++ DAWG, которая бы поддерживала конструкцию из несортированных данных, но если вы открыты для создания собственного решения, имеющего такую функцию, Инкрементальное построение минимальных ациклических конечных автоматов (2000) это документ, который в основном излагает алгоритм позади него.
Кроме того, если вы открыты для портирования решений с других языков, возможно, стоит потратить время на ознакомление MDAG, Java-реализация структуры данных. Он поддерживает как добавление строк «на лету», так и удаление строк, и это именно то, что вы ищете. Код также прост в использовании и подробно прокомментирован, поэтому его перенос должен быть довольно простой задачей.
Отказ от ответственности: я автор MDAG :).