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

Question

Есть ли что-нибудь лучше, чем Три для этой ситуации?

• Хранение списка из ~ 100k английских слов
• Необходимо использовать минимальную память
• Поиски должны быть разумными, но не должны быть молниеносными

Я работаю с Java, поэтому моей первой попыткой было просто использовать Set . Тем не менее, я нацеливаюсь на мобильное устройство и уже недостаточно памяти. Поскольку многие английские слова имеют общие префиксы, три кажется неплохой ставкой для экономии памяти - кто-нибудь знает другие хорошие варианты?

РЕДАКТИРОВАТЬ - Подробнее - Структура данных будет использоваться для двух операций

• Ответ: Есть ли какое-нибудь слово XYZ в списке?
• Генерация окрестности слов вокруг XYZ с одной буквой, отличной

Спасибо за хорошие предложения

Answer 1

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

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

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

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

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

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

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

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

Answer 2

Патриция может быть более подходящей:

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

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

Paul.

Answer 3

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

Answer 4

Относится к посту Павла:

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

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

Патриция Поиск в C

Answer 5

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

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

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

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

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

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

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

РЕДАКТИРОВАТЬ: Похоже, я заново изобрел колесо. ; -)

Answer 6

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