Структура данных для поддержки больших наборов псевдонимов для быстрого поиска

Question

У меня есть список (> 50 000 слов). Каждое слово в списке имеет набор связанных псевдонимов (а). Каждое слово, в среднем, имеет 5 псевдонимов.

Я получаю входную строку, усредняющую до 6 слов. Я должен сделать:

// Pseudocode 
foreach word in input_string 
    if word == x or word in alias(x) // x is a word in the list 
     tag (word, x) // Tag word with x 
    else 
     tag (word, 0) 
end 

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

Answer 1

associative structure с поиском O (n/k) или O (log n) будет уместным.

Примеры включают в себя:

• hashtables; или
• tries