Эффективный способ (в Ruby), чтобы определить наибольшую совпадающую последовательность в массиве / строке?

Question

Допустим, у меня есть два массива слов:

array1 = ["hello", "world", "i", "am", "in", "the", "world"]
array2 = ["This", "is", "the", "hello", "world", "message"]

, которые так же легко можно представить двумя строками:

string1 = "hello world i am in the world"
string2 = "This is the hello world message"

Предположим, я иду с массивамитеперь.

Я хочу найти самый большой вложенный массив array2, который появляется в том же порядке в array1.

Итак, если бы вы собирались сделать это самым медленным из возможных способов, скажем, вы бы сказали:

• получить все подмассивы из 6 слов (из которых есть один)из массива2.
  • он появляется в массиве 1, в таком порядке?NO
• получить все 5-словарные подмассивы (из которых их два) из массива 2.
  • появляются ли они в массиве 1, в таком порядке?НЕТ
• получить все 4-словарные подмассивы из array2.
  • появляются ли какие-либо из них в array1, в таком порядке?НЕТ
• и т. Д., Пока мы не доберемся до
• , чтобы получить все 2-словарные подмассивы из array2.
  • появляются ли какие-либо из них в массиве 1, в таком порядке?ДА: ["привет", "мир"] делает.СТОП.

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

Обратите внимание, что это не просто пересечение массива, потому что это (по крайней мере, в ruby) не заботится о порядке элементов , о котором я забочусь.

спасибо!

Answer 1

Это похоже на проблему "самой длинной общей подстроки", но с использованием слов вместо символов в строках.

В этой вики (https://en.wikipedia.org/wiki/Longest_common_substring_problem)) описан подход динамического программирования для определения местоположения наибольшего общего совпадения в псевдокоде, и он может быть перенесен в ruby, передавая два массива в качестве параметров.

function LCSubstr(S[1..r], T[1..n])
L := array(1..r, 1..n)
z := 0
ret := {}
for i := 1..r
    for j := 1..n
        if S[i] == T[j]
            if i == 1 or j == 1
                L[i,j] := 1
            else
                L[i,j] := L[i-1,j-1] + 1
            if L[i,j] > z
                z := L[i,j]
                ret := {S[i-z+1..i]}
            else
            if L[i,j] == z
                ret := ret ∪ {S[i-z+1..i]}
        else
            L[i,j] := 0
return ret

Answer 2

Сразу же выполните тест «шесть слов». Затем я проверил бы каждое слово во втором массиве и проверил, находится ли оно в 1-м.Если это так, ищите его и один после, если оба, то ищите следующий.

т.е. когда вы обнаружили, что "This" отсутствует в первом массиве, вы также отбросили пять других потенциальных кандидатов, начиная с этого.

Answer 3

Пока я не узнал о «самой длинной общей проблеме подстрок / последовательностей» (см. Ответ @ Dustin), я не думал, что есть подход, который лучше, чем тот, который вы обрисовали в вопросе: начните с максимально возможного подмассива (array2), затем последовательно уменьшайте размер подмассивов на единицу, пока не будет найдено совпадение (или определено, что два массива не содержат общего элемента).Хотя теперь я вижу, что есть более эффективный способ, ваша идея, безусловно, неплохая, особенно если подстроки не слишком велики, и их легче реализовать, чем решение для динамического программирования, на которое ссылается Дастин.Я реализовал вашу идею ниже.

Я решил использовать регулярное выражение для определения совпадений, поэтому мне нужно преобразовать array1 в строку.

str1 = array1.join(' ')
  #=> "hello world i am in the world" 

Расчет выполняется следующим образом.

[array1.size, array2.size].min.downto(1).each do |n|
  a = array2.each_cons(n).find { |a| str1.match?(/\b#{a.join(' ')}\b/) }
  break a unless a.nil? 
end
  #=> ["hello", "world"] 

nil возвращается, если array1 и array2 не имеют общего элемента.При желании можно сначала проверить (array1 & array2).empty?.

Вот возможное улучшение того, что у меня есть выше.Идея состоит в том, чтобы попытаться уменьшить m в m.downto(1).

h1 = array1.each_with_object(Hash.new(0)) { |word, h| h[word] += 1 }
  #=> {"hello"=>1, "world"=>2, "i"=>1, "am"=>1, "in"=>1, "the"=>1} 
h2 = array1.each_with_object(Hash.new(0)) { |word, h| h[word] += 1 }
  #=> {"hello"=>1, "world"=>2, "i"=>1, "am"=>1, "in"=>1, "the"=>1} 
m = [array1.size, array2.size, h2.sum { |k,v| [v, h2[k]].min }].min
  #=> [7, 6, 7].min
  #=> 6

Здесь это не поможет, но возможно, если бы массивы array1 и array2 были разными.

Answer 4

Это было частью реализации в Ruby схожего текста из PHP.Использование строк:

def substrings(str)
  (0...str.size).flat_map do |i|
    (i...str.size).map { |j| str[i..j] }
  end
end

def lcs(str1, str2)
  (substrings(str1) & substrings(str2)).max_by(&:size)
end

puts "'#{lcs("hello world i am in the world", "This is the hello world message")}'"

=> 'hello world '

Грубая сила для подстрок может быть кандидатом на вызов Rust FFI?Мы не проводили больших сравнений, поэтому у нас это получилось.

Answer 5

Вот быстрое рабочее решение, сокращающее сравнение только с теми общими элементами в массивах:

array1 = ["hello", "world", "i", "am", "in", "the", "world"]
array2 = ["This", "is", "the", "hello", "world", "message"]

common_words = array1 & array2

stringified_array1 = array1.join(' ')
stringified_array2 = array2.join(' ')

(common_words.length - 1).downto(0).map do |n|
  stringified_combo = array1[0..n].join(' ')

  if stringified_array1.include?(stringified_combo) && stringified_array2.include?(stringified_combo)
    stringified_combo.split($,)
  end 
end.compact.max

Таким образом, вы получаете общие слова для двух массивов и проверяете их от самых больших до самых маленьких. Вы проверяете их порядок в первом массиве, а затем, если они существуют во втором.

Я считаю, что это оправдывает себя и довольно эффективно, хотя и рад получить любые комментарии и отзывы,