Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 | 9x 9x 9x 9x 9x 8x 7x 7x 7x 24x 24x 24x 4x 20x 7x 13x 13x 7x 5x 2x 6x 6x 6x 6x 6x 6x 3x 1x 1x 2x 3x 2x 2x 2x 6x 2x 1x 1x 4x 4x 4x 4x 4x 4x 10x 1x 1x 9x 6x 3x 4x 10x 10x 10x 1x 1x 9x 6x 3x 4x 1x 3x 4x 13x 3x 3x 3x 3x 140x 9x 9x 2x 1x 7x 7x 7x 8x 8x 8x 9x 3x 3x 3x 3x 3x 3x 1x 1x 1x 1x 1x 8x 1x 7x 5x 2x | /**
* Cluster Merge Strategy — Post-training cluster consolidation.
*
* ## Purpose
*
* Applied AFTER all messages have been clustered. Scans existing clusters
* and merges those that represent the same underlying template but were
* split during training due to:
*
* - Token count differences (variable-length message formats)
* - Parameter value variations (different hosts, ports, durations)
* - Tree routing decisions (different branches for similar content)
*
* This is the mechanism that gives AEL 0.974 GA on Proxifier —
* its `reconcile()` method merges events within the same bin that
* differ by only a few tokens.
*
* ## Architecture
*
* - Interface: `ClusterMergeStrategy`
* - Pipeline: `ClusterMergePipeline` (iterative, runs until convergence)
* - 4 built-in strategies + user-customizable
* - Non-invasive: operates on existing clusters, doesn't modify training logic
*
* @module ClusterMergeStrategy
*/
import type { DrainBase } from "./DrainBase.js";
import type { LogCluster } from "./LogCluster.js";
import type { SimilarityStrategy } from "./SimilarityStrategy.js";
// ============================================================
// Core Types
// ============================================================
/** Context available to merge strategies during evaluation. */
export interface MergeContext {
readonly paramStr: string;
readonly totalClusters: number;
readonly totalMessages: number;
}
/** Result of a successful merge evaluation. */
export interface MergeAction {
/** The merged template tokens */
readonly mergedTokens: readonly string[];
/** Confidence score [0.0, 1.0] */
readonly confidence: number;
}
/**
* Post-training cluster merge strategy.
*
* Each strategy defines its own criteria for when two clusters
* should be merged. Strategies are applied iteratively until
* no more merges are possible.
*/
export interface ClusterMergeStrategy {
/** Unique name for identification and debugging */
readonly name: string;
/**
* Evaluates whether two clusters should be merged.
*
* @param cluster1 - First cluster (will be kept if merge succeeds)
* @param cluster2 - Second cluster (will be removed if merge succeeds)
* @param context - Merge context with global statistics
* @returns MergeAction if they should be merged, null otherwise
*/
evaluate(
cluster1: LogCluster,
cluster2: LogCluster,
context: MergeContext,
): MergeAction | null;
}
// ============================================================
// Strategy 1: Position-Diff Merge (AEL reconcile)
// ============================================================
/**
* AEL-style position-difference merge.
*
* Merges same-length clusters where the number of differing
* positions is below a configurable threshold.
*
* Algorithm (matching AEL's reconcile + merge_event):
* 1. Require equal token counts
* 2. Count positions where tokens differ (ignoring paramStr)
* 3. If diff / tokenCount ≤ mergePercent → merge
* 4. Merged template: diff positions → paramStr, same positions → keep
*
* Example:
* Cluster A: ["host1:<NUM>", "close", "sent"]
* Cluster B: ["host2:<NUM>", "close", "sent"]
* Diff: 1/3 = 0.33 ≤ 0.4 → merge
* Result: ["<*>", "close", "sent"]
*/
export class PositionDiffMergeStrategy implements ClusterMergeStrategy {
readonly name = "position-diff";
/**
* @param mergePercent - Maximum fraction of positions that may differ (default: 0.4)
*/
constructor(private readonly mergePercent: number = 0.4) {}
evaluate(
cluster1: LogCluster,
cluster2: LogCluster,
context: MergeContext,
): MergeAction | null {
const t1 = cluster1.logTemplateTokens;
const t2 = cluster2.logTemplateTokens;
if (t1.length !== t2.length) return null;
if (t1.length === 0) return null;
let diff = 0;
const merged: string[] = [];
for (let i = 0; i < t1.length; i++) {
const token1 = t1[i]!;
const token2 = t2[i]!;
if (token1 === context.paramStr || token2 === context.paramStr) {
// Either is already a param → keep as param
merged.push(context.paramStr);
} else if (token1 === token2) {
// Same non-param → keep
merged.push(token1);
} else {
// Different non-params → generalize to param
diff++;
merged.push(context.paramStr);
}
}
// Require at least one difference (don't merge identical clusters)
if (diff === 0) return null;
// Check against threshold
if (diff / t1.length > this.mergePercent) return null;
return {
mergedTokens: Object.freeze(merged),
confidence: 1.0 - diff / t1.length,
};
}
}
// ============================================================
// Strategy 2: Similarity-Based Merge (Drain-native)
// ============================================================
/**
* Drain-native similarity-based merge.
*
* Uses a SimilarityStrategy to compute the similarity between
* two cluster templates. Merges if similarity exceeds threshold.
*
* Handles variable-length clusters naturally via the SimilarityStrategy.
*/
export class SimilarityMergeStrategy implements ClusterMergeStrategy {
readonly name = "similarity";
/**
* @param similarityStrategy - Strategy for computing inter-cluster similarity
* @param similarityThreshold - Minimum similarity to trigger merge (default: 0.7)
* @param drain - DrainBase instance for createTemplate
*/
constructor(
private readonly similarityStrategy: SimilarityStrategy,
private readonly similarityThreshold: number = 0.7,
private readonly drain?: DrainBase,
) {}
evaluate(
cluster1: LogCluster,
cluster2: LogCluster,
context: MergeContext,
): MergeAction | null {
const result = this.similarityStrategy.compute(
cluster1.logTemplateTokens,
cluster2.logTemplateTokens,
context.paramStr,
true, // include params for merge decision
);
if (result.similarity < this.similarityThreshold) return null;
// Use Drain's createTemplate for proper merging if available
let mergedTokens: readonly string[];
if (this.drain) {
try {
mergedTokens = this.drain.createTemplate(
cluster1.logTemplateTokens,
cluster2.logTemplateTokens,
);
} catch {
// Length mismatch in createTemplate — fall back to simple merge
mergedTokens = this.simpleMerge(
cluster1.logTemplateTokens,
cluster2.logTemplateTokens,
context.paramStr,
);
}
} else {
mergedTokens = this.simpleMerge(
cluster1.logTemplateTokens,
cluster2.logTemplateTokens,
context.paramStr,
);
}
return {
mergedTokens,
confidence: result.similarity,
};
}
private simpleMerge(
t1: readonly string[],
t2: readonly string[],
paramStr: string,
): readonly string[] {
const base = t1.length >= t2.length ? [...t1] : [...t2];
const minLen = Math.min(t1.length, t2.length);
for (let i = 0; i < minLen; i++) {
if (t1[i] !== t2[i]) base[i] = paramStr;
}
return Object.freeze(base);
}
}
// ============================================================
// Strategy 3: Shared Affix Merge
// ============================================================
/**
* Shared affix merge strategy.
*
* Detects clusters that share significant prefix and/or suffix
* patterns, suggesting they represent the same template with
* different parameter counts or intermediate tokens.
*
* Useful for datasets where the same event type produces messages
* with slightly different structures (e.g., optional fields).
*/
export class SharedAffixMergeStrategy implements ClusterMergeStrategy {
readonly name = "shared-affix";
/**
* @param minAffixMatch - Minimum number of matching token positions (default: 3)
*/
constructor(private readonly minAffixMatch: number = 3) {}
evaluate(
cluster1: LogCluster,
cluster2: LogCluster,
context: MergeContext,
): MergeAction | null {
const t1 = cluster1.logTemplateTokens;
const t2 = cluster2.logTemplateTokens;
let prefixMatches = 0;
let suffixMatches = 0;
// Count prefix matches
const minLen = Math.min(t1.length, t2.length);
for (let i = 0; i < minLen; i++) {
if (t1[i] === context.paramStr || t2[i] === context.paramStr) {
prefixMatches++;
continue;
}
if (t1[i] === t2[i]) {
prefixMatches++;
} else {
break;
}
}
// Count suffix matches
for (let i = 1; i <= minLen; i++) {
const idx1 = t1.length - i;
const idx2 = t2.length - i;
if (t1[idx1!] === context.paramStr || t2[idx2!] === context.paramStr) {
suffixMatches++;
continue;
}
if (t1[idx1!] === t2[idx2!]) {
suffixMatches++;
} else {
break;
}
}
if (prefixMatches < this.minAffixMatch && suffixMatches < this.minAffixMatch) {
return null;
}
// Merge: use longer sequence as base
const base = t1.length >= t2.length ? [...t1] : [...t2];
for (let i = 0; i < minLen; i++) {
if (t1[i] !== context.paramStr && t2[i] !== context.paramStr && t1[i] !== t2[i]) {
base[i] = context.paramStr;
}
}
const totalMatches = prefixMatches + suffixMatches;
const confidence = totalMatches / Math.max(t1.length, t2.length);
return {
mergedTokens: Object.freeze(base),
confidence: Math.min(confidence, 0.95),
};
}
}
// ============================================================
// Cluster Merge Pipeline
// ============================================================
/**
* Pipeline of cluster merge strategies, applied iteratively until convergence.
*
* The pipeline applies all registered strategies in order. For each pair
* of clusters, the first strategy that accepts the merge is used.
* This process repeats until no more merges occur (convergence) or
* the iteration limit is reached.
*/
export class ClusterMergePipeline {
private strategies: ClusterMergeStrategy[] = [];
/**
* Registers a merge strategy.
*/
register(strategy: ClusterMergeStrategy): this {
this.strategies.push(strategy);
return this;
}
registerAll(strategies: readonly ClusterMergeStrategy[]): this {
for (const s of strategies) this.register(s);
return this;
}
/**
* Applies all merge strategies iteratively until convergence.
*
* Algorithm:
* 1. For each iteration:
* 2. For each pair of clusters (i, j):
* 3. For each strategy:
* 4. If strategy accepts → merge (update c_i, remove c_j)
* 5. If no merges this iteration → done
* 6. Safety: max maxIterations (default: 10)
*
* @param drain - Drain engine instance (modified in-place)
* @param maxIterations - Safety limit
* @returns Total number of merges performed
*/
merge(drain: DrainBase, maxIterations: number = 10): number {
let totalMerged = 0;
const context: MergeContext = {
paramStr: drain.paramStr,
totalClusters: drain.idToCluster.size,
totalMessages: drain.getTotalClusterSize(),
};
for (let iter = 0; iter < maxIterations; iter++) {
let mergedThisRound = 0;
const ids = [...drain.idToCluster.keys()];
for (let i = 0; i < ids.length; i++) {
for (let j = i + 1; j < ids.length; j++) {
const c1 = drain.idToCluster.get(ids[i]!);
const c2 = drain.idToCluster.get(ids[j]!);
Iif (!c1 || !c2) continue;
for (const strategy of this.strategies) {
const action = strategy.evaluate(c1, c2, context);
if (action) {
// Merge: update cluster 1, remove cluster 2
c1.logTemplateTokens = action.mergedTokens;
c1.size += c2.size;
drain.idToCluster.delete(ids[j]!);
mergedThisRound++;
break; // Next pair
}
}
}
}
if (mergedThisRound === 0) break;
totalMerged += mergedThisRound;
}
return totalMerged;
}
get size(): number {
return this.strategies.length;
}
}
// ============================================================
// Factory
// ============================================================
/**
* Creates the default merge pipeline (AEL-style position-diff only).
*/
export function createDefaultMergePipeline(
mergePercent: number = 0.4,
): ClusterMergePipeline {
return new ClusterMergePipeline().register(
new PositionDiffMergeStrategy(mergePercent),
);
}
|