用于搜索的同义词数据结构

Question

我正在寻找一种数据结构来保存同义词。我想在存储桶中保留同义词，例如 "North America"、"USA"、"United States".

搜索内容可以用 "North America"、"USA"、"United States" 中的任何一个标记。

For example, 
Content_1 is tagged "USA"
Content_2 is tagged "North America"
Content_3 is tagged "United States"

如果用户搜索 "USA"，搜索结果应该 return 所有三个内容，而不仅仅是 Content_1。为此，我必须获取 USA 的所有同义词，然后进行搜索。

如何在查找其中一个同义词并获取所有其他同义词的地方存储同义词？

一种方法是通过如下所示的 HashMap

USA -> North America,United States
United States -> USA, North America
North America -> USA,United States

这个看起来不太好。请推荐一个好的数据结构来存储同义词。

谢谢。

Answer 1

Access is O(1). But building a data structure looks like generating duplicate items. A better data structure where only one entry is stored.

您可以使用两种数据结构。一个用于存储它们，一个用于查找。一个向量的向量，包含一个词的所有同义词。以及指向容器的哈希图，其中包含 O(1) 查找的所有同义词。

因此您可以将同义词存储在这样的数据结构中（字符串列表）：

{{"USA","North America","United States"},{"Tiny","Small"},{"Great","Good"}}

然后你会得到一个 hashmap，所以如果你搜索 "USA" 你会得到第一个列表。如果您搜索 "Small"，您将获得第二个列表。

"USA"->{"USA","North America","United States"}
"Small"->{"Small","Tiny"}

哈希图中的数据只是对您保存在其他数据结构中的同义词列表的引用。

Answer 2

构建一个数据类型 Synonym，它有一个 Set<String> 包含一个词的所有同义词（在您的例子中是 "North America"、"USA"、"United States"）。然后用Map<String, Synonym>映射你所有的单词到相应的Synonym.

synonym data structure for searching