commit 0df52659fb78a8df18af60492079e7d4fe408b69
parent 9476d6a67d3b81063a17dc4265377fa33dc23bf1
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 6 Sep 2019 18:51:02 +0200
do not talk about knapsack, it is not knapsack
Diffstat:
2 files changed, 12 insertions(+), 7 deletions(-)
diff --git a/README b/README
@@ -37,12 +37,13 @@ Songflow does the following:
cut at bars that break a slur.
Once bars are detected, the program splits them in blocks of the right width
- (by a bruteforce algorithm minimizing the length of the shortest segment), and
- each block is stretched to the required width by stretching empty space only
- to avoid distorting the picture. This step may fail by stretching things
- (e.g., notes) that should not be stretched, or by failing to detect some empty
- space and stretching too much the places that it detects (especially when
- constrained because not all bars were correctly detected).
+ (by a bruteforce algorithm that finds a solution minimizing the length of the
+ shortest segment), and each block is stretched to the required width by
+ stretching empty space only to avoid distorting the picture. This step may
+ fail by stretching things (e.g., notes) that should not be stretched, or by
+ failing to detect some empty space and stretching too much the places that it
+ detects (especially when constrained because not all bars were correctly
+ detected).
- Combining the blocks back into pages of the right size (greedily fitting them
and arranging them on the page)
@@ -184,6 +185,10 @@ height is too large to fit will be ignored with a warning.
- When splitting pages into systems, sometimes lyrics are lost or not put at the
right place
+- The word-wrapping algorithm is an exponential-time bruteforce algorithm,
+ whether it could be implemented using dynamic programming. That said, given
+ the size of instances, I doubt it's a bottleneck.
+
- Splitting lines is pretty error-prone, with some inadequate cuts (not at bars)
and some weird stretching. The accuracy could be improved by better improved,
or by genuine learning techniques instead of crude heuristiques.
diff --git a/splitw.py b/splitw.py
@@ -188,7 +188,7 @@ for b in range(len(bars2)-1):
# Step 5: optimal fit
-# naive bruteforce for knapsack
+# naive bruteforce for word wrapping
def fit(remaining, current_bucket, current_bucket_weight, previous_buckets, worst_difference):
if len(remaining) == 0:
return (max(worst_difference, args.width-current_bucket_weight),
