算法将一个输入文件与给定数量的文件相匹配

上周我接受了采访。我在算法轮回中遇到了一个问题。我回答了这个问题，但面试官似乎并不相信。这就是为什么我分享相同。算法将一个输入文件与给定数量的文件相匹配

请告诉我这个问题的任何优化方法，以便它可以帮助我在未来的访谈。

问题： -

有给出，所有文件都是ASCII文本文件20个文本文件，具有比10^9个字节少大小。还有一个输入也给出了，这也是也是一个ASCII文件，比如input.txt。

我们的任务是将输入文件的内容与给定的20个文件进行战略匹配，并打印最接近的匹配文件的名称。输入文件的内容可能只匹配部分

在此先感谢。寻找你的回应。

来源

2013-04-04 devsda

在这种形式下回答是不太可能的。这些文件是真实文本还是任何可打印的ASCII，或基本ASCII或扩展ASCII？结果必须是最佳匹配还是近似值？ – 2013-04-04 19:37:57

我相信有一个用于这个特定目的的系统工具。 'cmp'我相信是命名的。 POSIX兼容SO。 – yeyo 2013-04-04 19:39:23

@Kira事情告诉我，这不是面试官希望的！ – JBentley 2013-04-04 19:40:04

diff的他们并穿过WC -l，或者实现用C Levenshtein distance ++处理每一行的单个字符（或任何更合适的单元condidering受试者域）

来源

2013-04-04 19:41:48 bobah

+1，非常好的答案，但是，使用编辑距离算法有点难以实现（在我看来）。 – yeyo 2013-04-04 19:47:00

@anonymous：没有建设性意见的倒票 - 不好 – bobah 2013-04-08 09:34:39

可以创建某种索引（示例：特里）来总结输入文件。然后您可以检查多少个索引匹配文档。

例如，为输入文件创建一个长度为10的树。对于文本文件中每个长度为10（重叠）的字符串，检查它们在树中的匹配数目。

来源

2013-04-04 20:24:49 ElKamina

使用trie将是低效的，因为文件的大小很大，而使用B +树会是更好的选择。 – 2013-04-06 07:33:34

作为一个建议，设计真正有能力的，可扩展的文档相似系统，我建议阅读第3章的Mining Massive Datasets，这是免费的在线。其中一种方法是通过将单词计数向量化为集合来“拼凑”数据集，然后散列这些单词计数，并将哈希结果家族与Jaccard相似性进行比较以获得所有文档之间的分数。如果做得对，这可以在高精度的PB级文件上工作。可以从斯坦福大学的CS246 Slides on Locality Sensitive Hashing中读取具有良好图表的明确细节。书中还描述了更简单的方法，如词频计数。

来源

2013-04-04 21:45:53 Pyrce

算法将一个输入文件与给定数量的文件相匹配

回答

相关问题