我有一个大约10MB的文本文件，其中包含特定语言的几乎所有词典，每个单词都是以新行分隔的。
我想进行快速查找来确定一个单词是否存在于文件中 - 有什么最快的方法可以做到这一点而不需要循环遍历每一行？
它已经排序过了，我可以做所有预处理工作。
我考虑过进行某种二进制搜索，但是我不知道该如何做，因为我的每一行不是固定字节数（因此我不知道在哪里跳转流）。令人惊讶的是，我找不到一个可以为我执行固定宽度操作的工具。
有什么建议吗？ 谢谢！
在字典文本文件中快速查找单词是否存在
3
- Steve
3
我猜你不能只是把文件加载到内存中并一直保留在那里吗？10 MB 并不算太大... - Jim Mischel
如果您可以将文件加载到内存中，则通用的“Dictionary”类将起作用。或者，如果您正在使用Silverlight 4，则可以使用“HashSet”。 - Jim Mischel
这些都是可能性，当然，如果我不想承受将所有内容加载到内存中所需的时间成本呢？而且，这是一台移动设备。 - Steve
2个回答
6
我建议从词典中构建一个Trie数据结构。这可以非常快速地进行查找，以确定一个单词是否存在于其中。
- Anon.
10
@Anon - 没有。我很乐意预处理它，但问题会分解为：
- 如果我做一个trie，我必须将数据结构加载和创建到内存中 - 这需要时间，对吧？
- 类似于＃1 - 在每次查找时执行＃1是否比在文件中跳来跳去更快？（老实说我不知道答案，因此寻求指导）
如果我使用 trie，我会将其序列化并反序列化到磁盘上（尽管我对 trie 不够了解）。但是将其保留在内存中并不是很可行 - 我需要应用程序快速启动（因此不会将 trie 作为加载时间的一部分），并且偶尔，一旦用户已经执行操作，我希望进行单词查找。我对 trie 的了解还不足以真正知道加载所有内容需要多快... =/ - Steve
@Steve：你实际上不需要加载它 - 你可以直接从磁盘上运行它，效率还不错（尤其是作为移动设备，它可能配备了适用于随机访问的固态存储设备，而不是旋转金属）。 - Anon.
哇，直接从磁盘上运行听起来很诱人...你能否提供如何实现的进一步信息？ :) - Steve
@Steve：好的。给每个节点分配一个唯一的编号，表示它在文件中的位置 - 节点1是第一个节点，节点2是第二个节点，以此类推。每个节点的大小完全相同，包含26个整数，这些整数指向下一个节点。在查找时，打开根节点，并读取与第一个字符对应的桶中的值。计算新的文件偏移量，打开该节点，并重复此过程，直到通过字符串或找到对0的引用为止，这意味着该字符串不存在。 - Anon.
显示剩余5条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接