concourse icon indicating copy to clipboard operation
concourse copied to clipboard

Use Finite State Transducers for more efficient memory representation of search strings

Open jtnelson opened this issue 9 months ago • 3 comments

An FST may drastically improve memory efficiency at the slight cost of search performance (going from O(1) to O(m)), but the reduction in garbage collection may balance it out .

An FST can be used to map a String to a value.

  • Create an FST class
  • Create an FST backed implementation of the Map interface. Should take in any key type (generic type K) and just toString it when it stores it in the FST.
  • replace the hashmap in the manifest with the FST backed map. And if that goes well
  • add logic to corpus records to replace the map in those with an FST backed map

jtnelson avatar May 14 '24 11:05 jtnelson