Найти массив строк внутри массива строк

Question

Я прочитал много способов найти подстроку в строке. Но в моем случае мне нужно найти строку слов (ie подстрока) внутри строки. Мы можем достичь этого в O(n^3) раз, что является очень плохой временной сложностью

Например

sentences = ["jim likes mary", "kate likes tom", "tom does not like jim"]<br/>
phrases = ["jim tom", "likes"]

Я хочу найти полную фразу в предложении независимо от позиции

В вышеприведенном случае выводом будет

[2, [0,1]]

Объяснение: Везде, где совпадение всех слов фразы в предложении, возвращает индекс предложения

1) Первая фраза Джим Том присутствует только во 2-х индексах предложений, что Том не любит Джим , поэтому верните 2-й индекс 2) В то время как вторая фраза лайки присутствует в 1-м и 2-м массиве, поэтому возвращают 0 и 1 индексы

Я сделал с грубой силой, но это не эффективный способ сделать это

final_arr = []
phrases.each do |phrase|
  temp_arr = []
  sentences.each_with_index do |sentence, index|    
    multiple_word_phrase  = phrase.split(" ")
    if multiple_word_phrase.length > 1
      flag = 1
      multiple_word_phrase.each do |word|
        if !sentence.include?(word)
          flag = 0
          break
        end
      end
      temp_arr << index if flag == 1
    else
      temp_arr << index if sentence.include?(phrase)
    end
  end
  final_arr << temp_arr if temp_arr.any?
end

Есть ли эффективный способ решить эту проблему O(NlogN) Time. Я думаю, что это может быть достигнуто с помощью Dynami c программирования, но не знаю, как это сделать

Answer 1

Вы можете ускорить вычисления следующим образом:

require 'set'

h = sentences.each_with_index.with_object({}) do |(str,i),h|
  h[i] = str.split.to_set
end
  #=> {0=>#<Set: {"jim", "likes", "mary"}>,
  #    1=>#<Set: {"kate", "likes", "tom"}>,
  #    2=>#<Set: {"tom", "does", "not", "like", "jim"}>} 

keys = h.keys
  #=> [0, 1, 2]

phrases.map do |p|
  pa = p.split
  keys.select { |j| pa.all? { |s| h[j].include?(s) } }
end
  #=> [[2], [0, 1]]

Возвращаемое значение - не совсем возвращаемое значение, требуемое вопросом: [2, [0,1]]. Тем не менее, я предлагаю создать все элементы этого массива, даже если они содержат только один элемент (например, [2]). Это облегчит жизнь программисту в будущем. Однако, если требуется [2, [0,1]], в конце выполните простую настройку:

phrases.map do |p|
  pa = p.split
  keys.select { |j| pa.all? { |s| h[j].include?(s) } }
end.map { |e| e.size == 1 ? e.first : e }
  #=> [2, [0, 1]]

Поскольку вычислительная сложность поиска по множеству близка к O (1) (постоянная), вычислительная сложность этого подхода близко к O (n ² ), где n - некоторая мера для размеров sentences и phrases.

Answer 2

Я не очень знаком с Ruby, но если у вас есть такие понятия, как хэш-карты и хэш-наборы, вы можете оптимизировать их. Как я уже упоминал в моем комментарии, если вы уверены, что временная сложность вашего алгоритма равна O(N^3), вы можете оптимизировать его до O(N^2).

. Для этого возьмите массив sentences и выполните преобразование. это к хэш-карте, которая связывает каждое слово с набором индексов, где оно появляется. Для вашего примера это будет выглядеть так: "jim" -> Set(0, 2), "tom" -> Set(1, 2), "kate" -> Set(1) et c ... Это займет временную сложность O(N) (из-за O(1) временной сложности как поиска в hashmap, так и добавления в Set)

Теперь для каждой фразы вы разбиваете ее и берете пересечение Наборов ее слов. Например, результатом первой фразы будет пересечение Indexes_of("jim") и indexes_of("tom"), что равно Set(1). Пересечение займет у вас O(N) для каждой фразы. Учитывая, что у вас есть N фраз, сложность времени составляет O(N^2).

Answer 3

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

phrases.map do |phrase|
  words = phrase.split
  sentences.map.with_index do |sentence, index|
    index if words.all? { |word| sentence[word] }
  end.compact
end

Разбивка:

• Конечный результат имеет то же измерение, что и phrases, так что вы можете express, что с операцией карты.
• Внутри каждого результата список результатов поиска содержит не более числа элементов в sentences, так что вы либо используйте filter() или map().compact
• Для самого внутреннего l oop, all?() используется для описания всех слов, которые должны существовать внутри каждого предложения.

Answer 4

Другой вариант, используя Array # product :

# setup
mapped_phr = phrases.map(&:split).zip(0..)
mapped_sen = sentences.zip(0..)

# loop
res = mapped_phr
  .product(mapped_sen)
  .each_with_object(Hash.new { |h, k| h[k] = [] }) do |(phr, sen), h|
    h[phr.first] << sen.last if phr.first.all? { |e| sen.first.include? e }
  end

res #=> {["jim", "tom"]=>[2], ["likes"]=>[0, 1]}
res.values #=> [[2], [0, 1]]

Или вы можете присоединиться к phr.first, чтобы получить строку в виде ключа ha sh.

Answer 5

Может быть, что-то подобное, используя each_with_index и массив массивов для фраз (я думаю, это лучше):

sentences = ["jim likes mary", "kate likes tom", "tom does not like jim"]
phrases = [["jim", "tom"], ["likes"]]

final_arr = []
sentences.each_with_index do |sentence, index|
    phrases.each do |words|
        if words.all? { |word| sentence.include? word }
            final_arr << index
        end
    end
end

Демо

Хотя , это в основном та же сложность.