Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.13330 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909847497211904 |
|---|---|
| author | Smart, Bridget Ward, Max Roughan, Matthew |
| author_facet | Smart, Bridget Ward, Max Roughan, Matthew |
| contents | Non-parametric entropy estimation on sequential data is a fundamental tool in signal processing, capturing information flow within or between processes to measure predictability, redundancy, or similarity. Methods based on longest common substrings (LCS) provide a non-parametric estimate of typical set size but are often inefficient, limiting use on real-world data. We introduce LCSFinder, a new algorithm that improves the worst-case performance of LCS calculations from cubic to log-linear time. Although built on standard algorithmic constructs - including sorted suffix arrays and persistent binary search trees - the details require care to provide the matches required for entropy estimation on dynamically growing sequences. We demonstrate that LCSFinder achieves dramatic speedups over existing implementations on real and simulated data, enabling entropy estimation at scales previously infeasible in practical signal processing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_13330 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A faster algorithm for efficient longest common substring calculation for non-parametric entropy estimation in sequential data Smart, Bridget Ward, Max Roughan, Matthew Data Structures and Algorithms Information Theory Non-parametric entropy estimation on sequential data is a fundamental tool in signal processing, capturing information flow within or between processes to measure predictability, redundancy, or similarity. Methods based on longest common substrings (LCS) provide a non-parametric estimate of typical set size but are often inefficient, limiting use on real-world data. We introduce LCSFinder, a new algorithm that improves the worst-case performance of LCS calculations from cubic to log-linear time. Although built on standard algorithmic constructs - including sorted suffix arrays and persistent binary search trees - the details require care to provide the matches required for entropy estimation on dynamically growing sequences. We demonstrate that LCSFinder achieves dramatic speedups over existing implementations on real and simulated data, enabling entropy estimation at scales previously infeasible in practical signal processing. |
| title | A faster algorithm for efficient longest common substring calculation for non-parametric entropy estimation in sequential data |
| topic | Data Structures and Algorithms Information Theory |
| url | https://arxiv.org/abs/2510.13330 |