Реализация Android DAWG
В моем приложении мне нужно работать со словарем, в котором много слов (110 000), поэтому я решил использовать trie, но загрузка trie каждый раз стоила 9 секунд. И это очень много даже для моего эмулятора. Недавно я читал о DAWG(прямая графическая схема Acyclinc Word) или вики минимального ациклинового конечного автомата DAWG, что повлияет на производительность нагрузки, но я не могу найти хорошее объяснение алгоритма создания DAWG или алгоритма Trie to DAWG. Также я не могу найти ни одного примера, написанного на Java, поэтому я прошу вас о помощи. заранее спасибо
2 ответа
Это может быть слишком поздно для ваших нужд, но ради других, которые могут оказаться здесь, взглянуть на MDAG, созданный и поддерживаемый вами по-настоящему:) .
В настоящее время я читаю книгу Хопкрофта "Введение в теорию автоматов", в которой объясняется множество автоматных алгоритмов, включая минимизацию автоматов (в главе 4.4.3).
ссылка на эту книгу Джона Хопкофта "Введение в теорию автоматов"
Также есть JFLAP, который может минимизировать состояние конечного автомата.