Найти последовательность строк массива в другом массиве

Question

У меня вопрос по поиску в массивах. Мне нужно найти последовательность строк, которую я сохранил в массиве, и, например, это может выглядеть так array1:

['818181' '747473' '747474' '636363' '767676' '737373' '727373' '373838'
 '697070' '686869' '115115115' '737474' '757575' '777777' '818181' '747473'
 '747474' '636363' '767676' '737373' '727373' '757575' '696969']

Это простой массив со строками. Dtype показывает, что это S9. Тогда у меня есть другой основной массив с той же структурой, но гораздо больше. Я ищу наиболее эффективный способ найти позицию, где array1 начинается в основном массиве, так что я ищу указанный шаблон в массиве numpy. Эти значения повторяются, и мне нужно найти точно такой же. Я искал лучшие решения для этого, но я не мог найти ничего, что могло бы помочь. Основной массив очень большой, и мне нужно, чтобы позиция array1 была меньше 1 с. Я нашел несколько примеров сценариев поиска последовательности в массиве, к сожалению, ничего из этого мне не помогло. В основном они находили некоторые целочисленные значения в небольших массивах. Мне нужен совет.

Я попытался пройти весь массив с for i, e в enumerate () Итак, один элемент выглядит так: «818181». Тогда я рассчитывал, если 23 элемента подряд (в этом примере) одинаковы. Но когда 5-й элемент был неправильным, мне пришлось бы пойти туда, где я нашел 1-й, чтобы добиться 100% успеха (потому что скороговорки могут идти друг на друга), и это было очень медленно.

Основной массив похож на array1, но 1000x и имеет больше значений

Answer 1

Вы можете просмотреть каждое значение в массиве1 и использовать np.where(), чтобы получить индексы значений в вашем основном массиве. Добавьте индексы в список, затем отсортируйте список. Затем найдите последовательную длину индексов, которая соответствует длине массива 1.

Например:

def consecutive(data, stepsize=1):
    return np.split(data, np.where(np.diff(data) != stepsize)[0]+1)

index_list = []
for val in array1:
    index_list.extend(list(np.where(main_array == val)))
index_list.sort()

for sequence in consecutive(index_list):
    if len(sequence) == len(array1):
        print(sequence)

Кредиты @unutbu от как найти группы последовательных элементов из массива в numpy? для последовательной функции.

Answer 2

Совсем нет; посмотри снова. Достигнув 5-го элемента, вы уже знаете, что элементы 2, 3, 4 являются , а не первым элементом, поэтому вы просто переключаетесь, чтобы начать заново с несоответствующего элемента.

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

Сначала не беспокойтесь о содержимом ваших строк; все, что имеет значение, это то, что у вас есть последовательность символов для поиска Каждая строка «число» - это отдельный символ. Для удобства сопоставим следующее:

'818181' => a
'747473' => b
'747474' => c
etc.

Таким образом, массив может быть уменьшен до чего-то подобного:

 '818181' '747473' '747474' '636363' '767676' '737373' '727373' '373838'
  a        b        c        d        e        f        g        h
 '697070' '686869' '115115115' '737474' '757575' '777777' '818181' '747473'
  i        j        k           l        m        n        a        b
 '747474' '636363' '767676' '737373' '727373' '757575' '696969']
  c        d        e        f        g        m        o

Или как последовательность из одной строки:

  abcdefghijklmnabcdefgmo

В случае, если вы отметили несоответствие на b, нам не нужно возвращаться к положению b ввода и начинать заново; мы уже определили, что bcd соответствует, а они не a, поэтому мы не копируем: мы просто начинаем снова, сравнивая a с элементом, который не матч.

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

Рассмотрим, что происходит, когда мы имеем несовпадение во втором m, ближе к концу целевой последовательности. В этом случае мы знаем, что мы только что сопоставили abcdefg, но текущий символ не m ... но если может быть h. Чтобы избежать резервного копирования, мы используем частичное совпадение и возобновляем проверку с помощью h.

Для обработки этого алгоритма вам необходимо выполнить некоторую предварительную обработку целевой строки. Создайте второй массив, содержащий индекс перезапуска для каждой позиции в целевой строке. Вы делаете это с простой проверкой того, где он отклоняется от самого себя. Для вашего примера это просто: o - единственное место, где основная строка и сдвинутая строка соответствуют нескольким символам, но отличаются в этом месте.

  abcdefghijklmnabcdefgmo
  11111111111111111111181

Это заставляет вас двигаться?