1

我有一个超过一百万字的文件，每行一个字。我正在尝试编写代码，如果给我一个单词，我需要找出该单词是否存在于文件中。这里的问题是，每个单词都必须检查26^(word.length()-1)多次。因此，遍历文件中的每个单词并不是一个好的解决方案。我尝试在网上查找算法，但还没有找到任何明显的答案。

编辑 我已经考虑过 aHashMap和Trie. 这里的实际问题是说我有这个词abc。现在，我的任务是在 word 中添加、删除或替换一个字母abc以创建单词 X，然后检查 X 是否在文件中。因此，对于哪种解决方案可能是更好的方法感到困惑。

4

7 回答 7

8

您可以从文件中的单词构建一个trie。这将比 Hashset 使用更少的内存，并允许您检查 O（单词中的字符数）中单词的存在。如果不关心内存，当然可以使用 Hashset（因为它内置了它也少得多的努力）。

于 2012-05-02T17:49:37.197 回答
3

将单词存储在内存中的 HashSet 中，您将进行 O(1) 次查找。

于 2012-05-02T17:50:39.173 回答
1

假设您的单词是“cad”，并且您正在寻找编辑距离为 1 内的所有单词。

在这种情况下，您可以执行以下操作。

1）将字典单词存储在HashMap中。2）生成编辑距离为1到“cad”的所有单词组合。3) 对于这些单词中的每一个，测试该单词是否存在于 HashMap 中。

您的搜索应该匹配“爸爸”、“猫”、“汽车”、“小伙子”等词。

于 2012-05-02T18:11:26.047 回答
0

当您在文件中读取包含单词的文件时，我将构建一个哈希表。您应该能够检查一个单词是否在恒定时间内出现。

于 2012-05-02T17:50:28.850 回答
0

HashMap 是要走的路。只需将所有单词存储在 HashMap 中，然后查找地图以查看您的单词是否存在。当然，这仅在您想要多次查找时才有用。

更实用的解决方案是将 HashMap 写入磁盘并在下次运行应用程序时将其加载到内存中。

于 2012-05-02T17:53:34.153 回答
0

tabla hast 是更快的方法

FileInputStream inputStream = new FileInputStream("input.txt");
InputStreamReader streamReader = new InputStreamReader(inputStream, "UTF-8");
BufferedReader in = new BufferedReader(streamReader);
Map<String, Integer> map = new HashMap<String, Integer>();
for (String s; (s = in.readLine()) != null;) {
   ...
}
于 2012-05-02T18:01:08.557 回答
0

另一种解决方案是使用Bloom Filter。一种非常快速且节省空间的数据结构，用于检查元素是否是集合的成员。缺点是它是一种概率数据结构，这意味着可能出现误报。

它通过具有 m 位的数组来工作。当向过滤器添加一个词时，该词被馈送到 k 个不同的散列函数中，在这些散列计算的位置处将位设置为 1。查询过滤器时，将单词提供给相同的散列并检查这些位是否设置在这些位置。如果这些位中的任何一个为 0，则可以确定该单词在集合中不存在，如果全部为 1，则需要进行查找，因为在将其他单词散列到相同位置时，这些位可能已设置。

于 2012-05-02T18:20:29.727 回答