全文搜索最接近的匹配

Question

我正在尝试为我的网站实现内部搜索，以便在用户输入错误的情况下为用户指明正确的方向，类似于 Google 搜索中的“您的意思是吗”：。

有人知道如何进行这样的搜索吗？ 我们如何确定我们假设用户想要搜索的单词或短语的相关性？

• 我使用 asp.net 和 sql server 2005 以及 FTS (fullTextSearch)

谢谢

Answer 1

我能想到的最简单的方法是编写一个返回两个单词之间不匹配程度的函数，然后循环遍历所有单词并找到最好的单词。

我已经用分支定界方法完成了此操作。 让我挖一下代码：

bool matchWithinBound(char* a, char* b, int bound){
  // skip over matching characters
  while(*a && *b && *a == *b){a++; b++;}
  if (*a==0 && *b==0) return true;
  // if bound too low, quit
  if (bound <= 0) return false;
  // try assuming a has an extra character
  if (*a && matchWithinBound(a+1, b, bound-1)) return true;
  // try assuming a had a letter deleted
  if (*b && matchWithinBound(a, b+1, bound-1)) return true;
  // try assuming a had a letter replaced
  if (*a && *b && matchWithinBound(a+1, b+1, bound-1)) return true;
  // try assuming a had two adjacent letters swapped
  if (a[0] && a[1]){
    char temp;
    int success;
    temp = a[0]; a[0] = a[1]; a[1] = temp;
    success = matchWithinBounds(a, b, bound-1);
    temp = a[0]; a[0] = a[1]; a[1] = temp;
    if (success) return true;
  }
  // can try other modifications
  return false;
}

int DistanceBetweenWords(char* a, char* b){
  int bound = 0;
  for (bound = 0; bound < 10; bound++){
    if (matchWithinBounds(a, b, bound)) return bound;
  }
  return 1000;
}

Answer 2

你为什么不使用Google Power？，你可以使用他们的建议服务

这里是一个c#示例

Answer 3

您可以使用算法来确定字符串相似性，然后建议搜索索引中的其他字符串，直到一定的差异。

其中一种算法是Levenshtein 距离。

但是，不要忘记寻找现有的解决方案。 我认为例如 Lucene 具有搜索相似字符串的能力。

顺便说一句，这里有一篇关于此主题的相关文章：Google 如何“你的意思？” 算法有效吗？

Answer 4

这是通过正则表达式查询与短语匹配的最接近的关键字来完成的。

这里是一篇很棒的文章，可能会对您有所帮助。

Answer 5

对于 T-SQL，您可以使用 SOUNDEX 功能对单词进行语音比较。

如果您获取用户输入，然后通过 soundex 代码将其与数据库中的其他单词进行比较，您应该能够得出“您的意思是”的列表吗？ 字。

例如，

select SOUNDEX('andrew')
select SOUNDEX('androo')

两者都会产生相同的输出（A536）。

现在有更好的算法，但 soundex 内置于 sql server 中。