返回文本之间的亲和力的函数？

考虑我有一个

string1 = "hello hi goodmorning evening [...]"

我有一些小关键字

compare1 = "hello evening"
compare2 = "hello hi"

我需要一个返回文本和关键字之间的关联性的函数。例子：

function(string1,compare1);  // returns: 4
function(string1,compare2);  // returns: 5 (more relevant)

请注意5和4只是示例。

你可以说 - 编写一个计算出现次数的函数 - 但对于这个例子来说，这是行不通的，因为两者都出现了 2 次，但compare1 不太相关，因为在 string1 中没有准确找到“hello night”（hello 和 night 这两个词是比你好更遥远）

有没有已知的算法可以做到这一点？

ADD1:

在这种情况下，像“编辑距离”这样的算法将不起作用。 因为 string1 是一个完整的文本（如 300-400 个单词），并且比较字符串最多为 4-5 个单词。

动态规划算法

看来您正在寻找的内容与史密斯-沃特曼算法 http://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm does.

来自维基百科：

该算法最初由 Temple F. Smith 和 Michael S. Waterman 于 1981 年提出。尼德曼-温施 http://en.wikipedia.org/wiki/Needleman-Wunsch_algorithmSmith-Waterman 算法，它是它的一个变体动态规划算法 http://en.wikipedia.org/wiki/Dynamic_programming。因此，它具有理想的特性，即保证找到相对于所使用的评分系统（包括替换矩阵和间隙评分方案）的最佳局部对齐。

让我们看一个实际的例子，这样你就可以评估它的实用性。

假设我们有一个文本：

text = "We the people of the United States, in order to form a more 
perfect union, establish justice, insure domestic tranquility, 
provide for the common defense, 

  promote the general welfare, 

  and secure the blessings of liberty to ourselves and our posterity, 
do ordain and establish this Constitution for the United States of 
America.";  

我将我们要匹配的部分隔离出来，只是为了方便您阅读。

我们将比较相似度（或相似度）与字符串列表：

list = {
   "the general welfare",
   "my personal welfare",
   "general utopian welfare",
   "the general",
   "promote welfare",
   "stackoverflow rulez"
   };  

我已经实现了算法，因此我将计算相似度并对结果进行标准化：

sw = SmithWatermanSimilarity[ text, #] & /@ list;
swN = (sw - Min[sw])/(Max[sw] - Min[sw])  

然后我们绘制结果：

我认为这与您的预期结果非常相似。

HTH!

一些实现（带源代码）

• 史密斯-沃特曼 CUDA 源代码 (GSW) http://www2.engr.arizona.edu/~rcl/gsw.html
• S-M算法解释 （推介会） http://www.maths.tcd.ie/~lily/pres2/sld012.htm
• 交互式分步演示 小程序 http://baba.sourceforge.net/
• Java源代码 http://jaligner.sourceforge.net/
• Python源代码 http://narnia.cs.ttu.edu/drupal/node/104