Ruby: Как можно проверить сходство между двумя блоками текста?

Question

Итак, допустим, у меня есть следующие тексты:

Текст1:

абсолютное подчинение коллективному чувству зергов, известному как Сверхразум.Сверхразум направлял действия каждого существа зергов в Рое, действуя через иерархию меньших чувств.

Text2:

существо-зерг в Рое, функционирующее через иерархию меньших чувств.Хотя Сверхразум был в первую очередь движим своим желанием поглощать и ассимилировать

Текст 3

Когда зерги впервые прибыли в сектор Копрулу, они были объединены своим абсолютным послушаниемк коллективному чувству зергов, известному как Сверхразум.Сверхразум направлял действия каждого существа зергов в Рое, действуя через иерархию меньших чувств.Хотя Сверхразум был в первую очередь движим своим желанием поглощать и ассимилировать продвинутую расу протоссов, он нашел в человечестве полезный, но неразвитый материал.

Теперь, конец текста1 и начало текста2 совпадают, поэтомумы бы сказали, что текстовые блоки не являются уникальными.Точно так же с Text3, Text1 может быть найден внутри (так же как и Text2), так что это также не уникально из-за перекрытия.

Итак, мой вопрос:

Как мне поступитьписать что-то, что может смотреть на последовательные буквы или слова и определять уникальность?В идеале, я бы хотел, чтобы такой метод возвращал какое-то значение, представляющее степень сходства - возможно, количество совпавших слов в среднем по размеру двух текстовых блоков.Когда он возвращает 0, оба протестированных текста должны быть полностью уникальными.

С какой-то проблемой я столкнулся, когда играл с строковыми методами Руби.

Сначала я попытался найти пересечение двух строк.

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

проблемаПриведенный выше метод заключается в том, что он просто добавляет буквы, которые являются общими к концу результата (мы теряем порядок символов), что затрудняет проверку уникальности.Но я не думаю, что пересечение - лучший способ начать это сравнение подобия.В обоих сравниваемых текстах может присутствовать любое количество комбинаций слов.Так что, может быть, если бы я сделал множество последовательных сходств ... но это потребовало бы, чтобы мы перебирали один из текстов столько раз, сколько мы пытаемся использовать длины фраз.

Полагаю, я просто не знаю, с чего начать, и таким способом, который эффективен, а не O(n^too_high).

Answer 1

Вот реализация Ruby алгоритма расстояния Левенштейна .После установки драгоценного камня вы можете использовать его так:

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)

Answer 2

Я полагаю, что вы ищете, это проблема Longest Common Substring , т. Е. Проблема поиска, учитывая две строки, самой длинной подстроки, которую они обе имеют общего.Ссылка на страницу Википедии, которая поможет вам понять домен, и содержит пример псевдокода алгоритма, который работает за O (нм) время.

Далее, книга по реализации алгоритма Wikibooks имеет реализацию в Ruby .Он включает в себя метод lcs_size, который может быть всем, что вам нужно.Короче говоря, если lcs_size (text1, text2) возвращает 4, это означает, что text1 и text2 имеют очень мало общего последовательного текста, вероятно, только одно слово, но если он возвращает, скажем, 40, они могутиметь общее предложение.

Надеюсь, это полезно!

Answer 3

Gem amatch идеально подходит для сравнения строк.

Answer 4

Это можно улучшить, но это идея:

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

Answer 5

Ваша проблема не в Ruby.Это алгоритм.Вы можете разбить каждый текст на слова, а затем запустить алгоритм минимального расстояния (http://en.wikipedia.org/wiki/Levenshtein_distance), чтобы получить его.

Чем меньше число, тем больше похожи тексты.