In this situation, I'd seriously consider throwing down a binary blob as a string that directly represents this data as whatever fancy structure you want and writing the small handful of functions it would take to traverse that "string" to do the lookup. Then you can do whatever optimal thing you want and memory usage is very predictable.
Technically this is what his final solution converged on, it's just the least fancy "fancy structure" there is.
It's a last resort, certainly, but in certain cases it's the simplest answer. Be aware of encoding issues, though; UTF-8 technically can't carry arbitrary binaries and you may have to work around some things a bit.