Code:
for pos in (0..N)
state[pos] := state[best_prev_pos[pos]], updated for a best_match[pos]
for (len,dist) in possible_matches[]
if price[pos]+price(len,dist) < price[pos+len]
price[pos+len] = price[pos]+price(len,dist)
best_prev_pos[pos+len] = pos
best_match[pos+len] = (len,dist)
you are right. in the second line, when i update the state (that may be many KB), i update the prices too. so we have already selected the optimal path to this concrete pos, we know full state and we can compute all prices
it may look too slow, but in lzma updating prices with one match/literal is usually very cheap and copying multiple KBs within L3 cache has the speed >100 GB/s
it seems that for a given pos you're examining prices of future positions.
it is how lzma/tornado optimal parsing work - we start with
Code:
price[0]=0
for (pos in 1..N)
price[pos] = VERY_HIGH_PRICE
and then try every possibility to reach every position and choose minimal price. but it uses price[pos+len] only for comparison with new price, so no future prices are involved
you can read this post for details of lzma/tor algo