Структура данных для хранения и извлечения соответствия между одним действием и несколькими глаголами в Java

Question

Какой тип структуры данных я должен использовать для построения словарной структуры, в которой один тип действия сопоставлен с несколькими глаголами?

Пример: Action1 будет сопоставлен с verb1, verb2, verb5 и Action2 будет сопоставлен с глаголом 3, глаголом 4.

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

Кроме того, мне нужно найти глагол, введенный пользователем в списке глаголов, определенном и отображенном в соответствующем имени действия:

Пример: если пользовательский ввод - глагол 4, система должна вернуть Action2

Answer 1

Если вам нужен точный словарь, подобный структуре данных, выберите Дерево префиксов или Trie . Если имеется n Количество ключей и m - это длина ключа, то Trie имеет временную сложность O (м) .

Три предпочтительнее, если в ваших глаголах есть какой-то лексикографический порядок или подобные префиксы.

                     t
                   /   \
                te     ta
               /  \      \
             tea  ten    tar

Leetcode: Дерево префиксов

Википедия: Три

Если это не так, тогда HashMap является подходящим вариантом, как описано в других ответах.

Answer 2

Структура данных зависит от отношений между глаголами и действиями.Каковы ваши отношения между глаголами и действием?1-N NN или N-1?

Answer 3

Это звучит как Карта действия и набор глаголов

Map<String, Set<String>> dictionary = new HashMap<>();

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

Set<String> action1Verb = new HashSet<>();
action1Verb.add("verb1");
action1Verb.add("verb2");
....
dictionary.put(action1, action1Verb);
dictionary.put(action2, action2Verb);

Для поиска действия по глаголам:

String action = dictionary.keySet().stream()
          .filter(key -> dictionary.get(key).contains("verb"))
          .findFirst()
          .orElse(null);

Если вас не волнует использование памяти, я предлагаю вам использовать две карты для хранения:

Map<String, Set<String>> dictionary to store action -> set of verbs
Map<String, String> verbMap to store verb -> action

В этом случае действие поиска по глаголу происходит очень быстро, например:

String action = verbMap.get("verb")

Answer 4

Я думаю, что HashMap<String, Action> подойдет.

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

Вотнекоторые примеры сопоставлений:

verb1 -> Action1
verb2 -> Action1
verb5 -> Action1
verb3 -> Action2
verb4 -> Action2

Таким образом, вы можете убедиться, что ни один глагол не ссылается на два действия, потому что ключи уникальны.

Answer 5

Вы можете использовать HashMap для этого, ключом будет действие, а значением будет список глаголов:

 Map<String,List<String>> actionVerbMap=new HashMap<>();