Алгоритм поиска

Question

Я ищу эффективный алгоритм поиска, чтобы получить повторяющийся шаблон самый длинный самый короткий в коллекции (~ 2k целых чисел), где моя коллекция состоит из этого повторного шаблона только (нет шума между повторяющимися рисунками), но последнее появление рисунка может быть неполным.

Примеры: У меня есть: [2,4,1, 2,4,1, 2,4,1, 2,4,1, 2,4,1]
Я хотел бы получить: [2,4,1]

У меня есть: [21,1,15,22, 21,1,15,22, 21,1,15,22, 21,1,15]
Я хотел бы получить: [21,1,15,22]

У меня есть: [3,2,3,2,5]
Я хотел бы получить: [] (нет шаблона)

(пробелы добавлены только для удобства чтения)

Answer 1

Очень простой алгоритм выглядел бы так (в Python, но не должно быть проблем с переводом на Javascript):

def check(a, width):
  '''check if there is a repeated pattern of length |width|'''
  for j in range(width, len(a)):
    if a[j] != a[j-width]:
      return False
  return True

def repeated(a):
  '''find the shortest repeated pattern'''
  for width in range(1, len(a)):
    if check(a, width):
      return a[:width]
  return []

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

Answer 2

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

Answer 3

Вы можете оптимизировать поиск, наблюдая, что длина вашей коллекции должна быть кратна длине вашего образца. Если размер вашей коллекции прост, единственная возможная длина шаблона - 1, т. Е. Все элементы должны быть идентичны!

Answer 4

Я думаю, что вы могли бы подойти к этой проблеме, рассматривая период паттерна. Период последовательности A [] является наименьшим целым числом T таким, что A [i + T] = A [i] для всех i. В вашем случае, когда вы найдете период T, все готово, так как A [0..T-1] - самый короткий шаблон, который вы ищете. Итак, начните с минимально возможного периода T = 1 и проверьте, удовлетворяет ли последовательность периодическому свойству. Если да, то все готово (это на самом деле происходит только тогда, когда все элементы идентичны). Для любого большего T вам нужно проверить, является ли A [i + T] = A [i] для i = 0..A.len-T-1. Это просто простой цикл.