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

Question

上周我进行了一次面试。我被困在算法圈里的一个问题里。我回答了这个问题，但面试官似乎并不信服。这就是为什么我要分享同样的东西。

请告诉我这个问题的优化方法，以便在以后的面试中对我有所帮助。

问题 :-

有20个文本文件，所有文件都是ASCII文本文件，大小小于10^9字节。也有一个输入，这也是一个ASCII文件，比如说，input.txt。 我们的任务是将此输入文件的内容与给定的20个文件进行战略性匹配，并打印最接近匹配文件的名称。输入文件的内容可能仅部分匹配。

提前谢谢。期待您的好意答复。

Answer 1

区分它们并通过wc -l，或在C++中实现Levenshtein距离，将每一行视为一个字符(或任何对主题域进行更适当调整的单元)。

Answer 2

您可以创建某种索引(例如: trie)来总结输入文件。然后，您可以检查文档中有多少个索引匹配。

例如：为长度为10的输入文件创建一个trie。对于文本文件中每一个长度为10 (重叠)的字符串，检查它们在trie中匹配的数量。

Answer 3

作为设计真正有能力的、可伸缩的文档相似性系统的建议，我建议阅读挖掘海量数据集的第3章，它可以在网上免费获得。这里提出的一种方法是将单词计数向量化成集合，然后对这些单词计数进行散列，并将散列结果与Jaccard相似度进行比较，从而获得所有文档之间的分数。这可以工作在千兆字节的文件，以高精度，如果做对了。清晰的细节和良好的图表可以阅读斯坦福大学的关于局部性散列的CS246幻灯片。更简单的方法，如词频计数，也在书中描述。