В настоящее время я храню список слов (около 120 000) в HashSet с целью использования в качестве списка для проверки введенных слов, чтобы проверить, правильно ли они написаны, и просто вернуть да или нет.
Мне было интересно, есть ли способ сделать это, который занимает меньше памяти. В настоящее время 120 000 слов составляют около 12 мг, фактический файл, из которого считываются слова, составляет около 900 кб.
Любые предложения?
Заранее спасибо
Проверьте фильтры цветения или хеширование кукушки. Фильтр цветка или хеширование кукушки?
Я не уверен, что это ответ на ваш вопрос, но стоит изучить эти альтернативы. цветные фильтры в основном используются для использования в случаях проверки орфографии.
Вы можете использовать дерево префикса или trie: http://en.wikipedia.org/wiki/Trie
HashSet, вероятно, не является правильной структурой для этого. Вместо этого используйте Trie.
Это может быть немного поздно, но с помощью Google вы можете легко найти расследование DAWG и код C, который я опубликовал некоторое время назад.
http://www.pathcom.com/~vadco/dawg.html
TWL06 - 178,691 слова - вписывается в 494 676 байт
Недостатком структуры compress-shared- node является то, что она не работает как хэш-функция для слов в вашем списке. То есть, он скажет вам, существует ли слово, но оно не вернет индекс связанным данным для слова, которое существует.
Если вам нужна идеальная и полная хэш-функция, в структуре размера кэша процессора вам придется читать, понимать и изменять структуру данных, называемую ADTDAWG. Он будет немного больше, чем традиционный DAWG, но он быстрее и полезнее.
http://www.pathcom.com/~vadco/adtdawg.html
Все самое лучшее,
Джон Паул Адамовский
12 МБ для хранения 120 000 слов составляет около 100 байт на каждое слово. Вероятно, по меньшей мере 32 байта, это служебные данные String. Если слова усредняют 10 букв, и они хранятся как 2-байтовые символы, на которые приходится еще 20 байт. Тогда есть ссылка на каждую строку в вашем HashSet, которая, вероятно, еще 4 байта. Остальные 44 байта, вероятно, являются служебными данными HashSet и индексацией, или что-то, что я не рассматривал выше.
Самое легкое, что нужно сделать, это накладные расходы самих объектов String, которые могут занимать гораздо больше памяти, чем требуется для хранения фактических символьных данных. Таким образом, ваш основной подход заключается в разработке пользовательского представления, которое позволяет избежать хранения отдельного объекта для каждой строки. В процессе этого вы также можете избавиться от накладных расходов HashSet, так как все, что вам действительно нужно, это простой поиск слов, который может быть выполнен простым двоичным поиском в массиве, который будет частью вашей пользовательской реализации.
Вы можете создать свою собственную реализацию как массив типа int с одним элементом для каждого слова. Каждый из этих элементов int будет разбит на подполя, которые содержат длину и смещение, которое указывает на отдельный массив поддержки типа char. Поместите оба из них в класс, который ими управляет, и который поддерживает общедоступные методы, позволяющие извлекать и/или преобразовывать ваши данные и отдельные символы с учетом строкового индекса и необязательного символьного индекса и выполнять простые поиски в списке слов которые необходимы для вашей проверки орфографии.
Если у вас есть не более 16777216 символов базовых строковых данных (например, 120 000 строк раз средней длины 10 символов = 1,2 миллиона символов), вы можете взять младшие 24 бита каждого int и сохранить начальное смещение каждой строки в ваш массив подкачки из данных char, и возьмите 8-й бит 8-го порядка каждого int и сохраните размер соответствующей строки там.
Ваши данные char будут иметь ваши прежние строки, переполненные без каких-либо разделителей, полностью полагаясь на массив int, чтобы знать, где каждая строка начинается и заканчивается.
Взяв вышеуказанный подход, ваши 120 000 слов (в среднем по 10 букв) потребуют около 2,400,000 байт данных массива поддержки и 480 000 байтов данных с индексом целого индекса (120 000 x 4 байта), в общей сложности 2 880 000 байт, что составляет около 75 процентов экономии за текущую сумму в 12 МБ, о которой вы сообщали выше.
Слова в массивах будут отсортированы в алфавитном порядке, и ваш процесс поиска может быть простым двоичным поиском в массиве int (получение соответствующих слов из массива char для каждого теста), что должно быть очень эффективным.
Если ваши слова являются полностью ASCII-данными, вы можете сохранить дополнительные 1200 000 байт, сохранив данные резервного копирования как байты, а не как символы.
Это может усложниться, если вам нужно изменить эти строки. По-видимому, в вашем случае (проверка орфографии) вам не нужно (если вы не хотите поддерживать добавления пользователей в список, что было бы нечасто в любом случае, и поэтому переписывать данные и индексы char для добавления или удаления слова могут быть приемлемыми).
Одним из способов сохранения памяти для сохранения памяти является использование дерева оснований. Это лучше, чем trie, поскольку префиксы не сохраняются избыточно.
Поскольку ваш словарь исправлен, другой способ - создать для него идеальную хеш-функцию. У вашего набора хэшей не нужны ковши (и связанные с ними служебные данные), поскольку не может быть столкновений. Для этой цели можно использовать любую реализацию хэш-таблицы/хеш-набора, которая использует открытую адресацию (например, google collection ImmutableSet).
Проблема заключается в следующем: хранение такого огромного количества слов в HashSet для проверки орфографии не является хорошей идеей:
Вы можете либо использовать проверку орфографии (пример: http://softcorporation.com/products/spellcheck/), либо вы можете создать "авто-wordcompletion" с помощью дерево префикса (описание: http://en.wikipedia.org/wiki/Trie).
В этом дизайне нет способа уменьшить использование памяти.
Вы также можете попробовать Radix Tree (Wiki, Реализация). Это нечто вроде trie, но с большей эффективностью памяти.