我有一个应用程序，我应该在其中实现 Bloom Filters 和 Minhashing 来查找类似的项目。
我已经实现了布隆过滤器，但我需要确保我理解 Minhashing 部分来做到这一点：
我必须将文件上的所有字符串都拼起来吗？问题是我真的找不到可以帮助我的东西，我发现的只是关于两个文档，而不是一个字符串到一组字符串。
所以：用户输入一个字符串，应用程序会在单个文档中找到最相似的字符串。通过“相似性”，您是指像莱文斯坦距离（其中“猫”被认为与“老鼠”和“购物车”相似），还是其他一些衡量标准？你（粗略地说）是否在寻找相似的段落、相似的句子、相似的短语或相似的词？这些都是重要的考虑因素。
另外，您说您正在将一个字符串与一组字符串进行比较。这些字符串是什么？句子？段落？如果您确定不想在多个段落（或多个句子，或您有什么）中找到任何相似之处，那么将文档视为多个单独的字符串是有意义的；否则，您应该将其视为单个长字符串。
MinHash 算法用于将许多文档相互比较，当不可能将所有文档同时存储在内存中时，单独比较每个文档将是一个 n 方问题。MinHash 通过仅存储一些带状疱疹的散列克服了这些问题，因此牺牲了一些准确性。您不需要 MinHash，因为您可以简单地将每个 shingle 存储在内存中，例如，为您的 shingles 使用 4-character-grams。但是，如果您不希望转换词序，您可能会发现Smith-Waterman 算法更合适（另请参见此处）。
如果您希望用户输入一长串单词，您可能会根据单词获得更好的结果；例如，3-word-grams 忽略了空格、大小写和标点符号的差异。
生成 4-character-gram 很简单：“The cat sat on the mat”会产生“The”、“he c”、“e ca”、“cat”等。每一个都将存储在内存中，以及它出现的段落编号。当用户输入搜索字符串时，它将以相同的方式组合在一起，并且可以检索包含最大数量的共享带状疱疹的段落。为了提高比较效率，您可以使用 FNV1a 或类似的廉价散列将它们存储为散列，而不是将带状疱疹存储为字符串。
带状疱疹也可以由单词而不是字符构成（例如“the cat sat”、“cat sat on”、“sat on the”）。对于较大的文本，这往往会更好：比如 30 个单词或更多。如果采用这种方法，我通常会忽略空格、大小写和标点符号的所有差异。
如果你想找到可以跨越段落的匹配，它会变得相当复杂，因为你必须存储每个带状疱疹的字符位置并考虑可能匹配的许多不同配置，根据它们的带状疱疹分散程度来惩罚它们是。这可能会导致相当复杂的代码，我会认真考虑坚持使用基于 Levenstein 的解决方案，例如 Smith-Waterman，即使它不能很好地处理字序倒置。
我不认为布隆过滤器可能对您有太大帮助，尽管我不确定您是如何使用它的。如果您的文档是高度结构化的，布隆过滤器可能会很有用：一组有限的可能字符串并且您正在搜索其中一个是否存在。但是，对于自然语言，我怀疑它会非常有用。