spockframework / spockframework/spock
Improve string comparison diffs with a linear-space edit-distance algorithm
Nobody has claimed this yet.
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 483
- PR merge metrics
- No merged PRs in 30d
Description
Spock’s EditDistance currently stores the complete Levenshtein matrix, requiring O(N * M) memory as well as O(N * M) time.
The protection introduced for #121 prevents OutOfMemoryError, but it does so by limiting the compared region. When the differing section exceeds the limit, failed string comparisons only report:
Strings too large to calculate edit distance.
This means moderately large strings can lose their useful inline diff even when the calculation would be practical with a more memory-efficient algorithm.
Replace the dense matrix with a linear-space optimal-alignment algorithm, such as the Myers-Miller/Hirschberg divide-and-conquer algorithm.
Note: The existing EditDistance Javadoc explicitly lists using an algorithm with lower time and/or space complexity as a potential improvement.
id est
/*
* Ideas for improvements:
* - Favor fewer EditOperationS when calculating distance and/or path
* - Use algorithm with lower time and/or space complexity
*/
This issue tracks addressing that TODO by replacing the dense matrix with a linear-space optimal-alignment algorithm.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by locating Spock’s EditDistance implementation and its Javadoc, then inspect how the current dense Levenshtein matrix and size protection produce comparison diffs. Replace that approach with a linear-space optimal-alignment algorithm while preserving useful inline diffs for larger strings. Done means the dense matrix is no longer required and the existing comparison behavior remains correct.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- performance, testing-qa
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100