Алгоритм для линейного сопоставления с образцом?
У меня есть линейный список нулей и единиц, и мне нужно сопоставить несколько простых шаблонов и найти первое вхождение. Например, мне может понадобиться найти,0001101101
01010100100
, ИЛИ ЖЕ10100100010
в списке длиной 8 миллионов. Мне нужно только найти первое вхождение любого из них, а затем вернуть индекс, по которому оно происходит. Тем не менее, выполнение циклов и доступ к большому списку может быть дорогим, и яЯ бы не хотел делать это слишком много раз.
Есть ли более быстрый метод, чем делать
foreach (patterns) {
for (i=0; i < listLength; i++)
for(t=0; t < patternlength; t++)
if( list[i+t] != pattern[t] ) {
break;
}
if( t == patternlength - 1 ) {
return i; // pattern found!
}
}
}
}
Редактировать: Кстати, я реализовал эту программу в соответствии с приведенным выше псевдокодом, и производительность в порядке, но ничего впечатляющего. Я'Я предполагаю, что я обрабатываю около 6 миллионов бит в секунду на одном ядре моего процессора. Я'Я использую это для обработки изображений, и этоНам придется пройти через несколько тысяч 8-мегапиксельных изображений, так что каждый кусочек помогает.
Редактировать: Если оно'не ясно, яя работаю с битовым массивом, так чтоЕсть только две возможности: один и ноль. И это'в C ++.
Редактировать: Спасибо за указатели на алгоритмы BM и KMP. Я отметил, что на странице Википедии для BM это говорит
Алгоритм предварительно обрабатывает искомую целевую строку (ключ), но не искомую строку (в отличие от некоторых алгоритмов, которые предварительно обрабатывают искомую строку и могут затем амортизировать затраты на предварительную обработку путем повторного поиска).
Это выглядит интересно, но это не такПриведите примеры таких алгоритмов. Может ли что-то подобное помочь?