Prague Stringology Conference 2026
A Lower-Bound Cascade for Lossless Pruning in~Levenshtein-Based Contour Matching
| Abstract: |
| Contour-based reassembly of fragmented two-dimensional objects requires a large number of Levenshtein comparisons between directional chain-code strings. This paper proposes a lossless pre-filtering strategy based on four lower bounds: string length, symbol-frequency histogram, signed directional turn histogram, and g-gram hit count. Candidates are rejected only when a bound proves that their distance must exceed the threshold; otherwise, exact verification is preserved. Experiments covered seeded synthetic strings, exhaustive whole-space validations, and real Afrosiyab relief contour data. No false negatives were observed in any tested configuration. In representative generated tests, survival decreased to 0.160\%, reducing exact verification by 99.840\% and yielding a 4.05 speedup. Real-data experiments confirmed strong parameter-dependent pruning under a redundancy-free unordered window-pair evaluation, with histogram filtering dominating equal-window settings. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |