Я столкнулся с проблемой, и я чувствую, что есть решение в теории графов или графических базах данных. Мои знания в этих областях очень ограничены. Я надеюсь, что кто-то сможет распознать мою проблему и, возможно, указать мне название метода, используемого для ее решения.
Упрощенный пример:
Я имею дело со временем -серия состояний. Простой пример, где есть только два состояния:
TS State
t0 T
t1 F
t2 F
t3 F
t4 T
t5 T
t6 T
t7 F
t... ...
Я мог бы преобразовать это в некоторый граф с двумя узлами (T и F), и где «время пребывания» в состоянии является атрибутом (в скобки):
T(1) -> F(3) -> T(3) -> F(1)
Пример моей проблемы - написать «запрос», который извлекает любую подпоследовательность, соответствующую этому шаблону F(>=2) -> T(<10). В моем примере выше мой запрос извлекал бы подпоследовательность: F(3) -> T(3)
Но если бы она присутствовала в наборе данных, запрос также мог бы извлекать такие последовательности, как:
F(2) -> T(8)
F(20) -> T(3)
Пример, который я привел, упрощен: существует более двух состояний, и более сложные запросы допускают циклы, где эти циклы могут быть ограничены либо общим временем, проведенным в l oop, либо количеством циклов, которые могут быть выполнены : Например,
`T(>2) -> [loops of F(1)->T(1)] -> T(<10)`
Где мой l oop может быть ограничен, чтобы он не занимал более 10 итераций или не более 10 единиц времени. Глазурью на торте было бы найти такие последовательности
T(n)->F(<n)
, что переводится как: последовательности, которые начинаются с T (и остаются в T в течение n единиц времени), за которыми следует состояние F, в котором он остается в F менее n (т.е. F короче предыдущего T)
То, что я пробовал :
Первоначально я думал преобразовать это в строку и использовать RegEx для извлечения совпадений. Regex может делать все, что мне нужно, но не понимает арифметические c, такие как «больше чем». Думаю, я мог бы сохранить свои необработанные временные ряды состояний (TFFFTTTF) и сделать для этого регулярное выражение ... но это кажется довольно уродливым.
Поля обработки естественного языка, теории графов, баз данных графов приходят на ум, как те, у которых были бы аналогичные проблемы. Я не знаю, как мне закодировать атрибут «продолжительность состояния» в моем графике. Я не знаю, существует ли какой-то «стандартный» язык запросов для поиска подпоследовательностей в графовых базах данных.
Вопросы :
-Есть ли структура для решения этих проблем извлечения подпоследовательностей, если да, то как это называется? Есть ли «лучшая практика»? Как мне структурировать свои данные? Есть ли язык запросов для запроса подпоследовательностей в базе данных последовательностей?