Компактная структура данных для хранения списка слов?

Вам все равно придется поддерживать саму древовидную структуру с помощью Trie. Кодирование Хаффмана алфавит или N-буквы (для распространенных форм, таких как «ция», «un», «ing») могут воспользоваться преимуществом частоты появления в вашем словаре и сжать запись до битов.

Что делаешь? Если это проверка орфографии, вы можете использовать фильтр цветения - см. Этот код ката.

Одна из структур, которые я видел для минимизации пространства в орфографическом словаре, заключалась в кодировании каждого слова как:

• количество символов (байт), общих с последним; а также
• новый финал.

Итак, список слов

HERE            would encode as    THIS
sanctimonious                      0,sanctimonious
sanction                           6,on
sanguine                           3,guine
trivial                            0,trivial

Вы экономите 7 байтов прямо там (19%), я подозреваю, что экономия будет аналогичной для словаря на 20000 слов только из-за минимальных расстояний между (общими префиксами) соседних слов.

Например, я запустил тестовую программу по отсортированному словарю и вычислил старое пространство для хранения как длину слова плюс один (для терминатора), а новое пространство для хранения - как единицу для общей длины, длину необычного суффикса и единицу для терминатора. Вот заключительная часть этой тестовой программы, показывающая, что вы можете более 50%:

zwiebacks   -> zygote      common=        old=1044662 new=469762 55.0%
zygote      -> zygotes     common=zygote  old=1044670 new=469765 55.0%
zygotes     -> zygotic     common=zygot   old=1044678 new=469769 55.0%
zygotic     -> zymase      common=zy      old=1044685 new=469775 55.0%
zymase      -> zymogenic   common=zym     old=1044695 new=469783 55.0%
zymogenic   -> zymology    common=zymo    old=1044704 new=469789 55.0%
zymology    -> zymolysis   common=zymol   old=1044714 new=469795 55.0%
zymolysis   -> zymoplastic common=zymo    old=1044726 new=469804 55.0%
zymoplastic -> zymoscope   common=zymo    old=1044736 new=469811 55.0%
zymoscope   -> zymurgy     common=zym     old=1044744 new=469817 55.0%
zymurgy     -> zyzzyva     common=zy      old=1044752 new=469824 55.0%
zyzzyva     -> zyzzyvas    common=zyzzyva old=1044761 new=469827 55.0%

Для ускорения поиска в памяти была таблица из 26 записей, в которой хранились начальные смещения для слов, начинающихся с a, b, c, ..., z. Слова в этих смещениях всегда имели 0 в качестве первого байта, поскольку у них не было букв, общих с предыдущим словом.

Похоже, что это своего рода дерево, но без указателей, которые, несомненно, будут занимать много места, если с каждым символом в дереве будет связан 4-байтовый указатель.

Имейте в виду, это было из моих дней CP / M, когда памяти было гораздо меньше, чем сейчас.

Три Патрисии могут быть более подходящими:

http://en.wikipedia.org/wiki/Patricia_tree

Моя (нечеткая) память подсказывает мне, что некоторые из первых полнотекстовых поисковых систем использовали ...

Павел.

Совершенно дикая идея ... (т.е. скорее всего очень неправильная)

Как насчет сохранения слов в виде дерева всех возможных комбинаций букв?

Тогда каждое «слово» стоит только один символ и два указателя (один на символ и один на терминатор). Таким образом, чем больше у них общих букв, тем меньше стоимость каждого слова.

      . .
     / /
    r-p-s-.
   /\\
  a  \s-.
 /    t-.
c      \
        s-.

автомобиль карп карпы легковые автомобили тележка телеги

Таким образом, для 9 символов и 14 указателей мы получаем 6 «слов» из 25 букв.

Поиск будет быстрым (поиск указателя вместо сравнения символов), и вы могли бы сделать некоторые оптимизации, чтобы сэкономить еще больше места ...?

Обновлено: Похоже, я заново изобрел колесо. ;-)

Относится к сообщению Пола:

Есть ли причина, по которой вы не можете рассматривать Trie в вашем случае? Если это просто проблема реализации, вот краткая реализация вставки и поиска Patricia trie на C (из NIST):

Патрисия Вставка в C

Патрисия ищет в C