构建字典的数据结构

4
我正在寻求一些高层次的想法/思路,帮助我构建一个字典数据结构的系统。我有一个旧的“产品(药物)搜索系统”,它非常缓慢且复杂。我们需要完全重新设计这个系统,以实现高效和可维护的解决方案。
为了简化问题,我以“字典”为例(我希望我的新系统表现得像字典一样):
1. 我应该能够存储单词、描述和几个同义词(等效通用药品);
2. 单词不应重复;
3. 同义词也应是单词的实例(它应该具有单词、描述和同义词的行为);
4. 更快的搜索;
使用案例:
1. 搜索单词时,显示其含义和同义词;
2. 更快的搜索;
3. 应该可以删除同义词;
4. 添加新单词时,应能够将其添加到任何现有单词的同义词中。
我创建了下面所示的数据结构:
Class Word {
    String meaning;
    List<Word> synonyms;
}

为了存储单词,我考虑使用 TreeSet,因为:

TreeSet提供了实现Set接口的方法,并使用树进行存储。对象按升序排序存储。访问和检索时间很快,这使得 TreeSet 成为存储大量需要快速查找的排序信息的绝佳选择。

或者我可以使用 HashMap,其中单词和同义词实例的哈希码相等,这可以加快检索速度。
仍然存在很多挑战:
  1. 每当添加新单词时,如何与其同义词建立链接?

  2. 在单词数量巨大时,查找会变慢。

  3. 编辑单词也应该反映出同义词,反之亦然。

如果您有任何想法/输入/技巧,将非常感谢。

3
我已经在现实世界中建立了这样一个系统。单词并不是唯一的。同样的拼写可以有多种形式(动词、名词、形容词等)或者相同的形式(名词),但具有多个独立的意义,每个意义都有自己的同义词集合。单词可能会有替代的拼写。在实践中,您需要多个层次:一个用于纯拼写,一个用于单词类型,一个用于特定词义。在最底层,您可以添加一些关注点(例如链接到同义词)。 - beerbajay
你想如何搜索一个单词?如果你不关心顺序,为什么要使用TreeSet而不是HashSet?为什么同义词也需要成为一个Word,因为根据定义它们与父Word共享其meaning - Philipp Reichart
更新了带有用例的问题,并且TreeSet应该比HashSet具有更快的检索速度。 - Satheesh Cheveri
我主要是在寻找一些通用的想法(不涉及代码),这些想法可能会帮助我构建高效的系统。评论、意见、链接和参考资料是我所追求的。一旦我完成架构设计,我会在这里整理我的发现。 - Satheesh Cheveri
2个回答

2
您可以使用Trie来存储字典中的所有单词。为每个单词(节点)添加一个同义词列表。

2
针对单词搜索和自动完成需求,Trie是一个快速的替代方案。请查看Java实现

在计算机科学中,trie(发音为“try”)又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。

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)。

1
Trie 很好,但我正在寻找同一节点(单词)在不同级别引用的情况(与树的概念相反)- 我担心这会变得太混乱。 - Satheesh Cheveri
我同意你的观点,我应该能够扩展Trie算法以满足我的需求(存储同义词)。 - Satheesh Cheveri
1
是的,这就是我想要寻找的东西...我认为为两个不同的需求寻找一个解决方案不会导致简单的实现。如果您可以将“同义词”列表与“单词”对象分离,那么事情会变得不那么混乱。 - harsh

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接