在给定的 ASCII 文本文件中匹配最接近的文件名

Question

问题:

我有大约20个ASCII文本文件，每个文件的大小都小于10^9字节。另外给出了一个ASCII文本文件（称为FOO）。程序需要与给定的20个文件中的内容进行策略性匹配，并打印最接近匹配文件的名称。FOO的内容可能只部分匹配。

由于文件大小太大，我在想：

1.如何使用信息检索（因为我不太了解IR）

2.应该使用哪种数据结构来存储这些信息

3.最好的算法是什么。

我知道我要求很多，但我真的陷入了这个问题，找不到如何处理的方法。任何帮助将不胜感激。谢谢！

- Ankush Dubey

---

如何扫描所有文件并为每个文本文件创建一个n维单词向量，然后可以计算文档之间的角度并选择最接近的一个？ - Bartlomiej Lewandowski

一个更简单的方法是使用Jaccard指数http://en.wikipedia.org/wiki/Jaccard_index，虽然它可能不能像余弦相似性那样提供相同的准确度。请注意，这些技术是基于标准化词频计数的。 - decden

你需要定义“最接近”的含义。如果测试文件中的所有单词与文件＃1完全匹配，但单词顺序相反（例如，“the quick red fox”和“fox red quick the”），那么它是否比文件＃2匹配前30％的单词顺序完全相同，但后面几乎没有相似之处更“接近”？大小写敏感吗？空格敏感吗？如果没有“最接近”的定义，你将很难决定要比较什么。 - Jim Mischel

也许可以基于文件中的某些特征（单词、段落、字母等）创建一个布隆过滤器，然后相互检查？ - ldog

要回答这个问题，首先需要更明确地说明您想要什么。您需要做两件事：1. 定义“最接近” - 最小更改字符数？两个字符之间的差异？例如，a->b比a->m更好，单词差异？两个连续更改的字母比相距很远的更改字母更好吗？2. 由于这是一个优化问题，您正在优化哪种用例？单个测试文件？还是许多？比较文件是否随每次测试而改变？还是每次都相同？ - Rafael Baptista

Rabin-Karp算法的一些应用？http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm - Jack

Answer 1

我猜“最接近”的文件是两个文件之间差异最小的文件。

我会寻找一个差异算法，或者最长公共子序列https://en.m.wikipedia.org/wiki/Longest_common_subsequence_problem

- mksteve

Answer 2

Vampire Coder的解决方案假设文档是词袋模型，即单词的顺序不重要。但是，“部分匹配”意味着一些句子匹配，那么这样做没有任何好处。

您可以将每个文档划分为重叠的子集，并获取每个子集的哈希值。然后，您将文档转换为哈希集合。然后，您可以比较哈希值。这是您想要做的一种方法。

对于每个文档，一旦您缩小了潜在匹配项，就可以增加您划分文档的分辨率。例如，您最初将它们分成两个部分，现在可以将它们分成10个部分。这是为了最小化运行时间。

此外，您应该使用类似于http://en.wikipedia.org/wiki/Nilsimsa_Hash的局部敏感哈希算法。

- Neo M Hacker

Answer 3

所以我假设一个文件包含一些文本。我们可以说每个文件都是一个大字符串。现在创建20个向量或数组。遍历文件并将每个单词作为向量中的一个元素。现在创建一个大小为20的向量来存储每个文件的匹配。同时，为给定的文件创建一个单词向量。现在创建一个循环来遍历这些向量，如果在任何给定的索引处找到与这20个向量和您给定的向量之一的匹配项，则增加匹配存储向量中相应文件的值。最后，匹配存储向量中的最高值将指示具有最佳匹配的文件。

- Muhammad Raihan Muhaimin