data-structures - 用于维护大量别名以便快速查找的数据结构

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

具有 O(n/k) 或 O(log n) 查找的关联结构将是合适的。

示例包括：

• 哈希表；或者
• 尝试