返回文本之间关联的函数？

Question

考虑我有一个

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中找到的(2个字你好和晚上是你好比你好更多)

有没有任何已知的算法来做到这一点？

ADD1:

在这种情况下,像编辑距离这样的算法是行不通的.因为string1是一个完整的文本(如300-400个单词),并且比较字符串最多为4-5个单词.

Answer 1

一种动态编程算法

看起来你正在寻找的东西与Smith-Waterman算法的作用非常相似.

来自维基百科:

该算法最初由Temple F. Smith和Michael S. Waterman在1981年提出.与Needleman-Wunsch算法一样,Smith-Waterman是一种动态编程算法.因此,它具有所需的性质,即保证找到关于所使用的评分系统的最佳局部对齐(其包括替换矩阵和间隙评分方案).

让我们看一个实际的例子,这样你就可以评估它的用处.

假设我们有一个文本:

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!

一些实现(带源代码)

• Smith-Waterman CUDA源代码(GSW)
• SM算法解释(演示)
• 一个交互式的逐步演示小程序
• Java源代码
• Python源代码