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

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

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

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

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

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

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

11.12.2008 01:54:52
Вы предполагаете, что нет сетевого подключения?
Milhous 12.12.2008 15:01:36
@Milhous, теперь мне интересно знать, что вы собираетесь предложить, возможно с сетевым подключением ...
paxdiablo 13.12.2008 11:31:21
6 ОТВЕТОВ
РЕШЕНИЕ

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

3
11.12.2008 02:05:58
Я тоже собирался предложить фильтр Блума, но, учитывая его цели, я не думаю, что фильтр Блума сработает. Фильтры Блума не дадут окончательного ответа «да / нет», если в списке есть слово, и не позволят создать соседство.
mipadi 12.12.2008 15:04:33
Фильтр Блума ответит окончательно «нет», если слова нет в списке. Да, требование соседства было добавлено позже :)
Mike Scott 12.12.2008 16:00:20

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

1
11.12.2008 02:14:58

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

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

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

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, когда память была гораздо более скудной, чем сейчас.

8
11.12.2008 02:26:03
+1 - спасибо, что поделились умным алгоритмом. Кстати, тогда надежность моей памяти более чем компенсировала дефицит .... :-)
Adam Liss 11.12.2008 02:35:45

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

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

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

Павел.

6
11.12.2008 03:35:29

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

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

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

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

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

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

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

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

1
11.12.2008 04:17:01

Связанные с постом Павла:

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

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

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

1
12.12.2008 14:58:20