当前位置: 首页 > 知识库问答 >
问题:

给定两个文件,在file1中查找单词,但在file2中查找单词

谭晓博
2023-03-14

给定两个文件会产生一个算法/程序来查找文件1中的单词,而不是文件2中的单词。请注意,文件中的单词不是按顺序排列的。

这是我的思考过程:

  • 步骤1:读取文件2的单词并将其添加到哈希集

如果两个文件中的字数都只有100或1000个,那么这个算法就可以正常工作
但是,如果两个文件都很大(数十亿字),那么此解决方案将无法工作,因此我提出了一个改进的解决方案:

  • 步骤1:逐字阅读文件2,并按字母顺序对单词进行排序为单词分配一个存储桶,对所有以“a”开头的单词说一个存储桶

所以地图看起来像['a':{'sample','and'…}]。这将帮助我在log(n)时间复杂度内搜索bucket,然后在log(n)中查找单词是否包含在排序列表中。

  • 步骤2:读取file1并检查file1中的一个单词是否没有bucket或不在bucket中包含的列表中

这个解决方案会奏效,但我相信还有改进的余地
如何进一步改进此解决方案

共有1个答案

严修德
2023-03-14

一个可能的解决方案是使用一些外部排序来排序两个文件,然后并行迭代它们以找到一个只出现在文件1中的单词:

伪代码(排序后):

iter1 = 0
iter2 = 0
while iter1 < file1.length:
    if file1[iter1] == file2[iter2]:
         iter1 = iter1 + 1
         iter2 = iter2 + 1
    else if file1[iter1] > file2[iter2]:
         iter2 = iter2 + 1
    else: //we know for sure the item is only in file1
         iter1 = iter1 + 1
         yield file1[iter1]

此解决方案占用O(nlogn)时间,并且只需要很少的空间(外部排序所需的空间量)。

还要注意的是,该问题是元素差异性问题的一个变体,因此在使用基于比较的算法时,它很可能具有Omega(nl0gn)的下限,或者使用散列的Omega(n)时间空间。

 类似资料:
  • 问题内容: 我试图加快我的项目以计算单词频率的速度。我有360多个文本文件,我需要获取单词的总数以及另一个单词列表中每个单词出现的次数。我知道如何使用单个文本文件执行此操作。 要获得“通货膨胀”,“工作”,“产出”个体的频率过于繁琐。我可以将这些单词放入列表中并同时查找列表中所有单词的出现频率吗?基本上,这与Python。 示例:代替此: 我想这样做(我知道这不是真实的代码,这是我在寻求帮助的内容

  • 问题内容: 我正在尝试查找文件中出现的单词数。我有一个文本文件(),文件内容如下: 我期望的结果是: 我使用的代码是: 我得到的结果是: 谁能帮帮我吗?提前致谢 。 问题答案: 使用计数器的方法。例: 输出:

  • 问题内容: 如何使用Java在多个文本文件中查找和替换单词? 这是我一次做的方法… 问题答案: 从Commons IO使用:

  • 问题内容: 我在MySql DB的一个表中有一个文本列。我想获取在文本列中具有特定单词的所有记录。例如: 在这种情况下,当搜索“ cto”时,我希望查询返回记录1,2,3,4,而不是5。 有任何想法吗? ps我希望它不区分大小写 问题答案: 您可能希望根据全文索引使用全文索引。否则,您可以使用REGEXP来指定正则表达式来搜索单词。您应该看到此问题(和答案),以了解如何使用REGEXP查找单词。

  • 问题内容: 我需要在HTML源代码中找到一个单词。我还需要计算发生的次数。我正在尝试使用正则表达式。但它说找到0个匹配项。 我正在使用正则表达式,因为我认为这是最好的方法。如果有更好的方法,请告诉我。 我需要在HTML源代码中找到单词“ hsw.ads”的出现。 我已采取以下步骤。 但是计数是0; 请让我知道您的解决方案。 谢谢。帮助寻求者 问题答案: 您应该尝试一下。 在字符串中传递要搜索的单词

  • 问题内容: 我有一个文件(更具体地说是一个log4j配置文件),我希望能够读取该文件并在代码中挑选出某些行并替换它们。例如,在文件中,有一串文本,指示文件的存储目录或记录器的级别。我希望能够替换这些文本字符串而无需读入文件,将其写入另一个文件以及删除原始文件。有没有一种使用Java来查找和替换文件中文本的更有效方法? 这是我尝试使用的文本文件的示例: 我希望能够读取文件并将’DEBUG’替换为另一