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