Ruby：如何测试两个文本块之间的相似度？

Question

假设我有以下文本：

文本1：

对虫族集体意识——超级智慧体“至高意志”的绝对服从。至高意志通过次级智慧体的层级结构指挥蜂群中每个虫族生物的行动。

文本2：

通过次级智慧体的层级结构指挥蜂群中每个虫族生物的行动。虽然至高意志主要是由其渴望消耗和同化先进的神族而驱动的。

文本3：

当虫族第一次来到科普鲁星系时，它们被其对虫族集体意识——超级智慧体“至高意志”的绝对服从所统一。至高意志通过次级智慧体的层级结构指挥蜂群中每个虫族生物的行动。虽然至高意志主要是由其渴望消耗和同化先进的神族而驱动的，但它在人类中发现了有用但未开发的资源。

现在，文本1的结尾和文本2的开头重叠，因此我们会认为这些文本块不是唯一的。同样，对于文本3，文本1和文本2都可以在其中找到，因此也不是唯一的，由于重叠。

所以，我的问题是：

我该如何编写一个程序来查看连续的字母或单词并确定其唯一性？理想情况下，我希望这种方法返回某个值，表示相似度的程度——可能是匹配单词数除以两个文本块大小的平均值。当返回0时，测试的两个文本应完全独特。

当我使用Ruby的字符串方法时，遇到了一些问题。

首先，我开始尝试查找两个字符串的交集。

>> a = "nt version, there are no ch"  
>> b = "he current versi"  
>> (a.chars.to_a & b.chars.to_a).join  
=> "nt versihc"  

上述方法的问题在于它只是将共同的字母附加到结果的末尾（我们失去了字符的顺序），这会使测试唯一性变得困难。但我认为交集并不是开始进行相似性比较的最佳方式。被比较的两个文本中可能存在任意数量的单词组合。因此，也许如果我制作一个连续相似性的数组......但这将要求我们遍历其中一个文本，尝试短语长度的次数。我想我真的不知道从哪里开始，以一种既高效又不是O(n^太高)的方式。

- NullVoxPopuli

Answer 1

这是一个关于Levenshtein距离算法的Ruby 实现。安装完gem后，你可以像这样使用它：

require 'rubygems'
require 'Text'

t1 = "absolute obedience to the zerg collective sentience known as the Overmind. The Overmind directed the actions of every zerg creature in the Swarm, functioning through a hierarchy of lesser sentients."

t2 = "zerg creature in the Swarm, functioning through a hierarchy of lesser sentients. Although the Overmind was primarily driven by its desire to consume and assimilate"

puts Text::Levenshtein.distance(t1,t2)

- agregoire

---

我感觉这是基于每个字母而不是连续单词完成的。=\ idk。就像...我比较了我的代码块上面的大段文字和代码块前面的大段文字。我使用Text::Levenshtein.distance并除以两个段落长度的平均长度。我得到的差异百分比（越接近1，越不同；0，越相似）与您给出的示例几乎相同，就像我在上面的两个段落之间进行比较时一样（从“问题”开始和“我该如何去做”）。 - NullVoxPopuli

“连续单词”被称为一种算法，叫做“最长公共子串”。 - Hock

Answer 2

我相信你正在寻找的是最长公共子串问题，即给定两个字符串，找到它们共有的最长子串。链接指向维基百科页面，该页面将帮助您了解该领域，并包含一个运行时间为O(nm)的算法的伪代码示例。

此外，Wikibooks的算法实现书中有Ruby的实现。它包括一个可能是您所需的lcs_size方法。简而言之，如果lcs_size(text1，text2)返回4，那么意味着text1和text2几乎没有连续的共同文本，可能只有一个单词，但如果返回，例如，40，它们可能有整个句子相同。

希望这有所帮助！

- Jordan Running

---

非常有帮助！谢谢！这可能正是我开始所需的 =D - NullVoxPopuli

Answer 3

这个想法有很大的改进空间，但需要一些时间：

txt1 = "absolute obedience to the zerg collective sentience known as the Overmind. The Overmind directed the actions of every zerg creature in the Swarm, functioning through a hierarchy of lesser sentients."
txt2 = "zerg creature in the Swarm, functioning through a hierarchy of lesser sentients. Although the Overmind was primarily driven by its desire to consume and assimilate"

def txt_to_ary(txt)
    txt.gsub(/\.|,/, ' ').downcase.split(/\s+/)
end

def longest_match(txt1, txt2)
    longest = 0
    txt1.each_with_index do |w1, i|
        txt2.each_with_index do |w2, j|
            next unless w1 == w2
            k = 0
            k += 1 while txt1[i+k] == txt2[j+k]
            longest = k if k > longest          
        end
    end
    longest
end

txt1 = txt_to_ary( txt1 )
txt2 = txt_to_ary( txt2 )

puts longest_match(txt1, txt2) #=>12

- derp

---

当txt1.length - i == txt2.length -j时，此行代码：k += 1 while txt1[i+k] == txt2[j+k] 永远不会结束。 - wangii

Answer 4

amatch宝石非常适合字符串比较。

- Zuhaib Ali

Answer 5

你的问题不在于Ruby，而是算法。你可以将每个文本拆分为单词，然后运行最小距离算法（http://en.wikipedia.org/wiki/Levenshtein_distance）来得到结果。

数字越小，说明文本越相似。

- Hock