java - 二分查找具有不同字长的文件

Question

我正在制作一个粗略的 Java 拼写检查器，它需要一篇文章和一个预先排序的字典文件。文章的单词长度各不相同，因此我尝试制作一个堆栈来接收文件给出的单词。

不幸的是，这不起作用，因为堆栈空间不足(即使使用缩短的字典文件)，并且由于性能问题，我决定直接从文本文件中读取。

问题是该文件没有相同长度的单词。由于单词的长度各不相同，因此我不能也不应该期望单个单词的长度对于确定字典文件中有多少单词以及该文件有多大很有用。

正因为如此，我陷入了困境。我需要对该文件执行二进制搜索以使拼写检查程序正常工作。但是，如果没有明确的方法将文件视为数组，特别是当数组太大而无法放入程序内存时，我无法执行二分搜索。

我应该做什么？

Answer 1

牛津英语词典建议大约有 ~250,000 words您需要在词典中考虑这一点(不考虑仅在高度特定领域中使用的单词)。这对您来说是重要的设计信息。

我看到一些解决方案:

1) 只需使用 HashSet<>

理论上，您可以使用HashSet<>对于这个数量的元素(此 SO post 讨论了 HashSet 的理论限制以及其他详细信息)。

但是，这会带来(正如您所观察到的)一些问题:

• 将其读入 RAM 需要时间(在每次应用程序启动时)

• 它会占用内存

当然，您可以增加 JRE 的堆大小，但这有一个自然限制(@StvnBrkddll 链接了 SO post 在评论中完美地描述了这一点)

2) 使用数据库

我会考虑将有效单词存储在(关系)数据库中:

• 您不需要在应用程序启动时加载所有内容

• 它对 RAM 的影响不像选项 (1) 那样重

• 如果您想更改应用程序以向用户建议没有拼写错误的类似单词(例如，如果您使用 PostgreSQL，则可以实现 pg_trgm )，它为您提供了更多选择

但它有一些缺点:

• 您提到您的应用程序很简单:拥有数据库系统会增加复杂性