Approximate Alignments
For exact diagnostics and an explanation of alignment moves, start with alignment-based conformance checking. Use model evaluation to interpret fitness, and configuration parameters to adjust runtime settings.
Exact alignment computation may become expensive for long traces, large state spaces, or high-volume event streams. PM4Py provides five approximation strategies that trade a controlled amount of alignment quality for lower runtime or memory consumption. The implementations still return concrete alignments that can be validated against the Petri net.
This page demonstrates all methods on the real-life Receipt log and a model discovered from that log.
- Tandem-repeat compression
- Subset selection and edit distance
- Sliding-window top-k alignment
- IWS online alignment with decay
- Sequential fixed-horizon alignment
Shared Setup for Approximate Alignments
These low-level algorithms demonstrate individual Trace objects and trace slicing, so this page explicitly requests the legacy EventLog format. Standard discovery and conformance workflows accept DataFrames directly.
Load receipt.xes and discover an accepting Petri net with Inductive Miner. A noise threshold of 0.0 keeps all observed behavior in the discovered model.
import os
import pm4py
log_path = os.path.join("tests", "input_data", "receipt.xes")
# These examples select and align individual legacy Trace objects.
log = pm4py.read_xes(log_path, return_legacy_log_object=True)
# Discover an accepting Petri net from all behavior in the log.
net, initial_marking, final_marking = pm4py.discover_petri_net_inductive(
log,
noise_threshold=0.0,
)Tandem-repeat compression
Based on Efficient Conformance Checking using Approximate Alignment Computation with Tandem Repeats by Reißner, Armas-Cervantes, and La Rosa.
The method compresses repeated trace fragments before alignment and expands them afterward. Executable model loops are replayed for removed copies; otherwise, valid log moves are inserted. It is most useful for long traces containing repeated loop behavior.
from pm4py.algo.conformance.alignments.petri_net import algorithm as alignments
from pm4py.algo.conformance.alignments.petri_net.variants.approx_tandem_repeats import (
reduce_tandem_repeats,
)
# Select a trace for which compression can remove at least one repeat copy.
trace = next(
trace for trace in log
if reduce_tandem_repeats(
[event["concept:name"] for event in trace]
)[2]
)
result = alignments.apply(
trace,
net,
initial_marking,
final_marking,
variant=alignments.Variants.APPROX_TANDEM_REPEATS,
parameters={
"enable_best_worst_cost": False,
"max_align_time_trace": 10,
},
)
print(result["reduced_trace_length"], result["is_valid"])View the complete tandem-repeat example.
Subset selection and edit distance
Based on Conformance Checking Approximation Using Subset Selection and Edit Distance by Fani Sani, van Zelst, and van der Aalst.
Representative variants are aligned through the model, while remaining variants are mapped to the closest representative using insertion/deletion edit distance. Frequency, random, k-medoids, and simulation-based representative selection are supported. The summary includes per-trace and aggregate fitness bounds.
from pm4py.algo.conformance.alignments.edit_distance import (
algorithm as edit_distance_alignments,
)
summary = edit_distance_alignments.apply_approximation_with_summary(
log,
net,
initial_marking,
final_marking,
parameters={
"selection_method": "frequency",
"subset_size": 10,
},
)
print(summary["log_fitness"])
print(summary["fitness_lower_bound"], summary["fitness_upper_bound"])View the complete subset/edit-distance example.
Sliding-window top-k alignment
Based on A Scalable and Near-Optimal Conformance Checking Approach for Long Traces by Bogdanov, Cohen, and Gal.
A long trace is divided into windows. After every intermediate window, the best candidates ending in distinct model markings are retained. Increasing the window size or number of candidates generally improves quality at the cost of a larger search space.
from pm4py.algo.conformance.alignments.petri_net import algorithm as alignments
# A long trace makes the effect of splitting the search into windows visible.
trace = max(log, key=len)
result = alignments.apply(
trace,
net,
initial_marking,
final_marking,
variant=alignments.Variants.APPROX_SLIDING_WINDOW,
parameters={
"window_size": 5,
"max_candidates": 3,
"max_post_model_moves": 3,
"enable_best_worst_cost": False,
},
)
print(result["retained_candidates"], result["is_valid"])View the complete sliding-window example.
IWS online alignment with decay
Based on I Will Survive: An Online Conformance Checking Algorithm Using Decay Time by Raun and Awad.
IWS stores finite proxy behavior in a trie and updates alignment states as events arrive. Look-ahead permits upcoming trie behavior to be matched, while decay and a maximum state count remove stale alternatives. get() returns prefix alignments and finish(case_id) completes a case.
from pm4py.objects.log.obj import EventLog
from pm4py.streaming.algo.conformance.alignments import (
algorithm as streaming_alignments,
)
# The proxy log is a finite sample of complete model behavior.
proxy_log = EventLog(list(log[:20]))
online_aligner = streaming_alignments.apply(
net,
initial_marking,
final_marking,
variant=streaming_alignments.Variants.APPROX_IWS,
parameters={
"proxy_log": proxy_log,
"look_ahead": 3,
"decay_time": 8,
"discount_factor": 0.9,
"max_states": 20,
},
)
case_id = "receipt-example"
for event in log[0]:
online_aligner.receive({
"case:concept:name": case_id,
"concept:name": event["concept:name"],
})
prefix = online_aligner.get()[case_id]
complete = online_aligner.finish(case_id)
print(prefix["active_states"], complete["is_valid"])View the complete IWS streaming example.
Sequential fixed-horizon alignment
Based on Aligning Modeled and Observed Behavior: A Compromise Between Computation Complexity and Quality by van Dongen, Carmona, Chatain, and Taymouri.
This sequential method searches an executable prefix within a fixed horizon and estimates the remaining suffix with an integer marking equation. The horizon can grow when a short commitment is unsuitable. If no LP solver is available or the bounded search cannot finish, PM4Py falls back to direct state-space search.
from pm4py.algo.conformance.alignments.petri_net import algorithm as alignments
result = alignments.apply(
log[0],
net,
initial_marking,
final_marking,
variant=alignments.Variants.APPROX_FIXED_HORIZON,
parameters={
"horizon": 3,
"min_progress": 1,
"max_horizon": 6,
"max_prefix_states": 3000,
"enable_best_worst_cost": False,
},
)
print(result["committed_horizons"], result["is_valid"])