Алгоритм LCS с конкретными условиями
Итак, проблема в двух словах:
Мне нужно выполнить "Longest Common Subsequence" на трассировке системных вызовов программы в режиме реального времени. Что мы делаем сейчас, так это то, что у нас есть набор из ~250 подписей, каждая из которых состоит из ~40 системных вызовов. Мы фиксируем 1K фрагментов системных вызовов, связанных с потоком программы, проверяем, соответствует ли оно 70% любой сигнатуры, а затем возвращаем результат. Затем сдвиньте блок на 300 и выполните обнаружение на новом наборе.
Как видите, есть два условия, которые могут помочь выполнить обнаружение быстрее. Во-первых, набор системных вызовов 1К будет оставаться постоянным при проверке каждой подписи. Во-вторых, мы возвращаем true, если длина LCS уже превышает 70% подписи.
Я реализовал рекурсивный способ, и, используя этот способ, я могу определить текущую длину LCS, рассчитанную в каждой рекурсии, и, если она уже превышает 70% подписи, я выкидываю выход. Также я делаю препроцесс для поддержания матрицы "Появление системного вызова X после позиции Y". И используйте этот массив для всех проверяемых подписей.
Тем не менее я не могу найти приемлемое решение, и алгоритм все еще кажется довольно медленным. Также я не могу думать о каких-либо улучшениях динамического алгоритма, учитывая мои конкретные случаи. Какие-либо предложения?