Actualmente estoy trabajando en un algoritmo para reducir el número de iteraciones de bucle en las trazas al mínimo necesario.

Más exactamente, esto:

 trace = ["a", "b", "b", "b", "c"]

debe reducirse a:

 new_trace = ["a", "b", "b", "c"]

para que la información sobre "b" que sigue a "b" no se pierda.

Otro ejemplo es:

 trace = ["a", "b", "c", "d", "b", "c", "d", "b", "c", "d", "e"]

debe reducirse a:

 new_trace = ["a", "b", "c", "d", "b", "c", "d", "e"]

También implementé un algoritmo en Python que hace exactamente eso:

 def reduce_cycles(trace_variant: List[str], loop_retain_factor: int) -> List[str]: original_edges = list(zip(trace_variant, trace_variant[1:])) trace_follows_graph = Counter(original_edges) trace_graph = nx.DiGraph() trace_graph.add_edges_from(original_edges) trace_cycles: Generator[List[str], None, None] = nx.simple_cycles(trace_graph) edges_per_cycle = map( lambda cycle: list(zip(cycle, cycle[1:] + cycle[0:1])), trace_cycles ) # reduce number of edges for cycles in trace for cycle_edges in edges_per_cycle: reduce_cycle_weight = min(itemgetter(*cycle_edges)(trace_follows_graph)) for cycle_edge in cycle_edges: trace_follows_graph[cycle_edge] -= reduce_cycle_weight - loop_retain_factor # does not exactly work # especially not for examples such as trace_variant = ["a", "b", "c", "b", "c", "d", "c", "b", "e"] def replay_edge(acc: List[Edge], new: Edge): if trace_follows_graph[new] > 0: trace_follows_graph[new] -= 1 return acc + [new] return acc new_trace_edges = reduce(replay_edge, original_edges, []) new_trace_variant = list(map(itemgetter(0), new_trace_edges)) # add final event new_trace_variant.append(new_trace_edges[-1][-1]) return new_trace_variant

Pero como puede ver, obviamente, el algoritmo no es exactamente eficaz. Especialmente porque normalmente hay una gran cantidad de rastros, lo que significa que esta función se llamará para cada rastro. Entonces, me preguntaba si tal vez ya existe un algoritmo que pueda resolver este problema de manera más eficiente o si alguien más tiene una idea de cómo mejorar el rendimiento de esta implementación.

¡Agradecería su ayuda!

EDITAR: un dcbe bcbcbc debe convertirse en un dcbe bc

O si construye un gráfico dirigido a partir de la siguiente traza: abcdbcdbcdbcdbcde

debería convertirse en abcdbcde

EDIT2: actualicé el código, la descripción y un gráfico, ya que el comentario de @kcsquared me hizo reevaluar este problema.

Para resumir, lo que quiero es que al pasar un rastro a la función/algoritmo, debe eliminar todas las repeticiones, a menos que eliminar una repetición elimine un borde en el gráfico dirigido correspondiente.

• Ya descubrí cómo obtener las "repeticiones"/ciclos en el gráfico
• Y creo que descubrí cómo actualizar los pesos de borde (el peso de borde de los nodos A y B corresponde a la frecuencia con la que B sigue a A en la traza original)
• Estoy un poco atascado en cómo obtener el seguimiento después

Una vez más cualquier ayuda apreciada.