Лучший способ хранить и извлекать структуру данных DAWG для быстрой загрузки

Question

У меня есть список слов 500k +, который я загрузил в структуру данных DAWG . Мое приложение для мобильных телефонов. Я, конечно, не хочу повторять все шаги преобразования, чтобы каждый раз загружать этот список слов в DAWG, поскольку потребуется много места для хранения списка слов на телефоне и много времени, чтобы каждый раз загружать его в DAWG. , Итак, я ищу способ сохранить данные в моей DAWG в файле или БД в формате, который одновременно сэкономит пространство и позволит мне быстро загрузить их обратно в структуру данных DAWG.

Я получил одно предложение о том, что я могу хранить каждый узел в БД SQLite, но я не уверен, как именно это будет работать, и если я это сделаю, то как быстро его получить. Я, конечно, не хотел бы запускать много запросов. Будет ли какой-то другой тип хранения лучше? Я также получил предложения о создании сериализованного файла или его сохранении в виде растрового изображения.

Answer 1

Вы можете сделать дамп памяти, просто используя смещения вместо указателей (в терминах Java поместите все узлы в массив и используйте индекс массива для ссылки на узел).

500 тыс. Не похоже на количество, которое было бы проблематичным для современных телефонов, тем более что DAWG уже достаточно эффективна. Если вы отобразите файл, вы сможете работать со структурой данных, даже если она не помещается в памяти.

Answer 2

Вы пытались сократить список слов? Сохраняете ли вы только слово stam, если это возможно, для вашего приложения?

С другой стороны: вам никогда не следует перестраивать структуру данных, потому что список слов постоянен. Попробуйте использовать дамп памяти вроде suggusted. Для загрузки готовой структуры данных в вашу память используйте mmap для файла, сериализацию Java или методики засолки.

Answer 3

Полагаю, вы используете DAWG для быстрого поиска слова в словаре. DAWG имеет O(LEN) сложность поиска.

Много лет назад я разработал приложение J2ME и столкнулся с той же проблемой. Но в то время телефоны определенно не могли предоставить такой объем оперативной памяти, чтобы хранить строки размером 500K +). Я использовал следующее решение:

1. Читать все слова, сортировать их, вставлять в какой-то файл построчно и для каждое слово предварительно вычисляется skipBytes. - количество байтов до этого слово. Вычисление skipBytes тривиально. псевдокод skipBytes[0]=words[0].bytesLen; for i=1 to n skipBytes[i]=skipBytes[i-1]+words[i].getBytesLength
2. Когда приложение запускается, прочитайте 500k skipBytes в некоторый массив int. Это намного меньше, чем строки 500K)
3. Поиск слова в dict - двоичный поиск. Представьте, что вы выполняете его в отсортированном массиве, но вместо array[i] вы делаете что-то вроде RandomAccessFile.read(skipBytes[i]). Google Java Random Access Files мой псевдокод, конечно, неправильный, это просто направление.

Сложность - O(LEN*LOG(N)) = Журнал двоичного поиска и сравнения строк имеет линейную сложность. LOG (500000) ~ 19, LEN ~ средняя длина слова в худшем случае равна 50 (фантастическая верхняя граница), поэтому операция поиска все еще очень быстрая, всего ~ 1000 операций она будет выполнена за микросекунды. Преимущество - небольшое использование памяти.

Следует отметить, что в случае веб-приложения, когда многие пользователи выполняют поиск, LOG(N) становится важным, но если ваше приложение предоставляет сервис только для одного человека, LOG (500000) не сильно меняется, если оно выполняется не внутри петля) * * 1 022