11

考虑我有一个

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 这两个词是比你好你好）

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

添加1：

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

4

7 回答 7

9

一种动态规划算法

您正在寻找的似乎与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])

然后我们绘制结果：

在此处输入图像描述

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

！

一些实现（带源代码）

于 2011-02-03T00:55:57.347 回答
4

看看从输入数据中创建 N-gram，然后在 N-gram 上进行匹配。我有一个解决方案，我将每个 n-gram 视为向量空间中的一个维度（在我的情况下变成 4000 个维度的空间），然后亲和力是两个向量之间角度的余弦（这里涉及点积）。

困难的部分是想出一个以你想要的方式定义亲和力的指标。

另一种方法是查看滑动窗口并根据 compare_x 数据中有多少单词在窗口中进行评分。最后的分数是总和。

于 2011-01-25T01:42:31.030 回答
2

py-editdist将为您提供两个字符串之间的Levenshtein 编辑距离，这是一个可能有用的指标。

见： http: //www.mindrot.org/projects/py-editdist/

该页面的代码示例：

import editdist

# Calculate the edit distance between two strings
d = editdist.distance("abc", "bcdef")

相关： https ://stackoverflow.com/questions/682367/good-python-modules-for-fuzzy-string-comparison

于 2011-01-24T23:32:32.943 回答
1

我认为这里有一个很好且完整的答案 http://answers.google.com/answers/threadview?id=337832

对不起，它在谷歌的答案！

于 2011-02-02T05:42:59.083 回答
0

好吧，您可以计算比较文本的出现次数，即：

"abc" -> "a" , "b" , "c" , "ab" , bc" , "abc" （如果你想要的话，可能是 "ac"）

然后计算每一个的出现次数，并将它们相加，可能权重为（字符串长度）/（整个字符串的长度）。

然后你只需要一种方法来制作这些片段，并对所有这些片段进行检查。

于 2011-01-31T01:18:49.447 回答
0

虽然目前的Levenshtein 距离可能不适合您的目的，但对其进行修改可能会：尝试通过分别存储插入、删除和替换来实现它。

距离将是以下各项的总和：

  • 所有替代品
  • 每组连续插入/删除中的空格数减一：
    • （在您的情况下：“ hi goodmorning ”仅计为两次编辑，而 ' [...] ' 计为一次。）

当然，您必须对此进行测试，但如果效果不佳，请尝试简单地使用连续插入/删除的总和（因此，“嗨，早上好”只有 1 次编辑）。

编辑

PS：这假设 Levenshtein 的工作方式发生了相对重大的变化，您首先要“对齐”您的数据（找出显着（超过两个字符）重叠的位置并插入将被视为插入的“空”字符）。

此外，这只是一个未经测试的想法，因此欢迎任何改进想法。

于 2011-02-01T15:04:43.893 回答
0

在这里，您可以找到用于计算字符串之间距离的指标列表，以及可以执行此操作的开源 Java 库。 http://en.wikipedia.org/wiki/String_metric 特别是，看看史密斯-沃特曼算法，记住他们所谓的“字母表”可以由我们所说的字符串组成：所以，给定字母表

{A = "hello", B = "hi",C = "goodmorning",D = "evening"}

并调用 d 距离，您的函数尝试计算

d(ABCD,AB) vs d(ABCD,AC)
于 2011-01-27T23:58:12.407 回答