Как удалить все элементы из отсортированного массива Ruby, которые ближе к ближайшему соседу, чем предел?

У меня есть отсортированный массив действительных чисел в моей программе Ruby. Я хочу удалить все элементы, которые очень «похожи»: их разница меньше заданного предела. Итак, наконец, я хочу сохранить только те элементы, которые хорошо отличимы от других, отдельные элементы: в исходном массиве нет других элементов, которые ближе к ним, чем предел.

В настоящее время я экспериментирую с этими двумя подходами:

limit=0.5
vvs=vv.sort.reverse.each_cons(2).map{|a,b| (a-b).abs<limit ? nil : a}.compact

а также

vvs=vv.each_cons(3).map{|a,b,c| (a-b).abs<limit && (b-c).abs<limit  ? nil : b}.compact

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

Мои исходные реальные данные из «Уловки 22» https://pastebin.com/mRiS02mb


ruby arrays element threshold remove-if
person Konstantin    schedule 20.06.2019    source источник
comment
Не лучше ли округлить зашумленные значения?   -  person Stefan    schedule 20.06.2019
comment
Думаю нет, мне нужны исходные значения, без округления. Однако можно уменьшить массив путем округления/потолка/пола и uniq-ing: vv.uniq{|z| (8*z).ceil} Но значение limit/delta в данном случае для меня непонятно.   -  person Konstantin    schedule 20.06.2019
comment
Ваше второе предложение можно интерпретировать по-разному в зависимости от того, предполагается ли удаление элементов последовательно или одновременно. Следующее предложение кажется достаточно ясным, но я не считаю полезным определение термина отдельные элементы. Я предлагаю вам сформулировать вашу проблему только одним способом...   -  person Cary Swoveland    schedule 27.06.2019
comment
... Например (при условии, что я правильно его интерпретировал): учитывая отсортированный массив чисел с плавающей запятой, arr и неотрицательное число с плавающей запятой limit, я хочу вернуть массив, содержащий те элементы n из arr, для которых абсолютная разница между n и его непосредственные соседи (или соседи, если n является первым или последним элементом массива) не больше, чем limit.   -  person Cary Swoveland    schedule 27.06.2019

Ответы (3)


arrow_upward
1
arrow_downward

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

data = [ 3.42,  5.49,  6.12,  6.48,  7.11,  8.79,  9.36,
         9.54, 10.86, 10.95, 11.07, 13.08, 14.41, 14.92] 
limit = 0.5

([-Float::INFINITY].concat(data) << Float::INFINITY).each_cons(3).
  select { |a,b,c| b-a >= 0.5 && c-b >= 0.5 }.
  map { |_,b,_| b }
  #=> [3.42, 5.49, 7.11, 8.79, 14.41, 14.92]
person Cary Swoveland    schedule 27.06.2019

arrow_upward
2
arrow_downward

Реальные данные не проверял, но может что-то вроде (начало с формы 0, но может измениться на -Float::INFINITY):

data = [1, 1.05, 1.5, 1.5, 1.9, 2, 2.1, 3, 3.6, 4, 4.1]

delta = 0.5
data.each_with_object([]) { |e, o| o << e if e >= (o.last || 0) + delta }

#=> [1, 1.5, 2, 3, 3.6, 4.1]
person iGian    schedule 20.06.2019
comment
OP хочет сохранить только ... отдельные элементы: в исходном массиве нет других элементов, которые были бы ближе к ним, чем предел. Если data = [0.2, 0.5] и delta = 0.5, ваше возвращаемое значение равно [0.5]. Разве это не должен быть пустой массив? - person Cary Swoveland; 27.06.2019
comment
@CarySwoveland, это было неясно, поэтому я решил иметь хотя бы один элемент (первый). Если data = [0.2, 0.5] и delta = 0.5 возвращается [0.2]. Ваше решение должно быть правильным, так как принято. Но проверьте: он возвращает [] для упомянутого здесь примера; в примере вашего ответа он прыгает с 8.79 на 14.41. - person iGian; 02.07.2019

arrow_upward
1
arrow_downward

Учитывая данные этого примера:

data = [
  1.07, 1.14, 1.14, 1.24, 1.55, 1.56, 1.82, 1.83, 2.04, 2.16, 2.23,
  2.37, 2.38, 2.39, 2.41, 2.46, 2.54, 2.58, 2.93, 2.94, 2.98, 3.06,
  3.12, 3.18, 3.62, 3.65, 3.69, 3.87, 4.0, 4.25, 4.36, 4.36, 4.38,
  4.63, 4.78, 4.8, 4.83, 4.86, 5.13, 5.37
]

Вы можете сгруппировать числа по их округленному значению:

limit = 0.5
grouped_data = data.group_by { |f| (f / limit).round * limit }
#=> {
#     1.0 => [1.07, 1.14, 1.14, 1.24],
#     1.5 => [1.55, 1.56],
#     2.0 => [1.82, 1.83, 2.04, 2.16, 2.23],
#     2.5 => [2.37, 2.38, 2.39, 2.41, 2.46, 2.54, 2.58],
#     3.0 => [2.93, 2.94, 2.98, 3.06, 3.12, 3.18],
#     3.5 => [3.62, 3.65, 3.69],
#     4.0 => [3.87, 4.0],
#     4.5 => [4.25, 4.36, 4.36, 4.38, 4.63],
#     5.0 => [4.78, 4.8, 4.83, 4.86, 5.13],
#     5.5 => [5.37]
#   }

Значения от 0,75 до 1,25 находятся в слоте 1.0, значения от 1,25 до 1,75 — в слоте 1.5 и так далее.

Теперь выберите значение из группы, например. первый:

grouped_data.map { |k, vs| vs.first }
#=> [1.07, 1.55, 1.82, 2.37, 2.93, 3.62, 3.87, 4.25, 4.78, 5.37]

или средний:

grouped_data.map { |k, vs| vs[vs.size/2] }
#=> [1.14, 1.56, 2.04, 2.41, 3.06, 3.65, 4.0, 4.36, 4.83, 5.37]

или значение, ближайшее к соответствующему значению слота:

grouped_data.map { |k, vs| vs.min_by { |v| (k - v).abs } }
#=> [1.07, 1.55, 2.04, 2.46, 2.98, 3.62, 4.0, 4.38, 5.13, 5.37]

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

[1.24, 1.26].group_by { |f| (f / limit).round * limit }
#=> { 1.0 => [1.24], 1.5 => [1.26] }
person Stefan    schedule 21.06.2019
comment
Должен ли я опустить каждую вторую группу, чтобы обеспечить заданный лимит? - person Konstantin; 21.06.2019
comment
@Konstantin, ваше описание показалось немного расплывчатым (я хочу удалить все очень похожие элементы), поэтому я просто хотел предложить альтернативный подход. Определите, чего вы на самом деле хотите, а затем реализуйте это. - person Stefan; 21.06.2019
comment
На самом деле я хочу опустить те элементы, которые можно легко ошибиться в совместном домене из-за аддитивных ошибок в исходном домене, поскольку я сопоставляю два набора, чтобы найти как можно больше совпадающих строк субтитров. - person Konstantin; 21.06.2019
comment
Не уверен, что вы подразумеваете под «аддитивными ошибками» и «совпадающими строками субтитров». - person Stefan; 21.06.2019
comment
Например, X — это временные данные одного файла субтитров, тогда Y = a*X+b+eps — временные данные другого файла субтитров, где a и b должны быть рассчитаны, а eps — некоторый аддитивный шум, например случайные значения. в интервале (-1/8,+1/8). Чтобы решить эту проблему, можно изучить различия X(n+1)-X(n)=dX для всех пар и сопоставить их с соответствующими различиями Y(n+1)-Y(n)=dY. Если сопоставление выполнено успешно, то значение a можно рассчитать как сумму (dX) / сумму (dY). После этого можно легко вычислить и b. - person Konstantin; 21.06.2019