On: Parsing: the solved problem that isn't

[anamax]

> The algorithm they outline is exponential.

They claim that it's actually roughly linear (given some fairly obvious optimizations) and provide a table of measurements that support said claim.

http://arxiv.org/PS_cache/arxiv/pdf/1010/1010.5023v1.pdf

Number of tokens Parsing time

4,944 10 ms

42,346 43 ms

390,553 326 ms

5,049,213 3.9 s

22,155,402 17.1 s