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

Question

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

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

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

2

performance dictionary data-structures space-efficiency

Источник

user503760 23 ноя '10 в 22:14

3 ответа

Другие вопросы по тегам performance dictionary data-structures space-efficiency

user27009 13 дек '10 в 13:58 2010-12-13 13:58 · Answer 1 · 2010-12-13 13:58

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

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

user624214 20 мар '11 в 13:37 2011-03-20 13:37 · Answer 2 · 2011-03-20 13:37

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

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

user2104560 11 сен '14 в 05:54 2014-09-11 05:54 · Answer 3 · 2014-09-11 05:54

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

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

Читать все слова, сортировать их, вставлять в какой-либо файл построчно и для каждого слова предварительно вычислять skipBytes, - количество байтов перед этим словом. Вычисление skipBytes тривиально. псевдокод skipBytes[0]=words[0].bytesLen; for i=1 to n skipBytes[i]=skipBytes[i-1]+words[i].getBytesLength
Когда приложение запускается, прочитайте 500k skipBytes в некоторый массив int. Это намного меньше, чем 500K строк)
Поиск слова в 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) не сильно изменится, если он выполняется не внутри цикла)