java - 为字典构建数据结构

Question

我正在寻找一些高层次的想法/想法来帮助我为字典构建数据结构。我有一个遗留的“产品(药物)搜索系统”，它本质上非常缓慢和复杂。我们需要完全重新设计系统以获得高效且可维护的解决方案。

为了简化问题，我以“字典”为例(我希望我的新系统表现得像字典)

1. 我应该能够存储单词、描述和一些同义词(等效的泛型)，
2. 单词不能重复
3. Synonyms 也将是 Word 的实例(它应该携带单词、描述和同义词的行为)。
4. 更快的搜索

用例

1. 搜索某个词时，会显示其含义和同义词
2. 更快的搜索
3. 应该可以删除同义词
4. 添加新词，应该能够添加到任何现有词的同义词

我创建了如下所示的数据结构

Class Word {
    String meaning;
    List<Word> synonyms;
}

要存储单词，我正在考虑使用 TreeSet

因为

TreeSet provides an implementation of the Set interface that uses a tree for storage. Objects are stored in sorted, ascending order. Access and retrieval times are quite fast, which makes TreeSet an excellent choice when storing large amounts of sorted information that must be found quickly.

或者我可以使用HashMap，其中单词和同义词单词实例的哈希码相等，可以实现更快的检索。

我仍然可以看到很多挑战

1. 每当添加新词时如何与其同义词链接

2. 单词量大的时候查找会很慢

3. 编辑词也应该反射(reflect)同义词，反之亦然

任何想法/输入/技巧都将受到高度重视

Answer 1

用于单词搜索和单词完成要求 Trie将是一个快速的选择。看看Java implementations :

In computer science, a trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings.

http://pathakalgo.blogspot.in/2012/11/trie-data-structure-implementation-in.html

https://www.google.co.in/search?q=Trie&client=ubuntu&channel=cs&oq=Trie&aqs=chrome..69i57j69i60l2.856j0j1&sourceid=chrome&ie=UTF-8

对于同义词链接，你可以维护一个Map<String, LinkedList<String>> .使用 Trie 找到单词后，获取关联的系统同义词将是 O(1)。