Временная и пространственная реализация словаря

Question

Я пытаюсь создать эффективную в пространстве и времени реализацию словаря общих символов в Java.

Словарь, вместо того, чтобы быть заказанным из A-Z, каким-то образом сгруппирует все слова, содержащие буквы «A», «B» и т. Д. Приложение должно иметь возможность удалять все слова, содержащие любые буквы, которые вводит пользователь. Поэтому, если пользователь вводит «L», все слова, содержащие «L», удаляются.

Я создал:

Установить словарь - хранит все слова.

Map > - сопоставляет символы A с Z, каждый из которых имеет набор, содержащий все слова из словаря, которые содержат эту букву.

Пример:

dictionary {"AAB", "ABB", "BBC", "BBA", "CBB"}

Карта:

A - "AAB", "ABB", "BBA" 

B - "AAB", "ABB", "BBC", "BBA", "CBB"

C - "BBC", "CBB"

Если пользователь выбирает «A», набор A удаляется из словаря, и карта перестраивается, ожидая, когда пользователь удалит еще одну букву.

Моя проблема в том, что это приведет к огромному дублированию данных и неэффективности. Я не могу придумать другой способ эффективно реализовать это. Мне намекают, что деревья могут быть способом решения этой проблемы, но я не понимаю, как их реализация будет более эффективной как во времени, так и в пространстве.

Большое спасибо за вашу помощь.

Answer 1

Звучит так, как будто вы должны использовать три .Это довольно простая древовидная структура, подробности и примеры реализации можно найти в википедии:

• http://en.wikipedia.org/wiki/Trie
• http://en.wikipedia.org/wiki/Radix_tree

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

Кроме того, я бы подумал, нужно ли вам на самом делеудалите все элементы из вашей словарной структуры, которые не соответствуют заданному префиксу.С помощью попыток вы можете исключить недопустимые слова, просто «глядя» на соответствующее поддерево и рассматривая только эти записи.

надеюсь, что это помогло