Обновляемая библиотека DAWG или конструкция DAWG из несортированных данных

Question

Обновляемая библиотека DAWG или конструкция DAWG из несортированных данных

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

Есть ли библиотека, которая обеспечивает эффективную память как dawgdic что позволяет строить из несортированного словаря?

3

c++ nlp trie dawg

Источник

user609063 27 авг '13 в 15:48

3 ответа

Другие вопросы по тегам c++ nlp trie dawg

user1317826 04 окт '13 в 11:36 2013-10-04 11:36 · Answer 1 · 2013-10-04 11:36

В настоящее время я не думаю, что есть какая-либо библиотека, которая позволяет создавать DAWG из несортированных словарей.

Но, после долгих поисков, я нашел эту статью "Постепенное построение минимальных ациклических конечных автоматов", которая, я думаю, имеет именно то, что вы хотите. Может быть, вы могли бы сделать свою собственную библиотеку после прочтения этого, и поделиться ею со всеми!

РЕДАКТИРОВАТЬ: Вы смотрели на этот вопрос?

user468737 01 июл '16 в 18:32 2016-07-01 18:32 · Answer 2 · 2016-07-01 18:32

В настоящее время я не знаю ни одной реализации C++ DAWG, которая бы поддерживала конструкцию из несортированных данных, но если вы открыты для создания своего собственного решения, имеющего такую функцию, инкрементальное построение минимальных ациклических конечных автоматов (2000) документ, который в основном излагает алгоритм позади него.

Кроме того, если вы открыты для портирования решений с других языков, возможно, стоит потратить время на ознакомление с MDAG, реализацией структуры данных на Java. Он поддерживает как добавление строк "на лету", так и удаление строк, и это именно то, что вы ищете. Код также прост в использовании и подробно прокомментирован, поэтому его перенос должен быть довольно простой задачей.

Отказ от ответственности: я автор MDAG:) .

user609063 04 окт '13 в 11:53 2013-10-04 11:53 · Answer 3 · 2013-10-04 11:53

Я нашел несколько отличных библиотек, которые позволяют строить онлайн из несортированных данных, хотя они не основаны на DAWG:

кедр - очень быстрый двойной массив
marisa-trie - очень компактная библиотека соответствия строк

2

Источник

user609063 04 окт '13 в 11:53