0

我正在寻找一种数据结构来解决以下问题。接收大量相当短的字符串（例如 5000 万，少于 30 个字符）作为输入，并根据需要对它们进行索引。然后，回答我给出一个新字符串的查询，并且您提供与提供的字符串相似的初始集合中的字符串（例如，10 个最好的此类字符串）。“相似性”的概念理想地是类似于编辑距离或 Jaro-Winkler 距离，或其近似值，但它应该能够适应拼写和词序的微小变化，以及添加垃圾词。（例如，与标准索引任务不同，如果请求“foo bar”确实是集合中最接近的字符串，则它应该产生“foo”）。

举个例子，假设字符串集合是 {"Charles Dickens", "Mary Shelley", "Robert Stephenson"}。查询“狄更斯，查尔斯”应该找到“查尔斯狄更斯”。查询“by Shelley”应返回“Mary Shelley”。

逐一计算查询字符串与集合中所有字符串的相似性的简单方法对于大型集合来说太慢了。什么是更有效地回答此类查询的好数据结构？理想情况下，我会寻找一个好的 Java 实现。

4

2 回答 2

0

作为琐碎方法的替代方法，您可以分两步解决问题：

  1. 建立一个出现在所有字符串中的单词索引，它允许您找到包含给定单词的句子。这应该远小于 5000 万（如果我们谈论的是自然语言）。而且您可能不关心“foop bar”->“foo”，因为您只有单词。
  2. 将您的查询拆分为单词。对于每个单词，找到包含该单词的所有句子。对于每个句子，使用您的指标计算与查询字符串的相似度。

另一个好处是，在许多情况下，您可以在不重建单词索引的情况下更改指标。

于 2012-05-16T20:17:10.227 回答
0

想到两个建议：

1）选择一个满足三角不等式的距离函数并使用http://en.wikipedia.org/wiki/Cover_tree - 可能会提供一些加速但可能不是数量级。

2）猜测最接近的匹配将包括至少一段 k 连续字符，这是两个字符串之间的精确匹配。构建一个数据结构，例如使用哈希表查找可以找到集合中的所有字符串，这些字符串至少具有与查询字符串的某些部分相同的 k 个连续字符，然后使用您的距离函数查看从哪个字符串返回这是最好的比赛。应该很快，但有时会错过正确的答案。

于 2012-05-16T18:47:08.980 回答